Table des matières

1 Itroduction 2
1.1 Introduction générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Stabilité numérique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Conditionement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Principales notations et definitions . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Rappels et compléments sur les matrices . . . . . . . . . . . . . . . . . . . . . . 5

2 Résolution de systèmes linéaires 11

2.1 Méthodes directes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.1 La méthode de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.2 La factorisation LU d’une matrice . . . . . . . . . . . . . . . . . . . . . . 14
2.1.3 La factorisation de Cholesky . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Méthodes itératives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.2 La méthode de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.3 La méthode de Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.4 La méthode de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.5 Vitesse de convergence d’une méthode itérative . . . . . . . . . . . . . . 22

1
Chapitre 1

Itroduction

1.1 Introduction générale

La maîtrise des méthodes numèriques est une nécessité pour la résolution des problèmes que
l’ingénieur est amené à rencontrer au cours de sa vie professionnelle. Elle entretient des liens
étroits avec l’informatique. Si sa partie théorique relève plus des mathématiques, sa mise en
pratique aboutit généralement à l’implémentation d’algorithmes sur ordinateur. Ses méthodes
se fondent à la fois sur la recherche de solutions exactes comme dans le cas de l’analyse matricielle
ou du calcul symbolique, sur des solutions approchées qui résultent le plus souvent de processus
de discrétisation comme dans le traitement des équations différentielles.
Les deux sources d’erreur qui interviennent dans le calcul numérique sont :
1. Les erreurs d’arrondi sont imposées par le calculateur. La représentation d’un nombre en
mémoire de l’ordinateur étant finie, tout nombre réel n’est connu qu’avec une précision
donnée de n chiffres significatifs.
Exemple 1.1.
Pour effectuer l’addition des nombre x = 0.1234 et y = 0.5678 avec seulement trois chiffres
significatifs,on obtiendra x = 0.690 lorsque y est approché par 0.567 soit 0.691 lorsque y
est approché par 0.568. On comprend comment, à plus grande échelle, ces erreurs peuvent
induire des problèmes de précision.

2. Les erreurs de troncature ou de discrétisation qui proviennent de simplifications du modèle

mathématique. sont liées à la précision de l’algorithme utilisé.
Exemple 1.2.
considérons les nombres réels 5, 2009002; 32, 009891288; −6, 47009757. Pour tronquer ces
nombres à quatre décimales, seuls sont gardés les quatre chiffres après la virgule. Le
résultat serait : 5, 2009; 32, 0098; −6, 4700.

2
1.1.1 Stabilité numérique
Les méthodes numériques utilisées pour résoudre un problème approché conduisent à un résultat
qui est toujours entaché d’erreur. Cette erreur doit être suffisamment petite pour que la solution
numérique converge vers la solution réelle. Dans ce cas l’algorithme (ou la méthode) est dit
convergent.
La stabilité garantit que les erreurs ne s’amplifient pas au cours du déroulement de l’algorithme
et que la méthode reste stable
Lorqu’un problème (P ) admet une solution, il est intéressant d’envisager le problème perturbé,
noté (Pε ), où ε est un petit paramètre et de se demander si les solutions du système perturbé
sont voisines de la solution du système non perturbé

1.1.2 Conditionement
Le conditionnement mesure l’influence des erreurs d’arrondi sur la solution d’un problème donné.
Il est mis en évidence par une légère perturbation des données initiales. Il est mis en évidence
par une légère perturbation des données initiales.

Exemple 1.3.
On considère le système linéaire suivant :

S1 : Ax = b
! !
2 6 8
avec A = et b =
2 6.00001 8.00001
!
1
La solution est donnée par x =
1
Si par contre on considère le système linéaire S2 obtenu en "perturbant" très légèrement le
système S1 ! ! !
2 6 x1 8
S2 : =
2 5.99999 x2 8.00002
!
10
On trouve x =
−2
D’où la nécessité d’introduire la notion de conditionnement d’une matrice, vis-à-vis de la réso-
lution des systèmes linéaires. On dit que la matrice A du système linéaire (S1 ) est en fait "mal
conditionnée".
Pour une matrice A "bien conditionnèe" vis-à-vis de la résolution des systèmes linéaires, une
"petite" perturbation de A ou du second membre b engendre une "petite perturbation" de la
solution du système linéaire Ax = b

