Chapitre 1

Résolution d’équations non linéaires

1
Chapitre 2
Résolution de systèmes linéaires

2.1 Introduction
Un système linéaire est la donnée de n équations à m inconnues du type

 a11 x1 + a12 x2 + . . . + a1m xm = b1 ,

..
 .
 a x + a x + ... + a x = b , .
n1 1 n2 2 nm m n

Les inconnues ici sont x1 , x2 , . . . , xm . Sous forme matricielle, ce système s’écrit

Ax = b (2.1)
où
     
x1 b1 a11 a12 · · · a1m
 x2 
m
 b2 
n
 a21 a22 · · · a2m 
x= ∈ , b = ∈ , A =  ∈ Mnm (K)
     
..  K  ..  K  .. .. .. ..
 .   .   . . . . 
xm bn an1 an2 · · · anm
trois cas se présentent :
1. si n < m, il y a moins d’équations que d’inconnues. Le système est sous-déterminé.
L”ensemble des solutions est un sous espace affine.
2. si n > m, il y a plus d’équations que des inconnues. Le système est sur-déterminé.
3. si n = m il y a exactement le même nombre d’équations que d’inconnues. Dans la suite nous
nous considérons ces systèmes carrés.
Dans ce cas, le système (2.1) admet une unique solution x pour tout b ∈ Kn si et seulement si
A ∈ Mnn (K) est inversible. et cette solution est
x = A−1 b. (2.2)

2.2 Solution théorique

On peut mettre (2.2) sous la forme
com(A) com(A)
x= b, car A−1 = ,
det(A) det(A)

2
où com(A) est la comatrice de A donnée par com(A) = (cof A)t telle que cof A = [Aij ](n × n) (
matrice des cofacteurs de A ) avec Aij = (−1)i+j det(aij ) ; aij étant une sous-matrice déduite de la
matrice A par supression de la iime ligne et la jime colonne. Ceci constitue une méthode très
inefficaces car il y a plus de calculs que nécessaires.
De façon générale on distingue deux types de méthodes : les méthodes directes et les méthodes
itératives.

2.3 Méthodes directes

ces méthodes conduisent à un système équivalent au système initial en un nombre fini d’étapes mais
plus facile à résoudre, généralement on se ramène à un système diagonal ou triangulaire, ces
méthodes conduisent à la solution exacte (aux erreurs d’arrondi près). Cependant, elles ne sont
applicables que lorsque n < 50 environ.

2.3.1 Structure de la matrice

a) Matrices diagonales
Si tous les éléments de la matrice A sont nuls sauf ceux de la diagonale principale, la résolution du
système (2.1) est alors immédiate. si x = (x1 , x2 , · · · , xn ) et b = (b1 , b2 , · · · , bn ) on a xi = abiii ,
pour tout 1 ≤ i ≤ n.
b) Matrices triangulaires supérieure (ou inférieure)
Tous les éléments en dessous (ou au dessus) de la diagonale sont nuls
 
a11 a12 · · · a1n
 0 a22 · · · a2n 
A =  ..
 
.. .. .. 
 . . . . 
0 0 · · · ann

Dans ce cas, on utilisera toujours une méthode directe de résolution par remonté, soit


 a11 x1 + a12 x2 + . . . + a1n xn = b1 ,
 a22 x2 + . . . + a2n xn = b2 ,



..
 .



 an−1,n−1 xn−1 + an−1,n xn = bn−1 ,
 a x =b , .
nn n n

On commence par résoudre la dernière équation, puis on substitue le résultat obtenu pour xn dans la
précédente ce qui permet de calculer xn−1 , et on suit la même procédure jusqu’à obtenir x1 .

xn = abnn

 n
,
bn−1 −an−1,n xn

x = an−1,n−1 ,


 n−1


..
.
 b −a x −a x −···−ai,i+1 xi+1


 xi = i in n i,n−1 an−1 ii
 ..


.

Le cas des matrices triangulaires inférieures de traite de façon identique par un procédé de descente.

3
2.3.2 Méthode d’élimination de Gauss

