Chapitre I : Rappels sur les systèmes d’équations linéaires - Inversion de matrices

1. Position du problème

2. Méthode du pivot
    2.1. Méthode de GAUSS-JORDAN
    2.2. Méthode de GAUSS
    2.3. Cas des matrices bandes

3. Méthodes itératives
    3.1. Méthode de JACOBI
    3.2. Méthode GAUSS-SEIDEL
    3.3. Facteur de relaxation

4. Inversion de matrices
 

1. Position du problème

Considérons le système linéaire suivant de n équations à n inconnues :

Ce système s’écrit sous la forme : 
 

si  ,  et

i représente le numéro de ligne et j le numéro de colonne.
Une matrice est dite triangulaire si  pour j>i ou pour i>j. Une matrice bande est une matrice dont tous les éléments sont nuls sauf sur une bande autour de la diagonale principale. Ces matrices se rencontrent dans la résolution d'équations aux dérivées partielles par la méthode des différences finies ou dans la méthode des éléments finis.

La résolution du système précédent peut s’effectuer par deux méthodes :
- la méthode directe (dite méthode du pivot),
- la méthode itérative.

La méthode du pivot est commode pour les systèmes denses d’ordre supérieur, ainsi que pour les matrices bandes même d’ordre élevé. La méthode itérative est mieux adaptée aux autres matrices d’ordre élevé et comportant de nombreux éléments nuls.

2. Méthode du pivot

2.1. Méthode de GAUSS-JORDAN

2.1.1. Description de la méthode

C’est la méthode la plus utilisée. Pour la présenter, nous allons prendre l’exemple d’un système de 4 équations à 4 inconnues :

La méthode classique de Cramer qui repose sur les déterminants, donne :
où  est le déterminant de la matrice, et  celui déduit de  en y remplaçant la j^ème colonne par la colonne second membre.
Pour résoudre le système, cette méthode nécessite n⁴ opérations si n est le rang de la matrice.
Dans la méthode du pivot, on choisit successivement chaque ligne comme ligne pivot ; le pivot étant le 1^er élément non nul de la ligne.
 

Ainsi, on divise la ligne n° 1 du système par  :

On annule le 1^er terme de chacun des autres lignes : à la 2^ème ligne, on retranche la 1^ère multipliée par , à la 3^ème ligne, on retranche la 1^ère multipliée par , à la 4^ème ligne, on retranche la 1^ère multipliée par .
 

Le système devient :

a-     La 2^ème ligne est considérée maintenant comme une ligne pivot, et  comme un élément pivot. On répète sur cette 2^ème ligne les opérations précédentes, et on obtient après division de cette ligne par  :

On annule les autres termes de la seconde colonne ; c’est à dire : à la 1^ère ligne, on retranche la seconde multipliée par , à la 3^ème ligne, on retranche la 2^ème multipliée par , à la 4^ème ligne, on retranche la 2^ème multipliée par .
 

On obtient :

 a-     On considère ensuite la 3^ème ligne comme pivot, puis la 4^ème ligne ; ce qui donne :
 

soit la solution du système :

D’une manière générale, si on applique cette procédure au système  où A est une matrice d’ordre n,

•      on remarque qu’à l’issue de la 1^ère étape, on obtient la matrice  comportant des 0 et un 1 dans sa 1^ère colonne,
•      à l’issue de la 2^ème étape, on a une matrice  comportant des 0 et des 1 dans ses 2 premières colonnes, etc.
•      à l’issue de la k^ième étape, on obtient un système de la forme :  avec  et  matrice colonne d’éléments 

Pour les k premiers éléments diagonaux, on a :  si 
Pour les colonnes 1 à k éléments non diagonaux, on a : si  et ;  étant les composantes du vecteur .
L’étape suivante consiste à prendre  comme élément pivot.
On divise la (k+1) ième ligne par cet élément, ce qui donne pour j=k+1 à n :  et  si 

et 
Pour chaque ligne , la ligne k+1 multipliée par  est retranchée.

On obtient alors le système avec :

Résumé de la procédure :

1. Transformation de la matrice [A,y] en une matrice [I,y’] :  et 

Pour k variant de 0 à n-1, on a :

2. La solution x_i du système résultant s’écrit alors :  ; avec 

Le nombre d’opérations nécessaires au passage de [A ,y]^(k) à [A, y]^(k+1) est :
n. additions (= n.a) = n. multiplications (= n.m) = (n-1).(n-k+1)
n. divisions (= n.d) = (n-k+1)
Le passage de [A ,y] à [A, y]⁽ⁿ⁾ nécessite environ  opérations de calculs.

La méthode ainsi exposée, présente un certain nombre de défauts :

•  lenteur compte tenu du nombre d'opérations si le rang n de la matrice A est grand,
•  difficulté si le pivot est nul puisque la division n'est plus possible (dans ce cas, il faut permuter les colonnes tout en veillant à la cohérence des calculs qui suivent),
•  précision si le pivot est faible (<<1), les erreurs d’arrondi deviennent très importantes et affectent toute la suite des calculs.

2.1.2. Exemple
 

Soit le système à résoudre :

On forme tout d’abord la matrice [A, y] :

