   Next: 5.3.2 ADI Method for Up: 5.3 Boundary Value Problems: Previous: 5.3 Boundary Value Problems:

5.3.1 Relaxation and Multigrid Techniques

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