3
Remarque 1.1.
Pour conclure, on peut rappeler que si l’on veut obtenir des résultats numériquement précis
avec un ordinateur, il faut :
1. un probl‘eme bien conditionné,
2. un algorithme qui est numériquement stable lorsque l’on exécute avec une précision arith-
métique finie
3. un logiciel qui soit une bonne transcription de l’algorithme.
Un algorithme numériquement stable ne pourra pas résoudre un probl‘eme mal condi-
tionné avec plus de précision que celle contenue dans les données. Cependant, un algo-
rithme numériquement instable produira de mauvaises solutions pour des problèmes bien
conditionnés.

1.2 Principales notations et definitions

On utilise dans toute la suite les notations suivantes :
∗ Soit (ei )1≤i≤n la base canonique de Kn (K = R ou K = C) (C étant le corps des nombres
complexe).
∗∗ Un vecteur x de Kn admet une représentation unique sur la base canonique de Kn .
n
X
x= xi ei
i=1

xi , 1 ≤ i ≤ n i-ème composante de x
En notation matricielle, le vecteur x s’identifie à un vecteur colonne de Kn
 
x1
 
 x2 
 
x=
 

 
 x 
 n−1 
xn

on notera par :  
x1
 
 x2 
x=


 conjugué de x
 
xn
xt = (x1 , x2 , . . . , xn ) transposé de x

x∗ = (x1 , x2 , . . . , xn ) transconjugué de x

4
∗ ∗ ∗ Soit A = (ai,j )1≤i,j≤n une matrice à n lignes et n colonnes, à coefficients réels ou complexes
( i : indice de ligne ; j : indice de colonne). On désigne par :

At = (aj,i )1≤i,j≤n la transposée de A

A = (ai,j )1≤i,j≤n la conjugée de A

et par Mn,m (K) lensemble des matrices à n lignes et m colonnes et à coefficients dans K(K =
RouK = C). Lorsque m = n on utilisera la notation Mn (K).

La matrice identitée de Mn (R) (ou Mn (C)) est notée I. Le produit scalaire sur Rn est défini
pour x, y ∈ Rn par :
n
X
t
(x, y) = x y = xi yi
i=1