La méthode d’élimination de Gauss a pour but de transformer le système Ax = b par un système

équivalent de la forme U x = b̂ où U est une matrice triangulaire supérieure et b̂ est un second
membre convenablement modifié.
(k)
La méthode comporte (n − 1) étapes. On notera aij l’élément aij à l’étape k :
Étape 1 : On transforme A en une matrice dont les termes sous diagonaux de la première colonne
sont nuls.
– Pour éliminer le terme a21 on multiplie la ligne l1 par −a 21
a11

(1) −a21
l2 ← l2 + l1
a11
on obtient ainsi
(1) a21
a2j = a2j − a1j
a11
(1) −a21
b2 = b2 + b1
a11
– D’une manière générale pour éliminer tout les termes ai1 on utilise la transformation
(1) −ai1
li ← li + li
a11
on obtient ainsi
(1) ai1
aij = aij − aij
a11
(1) −ai1
bi = bi + bi
a11
À la fin de la première étape, le système d’équations aura la forme suivante :
    
a11 a12 · · · a1n x1 b1
 0 a(1) · · · a(1)   x2   b(1) 
22 2n     2 
..   ..  =  ..  .

 .. .. ...
 . . .   .   . 
(1) (1) (1)
0 an2 · · · ann xn bn

Étape k : En continuant de la même façon que l’étape 1, à l’étape k, nous éliminons les termes
sous-diagonaux de la kime colonne
(k−1)
(k) (k−1) ak+1,k (k−1)
lk+1 ← lk+1 − l
(k−1) k
akk
on obtient ainsi
(k−1)
(k) (k−1) ak+1,k (k−1)
ak+1,j = ak+1,j − a
(k−1) kj
akk
(k−1)
(k) (k−1) ak+1,k (k−1)
bk+1 = bk+1 − b
(k−1) k
akk
À la fin de la dernière étape, on obtient alors le système triangulaire supérieur suivant :
 (1) (1) (1)     (1) 
a11 a12 · · · a1n x1 b1
 0 a(2) · · · a(2)   x2   b(2) 
22 2n   2 
  ..  =  .  .
 
 . .. .. ..
 .. . . .   .   .. 
(n−1) xn (n−1)
0 · · · · · · ann bn

4
 (k)
Remarque 2.3.1. Les opérations précédentes supposent que les termes akk appelés pivots sont non
nuls.
Exemple 2.3.1. Soit le système d’équations représenté par la matrice augmentée suivante
 
2 1 2 10
 6 4 0 26 
8 5 1 35
l2 ← l2 − 26 l1


l3 ← l3 − 28 l1
 
2 1 2 10
 0 1 −6 −4 
0 1 −7 −5
1
l3 ← l3 − l2
 1 
2 1 2 10
 0 1 −6 −4 
0 0 −1 −1
la solution du système est x = (1, 2, 3), (il suffit de faire une remontée pour obtenir la solution)
Remarque 2.3.2. Dans la méthode de Gauss, il y a deux cas qui se présentent
1. Si un pivot est nul on permutera l’équation correspondante avec l’une de ses suivantes (
permutation de 2 lignes ), donc pour i = k + 1, n, de manière à mettre un pivot non nul en
position k.
(k)
aik
2. Si le pivot de valeur proche de zéro c’est-à-dire pivot très petit, les quantités (k) deviennent
akk
plus grandes que 1 et peut conduire à des erreurs très importantes ; dans ce cas il y peut y
avoir perte de précision, et on adopte généralement une stratégie du pivot :
Pivot partiel : On intervertit les lignes à chaque étape de façon à placer en pivot le terme de
coefficient le plus élevé de la ligne. C’est la méthode du pivot partiel, à la kime étape, le pivot est
l’élément :
(k) (k)
ai,k = max |ap,k |
k≤p≤n

Pivot total : On intervertit les lignes et les colonnes de façon à placer en pivot le terme de coefficient
le plus élevé de la matrice. C’est la méthode du pivot total, à la kime étape, le pivot est l’élément
(k)
 
a = max a(k)
i,j p,q

p,q=k,...,n
     
