Die Cholesky-Zerlegung

• Die Cholesky-Zerlegung ist eine Variante des Gauß-Algorithmus für symmetrische und positiv definite Matrizen.
• Zu einer symmetrischen und positiv definiten Matrix A wird eine obere Dreiecksmatrix R berechnet mit A = R^TR.
• Aus dem berechneten Cholesky-Faktor R wird die Inverse der Ausgangsmatrix A bestimmt. Es gilt A^-1=(R^TR) ^-1 = R^-1(R^-1)^T.
• Vorteile gegenüber dem Gauß-Algorithmus: Einsparung an Speicherplatz und Rechenzeit (ca. 50%) und geringere Empfindlichkeit gegen Rundungsfehler, insbesondere wenn man die sogenannte Produktsummenakkumulation benutzt (d.h. bei der Berechnung der auftretenden Skalarprodukte werden die Produkte als doppelt genaue Zahlen dargestellt und so summiert, erst danach wird wieder auf die Ausgangsgenauigkeit gerundet).
• Pivotisierung ist hier nicht notwendig.

Die Eingaben

• n ist die Dimension der quadratischen Matrix A und darf den Wert 11 nicht überschreiten.
• Für eine gegebene Dimension kann zwischen verschiedenen Matrizen gewählt werden.
  
  1. Eine parametrische Matrix A(x,y). Die Konditionszahl der Matrix beträgt
     (2n-2+x/y)/(n-2+x/y)
     
  2. Eine Dreibandmatrix, die bei der Diskretisierung einer gewöhnlichen Differentialgleichung 2. Ordnung (RWP) entsteht. Die Konditionszahl hängt quadratisch von der Dimension n ab (cond(A) = O(n²)). Für n kleiner oder gleich 11 ist die Konditionszahl also noch moderat.
  3. Die Inverse der Hilbertmatrix. Die Konditionszahl steigt bei dieser Matrix exponentiell mit der Dimension (cond(A) = O(e^(3.5n))). Die Hilbertmatrix ist bekannt dafür schon bei geringer Dimension sehr schlecht konditioniert zu sein. Die Hilbertmatrix hat die Elemente 1/(i+j-1). Ihre Inverse ist ganzzahlig und für den gegebenen Bereich von n exakt darstellbar. D.h. die zu beobachtenden Ungenauigkeiten sind nur auf die Rundungsfehler während der Rechnung zurückzuführen.
  4. Eine eigene Matrix A der Dimension n kann eingegeben werden. Es wird nur das obere Dreieck der Matrix A benötigt. Es ist darauf zu achten, daß die Matrixelemente zeilenweise ab der Diagonalen 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 bekannt (also nicht im Falle einer eigenen Matrix A).
• Die Konditionszahl der Matrix A bzgl. der L₁-Norm.
• Der relative Fehler der Cholesky-Zerlegung: L₁-Norm von A-R^TR geteilt durch das betragsmäßig größte Element in A.
• Die berechnete Inverse A^-1_berechnet.
• Den Fehler in der berechneten Inversen: L₁-Norm von A^-1-A^-1_berechnet, falls die exakte Inverse bekannt ist.
• Die Güte der berechneten Inversen: L₁-Norm von I - AA^-1_berechnet.

Fragen ?!

• Wie verhält sich die Güte der berechneten Inversen A^-1_berechnet mit steigender Konditionszahl ?
• Wie verhält sich der Fehler des berechneten Cholesky-Faktors R mit steigender Konditionszahl ?

Das Eingabeformular

Zurück: Lineare Gleichungssysteme