et vérifie (
(λx, y) = λ(x, y)
∀λ ∈ R, ∀ x Rn , ∀ x ∈ Rn :
(x, λy) = (x, y)
n
X
n n ∗
Le produit hermitien de C est défini pour x, y ∈ C par : (x, y) = x y = xi yi et vérifie
i=1
(
(λx, y) = λ(x, y)
∀λ ∈ C, ∀ x ∈ Cn , ∀ x ∈ Cn :
(x, λy) = (x, y)

1.3 Rappels et compléments sur les matrices

Définition 1.1.
Soit A ∈ Mn (K)
1. La matrice A est dite symétrique si At = A
2. La matrice A est dite antisymétrique si At = −A
3. La matrice A est dite hermitienne si A∗ = A
4. La matrice A est dite inversible, s’il existe une matrice B telle que AB = BA = I. La
matrice B est alors unique et est noté A−1 .
5. La matrice A est dite orthogonale si At = A−1
6. La matrice A est dite unitaire si A−1 = A∗
7. La matrice A est dite normale si AA∗ = A∗ A

Propriétés 1.1.

5
 1. Si A ∈ Mn (R) est inversible, alors At est inversible et on a :

(At )−1 = (A−1 )t

2. Si A est une matrice orthogonale alors

AAt = At A = I

Définition 1.2.
Soit A ∈ Mn (K)
1. Une matrice A ∈ Mn (K) est dite triangulaire supérieure, si aij = 0 pour tout i > j, 1≤
i, j ≤ n
2. Une matrice A ∈ Mn (K) est dite triangulaire inférieure, si aij = 0 pour tout i < j, 1≤
i, j ≤ n

Proposition 1.1.
Soit A ∈ Mn (K) alors
1. Si A est triangulaire inférieure et triangulaire supérieure, alors A est diagonale
2. Si A est triangulaire inférieure (resp. supérieure), alors A est inversible, et A−1 est trian-
gulaire supérieure (resp.inférieure )
3. Si A est triangulaire inférieure et triangulaire supérieure, alors le déterminant de A est le
produit des coefficients diagonaux de A
n
Y
det(A) = aij
i=1

4. Soit B ∈ Mn (K). Si A et B sont triangulaire supérieure (resp.inférieure) alors la matrice

produit AB est triangulaire supérieure (resp.inférieure )

Définition 1.3.
Soit A ∈ Mn (R) (ou. Mn (C)) une matrice symétrique (ou hermitienne). Alors, A est dite définie
positive, si elle vérifie les deux propriétés suivantes :

∀x ∈ Rn (ou Cn ), (Ax, x) ≥ 0

pour x ∈ Rn (ou Cn ) (Ax, x) = 0 ⇐⇒ x = 0

Dans le cas où A vérifie uniquement (Ax, x) ≥ 0 on dit qu’elle est semi-définie positive

Proposition 1.2.

1. Soit A ∈ Mn (C), alors la matrice AA∗ est semi-définie positive.

6
 2. Si A est inversible, alors la matrice AA∗ est définie positive.

Définition 1.4.
Soient λ ∈ C, et A ∈ Mn (R) (ou Mn (C).) Alors λ est appelée valeur propre de A, si elle est
racine du polynôme caractéristique PA (λ) de A :

PA (λ) ≡ det(A − λI) = 0

Propriétés 1.2.
Soit A ∈ Mn (R) (ou Mn (C)) et λ une valeur propre de A. Alors on a
1. La matrice A − λI est non inversible
2. Il existe un vecteur x ∈ Rn (ou Cn ) non nul tel que Ax = λx.
Un tel vecteur x est appelé vecteur propre de A associé à la valeur propre λ
3. Soit A ∈ Mn (R) une matrice symétrique. Alors A est définie positive si et seulement si
toutes ses valeurs propres sont strictement positives.

7
 Série 1

Exercice 1.1.
 
1 1 1
 
1. Soit A = 
 1 1 0 

1 0 1
√ √
Vérifier que SP (A) = {1, 1 + 2, 1 − 2}. A est elle définie positive ?
 
2 −1 0
 
2. A =  −1 2 0  
0 0 1
Vérifier que SP (A) = {1, 1, 3}. A est elle définie positive ?

Exercice 1.2.
Soit T = (tij )1≤i,j≤n ∈ Mn (R) et U = (uij )1≤i,j≤n ∈ Mn (R) deux matrice triangulaires inférieures
(resp. supérieures).
Montrer que la matrice A = T U est triangulaires inférieure (resp. supérieure)

Exercice 1.3.
Soit T = (tij )1≤i,j≤n ∈ Mn (R) une matrice inversible et triangulaire inférieure.
1. Soit b = (bi )1≤i≤j ∈ Rn vérifiant

∃k, 2 ≤ k ≤ n, tel quebi = 0 pour i < k

On considère le système linéaire (S); T x = b

Trouver un algorithme pour déterminer la solution x = (xi )1≤i≤n ∈ Rn du système (S) en
fonction de b et de T
bk
2. Montrer que xi = 0 pour i < k et que xk =
tkk
3. En déduire que T −1 est triangulaire inférieure. Quels sont ses éléments diagonaux.

8
En effet 1.1.
Soit T = (tij )1≤i,j≤n ∈ Mn (R) et U = (uij )1≤i,j≤n ∈ Mn (R) deux matrice triangulaires infé-
rieures.

tij = 0 si i < j
uij = 0 si i < j
Montrons que A = T U est triangulaires inférieure. aij = 0 si i < j
X
Soit i < j. On a aij = tik ukj
k=1n
X i n
X
= tik ukj + tik ukj
|{z} |{z}
k=1 0 k=i+1 0

Soit T = (tij )1≤i,j≤n ∈ Mn (R) et U = (uij )1≤i,j≤n ∈ Mn (R) deux matrice triangulaires su-
périeurs. Alors At = (T U )t = U t T t est une matrice tiangulaire inférieur et par suite A est
supérieur.

En effet 1.2.

1. Soit b = (bi )1≤i≤j ∈ Rn vérifiant

∃k, 2 ≤ k ≤ n, tel quebi = 0 pour i < k

Résoudre (S) par la méthode de Descente :



 t11 x1 = b1 = 0


 t x + t22 x2 = b2 = 0
 21 1


..
.tk−1,1 x1 + · · · + tk−1,k−1 xk−1 = bk−1 = 0

tk,1 x1 + · · · + tk,k xk = bk




 ..


.tn,1 x1 + · · · + tn,n xn = bn

2. Pour i = 2, n
i−1
X
bi − til xl
l=1
xi =
tll
bk
alors x1 = x2 = . . . xk−1 = 0; xk =
tkk
3. En déduire que T −1 est tiangulaire inférieur
La colonne j de T −1 est la solution du système linéaire :

T x = ej

9
 Ainsi la colonne j Tj−1 de T −1 est donnée d’après 1) par
 
0
 .. 

 . 

 
 0
Tj−1  =⇒ T −1 = 1 ; 1 ≤ i ≤ n

= ij
 1/t
 jj

 tii
 
 0 
 
..
.

En par suite T −1 est donnée par :

 .. 
1/t11 0 ... .
..
 

0 1/t11 . 
T −1 =
 
.. .. .. 

 . . 0 . 

0 ... 1/tnn

10
Chapitre 2

Résolution de systèmes linéaires

2.1 Méthodes directes

2.1.1 La méthode de Gauss

La méthode de Gauss est une méthode générale de résolution d’un système linéaire

Ax = b (2.1)

où A est une matrice inversible de Mn (R).

Elle consiste à se ramener à un système triangulaire supérieur admettant la même solution que
le système linéaire 2.1.



 a1,1 x1 + a1,2 x1 + . . . a1,n xn = b1

 .. .. ..
 . . .
. .. .. (2.2)

 .. . .



 a x + a x + ...a x = b
n,1 1 n,2 1 n,n n n

Première étape de l’élimination

L’un au moins des éléments ai,1 , 1 ≤ i ≤ n est non nul, (si non la matrice serait non inversible).
On choisit alors le plus grand coefficient en valeur absolue de la première colonne de A, qu’on
appelle le pivot d’élimination. Ensuite, on échange la ligne du pivot avec la première ligne. La
(1)
matrice A(1) = P (1) A = (ai,j )1≤i,j≤n ainsi obtenue est telle que
 (1)
a ) 6= 0
 1,1



 |a(1) (1)

