Page 300 - Numerical Methods for Chemical Engineering

Discretized PDEs with more than two spatial dimensions 289

that
A = W W −1 b = Ax = W W −1 x (6.156)

Then, the first update is
[0]

x [1] = x [0] + a [0] − Ax [0] + b = I − a [0] A x [0] + a b
(6.157)
[0]
[0]

x [1] = W I − a W −1 [0] + a W W −1 x
x
Consider what happens when all eigenvalues of A are equal; i.e., A has a condition number
of 1 and is isotropic, = λI. Then,
[0]
[0]

x
x [1] = W I − a λI W −1 [0] + a W(λI)W −1 x (6.158)
and as WW −1 = I,wehave
[1] [0] [0] [0]
x = 1 − a λ x + a λx (6.159)
Therefore, when = λI, the conjugate gradient and GMRES methods converge in a single
−1
iteration to the solution x with a step-size a [0] = λ , from any initial guess.
This result is the motivation behind the use of a preconditioner, a transformation of
the linear system into a related one whose condition number is closer to 1. This reduces
the number of iterations necessary for iterative methods to converge to a solution, and
is common practice in the numerical solution of BVPs. Let us choose some nonsingular
upper-triangular matrix M 2 defining a coordinate transformation,
ˆ x = M 2 x x = M −1 ˆ x (6.160)
2
We then write Ax = b as
AM −1 ˆ x = b (6.161)
2
We next define a lower-triangular matrix M 1 and a perturbation matrix P such that PA ≈
M, M = M 1 M 2 . That is, if the exact LU factorization is PA = LU, M 1 ≈ L, M 2 ≈ U.
Multiplying (6.161) by M −1 P,wehave
1
−1 −1 −1
M PAM ˆ x = M Pb (6.162)
1 2 1
Substituting for PA, this becomes
−1 −1 −1 −1 −1 −1
M PAM ˆ x = M LU M ˆ x = M L UM ˆ x = c (6.163)
1 2 1 2 1 2
where we obtain c by solving
c = M −1 Pb ⇔ M 1 c = Pb (6.164)
1
by forward substitution.
[k]
Let the current estimate of the solution to (6.163) be ˆx , and let the conjugate gradient
or GMRES update be

ˆ x [k+1] = ˆx [k] + ˆp [k] (6.165)
Now, if we indeed use the exact LU factors M 1 = L and M 2 = U, (6.163) becomes ˆx = c
and (6.165) converges in a single iteration. Of course, we cannot use the exact factors