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), 573597
MSC (2000):
Primary 47A58, 47N10, 47N40, 49M20, 65F10, 65J05, 65N22, 65N55
DOI:
https://doi.org/10.1090/S0894034702003983
Published electronically:
April 8, 2002
MathSciNet review:
1896233
Fulltext 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.

NAronszjan1950a N. Aronszjan, Theory of reproducing kernels, Trans. Amer. Math. Soc. 68 (1950), 337–404.
 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 https://doi.org/10.1090/conm/204/02620 HBauschkeFDeutschHHundalSPark1999 H. Bauschke, F. Deutsch, H. Hundal, and S. Park, Accelerating the convergence of the method of alternating projections, Preprint, July 1999.
 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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1090/S0025571819870906174X
 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 https://doi.org/10.1090/S00255718199110790084
 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 https://doi.org/10.1090/S00255718199110904648
 James H. Bramble, Joseph E. Pasciak, and Jinchao Xu, Parallel multilevel preconditioners, Math. Comp. 55 (1990), no. 191, 1–22. MR 1023042, DOI https://doi.org/10.1090/S00255718199010230426
 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 https://doi.org/10.1090/S00255718199110668303
 James H. Bramble and Xuejun Zhang, The analysis of multigrid methods, Handbook of numerical analysis, Vol. VII, Handb. Numer. Anal., VII, NorthHolland, Amsterdam, 2000, pp. 173–415. MR 1804746
 F. Brezzi, On the existence, uniqueness and approximation of saddlepoint problems arising from Lagrangian multipliers, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge 8 (1974), no. R2, 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 https://doi.org/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 https://doi.org/10.1007/s002110050115
 Wolfgang Hackbusch, Multigrid methods and applications, Springer Series in Computational Mathematics, vol. 4, SpringerVerlag, Berlin, 1985. MR 814495
 Wolfgang Hackbusch, Iterative solution of large sparse systems of equations, Applied Mathematical Sciences, vol. 95, SpringerVerlag, New York, 1994. Translated and revised from the 1991 German original. MR 1247457
 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 https://doi.org/10.1007/BF02551235 RSmarzewski1996 R. Smarzewski, Iterative recovering of orthogonal projections, Preprint, December 1996.
 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 JvNeumann1933a 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.
 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 https://doi.org/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 JXu1989b 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.
 Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581–613. MR 1193013, DOI https://doi.org/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 JXuLZikatanov2000a J. Xu and L. Zikatanov, Some observations on Babuška and Brezzi theories, Num. Math., 2000 (to appear).
 Jinchao Xu and Jun Zou, Some nonoverlapping domain decomposition methods, SIAM Rev. 40 (1998), no. 4, 857–914. MR 1659681, DOI https://doi.org/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 https://doi.org/10.1017/S0962492900002385
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
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
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 #DMS0074299 and the Center for Computational Mathematics and Applications, The Pennsylvania State University.
Article copyright:
© Copyright 2002
American Mathematical Society