1,1 )| = max |ai,1 )|

1≤i≤n

11
On annule ensuite tous les éléments de la première colonne de la matrice A(1) situés sous la
diagonale, (la première ligne restant inchangée.) par des combinaisons linéaire appropriées de
la première ligne et des autres lignes de la matrice A(1) .
Soit de la forme

(1) (1) (1)

 
a1,1 a1,2 . . . ... a1,n
 (2) (2) 
 0 a2,2 . . . . . . a2,n 
.. .. .. ..
 
A(2) = . . . .
 

 .. .. . . . ..

. . .
 
 
(2)
0 an,2 ... a(2)
n,n
(2)
Les coefficients de la matrice A sont alors données par :
 (2) (1)

 a1,j = a1,2 1≤j≤n

 (1)

(2) (1) ai,1 (1)
ai,j = ai,j − (1) a1,j 2 ≤ i, j ≤ n


 a 1,1
 (2)

an,2 = 0 2≤i≤n

La seconde étape d’élimination consiste à effectuer les même opération que précédemment, mais
(2)
seulement sur la sous matrice (ai,j )2≤i,j≤n .
On obtient de proche en proche comme résultat de la (k − 1)−ème étape de l’élimination
2 ≤ k ≤ n, une matrice
(k)
A = E (k−1) P (k−1) . . . P (2) E (1) P (1) A

de qui est de la forme

 (1) (1) (1)

a1,1 a1,2 . . . ... ... a1,n
 (2) (2) 

 a2,2 . . . ... . . . a2,n 

 ... .. 
(k)  . 
A = (k) (k)


 ak,k . . . ak,n 

 .. ... .. 

 . . 

(k)
an,k . . . a(k)
n,n

Décrivons alors la k-ème étape de l’élimination

(k) (k) (k)
La matrice A est inversible (detA = ±detA). On choisit le plus grand éléments ai,k k ≤ i ≤ n
en valeur absolue comme pivot et ensuite on échange la ligne ik du pivot avec la k-ème ligne de
(k)
la matrice A .

(k)
On annule ensuite tous les éléments de la k− ème colonne de la matrice A situés sous la
diagonale, (la k− ème ligne restant inchangée.) par des combinaisons linéaire appropriées de la

