Leçon2 : Méthodes de résolution des systèmes linéaires

Leçon2 : Méthodes de
résolution des systèmes II
linéaires

Objectifs
Le but de cette leçon est de donner quelques méthodes utiles pour la résolution des systèmes linéaires. Il
s'agit en particulier de quelques méthodes directes et indirectes(itératives).

1. Méthodes directe de résolution des systèmes linéaires

Position du problème

Dans ce chapitre, nous considérons un système d'équations linéaires d'ordre de la forme où

est une matrice inversible, et sont
des vecteurs colonnes.

Alors devient

Le système linéaire peut s'écrire explicitement sous la forme :

Remarque
Si la matrice associée au système est triangulaire supérieure (resp. inférieure), on dira que est
triangulaire supérieure (resp. inférieure).

9
 Méthodes directe de résolution des systèmes linéaires

Méthode de Gauss

La méthode de Gauss consiste à transformer le système à un système équivalent où est une

matrice triangulaire supérieure (resp. inférieure). La résolution de ce dernier donne :

Algorithme d'élimination de Gauss

On pose et

Alors

A la première étape : si (sinon, on fait une permutation de lignes) ; on fait les affectations suivantes :

où

On obtient donc :

où

A la étape ( ) si (sinon on fait une permutation de lignes) ; on fait les

affectations suivantes :

où

On obtient par la suite :

10
 Méthodes directe de résolution des systèmes linéaires

On a donc :

et

En réitérant -fois l'opération, on obtient :

avec

triangulaire supérieure et

Remarque

1. Les sont appelés "pivots" de la méthode de Gauss.

2. La méthode de Gauss permet de calculer par où est le nombre

de permutation.
3. La méthode de Gauss sans permutation de lignes s'appelle "Gauss ordinaire".
4. Dans la triangulation, si l'on trouve que l'un au moins des on permute la ligne du pivot avec
une ligne supérieure dont l'élément de la colonne est non nul.

Exemple : Méthode de Gauss

Soit le système suivant :

avec et

1. étape : élimnation de Gauss : on forme le système triangulaire supérieur équivalent en éliminant

tous les termes situés sous la diagonale du système
2. étape -rémontée : on résout le système triangulaire supérieur comme, on vient de le faire pour le
système précédent et on trouve :

11
 Méthodes directe de résolution des systèmes linéaires

Méthode de la décomposition LU

Principe de la méthode

- étape : Décomposer la matrice de façon à la mettre sous la forme où est une matrice
unitaire triangulaire inférieure et est une matrice triangulaire supérieure.
- étape : Résolution : Le système devient :

La résolution du système révient à la résolution de deux systèmes triangulaires.

Théorème

Soit une matrice ayant pour sous matrices principales de alors il existe

une matrice triangulaire inférieure telle que et une matrice triangulaire supérieure telle
que De plus, cette décomposition est unique.

Détermination des matrices L et U

Connaissant on écrit l'égalité

En résolvant le système dans le cas particulier ( ), on constate que la détermination des éléments
et se fait grâce à l'algorithme suivant :

Principe de résolution

Supposons que l'on veut résoudre le système linéaire . Décomposons A sous la forme LU. Alors
ou encore Posons On cherche alors tel que soit un
système triangulaire inférieur à résoudre par méthode descendente. étant trouvé, on cherche tel que
est un système triangulaire supérieure qu'on résoud par la méthode ascendente.

Exemple : Considérons la matrice de l'exemple précédent.

1. étape : déconposition de sous la forme

Posons et

Alors et

12
 Méthodes directe de résolution des systèmes linéaires

On a donc,

De plus, on a et

et

Finalement : et

Donc

2. Etape : Résolution
Le système devient :

Pour la suite, on résout d'abord le système triangulaire inférieur et on trouve :

ensuite, on résout le système triangulaire supérieure On trouve alors

Méthode de Choleski

Dans ce paragraphe, on suppose que la matrice donnée dans (1) est symétrique définie positive.

Principe de la méthode

Pour résoudre le système on procède par les étapes suivantes :

1. Décomposition de avec triangulaire inférieure à éléments diagonaux positifs.

2. Résolution du système triangulaire inférieur :
3. Résolution du système triangulaire supérieur :

13
 Méthodes itératives (indirectes) pour la résolution de systèmes linéaires

Théorème (décomposition de Choleski)

Soit une matrice symétrique définie positive. Alors, il existe une unique matrice
telle que :

1. est triangulaire inférieure.

2.
3.

2. Méthodes itératives (indirectes) pour la résolution de systèmes linéaires

Définition

On appelle méthode itérative de résolution du système (1), une méthode qui construit une suite où
l'itérée est calculée à partir des itérées ) de vecteurs de censée converger vers
solution de

Définition
Une méthode itérative est dite :

1. consistante si la limite de la suite lorsqu'elle existe, est solution de

2. converge si pour toute valeur initiale on a

Remarque
La consistance d'une méthode n’entraîne pas la convergence de cette méthode.

Exemple

Soit Cette méthode est consistante car donc s'il

existe une limite, ça ne peut être que . Mais, il est évident que cette méthode diverge.

