6.6.2 : 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 :
- Les matrices de permutation
- Les matrices d'échelle
Le calcul de l'inverse utilise la propriété suivante des matrices :
$$\begin{eqnarray*} \left(A\times B\right)^{-1} & = & B^{-1} \times A^{-1} \end{eqnarray*}$$
Par conséquent, le produit des $K$ matrices élémentaires qui décomposent $A$ de sorte que :
$$\begin{eqnarray*} A & = & \prod^K_{i=1} G_i \end{eqnarray*}$$
Permet de trouver immédiatement l'inverse :
$$\begin{eqnarray*} A^{-1} & = & \prod^{K - 1}_{i=0} G^{-1}_{K - i} \end{eqnarray*}$$
Le calcul est bien plus simple, car ces matrices sont soit orthogonales :
$$\begin{eqnarray*} Q^{-1} & = & Q^T \end{eqnarray*}$$
Soit diagonnales :
$$\begin{eqnarray*} D^{-1}_{i, i} & = & \dfrac{1}{D_{i, i}} \quad 1 \leq i \leq N \end{eqnarray*}$$
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 $2N$ valeurs)
- Les matrices d'échelle multiplient une ligne ou une colonne par une valeur (multiplication de $N$ valeurs)
Leur complexité est donc en $O\left(N\right)$ .
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\left(N^3\right)$ ce qui est bien mieux que $O\left(N!\right)$ .
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.