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

Lineares Gleichungssystem mit symmetrischer Koeffizientenmatrix

entsprechend

Cholesky-Zerlegung einer quadratischen Matrix

in ein Produkt zweier zueinander transponierter Dreiecksmatrizen zerlegt. Die Ermittlung des Vektors der Unbekannten x aus

Lineares Gleichungssystem mit symmetrischer Koeffizientenmatrix nach der Cholesky-Zerlegung

kann dann wie beim verketteten Algorithmus durch Vorwärtseinsetzen

Vorwärtseinsetzen zur Lösung eines linearen Gleichungssystems nach Cholesky

und Rückwärtseinsetzen

Rückwärtseinsetzen zur Lösung eines linearen Gleichungssystems nach Cholesky

realisiert werden.

Cholesky-Zerlegung

Falksches Schema für die Cholesky-Zerlegung einer symmetrischen Matrix 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):

Erzeugen des ersten Elements der Choleskyzerlegung

Allgemeine Formel für das Erzeugen eines Elements der Dreiecksmatrix der Cholesky-Zerlegung

Script für die Cholesky-Zerlegung  einer symmetrischen Matrix mit  MatlabEinfaches Beispiel

Es soll das folgende lineare Gleichungssystem mit symmetrischer Koeffizientenmatrix nach dem Verfahren von Cholesky gelöst werden:

Einfaches Beispiel für die Lösung eines linearen Gleichungssystems nach Cholesky

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:

 

 

Beispiel für die Erzeugung der Cholesky-Zerlegung einer symmetrischen Matrix mit dem Falkschen Schema

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.

Komplettes Schema (Beispiel) für die Lösung eines linearen Gleichungssystems mit symmetrischer Koeffizientenmatrix nach CholeskyWie 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 .