Dans tout ce qui suit, on s'intéressera aux schémas itératives classiques de la forme :

où et

Proposition

La méthode est consistante si et seulement si et sont inversibles.

Proposition

Si la méthode est consistante, alors elle converge si et seulement si dans

Proposition

Soit . Alors où est le rayon spectral de

14
 Méthodes itératives (indirectes) pour la résolution de systèmes linéaires

Méthode de décomposition

On se propose de construire une matrice et un vecteur de sorte que la méthode itérative converge vers
a solution de l'équation

A toute décomposition de la matrice sous la forme où est inversible, on peut

associer la méthode itérative suivante :

quelconque. En effet, s'écrit aussi Cette

méthode est du type avec et

Proposition

Soit inversible et une décomposition de où est inversible. La condition

nécessaire et suffisante pour que le schéma converge est la solution et

Proposition

La méthode converge si et seulement si

Théorème

Soit inversible et Hermitienne. Soit une décomposition de sous la forme

est inversible) telle que soit définie positive. Alors le schéma est
convergent si et seulement si est définie positive.

Théorème

Soit une matrice à diagonale strictement dominante :

Alors la méthode de Jacobi converge.

Méthode de Gauss-Seidel

Ici, on pose avec et et on suppose que est inversible, i.e :

Alors le schéma devient :

La matrice est appelée matrice de

Gauss-Seidel associée à la matrice

A partir des composantes, l'algorithme de la méthode de Gauss-Seidel ponctuelle s'écrit de la manière

suivante :

15
 Exercices

Théorème

Soit matrice à diagonale strictement dominante :

Alors la méthode de Gauss-Seidel converge.

Méthode de relaxation successive

Soit le système linéaire La méthode de relaxation successive consiste à poser avec

Supposons que est inversible, ie : Alors, le schéma numérique devient :

La matrice est appelée matrice de relaxation successive associée

à

Remarque

Si est le vecteur donné par la méthode de Gauss-Seidel, alors la méthode de relaxation s'écrit :

C'est donc une moyenne pondérée avec la méthode de Gauss-Seidel.

Complément
- Si on a la méthode de sous-relaxation.
- Si on retrouve la méthode de Gauss-Seidel
- Si on a la méthode de sur-relaxation.

Lemme

Soit alors on a

Corollaire

Une condition nécessaire et suffisante pour que la suite de relaxation converge est que

Théorème

Si est Hermitienne définie positive, la méthode de relaxation successive converge si et

seulement si

16
 Exercices

3. Exercices
Exercice 1

Résoudre le système linéaire suivant par la méthode de Gauss

Exercice 2

Soit le système linéaire suivant :

1. Résoudre le système par la méthode du pivot de Gauss.

2. Ecrire le système sous la forme où et
3. Calculer et résoudre par la méthode Cramer.

Exercice 3

Soit la matrice suivante

1. Déterminer la décomposition de

2. Résoudre le système linéaire où est la première colonne de et

Exercice 4

Pour entier on définit la matrice tridiagonale d'ordre

1. Calculer la factorisation de la matrice

2. Calculer la factorisation de la matrice

17
 Exercices

Exercice 5

Effectuer la factorisation de Cholesky de la matrice

Exercice 6

Supposons que les nombres sont représentés en virgule flottante dans une base décimale avec chiffres
significatifs et que le résultat des opérations est arrondi à chiffres significatifs. Soit le système linéaire
avec

et

1. Résoudre par la méthode d'élimination de Gauss en choisissant comme premier pivot

2. Résoudre par la méthode d'élimination de Gauss en choisissant comme ligne pivot à la première étape,
la deuxième ligne.
3. Conclure.

Exercice 7

Soit la méthode itérative où est une matrice inversible.

Si la matrice d'itération a le rayon spectral nul, montrer qu'il existe un entier tel que

En déduire qu'il s'agit d'une méthode directe (i.e. la solution est obtenue en un nombre fini d'itérations).

Exercice 8

Pour donné, on considère la matrice définit par :

1. Ecrire la matrice de la méthode itérative de Jacobi. Pour quelles valeurs de cette méthode converge-
t-elle ?
2. Ecrire la matrice de la méthode itérative de Gauss-Seidel. Pour quelles valeurs de la méthode de
Gauss-Seidel converge-t-elle ?

18
 Exercices

Exercice 9

Soit une matrice symétrique définie positive, montrer que la méthode de Jacobi appliquée à la
matrice converge.

Exercice 10

Soit une matrice à diagonale strictement dominante.

1. Démontrer que la méthode de Jacobi converge.

2. Démontrer que la méthode de Gauss-Seidel converge.

Exercice 11

Soit (respectivement ) la matrice d'itération de la méthode itérative de Jacobi (respectivement Gauss-

Seidel) pour la résolution du système linéaire

Le but de cet exercice est de montrer (sur des exemples) qu'en toute généralité, les deux méthodes ne sont pas
comparables.

1. Soit

Écrire les itérations de Jacobi et de Gauss Seidel et montrer que

2. Soit

Écrire les itérations de Jacobi et de Gauss Seidel et calculer et Qu'en déduit-on ?

19