Successive Approximate Algorithm for Best Approximation from a Polyhedron

✍ Scribed by Shusheng Xu

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 275 KB
• Volume: 93
• Category: Article
• ISSN: 0021-9045
• DOI: 10.1006/jath.1998.3174

✦ Synopsis

Suppose K is the intersection of a finite number of closed half-spaces [K i ] in a Hilbert space X, and x # X "K. Dykstra's cyclic projections algorithm is a known method to determine an approximate solution of the best approximation of x from K, which is denoted by P K (x). Dykstra's algorithm reduces the problem to an iterative scheme which involves computing the best approximation from the individual K i . It is known that the sequence [x j ] generated by Dykstra's method converges to the best approximation P K (x). But since it is difficult to find the definite value of an upper bound of the error &x j &P K (x)&, the applicability of the algorithm is restrictive. This paper introduces a new method, called the successive approximate algorithm, by which one can generate a finite sequence x 0 , x 1 , ..., x k with x k =P K (x). In addition, the error &x j &P K (x)& is monotone decreasing and has a definite upper bound easily to be determined. So the new algorithm is very applicable in practice.