5.3 Iterative Methods
101
optimum over-relaxation factor. For values of w less than the optimum, the
convergence is monotonic and the rate of convergence increases as w increases.
When the optimum w is exceeded, the convergence rate deteriorates and the
convergence is oscillatory. This knowledge can be used to search for the optimum over-relaxation factor. When the optimum over-relaxation factor is
used, the number of iterations is proportional to the number of grid points in
one direction, a substantial improvement over the methods mentioned above.
For w = 1. SOR reduces to the Gauss-Seidel method.
5.3.4 Incomplete LU Decomposition: Stone's Method
We make two observations. LU decomposition is an excellent general-purpose
linear systems solver but it cannot take advantage of the sparseness of a matrix. In an iterative method, if M is a good approximation to A, rapid convergence results. These observations lead to the idea of using an approximate
LU factorization of A as the iteration matrix M i.e.:
where L and U are both sparse and N is small.
A version of this method for symmetric matrices, known as incomplete
Cholesky factorization is often used in conjunction with conjugate gradient
methods. Since the matrices that arise from discretizing convection-diffusion
problems or the Navier-Stokes equations are not symmetric, this method
cannot be applied to them. An asymmetric version of this method, called
incomplete LU factorization or ILU, is possible but has not found widespread
use. In the ILU method one proceeds as in LU decomposition but, for every
element of the original matrix A that is zero, the corresponding element of L
or U is set to zero. This factorization is not exact, but the product of these
factors can be used as the matrix M of the iterative method. This method
converges rather slowly.
Fig. 5.1. Schematic presentation of the matrices L and U and the product matrix
M; diagonals of M not found in A are shown by dashed lines
101
optimum over-relaxation factor. For values of w less than the optimum, the
convergence is monotonic and the rate of convergence increases as w increases.
When the optimum w is exceeded, the convergence rate deteriorates and the
convergence is oscillatory. This knowledge can be used to search for the optimum over-relaxation factor. When the optimum over-relaxation factor is
used, the number of iterations is proportional to the number of grid points in
one direction, a substantial improvement over the methods mentioned above.
For w = 1. SOR reduces to the Gauss-Seidel method.
5.3.4 Incomplete LU Decomposition: Stone's Method
We make two observations. LU decomposition is an excellent general-purpose
linear systems solver but it cannot take advantage of the sparseness of a matrix. In an iterative method, if M is a good approximation to A, rapid convergence results. These observations lead to the idea of using an approximate
LU factorization of A as the iteration matrix M i.e.:
where L and U are both sparse and N is small.
A version of this method for symmetric matrices, known as incomplete
Cholesky factorization is often used in conjunction with conjugate gradient
methods. Since the matrices that arise from discretizing convection-diffusion
problems or the Navier-Stokes equations are not symmetric, this method
cannot be applied to them. An asymmetric version of this method, called
incomplete LU factorization or ILU, is possible but has not found widespread
use. In the ILU method one proceeds as in LU decomposition but, for every
element of the original matrix A that is zero, the corresponding element of L
or U is set to zero. This factorization is not exact, but the product of these
factors can be used as the matrix M of the iterative method. This method
converges rather slowly.
Fig. 5.1. Schematic presentation of the matrices L and U and the product matrix
M; diagonals of M not found in A are shown by dashed lines