A sharp convergence estimate for the method of subspace corrections for singular systems of equations
HTML articles powered by AMS MathViewer
- by Young-Ju Lee, Jinbiao Wu, Jinchao Xu and Ludmil Zikatanov PDF
- Math. Comp. 77 (2008), 831-850 Request permission
Abstract:
This paper is devoted to the convergence rate estimate for the method of successive subspace corrections applied to symmetric and positive semidefinite (singular) problems. In a general Hilbert space setting, a convergence rate identity is obtained for the method of subspace corrections in terms of the subspace solvers. As an illustration, the new abstract theory is used to show uniform convergence of a multigrid method applied to the solution of the Laplace equation with pure Neumann boundary conditions.References
- I. Babuška and J. M. Melenk, The partition of unity method, Internat. J. Numer. Methods Engrg. 40 (1997), no. 4, 727–758. MR 1429534, DOI 10.1002/(SICI)1097-0207(19970228)40:4<727::AID-NME86>3.3.CO;2-E
- Abraham Berman and Robert J. Plemmons, Nonnegative matrices in the mathematical sciences, Classics in Applied Mathematics, vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. Revised reprint of the 1979 original. MR 1298430, DOI 10.1137/1.9781611971262
- Pavel Bochev and R. B. Lehoucq, On the finite element solution of the pure Neumann problem, SIAM Rev. 47 (2005), no. 1, 50–66. MR 2149101, DOI 10.1137/S0036144503426074
- 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
- J. H. Bramble and J. E. Pasciak, Iterative techniques for time dependent Stokes problems, Comput. Math. Appl. 33 (1997), no. 1-2, 13–30. Approximation theory and applications. MR 1442058, DOI 10.1016/S0898-1221(96)00216-7
- Zhi-Hao Cao, A note on properties of splittings of singular symmetric positive semidefinite matrices, Numer. Math. 88 (2001), no. 4, 603–606. MR 1836872, DOI 10.1007/PL00005451
- Frank Deutsch, Best approximation in inner product spaces, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, vol. 7, Springer-Verlag, New York, 2001. MR 1823556, DOI 10.1007/978-1-4684-9298-9
- Heinz W. Engl, Martin Hanke, and Andreas Neubauer, Regularization of inverse problems, Mathematics and its Applications, vol. 375, Kluwer Academic Publishers Group, Dordrecht, 1996. MR 1408680
- 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
- Herbert B. Keller, On the solution of singular and semidefinite linear systems by iteration, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal. 2 (1965), 281–290. MR 195244
- Young-Ju Lee, Jinbiao Wu, Jinchao Xu, and Ludmil Zikatanov, On the convergence of iterative methods for semidefinite linear systems, SIAM J. Matrix Anal. Appl. 28 (2006), no. 3, 634–641. MR 2262973, DOI 10.1137/050644197
- Ivo Marek and Daniel B. Szyld, Comparison theorems for the convergence factor of iterative methods for singular matrices, Linear Algebra Appl. 316 (2000), no. 1-3, 67–87. Conference Celebrating the 60th Birthday of Robert J. Plemmons (Winston-Salem, NC, 1999). MR 1782417, DOI 10.1016/S0024-3795(99)00275-X
- Ivo Marek and Daniel B. Szyld, Algebraic Schwarz methods for the numerical solution of Markov chains, Linear Algebra Appl. 386 (2004), 67–81. MR 2066608, DOI 10.1016/j.laa.2003.12.046
- Reinhard Nabben and Daniel B. Szyld, Schwarz iterations for symmetric positive semidefinite problems, SIAM J. Matrix Anal. Appl. 29 (2006/07), no. 1, 98–116. MR 2288016, DOI 10.1137/050644203
- S. V. Nepomnyaschikh, Schwartz alternating method for solving the singular Neumann problem [translation of Computational algorithms in problems of mathematical physics (Russian), 99–112, Akad. Nauk SSSR Sibirsk, Otdel., Vychisl. Tsentr, Novosibirsk, 1985], Soviet J. Numer. Anal. Math. Modelling 5 (1990), no. 1, 69–78. Soviet Journal of Numerical Analysis and Mathematical Modelling. MR 1124937
- Walter Rudin, Functional analysis, 2nd ed., International Series in Pure and Applied Mathematics, McGraw-Hill, Inc., New York, 1991. MR 1157815
- Ling Shen and Jinchao Xu, On a Schur complement operator arisen from Navier-Stokes equations and its preconditioning, Advances in computational mathematics (Guangzhou, 1997) Lecture Notes in Pure and Appl. Math., vol. 202, Dekker, New York, 1999, pp. 481–490. MR 1661553
- Qian-shun Chang and Wei-wei Sun, On convergence of multigrid method for nonnegative definite systems, J. Comput. Math. 23 (2005), no. 2, 177–184. MR 2118053
- T. Strouboulis, I. Babuška, and K. Copps, The design and analysis of the generalized finite element method, Comput. Methods Appl. Mech. Engrg. 181 (2000), no. 1-3, 43–69. MR 1734667, DOI 10.1016/S0045-7825(99)00072-9
- T. Strouboulis, K. Copps, and I. Babuška, The generalized finite element method, Comput. Methods Appl. Mech. Engrg. 190 (2001), no. 32-33, 4081–4193. MR 1832655, DOI 10.1016/S0045-7825(01)00188-8
- Theofanis Strouboulis, Lin Zhang, Delin Wang, and Ivo Babuška, A posteriori error estimation for generalized finite element methods, Comput. Methods Appl. Mech. Engrg. 195 (2006), no. 9-12, 852–879. MR 2195292, DOI 10.1016/j.cma.2005.03.004
- Andrea Toselli and Olof Widlund, Domain decomposition methods—algorithms and theory, Springer Series in Computational Mathematics, vol. 34, Springer-Verlag, Berlin, 2005. MR 2104179, DOI 10.1007/b137868
- 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
- Jinchao Xu and Ludmil Zikatanov, The method of alternating projections and the method of subspace corrections in Hilbert space, J. Amer. Math. Soc. 15 (2002), no. 3, 573–597. MR 1896233, DOI 10.1090/S0894-0347-02-00398-3
- 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 and Ludmil T. Zikatanov, On multigrid methods for generalized finite element methods, Meshfree methods for partial differential equations (Bonn, 2001) Lect. Notes Comput. Sci. Eng., vol. 26, Springer, Berlin, 2003, pp. 401–418. MR 2004013, DOI 10.1007/978-3-642-56103-0_{2}8
- Kôsaku Yosida, Functional analysis, Die Grundlehren der mathematischen Wissenschaften, Band 123, Academic Press, Inc., New York; Springer-Verlag, Berlin, 1965. MR 0180824
- 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
Additional Information
- Young-Ju Lee
- Affiliation: Department of Mathematics, University of California Los Angeles, Los Angeles, California 90089
- Address at time of publication: Department of Mathematics, Rutgers, The State University of New Jersey, Hill Center, Piscataway, New Jersey 08854-8019
- Email: leeyoung@math.rutgers.edu
- Jinbiao Wu
- Affiliation: Laboratory of Pure and Applied Mathematics, School of Mathematical Sciences, Peking University, Beijing 100871, People’s Republic of China
- Email: jwu@math.pku.edu.cn
- Jinchao Xu
- Affiliation: Department of Mathematics, Pennsylvania State University, McAllister Bldg., University Park, Pennsylvania 16802-6401 –and– Laboratory of Pure and Applied Mathematics, School of Mathematical Sciences, Peking University, Beijing 100871, People’s Republic of China
- MR Author ID: 228866
- Email: xu@math.psu.edu
- Ludmil Zikatanov
- Affiliation: Department of Mathematics, Pennsylvania State University, McAllister Bldg., University Park, Pennsylvania 16802-6401
- Email: ltz@math.psu.edu
- Received by editor(s): March 29, 2003
- Received by editor(s) in revised form: July 31, 2006
- Published electronically: October 17, 2007
- Additional Notes: The authors were supported in part by NSF Grant No. DMS-0209497 and Center for Computational Mathematics and Applications, Penn State University
The first author was supported in part by National Science Foundation DMS-0609655
The second author was supported in part by NSFC 10501001 and SRF for ROCS, SEM
The third author was supported in part by National Science Foundation DMS-0609727 and DMS-0619587, NSFC-10528102, and Research Award for National Outstanding Youth (Class B) by National Science Foundation of China
The fourth author was supported in part by National Science Foundation DMS-0511800 - © Copyright 2007
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 77 (2008), 831-850
- MSC (2000): Primary 65J10; Secondary 65F10
- DOI: https://doi.org/10.1090/S0025-5718-07-02052-2
- MathSciNet review: 2373182