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

• Pour une matrice régulière :
  • La méthode de Gauss-Jordan
  • La décomposition LU
  • La décomposition QR
  • La décomposition en valeurs singulières

• Pour une matrice symétrique définie positive :
  • La méthode de Cholesky

• Pour une matrice singulière :
  • La décomposition en valeurs singulières

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 b_i 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 :

Exemple avec n = 4 :

Le système devient :

soit :

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 :

Le système devient :

soit, en multipliant à gauche par Q^T :

soit :

puisque Q^TQ = 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 :

U et V sont des matrices orthogonales. S est une matrice diagonale. Ses termes diagonaux S_ii, 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.

• Si A est régulière, tous les S_ii sont > 0. La matrice inverse est donnée par :
  A^-1 = (USV^T)^-1 = (V^T)^-1 S^-1 U^-1 = V × diag(1/S_ii) × U^T

  (en se rappelant que l'inverse d'une matrice orthogonale est égale à sa transposée)

  On en déduit la solution du système par x = A^-1b

• Si A est singulière, les expressions précédentes restent valables à condition de remplacer, pour chaque valeur singulière nulle, le terme 1/S_ii par zéro.

  On montre que la solution ainsi calculée correspond :

  • dans le cas d'un système indéterminé, au vecteur de plus faible norme.
  • dans le cas d'un système impossible, à la solution des moindres carrés.

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 x^TAx est positif (Exemple en Statistiques : 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 :

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

Cette décomposition permet de :

• calculer la matrice inverse A^-1
• calculer det(A), égal au carré du produit des éléments diagonaux de L
• résoudre le système Ax = b selon un principe analogue à celui de la méthode LU.