Der Gauß-Algorithmus zur Matrixinversion

• Die explizite Berechnung einer Matrixinversen ist eine eher seltene Aufgabe. Jedenfalls sollte man dies nicht benutzen, um ein lineares Gleichungssystem zu lösen. Gelegentlich kommt es aber dennoch vor, daß man die explizite Inverse oder doch Teile davon (z.B. die Diagonale) benötigt. Dann kann man die durch den Gauß-Algorithmus berechnete Matrixfaktorisierung auch zur Berechnung der Inversen benutzen, indem man entweder die Dreiecksfaktoren für sich invertiert und dann miteinander in umgekehrter Reihenfolge multipliziert, was bei geschickter Ausnutzung der Struktur auch einen Aufwand von n³+O(n²) ergibt, wie man es vom Gauß-Jordan-Verfahren kennt, oder indem man n Gleichungssysteme mit den Einheitsvektoren als rechter Seite löst. Hier benutzen wir den zweiten Weg.
• Zu einer regulären Matrix A wird eine Zerlegung in zwei Dreiecksmatrizen L (untere Dreiecksmatrix) und R (obere Dreiecksmatrix) berechnet mit PAQ = LR. P und Q sind dabei Permutationsmatrizen, entsprechen also Zeilen- und Spaltenvertauschungen in A.
• Realisiert wird die Zerlegung mittels Linearkombination einzelner Zeilen der Matrix A. Die Faktoren dieser Linearkombinationen füllen die Matrix L, die eine Diagonale (1,...,1) besitzt und R ist die resultierende obere Dreiecksmatrix.
• Verwendet man simultan als n rechte Seiten die Spalten der Einheitsmatrix I, so sind die n berechneten Lösungen die Spalten der Inversen von A.
• Um den Einfluß von Rundungsfehlern zu reduzieren kann durch Vertauschen einzelner Zeilen (Spalten-Pivotisierung) dafür gesorgt werden, daß der Betrag der Elemente der Matrix L kleiner oder gleich 1 ist. Ebenso kann man Spalten vertauschen. Diese Vertauschungen sind bei der Lösung entsprechend zu berücksichtigen, dies ist jedoch einfach.
• Bei einer Matrixinversion wirkt sich eine schlechte Kondition immer in der Genauigkeit aus, was bei einem einzelnen Gleichungssystem ja nicht notwendig der Fall ist.

Die Eingaben

• n ist die Dimension der quadratischen Matrix A und darf den Wert 11 nicht überschreiten.
• Es kann angegeben werden, ob ohne Pivotisierung, mit Spalten-Pivotisierung (Zeilentausch) oder mit Restmatrix-Pivotisierung (Zeilen- und Spaltentausch) gerechnet werden soll.
• Für eine gegebene Dimension kann zwischen verschiedenen Matrizen gewählt werden.
  
  1. Eine reell orthogonale Matrix A, (die zu ihrer Transponierten invers ist). Konditionszahl in der euklidischen Norm daher cond(A) = 1.
  2. Eine symmetrische Matrix A mit der Konditionszahl cond(A) = O(n²).
  3. Die (ganzzahlige) Inverse A einer Hilbertmatrix. D.h. die Eingabematrix ist also im Rechner exakt dargestellt. Die Hilbertmatrix selbst hat die Elemente 1/(i+j-1) in der Position (i,j), 1<=i,j<=n. Die Konditionszahl steigt bei dieser Matrix exponentiell mit der Dimension (cond(A) = O(e^3.5n)). Dies ist ''das'' Standardbeispiel für eine schlecht konditionierte Matrix und ein beliebtes Testbeispiel.
  4. Eine eigene Matrix A der Dimension n kann eingegeben werden. Es ist darauf zu achten, daß die Matrixelemente zeilenweise eingetragen werden und durch Leerzeichen bzw. Kommata getrennt sind. Erlaubt sind die Zahlendarstellungen der Programmiersprache FORTRAN.

Die Ausgaben

• Die Ausgangsmatrix A.
• Die exakte Inverse A^-1, falls sie dem System bekannt ist (also nicht im Falle der Eingabe einer eigenen Matrix A).
• Die exakte Konditionszahl der Matrix A bzgl. der L₁-Norm, falls die exakte Inverse bekannt ist.
• Die Güte der exakten Inversen: L₁-Norm von I - AA^-1, berechnet mit der vollen Maschinengenauigkeit, also etwa 16 Dezimalstellen. Dies ergibt also nicht 0, sondern etwa 10^-16cond(A) wegen der Rundungsfehler bei der Skalarproduktberechnung ''Zeile mal Spalte''.
• Eine numerische Schätzung der Konditionszahl (im Falle einer eigenen Matrix wichtig).
• Die berechnete Inverse A^-1_berechnet.
• Den Fehler der berechneten Inversen: L₁-Norm von A^-1-A^-1_berechnet, falls die exakte Inverse bekannt ist.
• Die Güte des Residuums der berechneten Inversen: L₁-Norm von I - AA^-1_berechnet.

Fragen ?!

• Wie verhält sich die Güte der berechneten Inversen in Abhängigkeit von der Konditionszahl und der Pivotisierungsstrategie ?

Das Eingabeformular

Zurück: Lineare Gleichungssysteme