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

HTML articles powered by AMS MathViewer

- by Jinchao Xu and Ludmil Zikatanov PDF
- J. Amer. Math. Soc.
**15**(2002), 573-597 Request permission

## 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.## References

- P. Hebroni,
*Sur les inverses des éléments dérivables dans un anneau abstrait*, C. R. Acad. Sci. Paris**209**(1939), 285–287 (French). MR**14** - Ivo Babuška and A. K. Aziz,
*Survey lectures on the mathematical foundations of the finite element method*, The mathematical foundations of the finite element method with applications to partial differential equations (Proc. Sympos., Univ. Maryland, Baltimore, Md., 1972) Academic Press, New York, 1972, pp. 1–359. With the collaboration of G. Fix and R. B. Kellogg. MR**0421106** - Heinz H. Bauschke, Jonathan M. Borwein, and Adrian S. Lewis,
*The method of cyclic projections for closed convex sets in Hilbert space*, Recent developments in optimization theory and nonlinear analysis (Jerusalem, 1995) Contemp. Math., vol. 204, Amer. Math. Soc., Providence, RI, 1997, pp. 1–38. MR**1442992**, DOI 10.1090/conm/204/02620
HBauschke-FDeutsch-HHundal-SPark-1999 H. Bauschke, F. Deutsch, H. Hundal, and S. Park, - Heinz H. Bauschke and Jonathan M. Borwein,
*On projection algorithms for solving convex feasibility problems*, SIAM Rev.**38**(1996), no. 3, 367–426. MR**1409591**, DOI 10.1137/S0036144593251710 - D. Braess and W. Hackbusch,
*A new convergence proof for the multigrid method including the $V$-cycle*, SIAM J. Numer. Anal.**20**(1983), no. 5, 967–975. MR**714691**, DOI 10.1137/0720066 - James H. Bramble and Joseph E. Pasciak,
*New convergence estimates for multigrid algorithms*, Math. Comp.**49**(1987), no. 180, 311–329. MR**906174**, DOI 10.1090/S0025-5718-1987-0906174-X - James H. Bramble,
*Multigrid methods*, Pitman Research Notes in Mathematics Series, vol. 294, Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc., New York, 1993. MR**1247694** - James H. Bramble, Joseph E. Pasciak, Jun Ping Wang, and Jinchao Xu,
*Convergence estimates for multigrid algorithms without regularity assumptions*, Math. Comp.**57**(1991), no. 195, 23–45. MR**1079008**, DOI 10.1090/S0025-5718-1991-1079008-4 - James H. Bramble, Joseph E. Pasciak, Jun Ping Wang, and Jinchao Xu,
*Convergence estimates for product iterative methods with applications to domain decomposition*, Math. Comp.**57**(1991), no. 195, 1–21. MR**1090464**, DOI 10.1090/S0025-5718-1991-1090464-8 - James H. Bramble, Joseph E. Pasciak, and Jinchao Xu,
*Parallel multilevel preconditioners*, Math. Comp.**55**(1990), no. 191, 1–22. MR**1023042**, DOI 10.1090/S0025-5718-1990-1023042-6 - James H. Bramble and Jinchao Xu,
*Some estimates for a weighted $L^2$ projection*, Math. Comp.**56**(1991), no. 194, 463–476. MR**1066830**, DOI 10.1090/S0025-5718-1991-1066830-3 - James H. Bramble and Xuejun Zhang,
*The analysis of multigrid methods*, Handbook of numerical analysis, Vol. VII, Handb. Numer. Anal., VII, North-Holland, Amsterdam, 2000, pp. 173–415. MR**1804746** - F. Brezzi,
*On the existence, uniqueness and approximation of saddle-point problems arising from Lagrangian multipliers*, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge**8**(1974), no. R-2, 129–151 (English, with French summary). MR**365287** - Frank Deutsch,
*Applications of von Neumann’s alternating projections algorithm*, Mathematical methods in operations research (Sofia, 1983) Publ. House Bulgar. Acad. Sci., Sofia, 1983, pp. 44–51. MR**791945** - Frank Deutsch,
*von Neumann’s alternating method: the rate of convergence*, Approximation theory, IV (College Station, Tex., 1983) Academic Press, New York, 1983, pp. 427–434. MR**754371** - Frank Deutsch,
*Rate of convergence of the method of alternating projections*, Parametric optimization and approximation (Oberwolfach, 1983) Internat. Schriftenreihe Numer. Math., vol. 72, Birkhäuser, Basel, 1985, pp. 96–107. MR**882199** - Frank Deutsch,
*The method of alternating orthogonal projections*, Approximation theory, spline functions and applications (Maratea, 1991) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 356, Kluwer Acad. Publ., Dordrecht, 1992, pp. 105–121. MR**1165964** - Maksymilian Dryja and Olof B. 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**1064335** - Maksymilian Dryja and Olof B. Widlund,
*Multilevel additive methods for elliptic finite element problems*, Parallel algorithms for partial differential equations (Kiel, 1990) Notes Numer. Fluid Mech., vol. 31, Friedr. Vieweg, Braunschweig, 1991, pp. 58–69. MR**1167868** - J. Gilbert and W. A. Light,
*Multigrid methods and the alternating algorithm*, Algorithms for approximation (Shrivenham, 1985) Inst. Math. Appl. Conf. Ser. New Ser., vol. 10, Oxford Univ. Press, New York, 1987, pp. 447–458. MR**911328** - M. Griebel and P. Oswald,
*On additive Schwarz preconditioners for sparse grid discretizations*, Numer. Math.**66**(1994), no. 4, 449–463. MR**1254398**, DOI 10.1007/BF01385707 - M. Griebel and P. Oswald,
*On the abstract theory of additive and multiplicative Schwarz algorithms*, Numer. Math.**70**(1995), no. 2, 163–180. MR**1324736**, DOI 10.1007/s002110050115 - Wolfgang Hackbusch,
*Multigrid methods and applications*, Springer Series in Computational Mathematics, vol. 4, Springer-Verlag, Berlin, 1985. MR**814495**, DOI 10.1007/978-3-662-02427-0 - Wolfgang Hackbusch,
*Iterative solution of large sparse systems of equations*, Applied Mathematical Sciences, vol. 95, Springer-Verlag, New York, 1994. Translated and revised from the 1991 German original. MR**1247457**, DOI 10.1007/978-1-4612-4288-8 - Israel Halperin,
*The product of projection operators*, Acta Sci. Math. (Szeged)**23**(1962), 96–99. MR**141978** - Selahattin Kayalar and Howard L. Weinert,
*Error bounds for the method of alternating projections*, Math. Control Signals Systems**1**(1988), no. 1, 43–59. MR**923275**, DOI 10.1007/BF02551235
RSmarzewski-1996 R. Smarzewski, - Barry F. Smith, Petter E. Bjørstad, and William D. Gropp,
*Domain decomposition*, Cambridge University Press, Cambridge, 1996. Parallel multilevel methods for elliptic partial differential equations. MR**1410757** - 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**1807961** - Morgan Ward and R. P. Dilworth,
*The lattice theory of ova*, Ann. of Math. (2)**40**(1939), 600–608. MR**11**, DOI 10.2307/1968944 - Jun Ping Wang,
*Convergence analysis without regularity assumptions for multigrid algorithms based on SOR smoothing*, SIAM J. Numer. Anal.**29**(1992), no. 4, 987–1001. MR**1173181**, DOI 10.1137/0729060 - Olof 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**1189560**
JXu-1989b J. Xu, - Jinchao Xu,
*Iterative methods by space decomposition and subspace correction*, SIAM Rev.**34**(1992), no. 4, 581–613. MR**1193013**, DOI 10.1137/1034116 - Jinchao Xu,
*An introduction to multilevel methods*, Wavelets, multilevel methods and elliptic PDEs (Leicester, 1996) Numer. Math. Sci. Comput., Oxford Univ. Press, New York, 1997, pp. 213–302. MR**1600688**
JXu-LZikatanov-2000a J. Xu and L. Zikatanov, - Jinchao Xu and Jun Zou,
*Some nonoverlapping domain decomposition methods*, SIAM Rev.**40**(1998), no. 4, 857–914. MR**1659681**, DOI 10.1137/S0036144596306800 - Harry Yserentant,
*Old and new convergence proofs for multigrid methods*, Acta numerica, 1993, Acta Numer., Cambridge Univ. Press, Cambridge, 1993, pp. 285–326. MR**1224685**, DOI 10.1017/S0962492900002385

*Accelerating the convergence of the method of alternating projections*, Preprint, July 1999.

*Iterative recovering of orthogonal projections*, Preprint, December 1996.

*Theory of multilevel methods*, Ph.D. thesis, Cornell University, Ithaca, NY, 1989, AM report 48, Dept. of Math., Penn. State Univ., University Park, PA.

*Some observations on Babuška and Brezzi theories*, Num. Math., 2000 (to appear).

## Additional Information

**Jinchao Xu**- Affiliation: Center for Computational Mathematics and Applications, Department of Mathematics, The Pennsylvania State University, University Park, Pennsylvania 16802
- MR Author ID: 228866
- 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
- 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.
- © Copyright 2002 American Mathematical Society
- 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
- MathSciNet review: 1896233