K=1 k=1
 
 

Normalisation

Réduction

K=2 k=2
 

Normalisation

Réduction

K=3 k=3
 

Normalisation

Réduction

La solution est  ; d’où : 

2.2. Méthode de GAUSS

On diagonalise la matrice A, et on ne fait apparaître les zéros qu’en dessous de la diagonale. La solution x_i du système nécessite 2 étapes :
 

Une triangularisation de la matrice A,

Pour k variant de 0 à n-1, on a : 

 

Une résolution du système triangulaire :

D’où l’expression de la solution finale :

avec j=n-1 à 1

Cette solution nécessite environ n³/3 opérations.
Pour les pivots nuls ou petits, on est confronté aux mêmes difficultés signalées dans la méthode précédente de GAUSS-JORDAN.

2.3. Cas des matrices bandes

Soit le système tridiagonal suivant :

 

La matrice est connue par les 3n données :

où

Ainsi, le système décrit par ces 3n données peut être résolu par la méthode de triangularisation (méthode de Gauss).

3. Méthodes itératives

Nous allons décrire ces méthodes brièvement sans passer par des calculs ou des démonstrations mathématiques complexes, car cela nous éloignera des objectifs du cours.

3.1. Méthode de JACOBI
 

Soit le système suivant de 3 équations à 3 inconnues :

On résout le système de la manière suivante :

On donne aux inconnues les valeurs arbitraires initiales , , .
Si ces valeurs sont portées au second membre de la solution précédente, on obtient :

Ce nouvel ensemble porté dans le second membre des équations précédentes donne un autre ensemble , , , et ainsi de suite.

3.2. Méthode de GAUSS-SEIDEL

On reprend le calcul comme précédemment. Pour le système précédent par exemple, on choisit un ensemble de valeurs , , .
 

On porte  et dans la 1ère équation et on obtient :

C’est cette nouvelle valeur de x₁, et non pas , qui est portée dans la 2^ème équation du système, donnant :

De même dans la 3^ème équation, on porte  et , et non  et , et on obtient :

Lorsqu’une inconnue est utilisée, c’est automatiquement la plus récente valeur calculée. Ceci assure une convergence des calculs bien plus rapide que la méthode de JACOBI.

On arrête les calculs lorsque les valeurs successives de x_j sont suffisamment voisines.
Pour cela, on peut utiliser,

•  soit le critère de Convergence absolue : 

soit le critère de Convergence relative :

Pour les systèmes où les matrices qui sont de rang élevé, il n’est pas commode de faire le test de convergence sur chaque inconnue x_j.
Dans ce cas, on fait le test soit seulement sur certaines inconnues que l'on choisit, soit les quantités suivantes :
 

ou

ou

ou

La convergence du procédé ne dépend pas du choix des valeurs initiales , mais seulement des valeurs des coefficients.
On montre que la convergence est assurée si on a, pour chaque valeur de i (c’est à dire pour chaque ligne), la relation est vérifiée.

Autrement dit, il y a convergence si chaque élément diagonal est supérieur ou égal, en module, à la somme des modules des autres éléments de sa ligne.

3.3. Facteur de relaxation
Si la convergence existe, sa rapidité dépend du choix de . En effet, plus les valeurs initiales sont proches des valeurs réelles, et plus la convergence est rapide.

L’utilisation d’un facteur de relaxation l définie par  où  permet d’accélérer la convergence.
l est appelée " facteur de relaxation " (dans la pratique, il est compris entre 0 et 2).

Pour , le processus diverge.

Pour s’approcher de la valeur recherchée rapidement, on prend  dans un processus itératif déjà convergent et  pour un processus divergent.

Les méthodes itératives jouent un rôle très important dans la résolution numérique de systèmes de grandes tailles et dans les systèmes (ou équations) non linéaires.

4. Inversion des matrices

Selon la méthode de Cramer, une matrice A de rang n n’est inversible que si son déterminant D est différent de zéro. Dans ce cas, le produit de A par la matrice inverse A^-1 donne la matrice unitaire I.

où 

En appliquant la méthode de Cramer sur la matrice A, on peut déterminer A^-1.

Exemple :
 
 

;

 

On obtient en utilisant la méthode de Cramer :

qui vérifie que :

L’algorithme de Gauss-Jordan présenté au début de ce cours (méthode du pivot) opère aussi le passage de la matrice C=[A,y] à la matrice D=[I,X] où X est la solution du système linéaire A.X=y ; Soit X =A^-1.y .

Après les opérations de l’algorithme de Gauss-Jordan, on obtient : D=A^-1.C=A^-1.[A,I]=[I,A^-1]
Cette méthode, de calcul de l’inverse d’une matrice qui est résumée ci-dessous, permet de calculer A^-1 avec un nombre d’opérations nettement inférieur à celui de la méthode de Cramer.
 

Transformation (A,I)  (I,A-1) Pour , on a : Pour    Pour

Exemple :
 

Soit la matrice

. Calculer A-1 par la méthode de Jordan.

k =1
 

Normalisation

;   Réduction

k =2
 

Normalisation

;   Réduction

k =3
 

Normalisation

;   Réduction

 
 

Finalement, on vérifie que :