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

Xu, Jinchao¹ ; Zikatanov, Ludmil¹

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

Journal of the American Mathematical Society, Tome 15 (2002) no. 3, pp. 573-597

Résumé

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.

Détail

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

Bibliographie

[1] Hebroni, P. Sur les inverses des éléments dérivables dans un anneau abstrait C. R. Acad. Sci. Paris 1939 285 287

[2] Babuå¡Ka, Ivo, Aziz, A. K. Survey lectures on the mathematical foundations of the finite element method 1972 1 359

[3] Bauschke, Heinz H., Borwein, Jonathan M., Lewis, Adrian S. The method of cyclic projections for closed convex sets in Hilbert space 1997 1 38

[4] Bauschke, Heinz H., Borwein, Jonathan M. On projection algorithms for solving convex feasibility problems SIAM Rev. 1996 367 426

[5] Braess, D., Hackbusch, W. A new convergence proof for the multigrid method including the 𝑉-cycle SIAM J. Numer. Anal. 1983 967 975

[6] Bramble, James H., Pasciak, Joseph E. New convergence estimates for multigrid algorithms Math. Comp. 1987 311 329

[7] Bramble, James H. Multigrid methods 1993

[8] Bramble, James H., Pasciak, Joseph E., Wang, Jun Ping, Xu, Jinchao Convergence estimates for multigrid algorithms without regularity assumptions Math. Comp. 1991 23 45

[9] Bramble, James H., Pasciak, Joseph E., Wang, Jun Ping, Xu, Jinchao Convergence estimates for product iterative methods with applications to domain decomposition Math. Comp. 1991 1 21

[10] Bramble, James H., Pasciak, Joseph E., Xu, Jinchao Parallel multilevel preconditioners Math. Comp. 1990 1 22

[11] Bramble, James H., Xu, Jinchao Some estimates for a weighted 𝐿² projection Math. Comp. 1991 463 476

[12] Bramble, James H., Zhang, Xuejun The analysis of multigrid methods 2000 173 415

[13] Brezzi, F. 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 1974 129 151

[14] Deutsch, Frank Applications of von Neumann’s alternating projections algorithm 1983 44 51

[15] Deutsch, Frank von Neumann’s alternating method: the rate of convergence 1983 427 434

[16] Deutsch, Frank Rate of convergence of the method of alternating projections 1985 96 107

[17] Deutsch, Frank The method of alternating orthogonal projections 1992 105 121

[18] Dryja, Maksymilian, Widlund, Olof B. Towards a unified theory of domain decomposition algorithms for elliptic problems 1990 3 21

[19] Dryja, Maksymilian, Widlund, Olof B. Multilevel additive methods for elliptic finite element problems 1991 58 69

[20] Gilbert, J., Light, W. A. Multigrid methods and the alternating algorithm 1987 447 458

[21] Griebel, M., Oswald, P. On additive Schwarz preconditioners for sparse grid discretizations Numer. Math. 1994 449 463

[22] Griebel, M., Oswald, P. On the abstract theory of additive and multiplicative Schwarz algorithms Numer. Math. 1995 163 180

[23] Hackbusch, Wolfgang Multigrid methods and applications 1985

[24] Hackbusch, Wolfgang Iterative solution of large sparse systems of equations 1994

[25] Halperin, Israel The product of projection operators Acta Sci. Math. (Szeged) 1962 96 99

[26] Kayalar, Selahattin, Weinert, Howard L. Error bounds for the method of alternating projections Math. Control Signals Systems 1988 43 59

[27] Smith, Barry F., Bjã¸Rstad, Petter E., Gropp, William D. Domain decomposition 1996

[28] Trottenberg, U., Oosterlee, C. W., Schã¼Ller, A. Multigrid 2001

[29] Ward, Morgan, Dilworth, R. P. The lattice theory of ova Ann. of Math. (2) 1939 600 608

[30] Wang, Jun Ping Convergence analysis without regularity assumptions for multigrid algorithms based on SOR smoothing SIAM J. Numer. Anal. 1992 987 1001

[31] Widlund, Olof B. Some Schwarz methods for symmetric and nonsymmetric elliptic problems 1992 19 36

[32] Xu, Jinchao Iterative methods by space decomposition and subspace correction SIAM Rev. 1992 581 613

[33] Xu, Jinchao An introduction to multilevel methods 1997 213 302

[34] Xu, Jinchao, Zou, Jun Some nonoverlapping domain decomposition methods SIAM Rev. 1998 857 914

[35] Yserentant, Harry Old and new convergence proofs for multigrid methods 1993 285 326