1 3 3 x1 0
Exemple 2.3.2. 1. Soient A =  1 1 0  , x =  x2  , et b =  1 
3 2 6 x3 11
k = 1 : max(1, 1, 3) = 3 on permute, par exemple, les lignes 1 et 3 on obtient
.. ..
   
[3] 2 6 . 11 3 2 6 . 11
 1 1 0 ... 1  →  0 1 −2 ... −8 
   
   3 3 
.. 7 .. −11
1 3 3 . 0 0 3 1 . 3
k = 2 : max 13 , 73 = 37 . On permute les lignes 2 et 3.

.. ..
   
3 2 6 . 11 3 2 6 . 11
 0 7 1 ... −11  →  0 7 1 ... −11 
   
 3 3   3 3 
. .
0 31 −2 .. −8 3
0 0 −15
7
.. −15
7

5
 II s’ensuit que :
 
 x3 = 1  x3 = 1
3 −11
Ax = b ⇔ x2 = 7 ( 3 − x3 ) ⇔ x2 = −2
x1 = 31 (11 − 2x2 − 6x3 ) x1 = 3
 

 x1 + 3x2 + 3x3 = −2
2. Soit le système 2x1 + 2x2 + 5x3 = 7 Posons :
3x1 + 2x2 + 6x2 = 12


..
 
1 3 3 . −2

(A : b) =  .. 
 2 2 5 . 7 
..
3 2 6 . 12
  
 (1) 
k = 1 : max ai,j  , i = 1, 2, 3 j = 1, 2, 3 = 6. La ligne du pivot total sera alors L3 . En
permutant les lignes 1 et 3 on obtient :
..
 
3 2 6 . 12
 2 2 5 ... 7 
 
 
..
1 3 3 . −2
La colonne du pivot total est la colonne 3, et on permute les colonnes 1 et 3 :
.. ..
   
6 2 3 . 12 6 2 3 . 12
 5 2 2 .. 7  →  0 1 −1 ... −3 
.
   
   2 2 
.. .
.. −8
3 3 1 . −2 0 2 −1 2
  
 (2) 
k = 2 : max ai,j  , i = 2, 3 j = 2, 3 = 2.
La ligne du pivot total est alors L3 . En permutant les lignes 2 et 3
. .
   
6 2 3 .. 12 6 2 3 .. 12
 0 2 −1 ... −8  →  0 2 −1 ... −8 
   
 2   2 
1 −1 .. −5 .. −5
0 2 2 . −3 0 0 12 . 3
Du fait de la permutation précédente des colonnes 1 et 3 on obtient le système équivalent
suivant :  
 6x3 + 2x2 + 3x1 = 12  x3 = 1
1
2x2 − 2 x1 = −8 ⇔ x2 = −3
5
− 12 x1 = −5 x 1 = 4
 
3
Remarque 2.3.3. Notons bien à chaque permutation de colonnes les inconnues changent de places.

2.3.3 Factorisation LU

Le principe de cette méthode est de se ramener à deux systèmes triangulaires, on suit les étapes
suivantes :
1. On décompose la matrice A en produit de deux matrices A = LU où U est triangulaire
supérieure, et L est triangulaire inférieure avec des 1 sur la diagonale. On va alors résoudre le
système LU x = b.

6
 2. On résout le système triangulaire Ly = b d’inconnue y.
3. On résout le système triangulaire U x = y d’inconnue x.
Reste maintenant à savoir comment faire cette décomposition LU.
Supposons que dans l’élimination de Gauss on n’utilise aucune stratégie de pivotage et que tous les
(k)
pivots ak,k 6= 0.
Dans ce cas le passage de A(k) → A(k+1) (1 ≤ k ≤ n − 1) revient à multiplier à gauche la matrice
A(k) par la matrice de taille n × n :

1 0 ··· ··· ··· ··· 0

 
.

 0 1 0 ··· · · · · · · .. 
 .. . . ... 

 . . 0 ··· 

E (k)
=
 .. 
. 0 1 ··· ··· 0 
.. .. .. .. 
 

 . . −lk+1,k . . 
 .. .. .. . . .. 
 . . . 0 . . 