12
 (k)
k− ème ligne et des autres lignes de la matrice A .
(k+1) (k)
Les coefficients de la matrice A = E (k) P (k) A sont alors donnée par :
 (k+1) (k)

 ai,j = ai,j 1 ≤ i ≤ k, 1 ≤ j ≤ n
 (k)
ai,k (k)


(k+1) (k)
ai,j = ai,j − (k) ak,j k + 1 ≤ i, j ≤ n


 ak,k
 (k+1)

ai,k = 0 k+1≤i≤n
Après la (n-1)-ème étape de l’élimination on obtient une matrice U triangulaire supérieure :
 (1) (1) (1)

a1,1 a1,2 . . . . . . . . . a1,n
 (2) (2) 

 a2,2 . . . . . . . . . a2,n  
.. ..
.
 
 . 
U = (k)

(k) 

 ak,k . . . ak,n 
 . . .. 

 . . 

(n)
0 an,n
La seconde phase de la méthode de Gauss est la résolution du système linéaire :

Ux = d (2.3)
où d = E (n−1) P (n−1) . . . E (1) P (1) b.
La résolution du système (2.3) est immédiate. On calcule successivement xn à partir de la
dernière équation, puis xn−1 à partir de l’avant-dernière et ainsi de suite. ce qui donne
dn


 xn = (n)
an,n




 n−1
X (k)
 (dk − ak,j xj )

 j=k+1
 xk =


(k)

ak,k
Exemple 2.1.
Considérons le système linéaire
    
2 8 4 x 1
    
 2 10 6   y  =  1 
    
1 8 2 z 1
1. Montrer que le système admet une solution unique x
1
 
 4 
 1 
2. En utilisant la méthode de causs vérifier que x =  
 8 
 1 
−
8

13
2.1.2 La factorisation LU d’une matrice
Théorème 2.1. (Factorisation LU)
Soit A = (aij )1≤i,j≤n une matrice carée d’ordre n, inversible. Alors A possède une facorisation
A = LU où L est une matrice triangulaire inférieure à diagonale unité et U est une triangulaire
supérieure, si et seulement si toutes les sous-matrices
 
a11 ... ... a1k
 . ... .. 
 .. . 
M (k) =  . 1≤k≤n
 
 .. .. .. 
 . . 

ak1 ... akk

de A sont inversibles.
De plus, si une telle factorisation existe, alors elle est unique.

Mise en œuvre de la factorisation LU

Lorsque cette factorisation est possible, on pose a priori
   
1 u11 . . . . . . u1n
 ..   .. .. 
 l
 21 .   . . 
L= . et U =
  
 .. ..   .. .. 
 . 


 . . 

ln1 . . . . . . 1 unn

De l’égalité A = LU, on déduit les relations :

n inf (i,j)
X X
aij = lik ukj = lik ukj 1 ≤ i, j ≤ n
k=1 k=1

puisque lpq = uqp = 0 si 1 ≤ p < q ≤ n.

On détermine d’abord la première ligne de U en utilisant les formules

u1j = a1j, 1 ≤ j ≤ n,

en suite la première colonne de L dont les éléments sont donnés par :

ai1,
li1 = 2≤i≤n
u11
Supposons que l’on ait calculer les (p − 1) premières lignes de U et les (p − 1) premières colonnes
de L. On détermine alors la ligne p de U ensuite la colonne p de L en utilisant les formules
suivantes :
p−1
X
upj = apj − lpk ukj p≤j
k=1

14
 p−1
X
aip − lik ukp
k=1
lip =
upp
Ce qui donne comme alorithme de déterminer des matrices L et U
Pour p = 1 à n faire
Début
Pour j = p à n faire
p−1
X
upj = apj − lpk ukj
k=1
Fin
Pour i = p + 1 à n faire
p−1
X
aip − lik ukp
k=1
lip =
upp
Fin
Fin
Alors résoudre le système linéaire Ax = b revient à résoudre successivement les deux systèmes
linéaires triangulaires :
Ly = b puis Ux = y

Remarque 2.1.
Un intérêt majeur de la factorisation LU d’une matrice est de pouvoir résoudre plusieurs sys-
tèmes linéaires correspondant à la même matrice A.

2.1.3 La factorisation de Cholesky

