Numerical Methods and Optimization

70 Numerical Methods and Optimization: An Introduction

where C is an appropriately selected matrix. We are interested in a choice of

C, such that the above iteration produces a sequence {x

(k)

: k ≥ 0} such that

x

(k)

→ x

∗

,k →∞,wherex

∗

is the solution of the system, that is, Ax

∗

= b.

We have

x

(k)

− x

∗

= x

(k−1)

+ C(b − Ax

(k−1)

) − x

∗

= x

(k−1)

+ Cb − CAx

(k−1)

− x

∗

.

Replacing b with Ax

∗

in the last expression, we obtain

x

(k)

− x

∗

= x

(k−1)

+ CAx

∗

− CAx

(k−1)

− x

∗

=(I

n

− CA)(x

(k−1)

− x

∗

),

where I

n

is the n × n identity matrix. Consider a matrix norm ·

M

and a

vector norm ·

V

which are compatible, that is,

Ax

V

≤A

M

·x

V

, ∀A ∈ IR

n×n

,x∈ IR

n

.

Then the absolute error after k iterations of the scheme expressed in terms of

the norm ·

V

satisfies the following inequality:

x

(k)

−x

∗



V

= 