Résolution des systèmes d'équations linéaires

Dernière mise à jour : 14 Septembre 2006


Les principales méthodes de résolution des systèmes d'équations linéaires sont les suivantes :


I. Méthode de Gauss-Jordan

La méthode de Gauss-Jordan calcule simultanément la matrice inverse A-1 et le vecteur solution x. S'il y a plusieurs systèmes à résoudre, on peut réunir tous les vecteurs de termes constants bi dans une matrice unique B (chaque vecteur constituant une colonne de la matrice). L'application de l'algorithme de Gauss-Jordan fournit alors une matrice X dont la colonne i constitue la solution du ième système.

Cette méthode exige que tous les vecteurs de termes constants soient connus au moment d'appliquer l'algorithme. Si tel n'est pas le cas, ou si la matrice inverse n'est pas requise, il vaut mieux choisir la méthode LU qui est plus rapide.


II. Décomposition LU

Cette méthode exprime la matrice A sous forme du produit d'une matrice triangulaire inférieure L à diagonale unité par une matrice triangulaire supérieure U :

A = LU

Exemple avec n = 4 :

Le système devient :

LUx = b

soit :

Ly = b (1)

Ux = y (2)

On résout le système (1) pour trouver le vecteur y, puis le système (2) pour trouver le vecteur x. La résolution est facilitée par la forme triangulaire des matrices.

La méthode LU permet aussi de calculer le déterminant de A, qui est égal au produit des éléments diagonaux de la matrice U, puisque det(A) = det(L) × det(U) et det(L) = 1 (Rappelons que le déterminant d'une matrice triangulaire est égal au produit de ses éléments diagonaux).


III. Décomposition QR

Cette méthode exprime la matrice A sous forme du produit d'une matrice orthogonale Q par une matrice triangulaire supérieure R :

A = QR

Le système devient :

QRx = b

soit, en multipliant à gauche par QT :

QTQRx = QTb

soit :

Rx = QTb

puisque QTQ = I, la transposée d'une matrice orthogonale étant égale à son inverse.

On résout ce dernier système en tenant compte de la forme triangulaire de la matrice R.

Remarque : La décomposition QR peut s'appliquer à une matrice rectangulaire n × m (avec n > m). Dans ce cas, Q est de dimensions n × m et R de dimensions m × m. Dans le cas d'un système Ax = b, la solution retournée est celle des moindres carrés.


IV. Décomposition en valeurs singulières

La décomposition en valeurs singulières (SVD, Singular Value Decomposition) exprime la matrice A sous la forme :

A = USVT

U et V sont des matrices orthogonales. S est une matrice diagonale. Ses termes diagonaux Sii, tous positifs ou nuls, sont les valeurs singulières de A. Le rang de A est égal au nombre de valeurs singulières non nulles.

Remarque : Tout comme la décomposition QR, la décomposition en valeurs singulières peut s'appliquer à une matrice rectangulaire n × m (avec n > m). Dans ce cas, U est de dimensions n × m, S et V de dimensions m × m. Dans le cas d'un système Ax = b, la solution retournée est celle des moindres carrés.


V. Méthode de Cholesky

Une matrice symétrique A est dite définie positive si, pour tout vecteur x, le produit xTAx est positif (Exemple en régression linéaire : les matrices de variance-covariance ou les matrices des équations normales).

Pour une telle matrice, on montre qu'il est possible de trouver une matrice triangulaire inférieure L telle que :

A = LLT

L peut être considérée comme une sorte de "racine carrée" de A.

Cette décomposition permet de :



Retour au sommaire