Algorithme de passage de X (k) à X (k+1)
La programmation est très simple :
initialisation : [x 1 , x 2 , . . . , x n ] ← X
(k)
boucle : pour i de 1 à n, faire
⎡
⎢
⎣
s ← 0
pour j de 1 à n, faire s ← s + a ij x j
r ← b i − s
x i ← x i + ωr/a ii
fin : X
(k+1)
← [x 1 , x 2 , . . . , x n ]
Test d'arrêt
Pour tout k, on calcule le « résidu » r
(k) = B − AX
(k) et l’on s’arrête si
r
(k)
B
< ε , où ε est une précision choisie.
Notons e
(k) = X − X
(k) l’erreur commise en s’arrêtant à la k-ième itération.
On a AX = B et AX
(k) = B − r
(k) , donc Ae
(k) = AX − AX
(k) = r
(k) et e
(k)
=
A
−1 r
(k)
A
−1
r
(k)
.
Après un test d’arrêt positif, on a e
(k)
εA
−1
B εA
−1
AX. Pour l’erreur
relative, il vient donc la majoration
e
(k)
X
ε cond(A)
La matrice d'itération
Nous allons voir que les vecteurs X
(k) sont les itérés de X
(0) par une transformation
affine de la forme X → L ω X + K , où L ω est une certaine matrice ne dépendant
que de A et de ω. Décomposons la matrice A en trois matrices D, E , F :
® la matrice D est la matrice diagonale diag(a 11 ,a 22 ,. . .,a nn ) formée des coefficients
diagonaux de A (supposés tous non nuls) ;
® la matrice (−E) est la partie triangulaire strictement en dessous de la diagonale ;
® la matrice (−F ) est la partie triangulaire strictement au dessus de la diagonale.
A =
⎡
⎢
⎣
. . .
−F
D
−E
. . .
⎤
⎥
⎦
La formule (1) s’écrit X
(k+1) = X
(k) + ωD
−1
B + EX
(k+1) + (F − D)X
(k)
, ou encore
(I n − ωD
−1 E)X
(k+1) =
(1 − ω)I n + ωD
−1 F
X
(k) + ωD
−1 B
Chapitre 8 – DES M ´
ETHODES NUM ´
ERIQUES – 249