Existe-t-il un moyen simple d’inverser une matrice triangulaire (supérieure ou inférieure)?

Question

J'essaie d'implémenter des opérations élémentaires d'algèbre linéaire, dont l'une est l'inversion d'une matrice triangulaire (supérieure et / ou inférieure). Existe-t-il un algorithme simple et stable pour le faire?

Merci.

Answer 1

Oui, utilisez la substitution de retour . Un algorithme standard pour inverser une matrice consiste à trouver sa décomposition en LU (décomposition en une matrice inférieure-triangulaire et une matrice supérieure-triangulaire), d'utiliser une substitution en arrière sur les pièces triangulaires, puis de combiner les résultats pour obtenir l'inverse de la matrice d'origine.

Answer 2

Ne l'inversez pas si vous le pouvez. C’est l’un des commandements de base de l’algèbre linéaire numérique.

Il est beaucoup plus rapide et numériquement plus stable de garder la matrice L en mémoire et de calculer

inv(L)b

avec une substitution en arrière chaque fois que vous avez besoin de faire autre chose avec inv (L).

Notez que l'algorithme habituel pour l'inverser nécessite la résolution des systèmes

inv(L)[1 0 0 ...],
inv(L)[0 1 0 ....],
inv(L)[0 0 1 ....]

, etc., il est donc beaucoup plus facile de ne pas l'inverser du tout.

Answer 3

Étant donné une matrice triangulaire inférieure L, la substitution de substitution vous permet de résoudre le système. L x = b rapidement pour n'importe quel côté droit b.

Pour inverser L, vous pouvez résoudre ce système pour les côtés droits e1 = (1,0, ..., 0), e2 = (0,1, ..., 0), ..., en = (0,0, ..., 1) et combinez les vecteurs de solution résultants en une seule matrice (nécessairement de type triangulaire inférieur).

Si vous êtes intéressé par une solution de forme fermée, les éléments diagonaux de l'inverse sont les inverses des éléments diagonaux d'origine, et la formule pour le reste des éléments de l'inverse devient de plus en plus compliquée à mesure que vous vous déplacez. de la diagonale.

Answer 4

Si vous parlez de réels à simple précision, consultez le code source des routines LAPACK STRTRI et STRTI2 .

Answer 5

Wow, c'est pratiquement la moitié du contenu d'un cours d'analyse numérique. Les algorithmes standard le feront, et il y a un tas de code en conserve ici . . Recettes numériques constitue la source ultime de ce problème d'analyse numérique et de la plupart des problèmes habituels.