The method of alternating projections and the method of subspace corrections in Hilbert space

Authors:
Jinchao Xu and Ludmil Zikatanov

Journal:
J. Amer. Math. Soc. **15** (2002), 573-597

MSC (2000):
Primary 47A58, 47N10, 47N40, 49M20, 65F10, 65J05, 65N22, 65N55

DOI:
https://doi.org/10.1090/S0894-0347-02-00398-3

Published electronically:
April 8, 2002

MathSciNet review:
1896233

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A new identity is given in this paper for estimating the norm of the product of nonexpansive operators in Hilbert space. This identity can be applied for the design and analysis of the method of alternating projections and the method of subspace corrections. The method of alternating projections is an iterative algorithm for determining the best approximation to any given point in a Hilbert space from the intersection of a finite number of subspaces by alternatively computing the best approximations from the individual subspaces which make up the intersection. The method of subspace corrections is an iterative algorithm for finding the solution of a linear equation in a Hilbert space by approximately solving equations restricted on a number of closed subspaces which make up the entire space. The new identity given in the paper provides a sharpest possible estimate for the rate of convergence of these algorithms. It is also proved in the paper that the method of alternating projections is essentially equivalent to the method of subspace corrections. Some simple examples of multigrid and domain decomposition methods are given to illustrate the application of the new identity.

