Introduction to Computational Linear Algebra

164 Introduction to Computational Linear Algebra

Proposition 6.17 As long as r

(k)

6= 0, the Preconditioned Conjugate Gradi-

ent iterative method defines the sequence {x

(k)

}, k ≥ 0 by

x

(0)

given, (6.44)

r

(0)

= b − Ax

(0)

, (6.45)

z

(0)

= M

−1

r

(0)

, (6.46)

p

(0)

= z

(0)

, (6.47)

α

k

=

(r

(k)

)

T

z

(k)

(p

(k)

)

T

Ap

(k)

, (6.48)

x

(k+1)

= x

(k)

+ α

k

p

(k)

, (6.49)

r

(k+1)

= r

(k)

− α

k

Ap

(k)

, (6.50)

z

(k+1)

= M

−1

r

(k+1)

, (6.51)

β

k

=

(r

(k+1)

)

T

z

(k+1)

(r

(k)

)

T

z

(k)

, (6.52)

p

(k+1)

= z

(k+1)

+ β

k

p

(k)

. (6.53)

6.4.5 Memory and CPU Requirements in PCG

Each iteration requires a fixed number of vector operations. The most expen-

sive operations are the matrix-vector product and solving the preconditioning

system. The total ...