New convergence estimates for multigrid algorithms

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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="alpha element-of left-parenthesis 0 comma 1 right-bracket"> <mml:semantics> <mml:mrow> <mml:mi> α </mml:mi> <mml:mo> ∈ </mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">]</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\alpha \in (0,1]</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and the number of relaxations <italic>m</italic> . We show that for the symmetric and nonsymmetric <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper V"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">V</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {V}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> cycles, the multigrid iteration converges for any positive <italic>m</italic> at a rate which deteriorates no worse than <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1 minus c j Superscript minus left-parenthesis 1 minus alpha right-parenthesis slash alpha"> <mml:semantics> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo> − </mml:mo> <mml:mi>c</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>j</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo> − </mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo> − </mml:mo> <mml:mi> α </mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi> α </mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">1 - c{j^{ - (1 - \alpha )/\alpha }}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , where <italic>j</italic> is the number of grid levels. We then define a generalized <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper V"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">V</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {V}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> 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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="alpha"> <mml:semantics> <mml:mi> α </mml:mi> <mml:annotation encoding="application/x-tex">\alpha</mml:annotation> </mml:semantics> </mml:math> </inline-formula> 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.