Multigrid Methods

James H Bramble

• Publisher: Chapman and Hall/CRC
• Year: 2019
• Print ISBN: 9780582234352
• eBook ISBN: 9781351429856
• Topic: Mathematics
• Subtopic: Differential Equations
• Index: Mathematics

Multigrid methods are among the most efficient iterative methods for the solution of linear systems which arise in many large scale scientific calculations. Every researcher working with the numerical solution of partial differential equations should at least be familiar with this powerful technique. This invaluable book presents results concerning the rates of convergence of multigrid iterations.

1. Introduction to Iterative Methods

We shall consider the equation

(1.1)

$Ax=f$

in a finite dimensional real inner product space M with inner product (·,·) and dimension N. The operator A will be linear, symmetric with respect to (·,·) and positive definite (SPD).

For such operators A we have the eigenvalues {Λ_i} and corresponding eigenvectors {φ_i}. That is, 0 < Λ₁ ≤ Λ₂ ≤ ⋯ ≤ Λ_N and

$A{\phi }_i={\mathrm{\Lambda }}_i{\phi }_i,i=1,\mathrm{\dots },N.$

We may take φ_i so that

$\left({\phi }_i,{\phi }_j\right)={\delta }_{ij}$

where δ_ij is the Kronecker delta. The eigenvectors form an orthonormal basis for M, i.e., for any u ∈ M

(1.2)

$u={\displaystyle \sum _{i=1}^N(u,{\phi }_i){\phi }_i.}$

We want to consider the following linear iterative methods. Let B be another operator on M which is SPD. Consider for x⁰ arbitrary,

(1.3)

$x^{n+1}=x^n-B(A{x}^n-f).$

This iteration is called linear, since the error operator I − BA is linear. Such a scheme is automatically consistent in the sense that x is a fixed point.

We consider first the simple case B = τI, with τ a scalar and examine the convergence properties of (1.3) for this example.

To do this set eⁿ = x − xⁿ. Then

(1.4)

$\begin{array}{lll}{e}^n=e^{n-1}-\tau A{e}^{n-1}\hfill & =\hfill & (I-\tau A)e^{n-1}\hfill \\ \hfill & =\hfill & {(I-\tau A)}^n{e}^0.\hfill \end{array}$

Now, since the...

Table of contents

• Cover
• Title Page
• Copyright Page
• Table of Contents
• Preface
• 1. Introduction to Iterative Methods
• 2. Model problems and Sobolev spaces
• 3. Abstract Multilevel Algorithms
• 4. Multigrid Algorithms with Nonnested Spaces and Varying Forms
• 5. Construction of Classes of Smoothers
• 6. Application to second order elliptic problems
• 7. Perturbation of Forms
• 8. Pseudodifferential operators of order minus one
• 9. Application to fourth order problems
• 10. Implementation, work estimates, and full multigrid
• Appendix A: The Conjugate Gradient Algorithm
• Appendix B: Introduction to interpolation spaces
• Appendix C: Glossary of conditions
• References
• Index