Algorithme de Gauss

La décomposition se fait glocalement de la même manière que dans la section 6.5.2. Les matrices élémentaires seront :

Le calcul de l'inverse utilise la propriété suivante des matrices :

\begin{array}{rcl} {(A \times B)}^{- 1} & = & B^{- 1} \times A^{- 1} \end{array}

Par conséquent, le produit des

K

matrices élémentaires qui décomposent

A

de sorte que :

\begin{array}{rcl} A & = & \prod_{i = 1}^{K} G_{i} \end{array}

Permet de trouver immédiatement l'inverse :

\begin{array}{rcl} A^{- 1} & = & \prod_{i = 0}^{K - 1} G_{K - i}^{- 1} \end{array}

Le calcul est bien plus simple, car ces matrices sont soit orthogonales :

\begin{array}{rcl} Q^{- 1} & = & Q^{T} \end{array}

Soit diagonnales :

\begin{array}{rcl} D_{i, i}^{- 1} & = & \frac{1}{D_{i, i}} 1 \leq i \leq N \end{array}

Un dernier point, est qu'il n'y a pas besoin d'effectuer explicitement les multiplications car :

Les matrices de permutation échangent deux lignes ou deux colonnes entre elles (lecture et écriture de $2 N$ valeurs)
Les matrices d'échelle multiplient une ligne ou une colonne par une valeur (multiplication de $N$ valeurs)

Leur complexité est donc en

O (N)

Pour résumer :

On applique le pivot de Gauss sur notre matrice de départ $A$ jusqu'à ce que l'on obtienne la matrice unitaire
On applique les mêmes transformations sur la matrice unitaire, qui donnera $A^{- 1}$ à la fin de l'algorithme

Cela nous donne donc un algorithme avec une complexité en

O (N^{3})

ce qui est bien mieux que

O (N!)

Si l'algorithme du pivot de Gauss reste bloqué sur un

0

alors la matrice

A

n'a pas d'inverse et son déterminant est nul. Il n'est donc pas nécessaire de calculer sont déterminant en plus.