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

Xu, Jinchao; Zikatanov, Ludmil

doi:10.1090/S0894-0347-02-00398-3

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;

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

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

Published electronically: April 8, 2002

PDF | 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-London, 1972, pp. 1–359. With the collaboration of G. Fix and R. B. Kellogg. MR 421106
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

Accelerating the convergence of the method of alternating projections

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

Iterative recovering of orthogonal projections

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

Theory of multilevel methods

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

Some observations on Babuška and Brezzi theories

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