Idee des Cholesky-Verfahrens
Für den wichtigen Spezialfall eines linearen Gleichungssystems mit
symmetrischer Koeffizientenmatrix
Die Elemente einer symmetrischen Matrix sind zur Hauptdiagonalen (im Beispiel gelb unterlegt) spiegelbildlich gleich.
Das bedeutet auch, dass die Elemente einer Zeile gleich sind mit den
Elementen der entsprechenden Spalte (hier für die 4. Zeile bzw. Spalte
farblich gekennzeichnet).
lässt sich der verkettete Algorithmus derart abwandeln, das die Anzahl der erforderlichen Operationen auf etwa die Hälfte verringert wird. Eine als Verfahren von Cholesky bezeichnete Modifikation hat aus verschiedenen Gründen besondere Bedeutung erlangt. Hierbei wird die symmetrische Matrix A des Systems
entsprechend
in ein Produkt zweier zueinander transponierter Dreiecksmatrizen zerlegt. Die Ermittlung des Vektors der Unbekannten x aus
kann dann wie beim verketteten Algorithmus durch Vorwärtseinsetzen
realisiert werden.
Cholesky-Zerlegung
Falksches Schema für Matrixmultiplikation
Nebenstehend ist das
Falksche Schema
Beispiel für Matrixmultiplikation
für die Rückmultiplikation zu sehen, das den erforderlichen Algorithmus für die Gewinnung von R verdeutlicht (zur Erinnerung: Jedes Element ai j der Matrix A muss sich aus dem Skalarprodukt der i-ten Zeile von RT mit der j-ten Spalte von R ergeben):
Es soll das folgende lineare Gleichungssystem mit symmetrischer Koeffizientenmatrix nach dem Verfahren von Cholesky gelöst werden:
Zunächst wird die Cholesky-Zerlegung der Matrix A durchgeführt (im Bildschirm-Schnappschuss des Command Windows rechts ist die Kontrollrechnung mit der chol-function von Matlab zu sehen).
Das nachfolgend links zu sehende Falksche Schema ist so zu füllen, dass die Multiplikation der beiden zueinander transponierten Dreiecksmatrizen die eingetragene Matrix A ergibt:
Rechts sieht man das ausgefüllte Schema. Als erster Wert entsteht die 3 (links oben), weil sich bei Multiplikation der ersten Zeile von RT mit der ersten Spalte von R die auf der Position links oben in A stehende 9 ergeben muss. Dann geht es wie oben beschrieben weiter, wobei man stets die in R entstehenden Elemente auch nach RT übertragen muss.
Wie beim verketteten Algorithmus gestattet auch hier das Falksche Schema die kompakte Anordnung aller Matrizen und Vektoren, die bei der Cholesky-Zerlegung und dem Vorwärts- und Rückwärtseinsetzen benötigt bzw. erzeugt werden.
Nebenstehend ist das komplette Schema zu sehen. Nach der Cholesky-Zerlegung der Matrix A wird zunächst das Vorwärtseinsetzen durchgeführt, mit dem der Vektor y erzeugt wird. Es beginnt damit, dass die Multiplikation der ersten Zeile von RT mit y eine 72 ergeben muss, also 3·y1=72, so dass als y1 die 24 eingetragen werden kann. Die nächste Rechnung lautet dann (zweite Zeile von RT mit y multipliziert): 1·24+5·y2=34, so dass für y2 die 2 eingetragen werden kann usw.
Analog dazu verläuft das Rückwärtseinsetzen mit der Matrix R zur Bestimmung des Vektors x, nur dass es hier mit der letzten Zeile beginnt: Multiplikation der vierten Zeile von R mit dem Vektor x führt auf die Rechnung 2·x4=10, so dass für x4 die 5 eingetragen werden kann usw.
Vorteile des Cholesky-Verfahrens
Die wesentlichen Vorzüge des Cholesky-Verfahrens, das neben dem Problem der Lösung linearer Gleichungssysteme auch noch in anderen Bereichen der Numerik symmetrischer Matrizen eine wichtige Rolle spielt (z. B. bei Matrizeneigenwertproblemen), sind (siehe auch Seite "Gauß vs. Cholesky"):
det (A) = det (RT) · det (R) = ( r11 · r22 · r33 · .... · rnn)2 .