5.3 Iterative Methods
109
This property is akin to orthogonality; the vectors p1 and p2 are said to be
conjugate with respect to the matrix A, which gives the method its name. A
detailed proof of this statement and others cited below can be found in the
book of Golub and van Loan (1990).
This property can be extended to any number of directions. In the conjugate gradient method, each new search direction is required to be conjugate
to all the preceding ones. If the matrix is non-singular, as is the case in nearly
all engineering problems, the directions are guaranteed to be linearly independent. Consequently, if exact (no round-off error) arithmetic were employed,
the conjugate gradient method would converge exactly when the number of
iterations is equal to the size of the matrix. This number can be quite large
and, in practice, exact convergence is not achieved due to arithmetic errors.
It is therefore wiser to regard the conjugate gradient method as an iterative
method.
While the conjugate gradient method guarantees that the error is reduced
on each iteration, the size of the reduction depends on the search direction. It
is not unusual for this method to reduce the error only slightly for a number
of iterations and then find a direction that reduces the error by an order of
magnitude or more in one iteration.
It can be shown that the rate of convergence of this method depends on
the condition number n of the matrix where
and Amax and Xmi, are the largest and smallest eigenvalues of the matrix.
The condition numbers of matrices that arise in CFD problems are usually
approximately the square of the maximum number of grid points in any
direction. With 100 grid points in each direction, the condition number should
be about lo4 and the standard conjugate gradient method would converge
slowly. Although the conjugate gradient method is significantly faster than
steepest descents for a given condition number, this basic method is not very
useful.
This method can be improved by replacing the problem whose solution we
seek by another one with the same solution but a smaller condition number.
For obvious reasons, this is called preconditioning. One way to precondition
the problem is to pre-multiply the equation by another (carefully chosen) matrix. As this would destroy the symmetry of the matrix, the preconditioning
must take the following form:
The conjugate gradient method is applied to the matrix C-' AC-' i.e. to the
modified problem (5.58). If this is done and the residual form of the iterative
method is used, the following algorithm results (for a detailed derivation, see
109
This property is akin to orthogonality; the vectors p1 and p2 are said to be
conjugate with respect to the matrix A, which gives the method its name. A
detailed proof of this statement and others cited below can be found in the
book of Golub and van Loan (1990).
This property can be extended to any number of directions. In the conjugate gradient method, each new search direction is required to be conjugate
to all the preceding ones. If the matrix is non-singular, as is the case in nearly
all engineering problems, the directions are guaranteed to be linearly independent. Consequently, if exact (no round-off error) arithmetic were employed,
the conjugate gradient method would converge exactly when the number of
iterations is equal to the size of the matrix. This number can be quite large
and, in practice, exact convergence is not achieved due to arithmetic errors.
It is therefore wiser to regard the conjugate gradient method as an iterative
method.
While the conjugate gradient method guarantees that the error is reduced
on each iteration, the size of the reduction depends on the search direction. It
is not unusual for this method to reduce the error only slightly for a number
of iterations and then find a direction that reduces the error by an order of
magnitude or more in one iteration.
It can be shown that the rate of convergence of this method depends on
the condition number n of the matrix where
and Amax and Xmi, are the largest and smallest eigenvalues of the matrix.
The condition numbers of matrices that arise in CFD problems are usually
approximately the square of the maximum number of grid points in any
direction. With 100 grid points in each direction, the condition number should
be about lo4 and the standard conjugate gradient method would converge
slowly. Although the conjugate gradient method is significantly faster than
steepest descents for a given condition number, this basic method is not very
useful.
This method can be improved by replacing the problem whose solution we
seek by another one with the same solution but a smaller condition number.
For obvious reasons, this is called preconditioning. One way to precondition
the problem is to pre-multiply the equation by another (carefully chosen) matrix. As this would destroy the symmetry of the matrix, the preconditioning
must take the following form:
The conjugate gradient method is applied to the matrix C-' AC-' i.e. to the
modified problem (5.58). If this is done and the residual form of the iterative
method is used, the following algorithm results (for a detailed derivation, see