En posant
L=D
−1 E=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
0
−a 21
a 22
. . .
0
−a 31
a 33
−a 32
a 33
. . .
. . .
. . .
−a n1
a nn
−a n2
a nn
· · ·
−a n n−1
a nn
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
et U=D
−1 F=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
0
−a 12
a 11
−a 13
a 11
· · ·
−a 1n
a 11
. . .
−a 23
a 22
· · ·
−a 2n
a 22
. . .
. . .
0
. . .
−a n−1 n
a n−1 n−1
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,
il vient (I n − ωL)X
(k+1) =
(1 − ω)I n + ωU
X
(k) + ωD
−1 B. La matrice triangulaire
I n − ωL est inversible, car ses coefficients diagonaux sont tous égaux à 1. On a donc
X
(k+1) = (I n − ωL)
−1
(1 − ω)I n + ωU
X
(k) + ω(I n − ωL)
−1 D
−1 B
et en posant L ω = (I n −ωL)
−1
(1−ω)I n +ωU
et K = ω(I n −ωL)
−1 D
−1 B, on obtient
(2)
X
(k+1) = L ω X
(k) + K , pour tout entier k 0.
La solution de l’équation linéaire AX = B est le point fixe de cette transformation.
D’après le corollaire page 185, on en déduit :
pour que la suite de X
(k) converge quel que soit le vecteur initial X 0 ,
il faut et il suffit que la matrice d’itération L ω ait toutes ses valeurs
propres (réelles ou complexes) de module strictement inférieur à 1.
On a (I n − ωL)L ω = (1 − ω)I n + ωU et la matrice triangulaire I n − ωL a pour déterminant 1, donc det L ω = det
(1 − ω)I n + ωU
= (1 − ω)
n . On sait que le déterminant
d’une matrice est le produit de toutes les valeurs propres réelles ou complexes. Si les
valeurs propres de L ω sont de module inférieur à 1, alors en faisant leur produit, il
vient |1 − ω|
n < 1, donc |1 − ω| < 1 ; puisque nous avons pris ω réel, cela implique que
ω est strictement compris entre 0 et 2. La condition 0 < ω < 2 est n´ ecessaire pour que
la m´ ethode de relaxation converge quel que soit le vecteur initial X 0 .
Des conditions suffisantes de convergence
Dans les applications, la matrice A est souvent bien particulière, par exemple symétrique ou tridiagonale (voir page 142) ; il est également fréquent que les coefficients
diagonaux soient prépondérants au sens de la définition suivante.
Définition
Une matrice carrée A = [a ij ] est à diagonale strictement dominante si le module de
chaque coefficient diagonal est strictement supérieur à la somme des modules des
autres coefficients situés sur la même ligne : pour tout i, |a ii | >
j =i |a ij |.
Proposition. Toute matrice carrée à diagonale strictement dominante est inversible.
Démonstration. Soit A=[a ij ] une matrice carrée de taille n à diagonale strictement dominante
et soit X un vecteur-colonne non nul, de coefficients x 1 , x 2 , . . . , x n . Choisissons un coefficient
x q de module maximum : |x q ||x j | pour tout j . Puisque X n’est pas le vecteur nul, x q est non
250 – R ´
ESOLUTION D’ ´
EQUATIONS LIN ´
EAIRES
L=D
−1 E=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
0
−a 21
a 22
. . .
0
−a 31
a 33
−a 32
a 33
. . .
. . .
. . .
−a n1
a nn
−a n2
a nn
· · ·
−a n n−1
a nn
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
et U=D
−1 F=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
0
−a 12
a 11
−a 13
a 11
· · ·
−a 1n
a 11
. . .
−a 23
a 22
· · ·
−a 2n
a 22
. . .
. . .
0
. . .
−a n−1 n
a n−1 n−1
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,
il vient (I n − ωL)X
(k+1) =
(1 − ω)I n + ωU
X
(k) + ωD
−1 B. La matrice triangulaire
I n − ωL est inversible, car ses coefficients diagonaux sont tous égaux à 1. On a donc
X
(k+1) = (I n − ωL)
−1
(1 − ω)I n + ωU
X
(k) + ω(I n − ωL)
−1 D
−1 B
et en posant L ω = (I n −ωL)
−1
(1−ω)I n +ωU
et K = ω(I n −ωL)
−1 D
−1 B, on obtient
(2)
X
(k+1) = L ω X
(k) + K , pour tout entier k 0.
La solution de l’équation linéaire AX = B est le point fixe de cette transformation.
D’après le corollaire page 185, on en déduit :
pour que la suite de X
(k) converge quel que soit le vecteur initial X 0 ,
il faut et il suffit que la matrice d’itération L ω ait toutes ses valeurs
propres (réelles ou complexes) de module strictement inférieur à 1.
On a (I n − ωL)L ω = (1 − ω)I n + ωU et la matrice triangulaire I n − ωL a pour déterminant 1, donc det L ω = det
(1 − ω)I n + ωU
= (1 − ω)
n . On sait que le déterminant
d’une matrice est le produit de toutes les valeurs propres réelles ou complexes. Si les
valeurs propres de L ω sont de module inférieur à 1, alors en faisant leur produit, il
vient |1 − ω|
n < 1, donc |1 − ω| < 1 ; puisque nous avons pris ω réel, cela implique que
ω est strictement compris entre 0 et 2. La condition 0 < ω < 2 est n´ ecessaire pour que
la m´ ethode de relaxation converge quel que soit le vecteur initial X 0 .
Des conditions suffisantes de convergence
Dans les applications, la matrice A est souvent bien particulière, par exemple symétrique ou tridiagonale (voir page 142) ; il est également fréquent que les coefficients
diagonaux soient prépondérants au sens de la définition suivante.
Définition
Une matrice carrée A = [a ij ] est à diagonale strictement dominante si le module de
chaque coefficient diagonal est strictement supérieur à la somme des modules des
autres coefficients situés sur la même ligne : pour tout i, |a ii | >
j =i |a ij |.
Proposition. Toute matrice carrée à diagonale strictement dominante est inversible.
Démonstration. Soit A=[a ij ] une matrice carrée de taille n à diagonale strictement dominante
et soit X un vecteur-colonne non nul, de coefficients x 1 , x 2 , . . . , x n . Choisissons un coefficient
x q de module maximum : |x q ||x j | pour tout j . Puisque X n’est pas le vecteur nul, x q est non
250 – R ´
ESOLUTION D’ ´
EQUATIONS LIN ´
EAIRES