For example, the Jacobi scheme reads

The somewhat faster Gauss-Seidel and SOR methods are also easy to apply.

**Problem:**

The estimated rate of convergence is linked to the largest (by absolute value) eigenvalue of the iteration matrix constructed from .

In the case of the Poisson equation, the Jacobi and Gauss-Seidel
iteration matrices have spectral radii that are
close to
Slow convergence!

**Solution:**
Let
be the residual error
after the -th relaxation step.
Convergence depends not only on
, but also on the
properties of the iterated vector
. By applying **multigrid schemes** we may manipulate these
properties so as to improve convergence by orders of magnitude.

Let
be the total number of grid points;
the iterated vectors
and
are then both
of dimension .
may be written as a sum of Fourier components, or *modes*,

where

Relaxation is faster for the ``oscillatory'' high wave number modes of than for the ``smooth'', low wave number components.

**Multigrid:**
Double the lattice width:
Each wave number is automatically
increased by a factor of two.
Faster convergence of the
modes!

**Basic procedure:**

- Do several iterations on the fine grid, to get rid of the oscillatory modes
- Double the grid spacing by considering only every other lattice point (or by a more refined recipe) and relax the long-wavelength modes through a number of steps.
- If necessary, go through a cascade of such coarsening stages
- Reconstruct the fine grid gradually, using some interpolation scheme.

See also: