Introduction to Computational Linear Algebra

Iterative Methods for Systems of Linear Equations 159

In other words, φ(x

(k)

) = min

y∈{x

(0)

+K

k

(A,r

(0)

)}

φ(y), or equivalently

ke

(k)

k

A

= min

y∈{x

(0)

+K

k

(A,r

(0)

)}

ky − xk

A

. (6.32)

This minimization property is equivalent to an orthogonality condition.

Proposition 6.10 In the Conjugate Gradient method, the residuals satisfy

(r

(k)

)

T

v = 0, ∀v ∈ K

k

(A, r

(0)

). (6.33)

Proof. We simply apply Proposition 6.4.

This condition defines both the scalar α

k

and the descent direction p

(k)

.

6.4.1 Krylov Basis Properties

The orthogonality conditions imply that the residuals form an orthogonal

basis of the Krylov subspace, provided they are non-zero. If a residual is zero,

then the ...