CHAPITRE I
METHODES DE RESOLUTION DIRECTE ET APPROXIMATIVES DES
SYSTEMES D’EQUATIONS LINEAIRES
I. Introduction :
Les systèmes d'équations sont utilisés pour représenter des problèmes physiques qui
impliquent l'interaction de diverses propriétés. Les variables du système représentent les
propriétés du système physique étudié, et les équations décrivent l'interaction entre les
différentes variables. Le système est plus facile à étudier quand les équations sont linéaires.
Souvent, le nombre d'équations est le même que le nombre de variables, et donc il est
probable qu'une solution unique existe.
Dans ce chapitre, nous examinons les méthodes directes et approximatives pour trouver la
solution d'un système d’équations linéaires à n équations et n inconnues. Les méthodes
directes sont celles qui donnent la solution exacte du système, tandis que les méthodes
itératives donnent la solution approchée du système.
II. Méthodes directes :
II.1. Méthode de Gauss :
La méthode l'élimination de Gauss est la méthode la plus utilisée pour déterminer
systématiquement la solution d'un système d'équations linéaires. Les variables sont éliminées
à partir de toutes les équations jusqu'à ce qu’une seule équation implique une seule variable,
puis une deuxième équation qui comporte seulement deux variables et ensuite une troisième
équation à seulement trois variables et ainsi de suite. La solution sera trouvée en résolvant
l'équation de variable unique, puis la seconde équation contenant deux variables et ainsi de
suite, jusqu'à ce que les valeurs de toutes les variables soient déterminées.
On suppose que la matrice A est de taille n n et le système linéaire résultant sera :
AX B (1)
Admettons que :
Ce système (1) admet une solution unique ;
La matrice A est non singulière, c'est-à-dire : A existe ;
1
Le déterminant de la matrice A est non zéro, c'est-à-dire : det A 0 .
Les trois opérations essentielles de cette méthode peuvent être résumées dans l’algorithme
suivant :
L’équation Ei peut être multipliée par une constante non nulle λ, et l'équation
résultante sera utilisée à la place de l’équation Ei . Cette opération est notée par :
Ei Ei ;
L’équation E j peut être multipliée par une constante λ, et sera rajoutée à l'équation
Ei , et l'équation résultante sera utilisée à la place de l’équation Ei . Cette opération est
notée par : Ei E j Ei ;
Equations Ei et E j peuvent être transposées dans l'ordre. Cette opération est notée
par : Ei E j .
Pr. Guenfoud S. Chapitre I 1
Exemple 1 :
Déterminer la solution du système d’équations linéaire suivant en utilisant la méthode
d’élimination de Gauss ?
E1: x1 + x2 +3x4 =4,
E2: 2x1 + x2 − x3 + x4 =1,
E3: 3x1 − x2 − x3 +2x4 =−3,
E4: −x1 +2x2 +3x3 − x4 =4,
1 1 0 3 x1 4
2 1 1 1 x 2 1
3 1 1 2 x3 3
1 2 3 1 x 4 4
Premièrement on utilise l’équation E1 pour éliminer l’inconnue x1 des équations E2, E3, E4
en effectuant le suivant : (E2-2E1) →(E2), (E3-3E1)→(E3), et (E4+E1)→(E4). Le système
résultant sera :
E1: x1 + x2 +3x4 =4,
E2: 0x1− x2 − x3 − 5x4 = −7,
E3: 0x1− 4x2 − x3 − 7x4 = −15,
E4: 0x1+3x2 +3x3 +2x4 =8,
1 1 0 3 x1 4
0 1 1 5 x 2 7
0 4 1 7 x3 15
0 3 3 2 x 4 8
Pour simplicité, les nouvelles équations sont encore notées par E1, E2, E3, et E4. Dans le
nouveau système, E2 est utilisée pour éliminer x2 de l'équation E3 et E4 en effectuant le
suivant : (E3-4E2)→(E3) et (E4+3E2)→(E4), ce qui donne :
E1: x1 + x2 +3x4 =4,
E2: 0x1−x2 − x3 − 5x4 = −7,
E3: 0x1+0x2+3x3 +13x4 =13,
E4: 0x1+0x2+0x3−13x4 = −13.
1 1 0 3 x1 4
0 1 1 5 x 2 7
0 0 3 13 x3 13
0 0 0 13 x 4 13
Le système d'équations est maintenant sous forme triangulaire et peut être résolu pour
déterminer les inconnues x1, x2, x3, x4 par un processus en arrière-substitution.
Ce qui donne : E4 implique : x4=1 ;
E3 implique : x3=1/3*(13−13x4)=1/3(13−13)=0 ;
E2 implique : x2=-(-7+5x4+x3)=-(-7+5+0)=2 ;
E1 implique : x2=4-3x4-x2=4-3-2=-1 ;
Pr. Guenfoud S. Chapitre I 2
Exemple 2 :
Soit le système linéaire suivant :
La matrice augmentée est :
Effectuant les opérations :
On obtient :
L'élément a22 dans cette matrice est égal à zéro, donc la procédure ne peut pas continuer dans
sa forme actuelle. Mais les opérations de la forme (Ei)↔(Ep) sont autorisées. Puisque a32≠0,
l'opération (E2)↔(E3) est effectuée pour obtenir une nouvelle matrice:
On remarque que la variable x2 est déjà éliminée de l’équation E3 et dans l’équation E4, mais
les calculs continuent avec l'opération (E4+2E3)→(E4), ce qui donne :
Enfin, l’arrière-substitution est appliquée:
Pr. Guenfoud S. Chapitre I 3
Exemple 3 :
Déterminer la solution des deux systèmes d’équations linéaires en utilisant la méthode
d’élimination de Gauss ?
La solution de ces deux systèmes est :
III. Méthodes itératives :
La technique itérative pour la résolution des systèmes d’équations linéaires Ax=b, tel que le
système est de taille n×n, commence par une approximation initiale x(0) à la solution x et
génère une séquence de vecteurs x x k 1 qui converge vers x. Ces techniques itératives
impliquent un processus qui convertit le système Ax=b en un système équivalent de la forme
x=Tx+c où T est une matrice de taille n×n et c est un vecteur.
Après avoir choisi le vecteur initial x(0), la séquence de vecteurs de solutions approchées est
générée par le calcul :
x k T x k 1 c , k 1,2, (2)
III.1. Méthode de Jacobi :
L’algorithme de cette méthode est donné par :
n
a x bi
xi ij j , i 1,2, , n (3)
j 1 aii aii
j i
Exemple :
Soit le système linéaire suivant :
Ce système possède la solution exacte suivante : x=(1, 2, 1, 1)t .
Pour convertir ce système de forme : Ax=b en un système sous forme : x=Tx+c, on résout
l'équation Ei pour chaque xi, c'est-à-dire :
Pr. Guenfoud S. Chapitre I 4
Donc la forme x=Tx+c est obtenue où :
,
Pour une approximation initiale : x(0)=(0, 0, 0, 0), on trouve x(1) :
Des itérations supplémentaires sont générées d'une manière similaire et les résultats sont
présentés dans le tableau, ci-dessous. La décision d'arrêter le processus itératif après 10
itérations a été basée sur le critère que : x 10 x 9 0 .
III.2. Méthode de Gauss-Seidel :
Une modification de la méthode itérative de Jacobi (exprimée par la formule (3)) permet
d’accélérer le processus itératif de manière significative. Cette manière est connue comme
étant la méthode de Gauss-Seidel.
Dans ce cas l’algorithme de cette méthode est le suivant :
1 i 1
n
xi k aij x j aij x j
k k 1
bi (4)
aii j 1 j i 1
Exemple 1 :
Soit le système linéaire suivant :
D’après (4), on pourra écrire :
Pr. Guenfoud S. Chapitre I 5
En partant du vecteur initial : x(0)=(0, 0, 0, 0)t, on trouve :
A noter que la méthode de Jacobi nécessite deux fois d'itérations, dans ce même l'exemple,
pour une même précision par rapport à la méthode de Gauss-Seidel.
Exemple 2 :
Soit le système linéaire suivant :
Utiliser la méthode Jacobi et la méthode de Gauss-Seidel pour trouver la solution de ce
système d’équations linéaire ? x(0)=(1, 1, 1)t,
La solution est {0.9 ; -0.8 ; 0.7}.
III.3. Méthode de la Relaxation :
La méthode de relaxation est similaire aux méthodes de Jacobi et de Gauss-Seidel, mais elle
utilise un facteur de relaxation en vue de réduire plus rapidement l'erreur d'approximation.
Cette méthode est considérée comme étant la méthode la plus récente en matière de résolution
approximative des systèmes d’équations linéaires.
Son algorithme est donné par :
i 1 n
xik 1 xik 1 bi aij x jk a ij x jk 1 (5)
aii j 1 j i 1
: est un facteur scalaire.
On constate, d’après (5), que lorsque ω=1, cette méthode devient la méthode de Gauss-Seidel.
Lorsque 0<ω<1, la méthode s’appelle méthode de sous-relaxation et peut être utilisée pour
obtenir la convergence de certains systèmes qui ne sont pas convergents par la méthode de
Gauss-Seidel.
Lorsque 1<ω, la méthode s’appelle méthode de sur-relaxation, dans ce cas elle serve à
accélérer la convergence des systèmes qui sont convergent par la méthode de Gauss-Seidel.
Pr. Guenfoud S. Chapitre I 6
Exemple :
Soit le système linéaire suivant :
Ce système admet la solution exacte : x=(3, 4, -5)t.
Prenons ω=1,25 pour résoudre ce système par la méthode de relaxation et aussi par la
méthode de Gauss-Seidel en partant du vecteur initial suivant : x(0) = (1, 1, 1)t pour les deux
méthodes.
Selon la méthode de Gauss-Seidel, on peut écrire :
Selon la méthode de relaxation, on peut écrire :
Après plusieurs itérations, on obtient :
On constate que la précision obtenue par la méthode de relaxation est beaucoup mieux par
rapport à celle obtenue par la méthode de Gauss-Seidel.
Remarque :
La question qui se pose est de savoir comment choisir la valeur de ω ?
Bien que pas de réponse complète à cette question, mais généralement elle est prise : 0<ω<2.
Pr. Guenfoud S. Chapitre I 7
Exemple 2 :
Déterminer la solution des deux systèmes d’équations linéaires en utilisant la méthode de
relaxation ? Prenez : ω=1.1 et x(0)=(0, 0, 0)t.
Pr. Guenfoud S. Chapitre I 8
