Multigrid Methods

James H Bramble

• Publisher: Chapman and Hall/CRC
• Year: 2019
• ISBN:
  9781351429856
• Edition: 1
• Topic: Mathematik
• Subtopic: Mathematik Allgemein

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...