0 ··· 0 −ln,k 0 ··· 1
(k)
ai,k
avec li,k = (k) , pour k + 1 ≤ i ≤ n. La matrice A(n−1) , qui est triangulaire supérieure, est alors égale
ak,k
à A(n−1) = M A, avec M = E (n−1) E (n−2) . . . E (1) M est le produit de matrices triangulaires
N
Y −1
det E (i) = 1 et l’inverse


inférieures, donc M est aussi triangulaire inférieure, on a det(M ) =
i=1
de M est aussi triangulaire inférieure.
En posant U = A(n−1) et L = M −1 , on a A = LU .

1 0 ··· ··· ··· ···

0
 
.

 0 1 0 ··· · · · · · · ..  
 .. . . .. 

 . . . 0 ··· 

(E (k) −1
) =
 .. 
. 0 1 ··· ··· 0 
.. .. ... .. 
 
. . lk+1,k . 


 .. .. .. . . . .. 
 . . . 0 . 
0 ··· 0 ln,k 0 ··· 1

L = M −1 = (E (1) )−1 (E (2) )−1 . . . (E (n−2) )−1 (E (n−1) )−1

1 0 ··· ··· ··· ··· 0

 
.. 

 l2,1 1 0 ··· ··· ··· . 
 .. ... ... 

 . 0 ··· 

L=
 .. ... 
. 1 ··· ··· 0 
.. .. ... .. 
 
. . lk+1,k . 


 .. .. .. .. .. 
 . . . . . 
ln,1 · · · ··· ln,k ··· ln,n−1 1
 
5 2 1
Exemple 2.3.3. Considérons la matrice A =  5 −6 2  = A(0)
−4 2 1

7
    
1 0 0 5 2 1
E (1) =  −1 1 0  ; A(1) =  0 −8 1 
4 18 9
 5 0 1  0 5 5  
1 0 0 5 2 1 1 0 0
E (2) =  0 1 0  ; A(2) =  0 −8 1  = U L =  1 1 0  et A = LU
9 −4 −9
0 20 1 0 0 94 5 20
1
Théorème 2.3.1. Soit A = (ai,j )1≤i,j≤n une matrice carrée d’orde n telle que les n sous-matrices de
A soient inversibles, alors il existe une matrice triangulaire inférieure L = (li,j )1≤i,j≤n , avec
li,i = 1(1 ≤ i ≤ N ), et une matrice triangulaire supérieure U telle que A = LU. De plus cette
factorisation est unique.

Preuve. la preuve se fait par récurrence sur n.

2.3.4 Matrice symétrique définie positive : Méthode de Cholesky

Dans le cas d’une matrice A symétrique définie positive, il est possible de résoudre le système
Ax = b avec un nombre d’opérations égal presque la moitié du nombre d’opérations utilisées dans la
méthode de Gauss.
Théorème 2.3.2. Une matrice A est symétrique définie positive si, et seulement si, il existe une
matrice triangulaire inférieure inversible R telle que : A = RRT . De plus si on impose que les
éléments diagonaux de R, rii > 0, 1 ≤ i ≤ n, cette décomposition est unique.

Preuve. Dans le cas où la matrice A est symétrique définie positive, la condition du théorème 
1 0 ··· 0

.. 
 l2,1 1 0 . 

précédent est satisfaite et elle admet une factorisation A = LU , avec L =  . .  et
 .. .. 0 
ln,1 ln,n−1 1
u1,1 · · · u1,n
 
... .. 
 0 . 

U = . ..  Comme la matrice A est définie positive, on a
 .. . 
0 0 un,n
Qk
t=1 ui,i = ∆k > 0, k = 1, 2, . . . , n (les
 √k
∆ sont les mineurs principaux dominants de A ) et ui,i > 0,
u1,1 0 · · · 0

..
 0 ··· .
 
pour i = 1, 2, . . . , n. Si on pose D =  .  . Cette matrice est inversible et son

 .. 0 
√
0 0 un,n
inverse est  1 
√
u1,1
0··· 0
 .. .. 
−1
 0 . . 