**1.**N. Aronszjan,*Theory of reproducing kernels*, Trans. Amer. Math. Soc.**68**(1950), 337-404. MR**14:479c****2.**I. Babuska and A. K. Aziz,*Lectures on the mathematical foundations of the finite element method*, University of Maryland, College Park, Washington DC, 1972, Technical Note BN-748. MR**54:9111****3.**H. Bauschke, J. Borwein, and A. Lewis,*The method of cyclic projections for closed convex sets in Hilbert space*, Recent developments in optimization theory and nonlinear analysis (Jerusalem, 1995), Amer. Math. Soc., Providence, RI, 1997, pp. 1-38. MR**98c:49069****4.**H. Bauschke, F. Deutsch, H. Hundal, and S. Park,*Accelerating the convergence of the method of alternating projections*, Preprint, July 1999.**5.**H. H. Bauschke and J. M. Borwein,*On projection algorithms for solving convex feasibility problems*, SIAM Rev.**38**(1996), no. 3, 367-426. MR**98f:90045****6.**D. Braess and W. Hackbusch,*A new convergence proof for the multigrid method including the -cycle*, SIAM J. Numer. Anal.**20**(1983), no. 5, 967-975. MR**85h:65233****7.**J. Bramble and J. Pasciak,*New convergence estimates for multigrid algorithms*, Math. Comp.**49**(1987), no. 180, 311-329. MR**89b:65234****8.**J. H. Bramble,*Multigrid methods*, Longman Scientific & Technical, Harlow, 1993. MR**95b:65002****9.**J. H. Bramble, J. E. Pasciak, J. Wang, and J. Xu,*Convergence estimates for multigrid algorithms without regularity assumptions*, Math. Comp.**57**(1991), no. 195, 23-45. MR**91m:65158****10.**-,*Convergence estimates for product iterative methods with applications to domain decomposition*, Math. Comp.**57**(1991), no. 195, 1-21. MR**92d:65094****11.**J. H. Bramble, J. E. Pasciak, and J. Xu,*Parallel multilevel preconditioners*, Math. Comp.**55**(1990), 1-22. MR**90k:65170****12.**J. H. Bramble and J. Xu,*Some estimates for a weighted projection*, Math. Comp.**56**(1991), no. 194, 463-476. MR**91k:65140****13.**J. H. Bramble and X. Zhang,*The analysis of multigrid methods*, Handbook of numerical analysis, Vol. VII, North-Holland, Amsterdam, 2000, pp. 173-415. MR**2001m:65183****14.**F. Brezzi,*On the existence, uniqueness and approximation of saddle-point problems arising from Lagrange multipliers*, R.A.I.R.O Anal. Numer.**R2**(1974), 129-151. MR**51:1540****15.**F. Deutsch,*Applications of von Neumann's alternating projections algorithm*, Mathematical methods in operations research (Sofia, 1983), Bulgar. Acad. Sci., Sofia, 1983, pp. 44-51. MR**86i:90093****16.**-,*von Neumann's alternating method: the rate of convergence*, Approximation theory, IV (College Station, TX, 1983), Academic Press, New York, 1983, pp. 427-434. MR**85m:41040****17.**-,*Rate of convergence of the method of alternating projections*, Parametric optimization and approximation (Oberwolfach, 1983), Birkhäuser, Basel, 1985, pp. 96-107. MR**88d:41026****18.**F. Deutsch,*The method of alternating orthogonal projections*, Approximation theory, spline functions and applications, Kluwer Acad. Publ., 1992, pp. 105-121. MR**93a:41047****19.**M. Dryja and O. Widlund,*Towards a unified theory of domain decomposition algorithms for elliptic problems*, Third International Symposium on Domain Decomposition Methods for Partial Differential Equations (Houston, TX, 1989), SIAM, Philadelphia, PA, 1990, pp. 3-21. MR**91m:65294****20.**-,*Multilevel additive methods for elliptic finite element problems*, Parallel algorithms for partial differential equations (Kiel, 1990), Vieweg, Braunschweig, 1991, pp. 58-69. MR**93b:65188****21.**J. Gilbert and W. A. Light,*Multigrid methods and the alternating algorithm*, Algorithms for approximation (Shrivenham, 1985), Oxford Univ. Press, New York, 1987, pp. 447-458. MR**88j:65116****22.**M. Griebel and P. Oswald,*On additive Schwarz preconditioners for sparse grid discretizations*, Numer. Math.**66**(1994), no. 4, 449-463. MR**95a:65188****23.**-,*On the abstract theory of additive and multiplicative Schwarz algorithms*, Numer. Math.**70**(1995), no. 2, 163-180. MR**96a:65164****24.**W. Hackbusch,*Multigrid methods and applications*, Springer-Verlag, Berlin, 1985. MR**87e:65082****25.**-,*Iterative solution of large sparse systems of equations*, Springer-Verlag, New York, 1994. MR**94k:65002****26.**I. Halperin,*The product of projection operators*, Acta Sci. Math. (Szeged)**23**(1962), 96-99. MR**25:5373****27.**S. Kayalar and H. L. Weinert,*Error bounds for the method of alternating projections*, Math. Control Signals Systems**1**(1988), no. 1, 43-59. MR**89b:65137****28.**R. Smarzewski,*Iterative recovering of orthogonal projections*, Preprint, December 1996.**29.**B. Smith, P. Bjørstad, and W. Gropp,*Domain decomposition*, Cambridge University Press, Cambridge, 1996, Parallel multilevel methods for elliptic partial differential equations. MR**98g:65003****30.**U. Trottenberg, C. W. Oosterlee, and A. Schüller,*Multigrid*, Academic Press Inc., San Diego, CA, 2001, With contributions by A. Brandt, P. Oswald and K. Stüben. MR**2002b:65002****31.**J. von Neumann,*The geometry of orthogonal spaces*, Functional operators- vol. II, Annals of Math. Studies, no. 22, Princeton University Press, 1950, This is a reprint of mimeographed lecture notes, first distributed in 1933. MR**11:599e****32.**J. Wang,*Convergence analysis without regularity assumptions for multigrid algorithms based on SOR smoothing*, SIAM J. Numer. Anal.**29**(1992), no. 4, 987-1001. MR**93e:65141****33.**O. B. Widlund,*Some Schwarz methods for symmetric and nonsymmetric elliptic problems*, Fifth International Symposium on Domain Decomposition Methods for Partial Differential Equations (Norfolk, VA, 1991), SIAM, Philadelphia, PA, 1992, pp. 19-36. MR**93j:65202****34.**J. Xu,*Theory of multilevel methods*, Ph.D. thesis, Cornell University, Ithaca, NY, 1989, AM report 48, Dept. of Math., Penn. State Univ., University Park, PA.**35.**-,*Iterative methods by space decomposition and subspace correction*, SIAM Review**34**(1992), 581-613. MR**93k:65029****36.**-,*An introduction to multilevel methods*, Wavelets, multilevel methods and elliptic PDEs (Leicester, 1996), Oxford Univ. Press, New York, 1997, pp. 213-302. MR**99d:65329****37.**J. Xu and L. Zikatanov,*Some observations on Babuska and Brezzi theories*, Num. Math., 2000 (to appear).**38.**J. Xu and J. Zou,*Some nonoverlapping domain decomposition methods*, SIAM Rev.**40**(1998), no. 4, 857-914. MR**99m:65241****39.**H. Yserentant,*Old and new convergence proofs for multigrid methods*, Acta numerica, 1993, Cambridge Univ. Press, Cambridge, 1993, pp. 285-326. MR**94i:65128**

Retrieve articles in *Journal of the American Mathematical Society*
with MSC (2000):
47A58,
47N10,
47N40,
49M20,
65F10,
65J05,
65N22,
65N55

Retrieve articles in all journals with MSC (2000): 47A58, 47N10, 47N40, 49M20, 65F10, 65J05, 65N22, 65N55

Additional Information

**Jinchao Xu**

Affiliation:
Center for Computational Mathematics and Applications, Department of Mathematics, The Pennsylvania State University, University Park, Pennsylvania 16802

Email:
xu@math.psu.edu

**Ludmil Zikatanov**

Affiliation:
Center for Computational Mathematics and Applications, Department of Mathematics, The Pennsylvania State University, University Park, Pennsylvania 16802

Email:
ltz@math.psu.edu

DOI:
https://doi.org/10.1090/S0894-0347-02-00398-3

Keywords:
Alternating projections,
subspace corrections,
nonexpansive operators,
multigrid,
domain decomposition

Received by editor(s):
July 11, 2000

Published electronically:
April 8, 2002

Additional Notes:
The authors were supported in part by NSF Grant #DMS-0074299 and the Center for Computational Mathematics and Applications, The Pennsylvania State University.

Article copyright:
© Copyright 2002
American Mathematical Society