Next: 5.3.2 ADI Method for
Up: 5.3 Boundary Value Problems:
Previous: 5.3 Boundary Value Problems:
Having transformed the given elliptic PDE
into a set of linear equations
,
we can apply any iterative technique to find
.
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.
Next: 5.3.2 ADI Method for
Up: 5.3 Boundary Value Problems:
Previous: 5.3 Boundary Value Problems:
Franz J. Vesely Oct 2005
See also: "Computational Physics - An Introduction," Kluwer-Plenum 2001