Convergence of the multigrid $V$-cycle algorithm for second-order boundary value problems without full elliptic regularity
HTML articles powered by AMS MathViewer
- by Susanne C. Brenner PDF
- Math. Comp. 71 (2002), 507-525 Request permission
Abstract:
The multigrid $V$-cycle algorithm using the Richardson relaxation scheme as the smoother is studied in this paper. For second-order elliptic boundary value problems, the contraction number of the $V$-cycle algorithm is shown to improve uniformly with the increase of the number of smoothing steps, without assuming full elliptic regularity. As a consequence, the $V$-cycle convergence result of Braess and Hackbusch is generalized to problems without full elliptic regularity.References
- Randolph E. Bank and Craig C. Douglas, Sharp estimates for multigrid rates of convergence with general smoothing and acceleration, SIAM J. Numer. Anal. 22 (1985), no. 4, 617–633. MR 795944, DOI 10.1137/0722038
- Randolph E. Bank and Todd Dupont, An optimal order process for solving finite element equations, Math. Comp. 36 (1981), no. 153, 35–51. MR 595040, DOI 10.1090/S0025-5718-1981-0595040-2
- Colin Bennett and Robert Sharpley, Interpolation of operators, Pure and Applied Mathematics, vol. 129, Academic Press, Inc., Boston, MA, 1988. MR 928802
- 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, 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
- J. H. Bramble and S. R. Hilbert, Estimation of linear functionals on Sobolev spaces with application to Fourier transforms and spline interpolation, SIAM J. Numer. Anal. 7 (1970), 112–124. MR 263214, DOI 10.1137/0707006
- 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 and Joseph E. Pasciak, New estimates for multilevel algorithms including the $V$-cycle, Math. Comp. 60 (1993), no. 202, 447–471. MR 1176705, DOI 10.1090/S0025-5718-1993-1176705-9
- James H. Bramble and Joseph E. Pasciak, Uniform convergence estimates for multigrid $V$-cycle algorithms with less than full elliptic regularity, Domain decomposition methods in science and engineering (Como, 1992) Contemp. Math., vol. 157, Amer. Math. Soc., Providence, RI, 1994, pp. 17–26. MR 1262601, DOI 10.1090/conm/157/01401
- J.H. Bramble and X. Zhang, The analysis of multigrid methods, Handb. Numer. Anal. VII, North-Holland, Amsterdam, 2000, 173–415.
- —, Uniform convergence of the multigrid $V$-cycle for an anisotropic problem, Math. Comp. 70 (2001), 453–470.
- Susanne C. Brenner, Multigrid methods for the computation of singular solutions and stress intensity factors. I. Corner singularities, Math. Comp. 68 (1999), no. 226, 559–583. MR 1609670, DOI 10.1090/S0025-5718-99-01017-0
- Susanne C. Brenner, A nonstandard finite element interpolation estimate, Numer. Funct. Anal. Optim. 20 (1999), no. 3-4, 245–250. MR 1691362, DOI 10.1080/01630569908816890
- Susanne C. Brenner and L. Ridgway Scott, The mathematical theory of finite element methods, Texts in Applied Mathematics, vol. 15, Springer-Verlag, New York, 1994. MR 1278258, DOI 10.1007/978-1-4757-4338-8
- S. C. Brenner and L.-Y. Sung, Multigrid methods for the computation of singular solutions and stress intensity factors. II. Crack singularities, BIT 37 (1997), no. 3, 623–643. Direct methods, linear algebra in optimization, iterative methods (Toulouse, 1995/1996). MR 1483677, DOI 10.1007/BF02510243
- Philippe G. Ciarlet, The finite element method for elliptic problems, Studies in Mathematics and its Applications, Vol. 4, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1978. MR 0520174
- Ph. Clément, Approximation by finite element functions using local regularization, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. 9 (1975), no. R-2, 77–84 (English, with Loose French summary). MR 0400739
- Monique Dauge, Elliptic boundary value problems on corner domains, Lecture Notes in Mathematics, vol. 1341, Springer-Verlag, Berlin, 1988. Smoothness and asymptotics of solutions. MR 961439, DOI 10.1007/BFb0086682
- Todd Dupont and Ridgway Scott, Polynomial approximation of functions in Sobolev spaces, Math. Comp. 34 (1980), no. 150, 441–463. MR 559195, DOI 10.1090/S0025-5718-1980-0559195-7
- 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
- P. Grisvard, Elliptic problems in nonsmooth domains, Monographs and Studies in Mathematics, vol. 24, Pitman (Advanced Publishing Program), Boston, MA, 1985. MR 775683
- W. Hackbusch, Multigrid convergence theory, Multigrid methods (Cologne, 1981) Lecture Notes in Math., vol. 960, Springer, Berlin-New York, 1982, pp. 177–219. MR 685774
- 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
- G.H. Hardy, J.E. Littlewood and G. Pólya, Inequalities, Cambridge University Press, Cambridge, 1934.
- J. Mandel, S. McCormick and R. Bank, Variational multigrid theory, Multigrid Methods (S.F. McCormick, ed.), Frontiers In Applied Mathematics 3, SIAM, Philadelphia, 1987, pp. 131–177.
- S. F. McCormick, Multigrid methods for variational problems: further results, SIAM J. Numer. Anal. 21 (1984), no. 2, 255–263. MR 736329, DOI 10.1137/0721018
- Sergey A. Nazarov and Boris A. Plamenevsky, Elliptic problems in domains with piecewise smooth boundaries, De Gruyter Expositions in Mathematics, vol. 13, Walter de Gruyter & Co., Berlin, 1994. MR 1283387, DOI 10.1515/9783110848915.525
- N. Neuss, $V$-cycle convergence with unsymmetric smoothers and applications to an anisotropic model problem, SIAM J. Numer. Anal. 35 (1998), 1201–1212.
- L. Ridgway Scott and Shangyou Zhang, Finite element interpolation of nonsmooth functions satisfying boundary conditions, Math. Comp. 54 (1990), no. 190, 483–493. MR 1011446, DOI 10.1090/S0025-5718-1990-1011446-7
- H. Triebel, Interpolation theory, function spaces, differential operators, VEB Deutscher Verlag der Wissenschaften, Berlin, 1978. MR 500580
- Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581–613. MR 1193013, DOI 10.1137/1034116
- 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
- Erich Rothe, Topological proofs of uniqueness theorems in the theory of differential and integral equations, Bull. Amer. Math. Soc. 45 (1939), 606–613. MR 93, DOI 10.1090/S0002-9904-1939-07048-1
Additional Information
- Susanne C. Brenner
- Affiliation: Department of Mathematics, University of South Carolina, Columbia, South Carolina 29208
- Email: brenner@math.sc.edu
- Received by editor(s): August 18, 1999
- Received by editor(s) in revised form: October 27, 1999, and July 10, 2000
- Published electronically: November 19, 2001
- Additional Notes: This work was supported in part by the National Science Foundation under Grant Nos. DMS-96-00133 and DMS-00-74246.
- © Copyright 2001 American Mathematical Society
- Journal: Math. Comp. 71 (2002), 507-525
- MSC (2000): Primary 65N55, 65N30
- DOI: https://doi.org/10.1090/S0025-5718-01-01361-8
- MathSciNet review: 1885612