Page 167 - Matrices theory and applications

9. Iterative Methods for Linear Problems
150
where k< 1 whenever the method converges. Typically, a dozen iterations
give a rather good result, and then O(10a) O(n ). another advantage of
the iterative methods is that the round-off errors are damped during the
computation, instead of being amplified.
General principle: Choose a decomposition of A of the form M − N and
rewrite the system, assuming that M is invertible:
x = M −1 (Nx + b). 3
n
0
Then choosingastartingvector x ∈ K , which may be a rather coarse
m
approximation of the solution, one constructs a sequence (x ) m∈IN by
induction:
m
x m+1 = M −1 (Nx + b). (9.1)
In practice, one does not compute M −1 explicitly but one solves the linear
systems Mx m+1 = ··· . It is thus important that this resolution be cheap.
This will be the case when M is triangular. In that case, the invertibility of
M can be read from its diagonal, since it occurs precisely when the diagonal
entries are nonzero.
9.1 A Convergence Criterion
Definition 9.1.1 Let us assume that A and M are invertible, A = M −N.
0
We say that an iterative method is convergent if for every pair (x ,b) ∈
n
n
K × K , we have
lim x m = A −1 b.
m→+∞
Proposition 9.1.1 An iterative method is convergent if and only if
ρ(M −1 N) < 1.
Proof
If the method is convergent, then for b =0,
m 0
lim (M −1 N) x =0,
m→+∞
0
n
for every x ∈ K .In other words,
lim (M −1 N) m =0.
m→+∞
From Corollary 4.4.1, this implies ρ(M −1 N) < 1.
Conversely, if ρ(M −1 N) < 1, then by Proposition 4.4.1,

lim (M −1 N) m =0,
m→+∞
and hence
m
m
0
x − A −1 b =(M −1 N) (x − A −1 b) → 0.