New convergence estimates for multigrid algorithms
Authors:
James H. Bramble and Joseph E. Pasciak
Journal:
Math. Comp. 49 (1987), 311329
MSC:
Primary 65Nxx; Secondary 65F10
MathSciNet review:
906174
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
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 and the number of relaxations m. We show that for the symmetric and nonsymmetric cycles, the multigrid iteration converges for any positive m at a rate which deteriorates no worse than , where j is the number of grid levels. We then define a generalized 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 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.
 [1]
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 (54 #9111)
 [2]
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
(86j:65037), http://dx.doi.org/10.1137/0722038
 [3]
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
(82b:65113), http://dx.doi.org/10.1090/S00255718198105950402
 [4]
D.
Braess and W.
Hackbusch, A new convergence proof for the multigrid method
including the 𝑉cycle, SIAM J. Numer. Anal.
20 (1983), no. 5, 967–975. MR 714691
(85h:65233), http://dx.doi.org/10.1137/0720066
 [5]
Achi
Brandt, Multilevel adaptive solutions to
boundaryvalue problems, Math. Comp.
31 (1977), no. 138, 333–390. MR 0431719
(55 #4714), http://dx.doi.org/10.1090/S0025571819770431719X
 [6]
Philippe
G. Ciarlet, The finite element method for elliptic problems,
NorthHolland Publishing Co., AmsterdamNew YorkOxford, 1978. Studies in
Mathematics and its Applications, Vol. 4. MR 0520174
(58 #25001)
 [7]
Todd
Dupont, Richard
P. Kendall, and H.
H. Rachford Jr., An approximate factorization procedure for solving
selfadjoint elliptic difference equations, SIAM J. Numer. Anal.
5 (1968), 559–573. MR 0235748
(38 #4051)
 [8]
R. P. Fedorenko, "The speed of convergence of one iterative process," USSR Comput. Math. and Math. Phys., v. 1, 1961, pp. 10921096.
 [9]
W. Hackbusch, MultiGrid Methods and Applications, SpringerVerlag, New York, 1985.
 [10]
J. L. Lions & E. Magenes, Problèmes aux Limites non Homogènes et Applications, Dunod, Paris, 1968.
 [11]
J.F.
Maitre and F.
Musy, Algebraic formalisation of the multigrid method in the
symmetric and positive definite case—a convergence estimation for the
𝑉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
(87i:65044)
 [12]
Jan
Mandel, Multigrid convergence for nonsymmetric, indefinite
variational problems and one smoothing step, Appl. Math. Comput.
19 (1986), no. 14, 201–216. Second Copper
Mountain conference on multigrid methods (Copper Mountain, Colo., 1985). MR 849837
(87i:65097), http://dx.doi.org/10.1016/00963003(86)901049
 [13]
Jan
Mandel, Algebraic study of multigrid methods for symmetric,
definite problems, Appl. Math. Comput. 25 (1988),
no. 1, 39–56. MR 923402
(89d:65036), http://dx.doi.org/10.1016/00963003(88)90063X
 [14]
J. Mandel, S. F. McCormick & J. Ruge, "An algebraic theory for multigrid methods for variational problems." (Preprint)
 [15]
S.
F. McCormick, Multigrid methods for variational problems: further
results, SIAM J. Numer. Anal. 21 (1984), no. 2,
255–263. MR
736329 (85h:65115), http://dx.doi.org/10.1137/0721018
 [16]
S.
F. McCormick, Multigrid methods for variational problems: general
theory for the 𝑉cycle, SIAM J. Numer. Anal.
22 (1985), no. 4, 634–643. MR 795945
(86m:65030), http://dx.doi.org/10.1137/0722039
 [17]
J. Nečas, Les Méthodes Directes en Théorie des Équations Elliptiques, Academia, Prague, 1967.
 [18]
R.
A. Nicolaides, On the 𝑙² convergence of
an algorithm for solving finite element equations, Math. Comp. 31 (1977), no. 140, 892–906. MR 0488722
(58 #8239), http://dx.doi.org/10.1090/S00255718197704887223
 [1]
 A. K. Aziz & I. Babuška, "Survey lectures on the mathematical foundations of the finite element method," in The Mathematical Foundations of the Finite Element Method with Applications to Partial Differential Equations. Part I (A. K. Aziz, ed.), Academic Press, New York, 1972, pp. 1362. MR 0421106 (54:9111)
 [2]
 R. E. Bank & C. C. Douglas, "Sharp estimates for multigrid rates of convergence with general smoothing and acceleration," SIAM J. Numer. Anal., v. 22, 1985, pp. 617633. MR 795944 (86j:65037)
 [3]
 R. E. Bank & T. F. Dupont, "An optimal order process for solving elliptic finite element equations," Math. Comp., v. 36, 1981, pp. 3551. MR 595040 (82b:65113)
 [4]
 D. Braess & W. Hackbusch, "A new convergence proof for the multigrid method including the Vcycle," SIAM J. Numer. Anal., v. 20, 1983, pp. 967975. MR 714691 (85h:65233)
 [5]
 A. Brandt, "Multilevel adaptive solutions to boundaryvalue problems," Math. Comp., v. 31, 1977, pp. 333390. MR 0431719 (55:4714)
 [6]
 P. G. Ciarlet, The Finite Element Method for Elliptic Problems, NorthHolland, New York, 1978. MR 0520174 (58:25001)
 [7]
 T. Dupont, R. P. Kendall & H. H. Rachford, "An approximate factorization procedure for solving selfadjoint elliptic difference equations," SIAM J. Numer. Anal., v. 5, 1968, pp. 559573. MR 0235748 (38:4051)
 [8]
 R. P. Fedorenko, "The speed of convergence of one iterative process," USSR Comput. Math. and Math. Phys., v. 1, 1961, pp. 10921096.
 [9]
 W. Hackbusch, MultiGrid Methods and Applications, SpringerVerlag, New York, 1985.
 [10]
 J. L. Lions & E. Magenes, Problèmes aux Limites non Homogènes et Applications, Dunod, Paris, 1968.
 [11]
 J. F. Maitre & F. Musy, "Algebraic normalization of the multigrid method in the symmetric and positive definite casea convergence estimation for the Vcycle," Multigrid Methods for Integral and Differential Equations (D. J. Paddon and H. Holstein, eds.), Clarendon Press, Oxford, 1985. MR 849375 (87i:65044)
 [12]
 J. Mandel, "Multigrid convergence for nonsymmetric, indefinite variational problems and one smoothing step," in Proc. Copper Mtn. Conf. Multigrid Methods, Applied Math. Comput., 1986, pp. 201216. MR 849837 (87i:65097)
 [13]
 J. Mandel, "Algebraic study of multigrid methods for symmetric, definite problems." (Preprint) MR 923402 (89d:65036)
 [14]
 J. Mandel, S. F. McCormick & J. Ruge, "An algebraic theory for multigrid methods for variational problems." (Preprint)
 [15]
 S. F. McCormick, "Multigrid methods for variational problems: Further results," SIAM J. Numer. Anal., v. 21, 1984, pp. 255263. MR 736329 (85h:65115)
 [16]
 S. F. McCormick, "Multigrid methods for variational problems: General theory for the Vcycle," SIAM J. Numer. Anal., v. 22, 1985, pp. 634643. MR 795945 (86m:65030)
 [17]
 J. Nečas, Les Méthodes Directes en Théorie des Équations Elliptiques, Academia, Prague, 1967.
 [18]
 R. A. Nicolaides, "On the convergence of an algorithm for solving finite element equations," Math. Comp., v. 31, 1977, pp. 892906. MR 0488722 (58:8239)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65Nxx,
65F10
Retrieve articles in all journals
with MSC:
65Nxx,
65F10
Additional Information
DOI:
http://dx.doi.org/10.1090/S0025571819870906174X
PII:
S 00255718(1987)0906174X
Article copyright:
© Copyright 1987
American Mathematical Society
