Chapitre 1-Methodes Numériques Appliquées

Chapitre I.

Résolution des systèmes d’équations linéaires et non linéaires par les méthodes
itératives

A- Méthodes pour résolution des systèmes d’équations linéaires :

A-1 Introduction :

Les méthodes directes de résolution de systèmes linéaires fournissent une solution x au

problème Ax = b en un nombre fini d'opérations. Si l'ordre n de la matrice A est élevée, le
nombre d'opérations est élevé et de plus, le résultat obtenu n'est pas rigoureusement exact.
Dans ce chapitre on va introduire les méthodes itératives ou indirectes qui donnent une
solution approximative du système d’équations linéaires. Ces méthodes sont très faciles à
mettre en œuvre et à programmer, elles ne consomment pas de l’espace mémoire et donnent
des résultats autant précis que l’on veut.

A-2- Principe :
Le problème consiste à trouver la solution du système d’équations suivant :
a11x1 + a12x2 + · · · + a1nxn = b1
a21x1 + a22x2 + · · · + a2nxn = b2 (1)
⋮ ⋮ ⋮ ⋮
an1x1 + an2x2 + · · · + annxn = bn

En notation matricielle ce système s´écrit

Ax = b (2)
L'objectif est de résoudre un système de type Ax = b. Pour cela, nous allons décomposer la
matrice A en :
A=M–N (3)
De sorte que M soit inversible. Ainsi, le système devient :
Mx = Nx + b (4)
et nous cherchons par récurrence une suite de vecteur x(i) obtenu à partir d'un vecteur x(0) et de
la relation : [Link]+1 = [Link] + b (5)
C’est-à-dire : xk+1 = M-1 Nxk +M-1.b (6)
Cette relation est une relation de récurrence. Nous pouvons en déduire une relation reliant

1
Chapitre 1-Methodes Numériques Appliquées

e(k) = x(k) - x à e (k-1) = x (k-1) - x :

M(x(k) - x) = N(x (k-1) - x) (7)
puisque Mx = Nx + b et donc e(k) = M-1 N e (k-1) pour k = 1, 2, ...
Si on pose B = M-1N, nous avons alors :
e (k) = B(k) e(0)

𝑎11 0 … 0
0 𝑎22 0 ⋮
Avec D la matrice diagonale suivante : 𝐷=( )
⋮ … ⋱ 0
0 … 0 𝑎𝑛𝑛
0 0 … 0
𝑎21 0 0 ⋮
𝐸=( 0)
E la matrice triangulaire inférieure suivante :
⋮ ⋱ ⋱
𝑎𝑛1 … 𝑎𝑛, 𝑛−1 0
0 𝑎12 … 𝑎1𝑛
⋱ ⋮
F la matrice triangulaire supérieure suivante : 𝐹 = (0 0 ⋱ 𝑎𝑛−1, 𝑛 )
⋮ ⋱
0 … 0 0
Nous obtiendrons donc la décomposition A = M - N à partir de différents types de
regroupement de ces matrices D, E, F.

A- 3- La méthode de Jacobi
On pose :
M = D ; N = - (E + F)
ainsi, B = M-1N = D-1(-E - F), ce qui implique :
xk+1 = D-1(-E - F) xk + D-1b (8)
et si on exprime cette relation en fonction des éléments de la matrice A, nous avons :
(𝑘+1) 1 (𝑘)
𝑥𝑖 = 𝑎 (𝑏𝑖 − ∑𝑛𝑗=1,𝑗≠𝑖 𝑎𝑖𝑗 𝑥𝑗 ); Pour i = 1 ... n
𝑖𝑖

Ce qui est équivalent a

