6.5.2 : Déterminant par décomposition de Gauss

Comme le calcul classique a une complexité bien trop grande, nous devons trouver une alternative.

Cette alternative utilise la propriété suivante du déterminant des matrices :



$$\begin{eqnarray*} \det \left(A\times B\right) & = & \det \left(A\right) \times \det \left(B\right) \end{eqnarray*}$$

Il faut bien entendu que les déterminants des matrices $A$ et $B$ soient rapides à calculer.

Typiquement, si $\det \left(A\right) = 1$ et si la matrice $B$ est diagonale (ou triangulaire), nous obtenons :



$$\begin{eqnarray*} \det \left(B\right) & = & \prod^N_{i=1} B_{i, i} \end{eqnarray*}$$

Dans ce cas, la complexité du calcul du déterminant devient $O\left(N\right)$ .

Donc, si la matrice $A$ peut être décomposée en deux matrices $Q$ et $R$ respectivement orthogonale et triangulaire supérieure :



$$\begin{eqnarray*} A & = & Q\times R \end{eqnarray*}$$

Alors :

$$\begin{eqnarray*} \det \left(A\right) & = & \det \left(Q\right) \times \det \left(R\right) \\ & = & \prod^N_{i=1} R_{i, i} \end{eqnarray*}$$

Maintenant nous devons contruire les matrices $Q$ et $R$ .

  • La matrice $R$ s'obtient par l'algorithme du pivot de Gauss
  • La matrice $Q$ s'obtient par la multiplication de matrices de permutation élémentaires obtenu par les étapes du pivot de Gauss


L'algorithme de Gauss a une complexité de $O\left(N^3\right)$ ce qui est bien mieux que $O\left(N!\right)$ .