Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

A sharp convergence estimate for the method of subspace corrections for singular systems of equations


Authors: Young-Ju Lee, Jinbiao Wu, Jinchao Xu and Ludmil Zikatanov
Journal: Math. Comp. 77 (2008), 831-850
MSC (2000): Primary 65J10; Secondary 65F10
DOI: https://doi.org/10.1090/S0025-5718-07-02052-2
Published electronically: October 17, 2007
MathSciNet review: 2373182
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. I. Babuška and J. M. Melenk.
    The partition of unity method.
    Internat. J. Numer. Methods Engrg., 40(4):727-758, 1997. MR 1429534 (97j:73071)
  • 2. A. B. Berman and R. J. Plemmons.
    Nonnegative matrices in the mathematical sciences.
    SIAM classics in Applied Mathematics, Philadelphia, 1994. MR 1298430 (95e:15013)
  • 3. Pavel Bochev and R. B. Lehoucq.
    On the finite element solution of the pure Neumann problem.
    SIAM Rev., 47(1):50-66 (electronic), 2005. MR 2149101 (2007a:65185)
  • 4. J. H. Bramble and X. Zhang.
    The analysis of multigrid methods.
    Handbook of numerical analysis, Vol. VII. North-Holland, Amsterdam, 2000. MR 1804746 (2001m:65183)
  • 5. J. H. Bramble and J. E. Pasciak.
    Iterative techniques for time dependent stokes problems.
    Comput. Math. with Appl., 33:13-30, 1997. MR 1442058 (98e:65091)
  • 6. Z. H. Cao.
    A note on properties of splittings of singular symmetric positive semidefinite matrices.
    Numer. Math., 88:603-606, 2001. MR 1836872 (2002b:65045)
  • 7. Frank Deutsch.
    Best approximation in inner product spaces.
    CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 7. Springer-Verlag, New York, 2001. MR 1823556 (2002c:41001)
  • 8. Heinz W. Engl, Martin Hanke, and Andreas Neubauer.
    Regularization of inverse problems, volume 375 of Mathematics and its Applications.
    Kluwer Academic Publishers Group, Dordrecht, 1996. MR 1408680 (97k:65145)
  • 9. Wolfgang Hackbusch.
    Multigrid methods and applications, volume 4 of Springer Series in Computational Mathematics.
    Springer-Verlag, Berlin, 1985. MR 814495 (87e:65082)
  • 10. H. B. Keller.
    On the solution of singular and semidefinite linear systems by iteration.
    J. Soc. Indust. Appl. Math. Ser. B Numer. Anal., 2:281-290, 1965. MR 0195244 (33:3447)
  • 11. Young-Ju Lee, Jinbiao Wu, Jinchao Xu, and Ludmil Zikatanov.
    On the convergence of iterative methods for semidefinite linear systems.
    SIAM Journal on Matrix Analysis and Applications., 28 (3): 634-641, 2006. MR 2262973
  • 12. I. Marek and D. B. Szyld.
    Comparison theorems for the convergence factor of iterative methods for singular matrices.
    Linear Algebra and its Applications., 316:67-87, 2000. MR 1782417 (2001h:65040)
  • 13. I. Marek and D. B. Szyld.
    Algebraic Schwarz methods for the numerical solution of Markov chains.
    Linear Algebra and its Applications., 386:67-81 Sp. Iss. SI, 2004. MR 2066608 (2005i:60005)
  • 14. R. Nabben and D. B. Szyld.
    Schwarz iterations for symmetric positive semidefinite problems. SIAM J. Matrix Anal. Appl., 29:98-116. MR 2288016
  • 15. 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(1):69-78, 1990.
    Soviet Journal of Numerical Analysis and Mathematical Modelling. MR 1124937 (92k:65182)
  • 16. Walter Rudin.
    Functional analysis.
    International Series in Pure and Applied Mathematics. McGraw-Hill, Inc., New York, second edition, 1991. MR 1157815 (92k:46001)
  • 17. L. Shen and J. Xu.
    On a Schur complement operator arisen from Navier-Stokes equations and its preconditioning, volume 202 of Advances in computational mathematics (Guangzhou, 1997) Lectures Notes in Pure and Appl. Math.
    Dekker, New York, 1999. MR 1661553 (99i:76129)
  • 18. Qian shun Chang and Wei wei Sun.
    On convergence of multigrid method for nonnegative definite systems.
    J. Comput. Math., 23(2):177-184, 2005. MR 2118053 (2005i:65207)
  • 19. T. Strouboulis, I. Babuška, and K. Copps.
    The design and analysis of the generalized finite element method.
    Comput. Methods Appl. Mech. Engrg., 181(1-3):43-69, 2000. MR 1734667 (2000h:74077)
  • 20. T. Strouboulis, K. Copps, and I. Babuška.
    The generalized finite element method.
    Comput. Methods Appl. Mech. Engrg., 190(32-33):4081-4193, 2001. MR 1832655 (2002h:65195)
  • 21. 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(9-12):852-879, 2006. MR 2195292 (2006i:65180)
  • 22. Andrea Toselli and Olof Widlund.
    Domain decomposition methods--algorithms and theory, volume 34 of Springer Series in Computational Mathematics.
    Springer-Verlag, Berlin, 2005. MR 2104179 (2005g:65006)
  • 23. U. Trottenberg, C. W. Oosterlee, and A. Schüller.
    Multigrid. With contributions by A. Brandt, P. Oswald and K. Stuben.
    Academic Press Inc., San Diego, CA, 2001. MR 1807961 (2002b:65002)
  • 24. J. Xu and L. Zikatanov.
    The method of subspace corrections and the method of alternating projections in Hilbert space.
    J. Amer. Math. Soc., 15(3):573-597, 2002. MR 1896233 (2003f:65095)
  • 25. Jinchao Xu.
    Iterative methods by space decomposition and subspace correction.
    SIAM Review, 34:581-613, 1992. MR 1193013 (93k:65029)
  • 26. Jinchao Xu and Ludmil T. Zikatanov.
    On multigrid methods for generalized finite element methods.
    In Meshfree methods for partial differential equations (Bonn, 2001), volume 26 of Lect. Notes Comput. Sci. Eng., pages 401-418. Springer, Berlin, 2003. MR 2004013
  • 27. Kôsaku Yosida.
    Functional analysis.
    Die Grundlehren der Mathematischen Wissenschaften, Band 123. Academic Press, Inc., New York, 1965. MR 0180824 (31:5054)
  • 28. Harry Yserentant.
    Old and new convergence proofs for multigrid methods.
    In Acta numerica, 1993, Acta Numer., pages 285-326. Cambridge Univ. Press, Cambridge, 1993. MR 1224685 (94i:65128)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65J10, 65F10

Retrieve articles in all journals with MSC (2000): 65J10, 65F10


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
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

DOI: https://doi.org/10.1090/S0025-5718-07-02052-2
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
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society