D =  ..


 . 0 
1
0 0 √
un,n

A = LU = (LD) (D−1 U ) = RB T La matrice R = LD est triangulaire inférieure et B T = D−1 U est

triangulaire supérieure et elles sont toutes les deux inversibles. Comme A est symétrique, on a

−1
AT = A. =⇒ RB T = BRT =⇒ B −1 R = RT B T De plus B −1 R est une matrice triangulaire

−1
inférieure et RT B T eat une matrice triangulaire supérieure, ce qui implique que

8

−1
B −1 R = RT B T est une matrice diagonale. Or les éléments diagonaux : (B −1 R)i,i = 1

−1
=⇒ B −1 R = RT B T = In =⇒ B = R et A = RRT .
√
Comme R = LD = (ri,j ) =⇒ ri,i = ui,i > 0, pour 1 ≤ i ≤ n.
Unicité de R : Supposons que A = RRT = BB T , avec R = (ri,j ) et B = (bi,j ) des matrices
triangulaires inférieures avec des éléments diagonaux rii > 0 et bi,i > 0, pour 1 ≤ i ≤ n

−1
−1
RRT = BB T =⇒ RT B T = R−1 B =⇒ RT B T = R−1 B = D matrice diagonale, et
ri,i bi,i 2 b
bi,i
= ri,i =⇒ ri,i = b2i,i , 1 ≤ i ≤ n =⇒ ri,i = bi,i , 1 ≤ i ≤ n et alors dii = ri,i
i,i
= 1, 1 ≤ i ≤ n et
R=B
Remarque 2.3.4. Il y a deux applications de la factorisation de Cholesky :
– Résoudre le système linéaire Ax = b se ramène à résoudre successivement les 2 systèmes linéaires
à matrices triangulaires : 
Ry = b
Ax = b ⇐⇒
RT x = y
– Calcul du déterminant de A : det(A) = ( ni=1 ri,i )2 .
Q

Calcul effectif de la matrice R : A = RRT , R = (ri,j ) =⇒ ai,j = ik=1 ri,k rj,k pour 1 ≤ i, j ≤ n
P
i = 1 on détermine la 1ère colonne de R :
2 √
→ j = 1 : a1,1 = r1,1 =⇒ r1,1 = a1,1
→ j = 2 : a1,2 = r1,1 r2,1 =⇒ r2,1 = ar1,1 1,2
;
..
.
→ j = n : a1,n = r1,1 rn,1 =⇒ rn,1 = ar1,n 1,1
;
ème
De proche en proche, on détermine la i colonne de R (i = 2, . . . , n) :
2 2
→ j = i : ai,i = ri,1 + . . . + ri,i
q
2 2
=⇒ ri,i = ai,i − (ri,1 + . . . + ri,i−1 );
→ j = i + 1 : ai,i+1 = ri,1 ri+1,1 + . . . + ri,i ri+1,i
a −(r r +...+r r )
=⇒ ri+1,i = i,i+1 i,1 i+1,1ri,i i,i−1 i+1,i−1 ;
..
.
→ j = n : ai,n = ri,1 ri,n + . . . + ri,i rn,i
a −(r r +...+r r )
=⇒ rn,i = i,n i,1 n,1 ri,i i,i−1 n,i−1 ;
1 21 13
 

Exemple 2.3.4. A =  12 13 14  ; la factorisation de Cholesky de A :

1 1 1
 3 4 5
1 0 0 1 √21 1
 
√ √3
A =  21 √63 √0   0 63 3  = RRT .
√6
1 3 5 5
3 6 30
0 0 30
√ √ 2
- det(A) = 63 305 = 2160
1
.
 
1 √ √
- Pour résoudre Ax = b; avec b =  1 , Ry = b =⇒ y1 = 1, y2 = 3 et y3 = 5
  1
3
RT x = y =⇒ x =  −24 
30

9
2.4 Méthodes itératives

2.4.1 Quelques rappels sur les matrices

Soit A = (aij )1≤i,j≤n une matrice carrée.

