Gibt es um eine einfache Möglichkeit, eine dreieckige (obere oder untere) Matrix zu invertieren?

Question

Ich versuche, einige grundlegenden Operationen des linearen Algebra zu implementieren und eine diese Operationen ist die Umkehrung eines dreieckigen (obere und / oder untere) Matrix. Gibt es einen einfachen und stabilen Algorithmus zu tun?

Danke.

Answer 1

Ja, verwenden Sie zurück Substitution . Ein Standard-Algorithmus, um eine Matrix zu invertieren ist, seine LU-Zerlegung (Zersetzung in einen unteren dreieckigen und einer oberen Dreiecksmatrix), verwenden zurück subsitution auf die dreieckigen Stücke, und dann verbinden die Ergebnisse zu erhalten, die Umkehrung der ursprünglichen Matrix zu finden.

Answer 2

Sie invertieren es nicht, wenn Sie können. Es ist eine der grundlegenden Gebote der numerischen linearen Algebra.

Es ist viel schneller und stabiler numerisch die Matrix L selbst im Speicher zu halten und berechnet

inv(L)b

mit Rücksubstitution, wann immer Sie benötigen etwas anderes mit inv zu tun (L).

Beachten Sie, dass der üblicher Algorithmus zum Umkehren es erfordert, dass die Systeme der Lösung

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

und so weiter, so dass Sie sehen, es ist viel einfacher, es gar nicht zu invertieren.

Answer 3

Bei einer unteren Dreiecksmatrix L, Rücksubstitution können Sie das System lösen L x B = schnell für jede rechte Seite b.

Um L zu invertieren, können Sie dieses System lösen für rechte Seiten e1 = (1,0, ..., 0), e2 = (0,1, ..., 0), ..., en = (0,0, ..., 1) und kombiniert die resultierende Lösung Vektoren zu einem einzigen (notwendigerweise unteren Dreiecks) Matrix.

Wenn Sie Interesse an einer Lösung in geschlossener Form sind, die Diagonalelemente der inversen sind die Umkehrungen der ursprünglichen Diagonalelemente und die Formel für den Rest der Elemente der inversen wird immer komplizierter, wie Sie aways bewegen von den diagonalen.

Answer 4

Wenn Sie mit einfacher Genauigkeit reellen Zahlen sprechen, einen Blick auf den Quellcode für die LAPACK Routinen STRTRI und STRTI2 .

Answer 5

Wow, das ist praktisch die Hälfte der Inhalt eines numerischen Analyse Kurs. Die Standard-Algorithmen werden es tun, und es gibt eine Reihe von Dosen Code hier . Die ultimative Quelle für diese und die meisten anderen üblichen numerischen Analyse Probleme ist Numerical Recipes .