On considère dans cette section, une matrice A symétrique définie positive. alors d’aprés le
théorème (2.1) une factorisation LU. Mais on utilise la symétrie de A pour modifier légèrement
la factorisation LU .

Théorème 2.2.
Soit A une matrice symétrique définie positive. Alors, il existe une matrice réelle triangulaire
inférieure B telle que
A = BB t

De plus, l’on peut imposer que les éléments diagonaux de la matrice B soient tous strictement
positifs, et la factorisation A = BB t est alors unique.

La méthode de cholesky :

15
La méthode de Cholesky, pour résoudre un système linéaire Ax = b où A est une matrice
symétrique définie positive, consiste à calculer la factorisation de cholesky A = BB t , puis à
résoudre successivement les deux système linéaires suivants à matrice triangulaires :

By = b, puis, Btx = y

Le vacteur x ainsi obtenu vérifie alors

Ax = BB t = By = b

Mise en œuvre de la factorisation de Cholesky :

Soit A une matrice symétrique définie positive. On pose a priori
 
b11
 . 
 .. b 
22
B= .
 
 .. . ..


 
bn1 . . . . . . bnn

De l’égalité A = BB t on déduit les relations

n inf (i,j)
X X
aij = bik bjk = bik bjk 1 ≤ i, j ≤ n (2.4)
k=1 k=1

puisque bpq = 0 si 1 ≤ p < q ≤ n.

La matrice A étant symétrique, il suffit que le relation (2.4) ci-dessus soient vérifiées pour i ≤, j
par exemple.
Calcul de B colonne par colonne
Pour j = 1 on obtient
ai1 = bi1 b11 1≤i≤n

et en particulier, on a a11 = b211 et en imposant aux coefficients diagonaux de B d’ être stricte-

ment positifs, on obtient
√
a11 = a11

Un fois b11 calculé, on détermine la première colonne de B en utilisant les relations

ai1
bi1 =
b11
De proche en proche, on détermine la j-ème colonne de B en calculant d’abord
v
u
u j−1
X
bjj = ajj −
t b2jk
k=1

16
ensuite
j−1
X
aij − bik bjk
k=1
bij = i = j + 1, . . . n
bjj
Ce qui donne pour algorithme de calcul de B colonne par colonne :
Pour j = 1 à n faire
Début v
u j−1
u X
bjj = ajj −
t b2jk
k=1
Pour i = j + 1 à n faire
j−1
X
aij − bik bjk
k=1
bij =
bjj
Fin
Fin
Fin
Calcul de B ligne par ligne
En suivant la même démarche que ci-dessus, l’algorithme de calcul de B ligne par ligne est
donné par :
Pour i = 1 à nfaire
Début
Pour j = 1 à i − 1 faire
Début
j−1
X
aij − bik bjk
k=1
bij =
bjj
Fin v
u i−1
X
u
bii = aii −
t b2ik
k=1
Fin
Fin

2.2 Méthodes itératives

2.2.1 Introduction
On va étudier les méthodes itératives pour résoudre un système linéair :

Ax = b (2.5)

17
Une méthode itérative engendre une suite de vecteur qui doit tendre vers la solution de l’équation
(2.5).
Soit A = (aij )1≤i,j≤n une matrice à coefficents complexes inversible et b un vecteur donné de
Cn . Les méthodes qu’on va étudier peuvent se formuler de la manière suivante :
1. On décompose A sous la forme A = M − N où M est une matrice facilement inversible.
On a :
Ax = b ⇐⇒ M x = N x + b

2. La matrice M étant inversible, on définit la méthode itérative permettant de calculer la