1. A est dite à diagonale strictement dominante en colonnes si elle vérifie :
i=n
X
|aij | < |ajj | , 1 ≤ j ≤ n
i=1,i6=j

2. A est dite à diagonale strictement dominante en lignes si elle vérifie :

j=n
X
|aij | < |aii | , 1 ≤ i ≤ n
j=1,j6=i

3. Une norme matricielle k.k vérifie les 4 propriétés suivantes :

– i) kAk = 0 ⇔ A = 0
– ii) kλAk = |λ|kAk pour tout λ ∈ R
– iii) kA + Bk ≤ kAk + kBk
– iv) kABk ≤ kAkkBk
4. (I + B) est inversible si kBk < 1 et de plus k(I + B)−1 k ≤ 1
1−kBk
i=n
X
j=n
5. kAk∞ = max Σj=1 |aij | ; kAk1 = max |aij |
1≤i≤n 1≤j≤n
i=1
ρ(A) = max |λi (A)| est dit rayon spectrale (λi (A) : valeur propore de A)
1≤j≤n

2.4.2 Méthodes classiques(Jacobi, Gauss Seidel, Relaxation)

Pour résoudre le système

Ax = b (2.3)
on utilise des méthodes itératives, du type

x(k+1) = T x(k) + C (2.4)

où T est une matrice obtenue à partir de A et c un vecteur dépendant de A et b. On écrit A sous la

forme A = M − N En supposant M inversible, l’équation (2.3) donne : x = M −1 Nx + M−1 b et ceci
suggère le procédé itératif du type (2.4) avec T = M −1 N et C = M −1 b. Il ya plusieurs façons
d’écrire A sous la forme A = M − N Dans le cadre de  ce cours on se limitera aux cas les plus
..

. −U
utilisés à partir de : A = D − L − U, on a alors A =  D
 

...
−L
– Méthode de Jacobi : M = D, N = L + U.
– Méthode de Gauss-Seidel : M = D − L, N = U.
– Méthode de relaxation : A = A(ω) = M (ω) − N (ω), avec M (x) = ω1 D − L, N (ω) = 1−ω ω
D−U
où ω est un scalaire.

10
Définition 2.4.1. Une méthode de type (2.4) est dite convergente si pour tout x(0) initial on a :

lim x(k) = x.
k→∞

Si une telle limite existe, alors elle vérifie :

x = Tx + c

Définition 2.4.2. On appelle erreur de la méthode (à la k ième itération) la quantité :

e(k) = x(k) − x

Avec e(0) = x(0) − x on obtient e(k) = T k e(0) la méthode est convergente si lim T k = 0
k→∞

Méthode de Jacobi :
Si A = (aij ) la méthode de Jacobi consiste à choisir ; M = D = diag (aii ) et
N = L + U = (−aij )i,6=j , le schéma itératif est comme suit :

x(k+1) = D−1 (L + U )x(k) + D−1 b = TJ x(k) + c.

La matrice TJ = D−1 (L + U ) est dite matrice de Jacobi associée à A. Si x(0) est le vecteur initial
donné, l’algorithme de Jacobi est de la forme :
j=n
(k+1) 1 X (k) bi
xi =− aij xj + ; i = 1, · · · , n
aii j=1,j6=i aii

Explicitement, on obtient :
(k+1) (k)
a11 x1 = −a12 x2 − · · · − a1n x(k)
n + b1
.... ..
.. .
(k) (k)
ann x(k+1)
n = −an1 x1 − · · · − ann−1 xn−1 + bn .

Une condition suffisante pour que la méthode de Jacobi converge est : ρ(TJ ) < 1 ou kTJ k∞ < 1.
Méthode de Gauss-Seidel :
Pour cette méthode, les matrices M et N sont données par : M = D − L (supposé inversible) et
N = U où D, L et U proviennent de l’écriture A = D − L − U , le schéma itératif est comme suit :

(D − L)x(k+1) = U x(k) + b (2.5)

