Inversion par la méthode de Kramer |
La méthode la plus connue pour inverser une matrice de taille raisonnable est la méthode des sous matrices dite méthode de Kramer. Cette méthode fait appel aux déterminants des sous matrices de la matrice transposée (on remplace l’élément i,j de trans(M) par (-1)^(i+j) * (le déterminant de trans(M) sans la ligne i et la colonne j).
Rappel à l’ordre 2 :
[ |
M11 |
M12 |
] | [ |
M22 |
- M12 |
] | ||||
M = |
[ |
] | inv(M) = 1/det(M) |
[ |
] | ||||||
[ |
M21 |
M22 |
] | [ |
- M21 |
M11 |
] |
Rappel à l’ordre 3 :
[ |
M11 |
M12 |
M13 |
] | [ |
M22 M33 - M23 M32 |
- M12 M33 + M13 M32 |
M12 M23 - M13 M22 |
] | ||
M = |
[ |
M21 |
M22 |
M23 |
] | inv(M) = 1/det(M) |
[ |
-M21 M33 + M23 M31 |
M11 M33 - M13 M31 |
-M11 M23 + M13 M21 |
] |
[ |
M31 |
M32 |
M33 |
] | [ |
M21 M32 - M22 M31 |
-M11 M32 + M12 M31 |
M11 M22 - M12 M21 |
] |
Avant de vous lancer dans la programmation de cet algorithme, vous devez, bien entendu, disposer de procédures de suppression d'une ligne et de suppression d'une colonne ainsi que la fonction de calcul du déterminant.
Votre procédure d'inversion doit être opérationnel quelle que soit la taille de la matrice.
Calculer la complexité de cette algorithme en termes d'opérations élémentaires de type multiplication.