Develop
The
method can be used as a basis for building a
preconditioner that normally one uses if incomplete Cholesky preconditioning is not effective or fails. Assume the diagonal elements of
are nonzero. The formula
specifies the
iteration in matrix form (see Equation 20.15). Using the equation
along with some matrix algebra, it follows that (Problem 21.12):
Unfortunately, an
preconditioner is not symmetric and cannot be used for a symmetric positive definite matrix. As a result, we will use Equation 21.20 to construct a symmetric positive definite matrix termed the
preconditioning
backward sweep by reversing the iteration direction to obtain
(k+1)
The reader can verify that in the backward sweep, the roles of
and
are swapped, so we have the two equations
where
(k+1)
are residuals. Eliminating
(k+1/2)
from Equation 21.21 gives the
preconditioning matrix. The somewhat involved computations follow:
The reader should verify that
SSOR
is symmetric positive definite (Problem 21.9). Using
in Equation 21.22 gives
The matrix
PGS
corresponds to the Gauss-Seidel method. The value of
is not as critical as the choice of ω for the SOR iteration, and ω = 1 can be quite effective in many cases. Solve
PGS
or
−1
in two stages.
Solve
1
for
1
Solve
1
for
In MATLAB, compute
as follows:
The function precg in the book software distribution implements Algorithm 21.3 and adds the option of using the
preconditioner
PGS
Its calling format is
where method
’incomplete Cholesky’ or ’SSOR’ and droptol is the drop tolerance. The drop tolerance is only applicable when method is ’incomplete Cholesky’. If method is omitted, incomplete Cholesky is assumed with zerofill. If method is specified and droptol is not, droptol defaults to
There is an extensive literature concerning preconditioning that includes the
method as well as other iterations. We will present a preconditioner for the
method in Section
For a general discussion of preconditioning, see Refs.
and the book by Ref.