ou encore
x(k+1) = (D − L)−1 U x(k) + (D − L)−1 b (2.6)
en explicitant (2.5) on obtient :
(k+1) (k)
a11 x1 = −a12 x2 − · · · − a1n x(k)
n + b1
(k+1) (k+1) (k)
a22 x2 = −a21 x1 − a23 x3 − · · · − a2n x(k)
n + b2
....
..
(k+1) (k+1) (k+1) (k)
aii xi = −ai1 x1 · · · − aii−1 xi−1 − aii+1 xi+1 − · · · − ain x(k)
n + b2
.... ..
.. .
(k+1) (k+1)
ann x(k+1)
n = −an1 x1 − · · · − ann−1 xn−1 + bn

La matrice TGS = (D − L)−1 U est dite matrice de Gauss-Seidel associée à A.

11
Théorème 2.4.1. Si A est une matrice carrée a diagonale strictement dominante en lignes alors la
méthode de Jacobi converge

Preuve. Si A est une matrice carrée à diagonale strictement dominante en lignes alors on a :
j=n
X
|aij | < |aii | , 1 ≤ i ≤ n,
j=1,j6=i
j=n
1 X 
−a

ou encore : |aij | < 1, 1 ≤ i ≤ n. Par ailleurs TJ = D−1 (L + U ) = (tij ) avec tij = aiiij
|aii | j=1,j6=i
si i 6= j et tii = 0
j=n j=n
X 1 X
kTJ k∞ = max |tij | = max |aij | < 1
1≤i≤n 1≤i≤n |aii |
j=1 j=1,j6=i

Application :
Montrer un nésultat analogue avec preuve similaire si A est strictement dominante en colonnes.
Théorème 2.4.2. Si A est une matrice carrée a diagonale strictement dominante en lignes alors la
méthode de Gauss-Seidel converge.

Preuve. on montre que kTGS k∞ = k(D − L)−1 U k∞ < 1 en passant par :

kT xk∞
kT k∞ = max
x6=0 kxk∞

On pose y = T x = (D − L)−1 U x
qui donne (D − L)y = U x et Dy = Ly + U x
ou encore y = D−1 Ly + D−1 U x. Soit k l’indice tel que |yk | = max1≤i≤n |yi | = kyk∞ = kT xk∞ .
j=k−1 j=n
X X
−1
D−1 U kj xj ,



On a yk = D L kj yj +
j=1 j=k+1
j=k−1 j=n
X |akj | X |akj |
d’où |yk | ≤ kyk∞ + kxk∞
j=1
|a kk | j=k+1
|akk |
j=k−1 j=n
 X |akj |  kyk∞ X |akj |
et 1 − ≤ .
j=1
|a kk | kxk ∞
j=k+1
|a kk |
Pj=n |akj |
kyk∞ j=k+1 |akk |
D’où : ≤ Pj=k−1 |akj |  < 1.
kxk∞
1 − j=1 |akk |

Méthode de relaxation
Si on considère des matrices M et N dépendantes d’un paramètre ω on obtient : A = M (ω) − N (ω)
avec M (ω) = ω1 D − L et N (ω) = 1−ω D+U
1

−1 1−ω
ω
−1
T (ω) = ω D − L ω
D + U et c(w) = ω1 D − L b
−1 −1 −1
T (ω) = (I − ωD L) ((1 − ω)I + ωD U )
Remarque 2.4.1. – Si ω = 1, on retrouve la méthode de Gauss-Seidel.
– Si ω > 1, on parle de sur-relaxation.
– Si ω < 1, on parle de sous-relaxation.
Théorème 2.4.3. Une condition nécessaire de convergence de la méthode de relaxation est :
0 < ω < 2.

12
Preuve.  −1  
1 1−ω
T (ω) = D−L D+U .
ω ω
Si les valeurs propres de T (ω) sont notées λi (ω) on a :
n
det 1−ω


Y D + U
det(T (ω)) = λi (ω) = ω
1

= (1 − ω)n
i=1
det ω
D − L

D’où ρ (Tw ) ≥ [|1 − ω|n ]1/n = |1 − ω|. Pour que la méthode converge, il est nécessaire d’avoir
ρ(T (ω)) < 1 et par conséquent |1 − ω| < 1 d’où ω ∈]0, 2[.

13