(𝑘+1) (𝑘) (𝑘)
𝑥1 = (𝑏1 − 𝑎12 𝑥2 − · · · −𝑎1𝑛 𝑥𝑛 )/ 𝑎11
(𝑘+1) (𝑘) (𝑘)
𝑥2 = (𝑏2 − 𝑎21 𝑥1 − · · · −𝑎2𝑛 𝑥𝑛 )/ 𝑎22 (9)
⋮ ⋮ ⋮ ⋮
(𝑘+1) (𝑘) (𝑘)
{𝑥𝑛 = (𝑏𝑛 − 𝑎𝑛1 𝑥1 − · · · −𝑎𝑛(𝑛−1) 𝑥𝑛−1 )/𝑎𝑛𝑛
c à d pour résoudre le système (1) on porte les termes de droite à l’itération (k) et ceux à
gauche à l’itération (k+1)

2
Chapitre 1-Methodes Numériques Appliquées

(0) (0) (0)

En prenant une estimation initiale 𝑋 (0) = (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) et en utilisant le système (9) on
(1) (1) (1)
calcule 𝑋 (1) = (𝑥1 , 𝑥2 , … , 𝑥𝑛 )ensuite on remplace le vecteur 𝑋 (1) dans le système (9)
avec k=1 on calcule 𝑋 (2) et continue de la même façon pour calculer les vecteurs 𝑋(3),(4),
𝑋(5),… jusqu’à la convergence.

A-4- La méthode de Gauss-Seidel :

Cette méthode utilise M = D+E et N = -F. D'où B = - (D+E)-1F.
Alors, on a :
xk+1 = - (D + E)-1Fxk + (D + E)-1b (10)
Le calcul de l'inverse de D + E peut être évite. Si on écrit (D + E) xk+1 = - F xk + b, on obtient :
∑𝑖𝑗=1 𝑎𝑖𝑗 𝑥𝑗(𝑘+1) = − ∑𝑛𝑗=𝑖+1 𝑎𝑖𝑗 𝑥𝑗(𝑘) + 𝑏𝑖 (11)
D’ou
(𝑘+1) 1 (𝑘+1) (𝑘)
𝑥𝑖 = 𝑎 (𝑏𝑖 − ∑𝑖−1
𝑗=1 𝑎𝑖𝑗 𝑥𝑗 − ∑𝑛𝑗=𝑖+1 𝑎𝑖𝑗 𝑥𝑗 ) ; Pour i=1 ... n
𝑖𝑖

Ce qui est équivalent à la formule :

(𝑘+1) (𝑘) (𝑘)
𝑥1 = (𝑏1 − 𝑎12 𝑥2 − · · · −𝑎1𝑛 𝑥𝑛 )/ 𝑎11
(𝑘+1) (𝑘+1) (𝑘)
𝑥2 = (𝑏2 − 𝑎21 𝑥1 − · · · −𝑎2𝑛 𝑥𝑛 )/𝑎22
(𝑘+1) (𝑘+1) (𝑘+1) (𝑘)
𝑥3 = (𝑏3 − 𝑎31 𝑥1 − 𝑎32 𝑥2 −· · · −𝑎3𝑛 𝑥𝑛 )/𝑎33 (12)

⋮ ⋮ ⋮ ⋮
(𝑘+1) (𝑘+1) (𝑘+1) (𝑘+1)
{𝑥𝑛 = (𝑏𝑛 − 𝑎𝑛1 𝑥1 − 𝑎𝑛2 𝑥2 −· · · −𝑎𝑛(𝑛−1) 𝑥𝑛−1 )/𝑎𝑛𝑛
Le processus itératif se fera avec un vecteur initial en prenant une estimation initiale 𝑋 (0) =
(0) (0) (0) (1) (1) (1)
(𝑥1 , 𝑥2 , … , 𝑥𝑛 )et en utilisant le système (12) on calcule 𝑋 (1) = (𝑥1 , 𝑥2 , … , 𝑥𝑛 ensuite

on remplace le vecteur 𝑋(1) dans le système (12) avec k=1 on calcule 𝑋(2) et continue de la
même façon de calculer les vecteurs 𝑋(3), 𝑋(4), 𝑋(5),… jusqu’à la convergence.
On remarque donc que la méthode de Gauss-Seidel est une amélioration de la méthode de
Jacobi en effet elle rend le processus itératif plus rapide.
(𝑘+1)
Le système réduit reste le même sauf que la nouvelle valeur de 𝑥𝑖 obtenue dans la ième
équation sera injectée dans la suivante.
Partons de la méthode de Jacobi, le calcul des vecteurs 𝑋(1), 𝑋(2), 𝑋(3),… mène à la
convergence, cela veut dire que chaque nouveau vecteur est meilleur que le précédent. On
remarque dans la méthode de Jacobi que pour calculer la composante 𝑥2(2) du vecteur 𝑋(2) on
utilise celles de 𝑋(1) bien que 𝑥1(2) est déjà calculée et elle est meilleure que 𝑥1(1). D’ici vient le
3
Chapitre 1-Methodes Numériques Appliquées

principe de la méthode de Gauss-Seidel, on utilise chaque composante dés quelle sera

calculée. Ainsi, pour calculer la composante 𝑥(𝑘+1) , on utilise toutes les composantes de 𝑥1(𝑘+1)
à 𝑥𝑖−1(𝑘+1) déjà calculées à l’itération (k+1) en plus de celles 𝑥𝑖+1(𝑘) à 𝑥𝑛(𝑘) qui ne sont qu’à
l’itération (k).

A-5- Condition de convergence des méthodes itératives

Pour que les méthodes itératives de résolution des systèmes d’équations linéaires convergent
il faut que la matrice A soit à diagonalement dominante ce qui est très facile à vérifier.
On dit qu’une matrice est diagonalement dominante si la valeur absolue de l’élément de la
diagonale est supérieure à la somme des valeurs absolues de tous les autres éléments sur la
même ligne. On écrit donc :
|𝑎𝑖𝑖 | > |𝑎𝑖1| + |𝑎𝑖2| + ⋯ + |𝑎𝑖𝑖−1| + |𝑎𝑖𝑖+1| + ⋯ + |𝑎𝑖𝑛| (13)
Avec i variable entre 1 et n le nombre de lignes ou de colonnes de la matrice.

A-6- Critère d’arrêt de calcul pour la méthode de Jacobi et Gauss-Seidel

On arrête les calculs pour ces méthodes lorsque la différence absolue entre deux itérations
successives soit inférieure à une certaine précision 𝜀 donnée.
|(𝑛+1) − 𝑋(𝑛)| < 𝜺 (14)
Ici, il faut vérifier la différence pour toutes les composantes une par une.
|𝑥1(𝑛+1) − 𝑋1(𝑛)| < 𝜺, |𝑥2(𝑛+1) − 𝑋2(𝑛)| < 𝜺, … , |𝑥𝑛(𝑛+1) − 𝑋𝑛(𝑛)| < 𝜺

B- Méthodes pour résolution des systèmes d’équations non linéaires

Dans cette partie on va étudier une méthode pour la résolution des équations non linéaires.
Comme exemple de ces équations, on peut citer
𝐟(𝐱) = 𝐬𝐢𝐧(𝒙) + 𝒙 = 𝟎, 𝐟(𝐱) = 𝐥𝐧(𝒙) − 𝟐𝒙 + 𝟑=𝟎. Ces équations ne possèdent pas une ou des
racines exactes qui peuvent être calculées directement, c’est pourquoi on fait recours aux
méthodes numériques pour trouver les solutions approchées de ces équations. Les racines
calculées sont autant précises que l’on veut surtout lorsqu’on dispose des moyens de calcul.
Ces méthodes numériques permettent seulement le calcul d’une seule racine sur un intervalle
bien choisi. Donc si l’équation possède plus d’une racine, il est nécessaire de les localiser
dans des intervalles choisis soigneusement et de faire le calcul pour chaque racine à part.

B-1- Localisation des racines d’une équation f(x)=0.

4
Chapitre 1-Methodes Numériques Appliquées

Soit l’équation f(x)=0 dont on cherche la solution sur un intervalle [a,b], on commence par un
tracé grossier de la fonction sur l’intervalle donnée puis on isole chaque racine dans un sous
intervalle le plus étroit possible. La [Link] dessous montre le tracé d’une fonction f qui
coupe l’axe des x en trois points, c’est-à-dire que l’équation f(x)=0 possède trois racines, on
note les racines exactes par 𝒙̅𝟏, 𝒙̅𝟐 et 𝒙̅𝟑.

On remarque que la fonction est continue sur chaque sous intervalle, aussi chaque sous
intervalle :
• Englobe une seule racine tel que 𝒙̅𝟏 ∈ [𝒂, 𝒃], 𝒙̅𝟐 ∈ [𝒂′, 𝒃] et ̅𝟑 ∈ [𝒂’’, 𝒃’’].
• Vérifie la condition 𝒇(𝒂)𝒇(𝒃) < 𝟎, 𝒇(𝒂′)𝒇(𝒃′) < 𝟎 𝐞𝐭 𝒇(𝒂’’)𝒇(𝒃’’) < 𝟎.
La forme de l’équation f(x)=0 peut être compliquée, dans ce cas s’il est possible de la
décomposer en deux parties simples g(x)=h(x).
Par exemple (𝒙) = 𝐥𝐧(𝒙) − 𝒙𝟐 + 𝟐 = 𝟎, qui est assez compliqué pour le tracé, peut être
décomposée en :
(𝒙) = 𝒉(𝒙) avec 𝒈(𝒙) = 𝐥𝐧(𝒙) 𝐞𝐭 𝒉(𝒙) = 𝒙𝟐 – 𝟐
Le tracé de g et h est très simple, la solution de f(x)=0 se situe à l’intersection de g et h.
Ensuite, on projette les points des intersections sur l’axe des x et on localise les racines. On
peut facilement vérifier les intervalles trouvées en calculant (𝒂𝒊)𝒇(𝒃𝒊) < 𝟎.
On remarque que la fonction est continue sur chaque sous intervalle, aussi chaque sous
intervalle :

5
Chapitre 1-Methodes Numériques Appliquées

• Englobe une seule racine tel que 𝒙̅𝟏 ∈ [𝒂, 𝒃], 𝒙̅𝟐 ∈ [𝒂′, 𝒃] et ̅𝟑 ∈ [𝒂’’, 𝒃’’].
• Vérifie la condition 𝒇(𝒂)𝒇(𝒃) < 𝟎, 𝒇(𝒂′)𝒇(𝒃′) < 𝟎 𝐞𝐭 𝒇(𝒂’’)𝒇(𝒃’’) < 𝟎.
La forme de l’équation f(x)=0 peut être compliquée, dans ce cas s’il est possible de la
décomposer en deux parties simples g(x)=h(x).
Par exemple (𝒙) = 𝐥𝐧(𝒙) − 𝒙𝟐 + 𝟐 = 𝟎, qui est assez compliqué pour le tracé, peut être
décomposée en :
(𝒙) = 𝒉(𝒙) avec 𝒈(𝒙) = 𝐥𝐧(𝒙) 𝐞𝐭 𝒉(𝒙) = 𝒙𝟐 – 𝟐
Le tracé de g et h est très simple, la solution de f(x)=0 se situe à l’intersection de g et h.
Ensuite, on projette les points des intersections sur l’axe des x et on localise les racines. On
peut facilement vérifier les intervalles trouvées en calculant (𝒂𝒊)𝒇(𝒃𝒊) < 𝟎.

B-2- Principe de la méthode de Newton-Raphson

C’est la méthode la plus efficace et la plus utilisée, elle repose sur le développement de
Taylor. Si f(x) est continue et continument dérivable dans le voisinage de 𝒙̅ solution exacte de
f(x)=0, alors le développement en série de Taylor autour d’un estimé 𝒙𝒏 proche de 𝒙̅ s’écrit :
(𝑥̅ −𝑥𝑛 ) (𝑥̅ −𝑥𝑛 )2
𝑓(𝑥̅ ) = 𝑓(𝑥𝑛 ) + 𝑓 ′ (𝑥𝑛 ) + 𝑓 ′′ (𝑥𝑛 ) + ⋯ (14)
1! 2!

Si 𝒙𝒏 est un estimé proche de 𝒙̅, alors le carré de l’erreur 𝜺𝒏 = 𝒙̅ − 𝒙𝒏 et les termes de degrés
supérieurs sont négligeable. Sachant que (𝒙̅) = 𝟎 on obtient la relation approximative :
𝒇(𝒙𝒏) + (𝒙̅ − 𝒙𝒏)𝒇’(𝒙𝒏) ≈ 𝟎
𝑓(𝑥 )
Donc 𝑥̅ = 𝑥𝑛 − 𝑓′(𝑥𝑛 )
𝑛

On peut écrire la (𝒏 + 𝟏)𝒎𝒆 itération approximant 𝑥̅ par :

𝑓(𝑥 )
𝑥𝑛+1 = 𝑥𝑛 − 𝑓′ (𝑥𝑛 ) 𝑛 = 0,1,2, (15)
𝑛

Cette suite, si elle converge, doit converger vers la solution 𝒙̅ de f(x)=0. On remarque que
f’(x) doit être non nulle.

B-3- Critère de convergence de la méthode de Newton-Raphson

Soit une fonction f définie sur [a,b] telle que :
i. 𝒇 (𝒂) 𝒇 (𝒃) < 𝟎
ii. 𝒇’(𝒙) 𝒆𝒕 𝒇’’(𝒙) sont non nulles et gardent un signe constant sur l’intervalle donné.

B-4- Critère d’arrêt de calcul pour la méthode de Newton-Raphson

6
Chapitre 1-Methodes Numériques Appliquées

Si la condition de convergence est vérifiée, le procédé itératif doit converger.

Cela veut dire que chaque nouvelle itération est meilleure que la précédente, de ce fait on peut
dire que si on a une précision 𝜺, on arrête le calcul lorsque la différence absolue entre deux
approximations successives est inférieure à la précision donnée.
C’est-à-dire :
|𝒙𝒏+𝟏 – 𝒙𝒏 | ≤ 𝜺 (16)
Si cette condition est vérifiée on prend 𝒙𝒏+𝟏 comme solution de f(x)=0.

Exemple :
Trouver la première racine de l’équation f(x) = ln(x) − 𝑥 2 + 2 = 0 qui appartient à [0.1, 0.5]
avec une précision ε=0.0001. On calcule la dérivée première et seconde de f et on vérifie les
conditions de convergence.
1
On a : 𝑓́ (𝑥) = 𝑥 − 2𝑥 qui est strictement décroissante et positive sur l’intervalle donné.
1
𝒇’(𝒙) > 𝟎 et 𝒇’’(𝒙) = 𝑓 ′′ (𝑥) = − 𝑥 2 − 2, 𝑓"(𝑥) < 0 sur l’intervalle donné. La condition de
𝑓(𝑥 ) 2 +2
ln(𝑥𝑛 )−𝑥𝑛
convergence est vérifiée. On écrit donc : 𝑥𝑛+1 = 𝑥𝑛 − 𝑓′ (𝑥𝑛 ) = 𝑥𝑛 − 1
𝑛 −2𝑥𝑛
𝑥𝑛

(n=0,1,2,…..).

Commençons x0=0.3 le milieu de l’intervalle initial donné :

ln(𝑥0 )−𝑥02 +2
𝒏 = 𝟎, 𝑥1 = 𝑥0 − 1 = 0.0417
−2𝑥0
𝑥0

On calcule |𝑥1 − 𝑥0| > 𝜀 ;

On continue 𝒏 = 𝟏, 𝒙𝟐 = 0.0910.
On calcule |𝑥2 − 𝑥1| > 𝜀
On continue 𝒏 = 𝟐, 𝒙𝟑 = 0.1285.
On calcule |𝑥3 − 𝑥2| > 𝜀 ;
On continue 𝒏 = 𝟑, 𝒙𝟒 = 0.1376.
On calcule |𝑥4 − 𝑥3| > 𝜀
On continue 𝒏 = 𝟒, 𝒙𝟓 = 0.1379.
On calcule |𝑥5 − 𝑥4| > 𝜀
On continue 𝒏 = 𝟓, 𝒙𝟔 = 𝟎. 𝟏𝟑𝟕𝟗. La solution est 𝒙5 = 𝟎. 𝟏𝟑𝟕𝟗