nul. Le coefficient d’indice q du vecteur Y = AX est y q =
n
j=1 a qj x j = a qq x q +
j =q a qj x j .
Puisque le module d’une somme est inférieur ou égal à la somme des modules, on a
j =q a qj x j
j =q |a qj ||x j | |x q |
j =q |a qj | < |x q ||a qq | et la dernière inégalité est stricte
car A est à diagonale strictement dominante et |x q | | = 0. On en déduit que y q n’est pas nul.
Ainsi, pour tout vecteur X = 0, on a AX = 0 : la matrice A est donc inversible.
Proposition. La méthode de relaxation converge dans chacun des cas suivants :
a) la matrice A est à diagonale strictement dominante et 0 < ω < 1 ;
b) la matrice A est symétrique définie positive et 0 < ω < 2.
Démonstration. On a (I n − ωL)L ω = (1 − ω)I n + ωU , donc
(I n − ωL)(L ω − zI n ) = (1 − ω − z)I n + ωU + zωL
et comme I n − ωL a pour déterminant 1, le polynôme caractéristique de L ω est
P (z) = det(L ω − zI n ) = det
(1 − ω − z)I n + ωU + zωL
Supposons 0 < ω < 1 et soit z un nombre complexe tel que |z| 1. Puisque 0 < 1 − ω < 1, on
a 1 − ω − z = 0, donc P (z) = (1 − ω − z)
n det(I n + bU + aL), où l’on a posé a =
zω
1 − ω − z
et
b =
ω
1 − ω − z
. D’autre part, l’inégalité |z|(1 − ω) 1 − ω s’écrit |z|ω |z|−(1 − ω) et comme on
a |1−ω −z| |z|−(1−ω) > 0 d’après l’inégalité triangulaire, on en déduit |a| =
|zω|
|1 − ω − z|
1.
Puisque ω |zω|, il vient |b| |a| 1. Supposons que A est à diagonale strictement dominante. Alors I n + U + L est à diagonale strictement dominante (voir les matrices U et L
page 250) ; la matrice I n + bU + aL s’obtient en multipliant les coefficients non diagonaux
par des nombres de module au plus 1, donc I n + bU + aL est aussi à diagonale strictement
dominante : ainsi cette matrice est inversible, donc de déterminant non nul. Finalement, si
|z| 1, alors P (z) = 0. Cela montre que les valeurs propres de la matrice L ω sont de module
strictement inférieur à 1, donc la méthode de relaxation converge.
Supposons maintenant A symétrique définie positive et 0 < ω < 2. Posons pour simplifier
B = L ω et M = 1
ω
D − E . La matrice triangulaire M est inversible et un calcul simple montre
que l’on a M (I n − B) = A, ou encore B = I n − M
−1 A. En utilisant l’égalité
t
A = A, on vérifie
en outre la relation suivante :
(∗)
A − (
t B)AB = (I n −
t B)(M +
t M − A)(I n − B)
Puisque A est symétrique, on a
t E=F ,
t M = 1
ω
D−F et M +
t M −A= 2
ω
D−E−F −A=
2 − ω
ω
D,
car A + E + F = D. Les coefficients de D sont les produits (
t E i )AE i , donc ils sont strictement
positifs puisque A est définie positive. Il s’ensuit que la matrice diagonale Δ =
2 − ω
ω
D est définie positive, car on a 0 < ω < 2. Soit λ une valeur propre de B et X un vecteur propre associé
(puisque A est symétrique, λ est un nombre réel). On a BX = λX et (I n − B)X = (1 − λ)X .
En multipliant les différents termes de (∗) à gauche par
t X et à droite par X , on obtient
(
t X)(
t B)ABX = λ
2 (
t X)AX et (
t X)(I n −
t B)Δ(I n − B)X = (1 − λ)
2 (
t X)ΔX , d’où
(1 − λ
2 )(
t X)AX = (1 − λ)
2 (
t X)ΔX .
Remarquons que λ ne peut pas être égal à 1 : sinon on aurait X = BX = X − M
−1 AX ,
donc M
−1 AX = 0, ce qui n’est pas possible car X est non nul et les matrices M
−1 et A
sont inversibles. Ainsi on a (1 − λ)
2 > 0, (
t X)ΔX > 0 et (
t X)AX > 0, donc aussi 1 − λ
2 > 0,
c’est-à-dire −1 < λ < 1.
Chapitre 8 – DES M ´
ETHODES NUM ´
ERIQUES – 251
n
j=1 a qj x j = a qq x q +
j =q a qj x j .
Puisque le module d’une somme est inférieur ou égal à la somme des modules, on a
j =q a qj x j
j =q |a qj ||x j | |x q |
j =q |a qj | < |x q ||a qq | et la dernière inégalité est stricte
car A est à diagonale strictement dominante et |x q | | = 0. On en déduit que y q n’est pas nul.
Ainsi, pour tout vecteur X = 0, on a AX = 0 : la matrice A est donc inversible.
Proposition. La méthode de relaxation converge dans chacun des cas suivants :
a) la matrice A est à diagonale strictement dominante et 0 < ω < 1 ;
b) la matrice A est symétrique définie positive et 0 < ω < 2.
Démonstration. On a (I n − ωL)L ω = (1 − ω)I n + ωU , donc
(I n − ωL)(L ω − zI n ) = (1 − ω − z)I n + ωU + zωL
et comme I n − ωL a pour déterminant 1, le polynôme caractéristique de L ω est
P (z) = det(L ω − zI n ) = det
(1 − ω − z)I n + ωU + zωL
Supposons 0 < ω < 1 et soit z un nombre complexe tel que |z| 1. Puisque 0 < 1 − ω < 1, on
a 1 − ω − z = 0, donc P (z) = (1 − ω − z)
n det(I n + bU + aL), où l’on a posé a =
zω
1 − ω − z
et
b =
ω
1 − ω − z
. D’autre part, l’inégalité |z|(1 − ω) 1 − ω s’écrit |z|ω |z|−(1 − ω) et comme on
a |1−ω −z| |z|−(1−ω) > 0 d’après l’inégalité triangulaire, on en déduit |a| =
|zω|
|1 − ω − z|
1.
Puisque ω |zω|, il vient |b| |a| 1. Supposons que A est à diagonale strictement dominante. Alors I n + U + L est à diagonale strictement dominante (voir les matrices U et L
page 250) ; la matrice I n + bU + aL s’obtient en multipliant les coefficients non diagonaux
par des nombres de module au plus 1, donc I n + bU + aL est aussi à diagonale strictement
dominante : ainsi cette matrice est inversible, donc de déterminant non nul. Finalement, si
|z| 1, alors P (z) = 0. Cela montre que les valeurs propres de la matrice L ω sont de module
strictement inférieur à 1, donc la méthode de relaxation converge.
Supposons maintenant A symétrique définie positive et 0 < ω < 2. Posons pour simplifier
B = L ω et M = 1
ω
D − E . La matrice triangulaire M est inversible et un calcul simple montre
que l’on a M (I n − B) = A, ou encore B = I n − M
−1 A. En utilisant l’égalité
t
A = A, on vérifie
en outre la relation suivante :
(∗)
A − (
t B)AB = (I n −
t B)(M +
t M − A)(I n − B)
Puisque A est symétrique, on a
t E=F ,
t M = 1
ω
D−F et M +
t M −A= 2
ω
D−E−F −A=
2 − ω
ω
D,
car A + E + F = D. Les coefficients de D sont les produits (
t E i )AE i , donc ils sont strictement
positifs puisque A est définie positive. Il s’ensuit que la matrice diagonale Δ =
2 − ω
ω
D est définie positive, car on a 0 < ω < 2. Soit λ une valeur propre de B et X un vecteur propre associé
(puisque A est symétrique, λ est un nombre réel). On a BX = λX et (I n − B)X = (1 − λ)X .
En multipliant les différents termes de (∗) à gauche par
t X et à droite par X , on obtient
(
t X)(
t B)ABX = λ
2 (
t X)AX et (
t X)(I n −
t B)Δ(I n − B)X = (1 − λ)
2 (
t X)ΔX , d’où
(1 − λ
2 )(
t X)AX = (1 − λ)
2 (
t X)ΔX .
Remarquons que λ ne peut pas être égal à 1 : sinon on aurait X = BX = X − M
−1 AX ,
donc M
−1 AX = 0, ce qui n’est pas possible car X est non nul et les matrices M
−1 et A
sont inversibles. Ainsi on a (1 − λ)
2 > 0, (
t X)ΔX > 0 et (
t X)AX > 0, donc aussi 1 − λ
2 > 0,
c’est-à-dire −1 < λ < 1.
Chapitre 8 – DES M ´
ETHODES NUM ´
ERIQUES – 251