Introduction to Computational Linear Algebra

154 Introduction to Computational Linear Algebra

where q

k

(X) = 1 − Xs

k−1

(X).

e

(k)

= A

−1

r

(k)

= A

−1

q

k

(A)r

(0)

= q

k

(A)A

−1

r

(0)

= q

k

(A)e

(0)

.

In order to define the iterates, the subspace condition can be written at least

in two different ways.

First, it is equivalent to

x

(k+1)

= x

(k)

+ α

k

p

(k)

, k ≥ 0, α

k

∈ R, p

(k)

∈ K

k+1

(A, r

(0)

), (6.10)

giving a recurrence relation between two consecutive iterates. The residuals

satisfy also a recurrence

r

(k+1)

= r

(k)

− α

k

Ap

(k)

. (6.11)

The method must define the coefficient α

k

and the descent direction p

(k)

.

Second, the subspace condition is equivalent to

x

(k)

= x

(0)

+ V

k

y

(k)

, y

(k)

∈ R

k

, (6.12)

where V

k

is a basis of K

k

(A, r

(0)

). The residuals