solution de (2.5) par : (
x0 donné de Cn
xk+1 = M −1 N xk + M −1 b
Soit, en posant B = M −1 N, l’écriture équivalente :

xk+1 = Bxk + c (2.6)

En notant xk le vecteur de composantes xk = (x1k , x2k , . . . , xnk ). L’algorithme est initialisé

par un vecteur arbitraire x0 = (x10 , x20 , . . . , xn0 ) et s’arrête quant kxk+1 − xk k < ε pour ε
donné. Lorsque la suite xk converge i.e lim xk = x, on dit que la méthode converge
k−→+∞

Lemme 2.1.
Soit B ∈ Mn (C), alors les quatre propriétés suivantes son t équivalentes :
1. B k tend vers 0, lorsque k tend vers +∞.
2. B k v tend vers 0 pour tout choix de v dans Cn , lorsque k tend vers +∞.
3. ρ(B) < 1
4. kBk < 1 pour au moins une norme matricielle subordonnée.

Théorème 2.3.
Soient B ∈ Mn (C), H = I − B et c ∈ Cn . La suite définie par
(
x0 donn
xk+1 = Bxk + c

e ∈ Cn , solution du système linéaire

converge, pour tout choix x0 vers un élément x

Hx
e=c

si et seulement si ρ(B) < 1

18
2.2.2 La méthode de Jacobi
La méthode de Jacobi nest pas utilisable que si aii 6= 0. À partir d’un vecteur x0 donné, la
méthode de Jacobi consiste à construire la suite xk de la manière suivante :
Pour i = 1 à n, on calcule  
1  X
xik+1 = bi − aij xjk  (2.7)
aii j=1 j6=i

Pour écrire la relation 2.7 sous forme matricielle, on décompose la matrice A sous la forme

A=D−E−F

ou D la matrice formée des seuls éléments diagonaux de A,

(
dij = 0 si i 6= j
D = (dij ) tel que
dii = aii si1 ≤ i ≤ n

(
eij = 0 si i ≤ j
E = (eij ) tel que (2.8)
eij = −aij si i > j

(
fij = 0 si i ≤ j
F = (fij ) tel que
fij = −aij si i < j

Alors, comme on a supposé que aii 6= 0 pour i = 1 à n, D est inversible est la relation (2.7)
s’écrit
xk+1 = D−1 (E + F )xk + D−1 b

La matrice J = D−1 (E + F ) = I − D−1 A est appelée matrice de Jacobi.

Théorème 2.4. !
X
Soit A une matrice à diagonale strictement dominante c’est-à-dire si |aii | > |aij | . Alors
j6=j
la méthode de Jacobi pour la résolution d’un système linéaire de matrice A est convergente.

Exemple 2.2.
Considérons le système     
4 2 1 x 4
    
 −1 2 0   y  =  2 
    
2 1 4 z 9
Soit x0 = (0, 0, 0) le vecteur initial,

19
2.2.3 La méthode de Gauss-Seidel
Dans la méthode de Gauss-Seidel, publiée en 1874 par ludwig Seidel, on choisit M = D − E et
N = F, ce qui conduit à considérer la relation de récurrence

xk+1 = (D − E)−1 F xk + (D − E)−1 b.

Dans la méthode de Gauss-Seidel au lieu d’attendre une itération entière pour corriger les
composantes de xk , les valeurs calculées sont utilisées au fur et à mesure du calcul. On améliore
ainsi la vitesse de convergence. Supposons qu’à l’interieur de la (k + 1)-ieme itération, on ait
déjà obtenu x1k+1 , x2k+1 ,. . .xi−1
k+1 , alors en supposant toujour aii 6= 0, on calcule

i−1 n
!
1 X X
xik+1 = bi − aij xjk+1 − aij xjk+1
aii j=1 j=1+1

Exemple 2.3.

1. Reprendre l’exemple 2.2

2. Résoudre le système  y
 x = sin(xy) −
2π
 y = 2πx − (π − 1 )(e2x−1 − 1)
4
2
Partant du point ( , 3)
5

20
Théorème 2.5.
Soit A une matrice à diagonale strictement dominante, alors la méthode de Gauss-Seidel pour
la résolution d’un système linéaire de matrice A est convergente.

2.2.4 La méthode de relaxation

La méthode de Jacobi correspond à la décomposition A = M − N avec M = D et N = E + F.
La méthode de Gauss-Seidel revient à prendre M = D − E et N = F Dans la méthode de
relaxation, on introduit un paramètre réel w non nul et on prend
1 1−w
M= D−E et N= D+F
w w
où D, E et F sont définies par (2.8).La matrice de la méthode itérative ainsi définie est alors
donnée par :
1 1−w
Lw = ( D − E)−1 ( D + F ) = (I − wL)−1 ((1 − w)I + wU
w w
où L = D−1 E et U = D−1 F

Remarques 2.1.

1. Pour w = 1, on retrouve la méthode de Gauss-Seidel.

Lorsque 0 < w < 1 on parle de sous-relaxation et lorsque 1 < w < 2, on parle de
surrelaxation(SOR, successive Over Relaxatiopn)
2. La matrice L est appelée matrice de relaxation.

L’algorithme est fondé sur le calcul des itérées

i−1 n
!
w X X
xik+1 = xik + bi − aij xjk+1 − aij xjk+1
aii j=1 j=1+1

Proposition 2.1.
La méthode de relaxation diverge Pour tout w ∈ R \ [0, 2].

Théorème 2.6.
Soit A une matrice symétrique définie positive décomposée sous la forme A = D − E − F. Alors
la méthode de relaxation est converge pour w ∈]0, 2[.

Théorème 2.7.
Soit A une matrice tridiagonale. On suppose que toutes les valeurs propres de la matrice de
Jacobi J sont réelles et strictement inférieures à 1 en valeur absolue. Alors, la méthode de

21
relaxation converge pour tout w ∈]0, 2[. De plus, il existe une valeur optimale de w notée w0
donnée par
2
w0 = p
1+ 1 − (ρ(J))2
Pour la quelle ρ(Lw ) est minimal et ρ(Lw ) = w0 − 1

avec ρ(J) c’est le rayon spectral (c’est-à-dire le plus grand module des valeurs propres de J)

2.2.5 Vitesse de convergence d’une méthode itérative

La convergence d’une méthode itérative ne dépend pas du chois du vecteur initial x0 , mais la
rapidité de convergence e itérative dépent. On peut caractériser la convergence d’une méthode
itérative par la vitesse avec lequelle l’erreur tend vers 0.Pour une méthode dont la matrice est
B, l’erreur à l’itération k est donnée par

ek = xk − x = B k e0

où xk est la valeur calculé à la k ieme itération à l’aide de (2.6) et x est la solution de système
pour une norme choisie, on a :
kek k = kB k e0 k

On va voir dans la suite de cette section qu’une méthode itérative est d’autant plus rapide à
converger que le rayon spectral de sa matrice d’itération B est plus petit. Ceci découle du lemme
suivant.

Lemme 2.2.
Pour B ∈ Mn (C), on a pour tout norme matricielle subordonnée :
1
lim kB k k k = ρ(B)
k→+∞

avec ρ(J) c’est le rayon spectral de la matrice B

Remarque 2.2.
Une deuxième méthode itérative dont la matrice de l’itération B
e a un rayon spectral ρ(B)
e et
tel que ρ(B)
e < ρ(B) converge plus rapide que la méthode itérative de la matrice B

22
 Série 2

Exercice 2.1.
On se propose de résoudre numériquement le système linéaire Ax = b.
Etudier la convergence des méthodes de Jacobi et Gauss-Seidel dans les deux cas suivants :
   
1 2 −2 2 −1 −1
   
A= 1 1
 1  A= 2
  2 2 
2 2 1 −1 −1 2

Exercice 2.2.
Etudier la convergence des méthodes de Jacobi et de relaxation avec
 
1 2 0
 
A=  1 1 0  
1 1 1

Exercice 2.3.
On considère le système Ax = b, où
   
2 −1 0 7
   
 −1 2 −1 
  et b=
 1 

0 −1 2 1

1. En utilisant la méthode de Gauss déterminer la solution de système S

2. Pour x0 =t (0, 0, 0) effectuer le 5 première itération de la méthode de Jacobi et celle de
Gauss-Seidel

Exercice 2.4.
Soit α ∈ R et soit le système linéaire Ax = b, avec
 
1 α α
 
A=  α 1 α 

α α 1

1. Déterminer les valeurs propres de A puis déduire les valeurs de α, pour lesquelles la matrice
est-elle definie positive ?
1
2. Montrer que pour tout α ∈] − , 1[ la méthode de relaxation converge pour tout w ∈]0, 2[
2
3. Ecrire la matrice J de la méthode de Jacobi correspondante. Pour quelle valeurs de α, la
méthode de Jacobi converge-t-elle ?
4. Ecrire la matrice L de la méthode de Gauss-Seidel correspondante. Calculer ρ(L)

23
 5. Pour quelles valeurs de α, la méthode de Gauss-Seidel converge-t-elle plus vite que celle
de Jacobi ?
ind : Si A est symétrique alors A est définie positive ssi toutes ses valeurs propres sont strictement
positives.

24