## New convergence estimates for multigrid algorithms

HTML articles powered by AMS MathViewer

- by James H. Bramble and Joseph E. Pasciak PDF
- Math. Comp.
**49**(1987), 311-329 Request permission

## Abstract:

In this paper, new convergence estimates are proved for both symmetric and nonsymmetric multigrid algorithms applied to symmetric positive definite problems. Our theory relates the convergence of multigrid algorithms to a "regularity and approximation" parameter $\alpha \in (0,1]$ and the number of relaxations*m*. We show that for the symmetric and nonsymmetric $\mathcal {V}$ cycles, the multigrid iteration converges for any positive

*m*at a rate which deteriorates no worse than $1 - c{j^{ - (1 - \alpha )/\alpha }}$, where

*j*is the number of grid levels. We then define a generalized $\mathcal {V}$ cycle algorithm which involves exponentially increasing (for example, doubling) the number of smoothings on successively coarser grids. We show that the resulting symmetric and nonsymmetric multigrid iterations converge for any $\alpha$ with rates that are independent of the mesh size. The theory is presented in an abstract setting which can be applied to finite element multigrid and finite difference multigrid methods.

## References

- 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, 1972, pp. 1–359. With the collaboration of G. Fix and R. B. Kellogg. MR**0421106** - 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 - 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 - Achi Brandt,
*Multi-level adaptive solutions to boundary-value problems*, Math. Comp.**31**(1977), no. 138, 333–390. MR**431719**, DOI 10.1090/S0025-5718-1977-0431719-X - 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** - Todd Dupont, Richard P. Kendall, and H. H. Rachford Jr.,
*An approximate factorization procedure for solving self-adjoint elliptic difference equations*, SIAM J. Numer. Anal.**5**(1968), 559–573. MR**235748**, DOI 10.1137/0705045
R. P. Fedorenko, "The speed of convergence of one iterative process," - J.-F. Maitre and F. Musy,
*Algebraic formalisation of the multigrid method in the symmetric and positive definite case—a convergence estimation for the $V$-cycle*, Multigrid methods for integral and differential equations (Bristol, 1983) Inst. Math. Appl. Conf. Ser. New Ser., vol. 3, Oxford Univ. Press, New York, 1985, pp. 213–223. MR**849375** - Jan Mandel,
*Multigrid convergence for nonsymmetric, indefinite variational problems and one smoothing step*, Appl. Math. Comput.**19**(1986), no. 1-4, 201–216. Second Copper Mountain conference on multigrid methods (Copper Mountain, Colo., 1985). MR**849837**, DOI 10.1016/0096-3003(86)90104-9 - Jan Mandel,
*Algebraic study of multigrid methods for symmetric, definite problems*, Appl. Math. Comput.**25**(1988), no. 1, 39–56. MR**923402**, DOI 10.1016/0096-3003(88)90063-X
J. Mandel, S. F. McCormick & J. Ruge, "An algebraic theory for multigrid methods for variational problems." (Preprint)
- 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 - S. F. McCormick,
*Multigrid methods for variational problems: general theory for the $V$-cycle*, SIAM J. Numer. Anal.**22**(1985), no. 4, 634–643. MR**795945**, DOI 10.1137/0722039
J. Nečas, - R. A. Nicolaides,
*On the $l^{2}$ convergence of an algorithm for solving finite element equations*, Math. Comp.**31**(1977), no. 140, 892–906. MR**488722**, DOI 10.1090/S0025-5718-1977-0488722-3

*USSR Comput. Math. and Math. Phys.*, v. 1, 1961, pp. 1092-1096. W. Hackbusch,

*Multi-Grid Methods and Applications*, Springer-Verlag, New York, 1985. J. L. Lions & E. Magenes,

*Problèmes aux Limites non Homogènes et Applications*, Dunod, Paris, 1968.

*Les Méthodes Directes en Théorie des Équations Elliptiques*, Academia, Prague, 1967.

## Additional Information

- © Copyright 1987 American Mathematical Society
- Journal: Math. Comp.
**49**(1987), 311-329 - MSC: Primary 65Nxx; Secondary 65F10
- DOI: https://doi.org/10.1090/S0025-5718-1987-0906174-X
- MathSciNet review: 906174