In der geradlinigen Algebra, der Zergliederung von Cholesky oder dem Dreieck von Cholesky ist eine Zergliederung von Hermitian, die positiv-bestimmte Matrix ins Produkt einer niedrigeren Dreiecksmatrix und seines verbundenen stellt um. Es wurde von André-Louis Cholesky für echten matrices entdeckt. Wenn es anwendbar ist, ist die Zergliederung von Cholesky ungefähr zweimal so effizient wie die LU Zergliederung, um Systeme von geradlinigen Gleichungen zu lösen. In einem losen, metaphorischen Sinn kann davon als die Matrixentsprechung gedacht werden, die Quadratwurzel einer Zahl zu nehmen.

Behauptung

Wenn A echte Einträge hat und symmetrisch ist (oder mehr allgemein, hat Einträge Komplex-geschätzt und ist Hermitian), und positiv bestimmt, dann kann A als zersetzt werden

:

wo L eine niedrigere Dreiecksmatrix mit ausschließlich positiven diagonalen Einträgen ist, und L anzeigt, dass die verbundenen von L umstellen. Das ist die Zergliederung von Cholesky.

Die Cholesky Zergliederung ist einzigartig: In Anbetracht Hermitian, positiv-bestimmte Matrix A, gibt es nur ein senken Dreiecksmatrix L mit ausschließlich positiven diagonalen solchen Einträgen dass = LL. Das gegenteilige hält trivial: Wenn A als LL für einen invertible L, tiefer dreieckig oder sonst geschrieben werden kann, dann ist A Hermitian und positiv bestimmt.

Die Voraussetzung, dass L ausschließlich positive diagonale Einträge haben, kann fallen gelassen sein, um den factorization zum positiv-halbbestimmten Fall zu erweitern. Die Behauptung liest dann: Eine Quadratmatrix A hat eine Zergliederung von Cholesky, wenn, und nur wenn A Hermitian und positiv halbbestimmt ist. Cholesky factorizations für positiv-halbbestimmten matrices sind im Allgemeinen nicht einzigartig.

Im speziellen Fall, dass A eine symmetrische positiv-bestimmte Matrix mit echten Einträgen ist, hat L echte Einträge ebenso.

Anwendungen

Die Cholesky Zergliederung wird für die numerische Lösung der geradlinigen Gleichungsaxt = b hauptsächlich verwendet. Wenn A symmetrisch ist und positiver bestimmt, dann können wir Axt = b durch die erste Computerwissenschaft der Zergliederung von Cholesky = LL, dann lösen, Ly = b für y lösend, und schließlich Lx = y für x lösend.

Geradlinig kleinste Quadrate

Systeme der Form-Axt = b mit Einem symmetrischen und bestimmtem positivem entstehen ganz häufig in Anwendungen. Zum Beispiel sind die normalen Gleichungen im geradlinigen kleinste Quadratprobleme dieser Form. Es kann auch geschehen, dass Matrix A aus einer funktionellen Energie kommt, der von physischen Rücksichten positiv sein muss; das geschieht oft in der numerischen Lösung teilweiser Differenzialgleichungen.

Nichtlineare Optimierung

Nichtlineare Multi-Variate-Funktionen können über ihre Rahmen mit Varianten der Methode von Newton genannt Quasinewton-Methoden minimiert werden. Bei jeder Wiederholung nimmt die Suche einen definierten Schritt s durch das Lösen von Hs =-g für s, wo s der Schritt ist, ist g der Anstieg-Vektor der teilweisen ersten Ableitungen der Funktion in Bezug auf die Rahmen, und H ist eine Annäherung an die Jute-Matrix der teilweisen zweiten Ableitungen, die durch die wiederholte Reihe 1 Aktualisierungen bei jeder Wiederholung gebildet sind. Zwei wohl bekannte Aktualisierungsformeln werden Davidon-Fletcher-Powell (DFP) und Broyden Fletcher Goldfarb Shanno (BFGS) genannt. Der Verlust der positiv-bestimmten Bedingung durch die Runde - vom Fehler wird vermieden, wenn, anstatt eine Annäherung an das Gegenteil der Jute zu aktualisieren, man die Zergliederung von Cholesky einer Annäherung der Jute-Matrix selbst aktualisiert.

Simulation von Monte Carlo

Die Cholesky Zergliederung wird in der Methode von Monte Carlo allgemein verwendet, um Systeme mit vielfachen aufeinander bezogenen Variablen vorzutäuschen: Die Korrelationsmatrix wird zersetzt, um den niedrig-dreieckigen L zu geben. Das Anwenden davon zu einem Vektoren von unkorrelierten Proben, u, erzeugt einen Beispielvektoren Lu mit den Kovarianz-Eigenschaften des Systems, das wird modelliert.

Filter von Kalman

Parfümfreie Filter von Kalman verwenden allgemein die Zergliederung von Cholesky, um eine Reihe so genannter Sigma-Punkte zu wählen. Der Filter von Kalman verfolgt den durchschnittlichen Staat eines Systems als ein Vektor x der Länge N und Kovarianz als eine N-by-N Matrix P. Die Matrix P ist immer halbbestimmt positiv, und kann in LL zersetzt werden. Die Säulen von L können hinzugefügt und vom bösartigen x abgezogen werden, um sich eine Reihe 2N Vektoren genannt Sigma-Punkte zu formen. Diese Sigma-Punkte gewinnen völlig das bösartige und die Kovarianz des Systemstaates.

Die Computerwissenschaft der Zergliederung von Cholesky

Es gibt verschiedene Methoden, für die Zergliederung von Cholesky zu berechnen. Die rechenbetonte Kompliziertheit allgemein verwendeter Algorithmen ist im Allgemeinen. Die unter allen beschriebenen Algorithmen schließen über N/3-MISSERFOLGE ein, wo n die Größe der Matrix A ist. Folglich sind sie Hälfte der Kosten der LU Zergliederung, die 2n/3-MISSERFOLGE verwendet (sieh Trefethen und Bau 1997).

Der der Algorithmen unten schneller ist, hängt von den Details der Durchführung ab. Allgemein wird der erste Algorithmus ein bisschen langsamer sein, weil er auf die Daten auf eine unregelmäßigere Weise zugreift.

Der Cholesky Algorithmus

Der Cholesky Algorithmus, verwendet, um die Zergliederungsmatrix L zu berechnen, ist eine modifizierte Version der Beseitigung von Gaussian.

Der rekursive Algorithmus fängt mit mir an: = 1 und

:

Am Schritt i hat die Matrix A die folgende Form:

:

\begin {pmatrix }\

\mathbf {ich} _ {i-1} & 0 & 0 \\

0 & a_ {ich, ich} & \mathbf {b} _ {ich} ^ {*} \\

0 & \mathbf {b} _ {ich} & \mathbf {B} ^ {(i) }\

\end {pmatrix},

</Mathematik>

wo ich die Identitätsmatrix der Dimension i &minus anzeige; 1.

Wenn wir jetzt die Matrix L durch definieren

:

: =

\begin {pmatrix }\

\mathbf {ich} _ {i-1} & 0 & 0 \\

0 & \sqrt {a_ {ich, ich}} & 0 \\

0 & \frac {1} {\\sqrt {a_ {ich, ich}}} \mathbf {b} _ {ich} & \mathbf {ich} _ {n-i }\

\end {pmatrix},</Mathematik>

dann können wir als schreiben

:

\mathbf {Ein} ^ {(i)} = \mathbf {L} _ {ich} \mathbf {Ein} ^ {(i+1)} \mathbf {L} _ {ich} ^ {* }\

</Mathematik>

wo

:

\mathbf {Ein} ^ {(i+1) }\

\begin {pmatrix }\

\mathbf {ich} _ {i-1} & 0 & 0 \\

0 & 1 & 0 \\

0 & 0 & \mathbf {B} ^ {(i)} - \frac {1} {a_ {ich, ich}} \mathbf {b} _ {ich} \mathbf {b} _ {ich} ^ {* }\

\end {pmatrix}.

</Mathematik>

Bemerken Sie, dass b b ein Außenprodukt ist, deshalb wird dieser Algorithmus die Außenproduktversion in (Golub & Van Loan) genannt.

Wir wiederholen das weil ich von 1 bis n. Danach n Schritte, wir kommen = ich. Folglich wird die niedrigere Dreiecksmatrix L, nach dem wir suchen, als berechnet

:

Der Cholesky-Banachiewicz und die Cholesky-Crout Algorithmen

Wenn wir die Gleichung = LL, ausschreiben

:

{\\mathbf {A=LL^T}} =

\begin {pmatrix} L_ {11} & 0 & 0 \\

L_ {21} & L_ {22} & 0 \\

L_ {31} & L_ {32} & L_ {33 }\\\

\end {pmatrix }\

\begin {pmatrix} L_ {11} & L_ {21} & L_ {31} \\

0 & L_ {22} & L_ {32} \\

0 & 0 & L_ {33 }\

\end {pmatrix }\

\begin {pmatrix} L_ {11} ^2 & & (\text {symmetrisch}) \\

L_ {21} L_ {11} & L_ {21} ^2 + L_ {22} ^2& \\

L_ {31} L_ {11} & L_ {31} L_ {21} +L_ {32} L_ {22} & L_ {31} ^2 + L_ {32} ^2+L_ {33} ^2

\end {pmatrix }\</Mathematik>

wir erhalten die folgende Formel für die Einträge von L:

::

Der Ausdruck unter der Quadratwurzel ist immer positiv, wenn A echt und positiv-bestimmt ist.

Für die komplizierte Matrix von Hermitian gilt die folgende Formel:

::

So können wir (ich, j) Zugang rechnen, wenn wir die Einträge nach links und oben wissen. Die Berechnung wird gewöhnlich in jeder der folgenden Ordnungen eingeordnet.

• Der Cholesky-Banachiewicz Algorithmus fängt von der oberen linken Ecke der Matrix L und des Erlöses an, um die Matrixreihe durch die Reihe zu berechnen.
• Der Cholesky-Crout Algorithmus fängt von der oberen linken Ecke der Matrix L und des Erlöses an, um die Matrix spaltenweise zu berechnen.

Stabilität der Berechnung

Nehmen Sie an, dass wir ein gut bedingtes System von geradlinigen Gleichungen lösen wollen. Wenn die LU Zergliederung verwendet wird, dann ist der Algorithmus nicht stabil, wenn wir eine Art sich drehende Strategie nicht verwenden. Im letzten Fall hängt der Fehler vom so genannten Wachstumsfaktor der Matrix ab, die gewöhnlich (aber nicht immer) klein ist.

Nehmen Sie jetzt an, dass die Zergliederung von Cholesky anwendbar ist. Wie oben erwähnt wird der Algorithmus zweimal so schnell sein. Außerdem ist kein Drehen notwendig, und der Fehler wird immer klein sein. Spezifisch, wenn wir Axt = b lösen wollen, und y anzeigt, dass die geschätzte Lösung dann y das gestörte System (+ E) y = b wo löst

:

Hier, || || ist die 2-Normen-Matrix, c ist eine kleine Konstante je nachdem n, und ε zeigt die Einheit herum - davon an.

Eine Sorge mit der Zergliederung von Cholesky, um dessen bewusst zu sein, ist der Gebrauch von Quadratwurzeln. Wenn die Matrix, die wird faktorisiert, bestimmt, wie erforderlich, positiv ist, sind die Zahlen unter den Quadratwurzeln immer in der genauen Arithmetik positiv. Leider können die Zahlen negativ wegen der Runde - von Fehlern werden, in welchem Fall der Algorithmus nicht weitergehen kann. Jedoch kann das nur geschehen, wenn die Matrix sehr schlecht-bedingt ist. Eine Weise, das zu richten, ist, eine diagonale Korrektur-Matrix zur Matrix hinzuzufügen, die in einem Versuch wird zersetzt, die positive Bestimmtheit zu fördern. Während das die Genauigkeit der Zergliederung vermindern könnte, kann es aus anderen Gründen sehr günstig sein; zum Beispiel, wenn das Durchführen der Methode von Newton in der Optimierung, das Hinzufügen einer Diagonalmatrix Stabilität wenn weit vom Optimum verbessern können.

Das Vermeiden von Einnahme-Quadratwurzeln

Eine alternative Form ist der symmetrische unbestimmte factorization

:

{\\mathbf {A=LDL} ^\\mathrm {T}} =

\begin {pmatrix} 1 & 0 & 0 \\

L_ {21} & 1 & 0 \\

L_ {31} & L_ {32} & 1 \\

\end {pmatrix }\

\begin {pmatrix} D_1 & 0 & 0 \\

0 & D_2 & 0 \\

0 & 0 & D_3 \\

\end {pmatrix }\

\begin {pmatrix} 1 & L_ {21} & L_ {31} \\

0 & 1 & L_ {32} \\

0 & 0 & 1 \\

\end {pmatrix} =

\begin {pmatrix} D_1 & & (\mathrm {symmetrisch}) \\

L_ {21} D_1 & L_ {21} ^2D_1 + D_2& \\

L_ {31} D_1 & L_ {31} L_ {21} D_ {1} +L_ {32} D_2 & L_ {31} ^2D_1 + L_ {32} ^2D_2+D_3.

\end {pmatrix }\</Mathematik>

Diese Form beseitigt das Bedürfnis, Quadratwurzeln zu nehmen. Wenn A bestimmt positiv ist, sind die Elemente der Diagonalmatrix D alle positiv. Jedoch kann dieser factorization für den grössten Teil invertible symmetrischen matrices verwendet werden; ein Beispiel einer invertible Matrix, deren Zergliederung unbestimmt ist, ist dasjenige, wo der erste Zugang Null ist.

Wenn A echt ist, bewerben sich die folgenden rekursiven Beziehungen um die Einträge von D und L:

::

Für die komplizierte Matrix von Hermitian A gilt die folgende Formel:

::

Der LDL und LL factorizations (bemerken, dass L zwischen den zwei verschieden ist), können leicht verbunden sein:

:

\mathbf L \mathbf D^ {\\frac 1 2\(\mathbf D^ {\\frac 1 2}) ^\\mathrm {T} \mathbf L^\\mathrm {T} =

\mathbf L \mathbf D^ {\\frac 1 2\(\mathbf L \mathbf D^ {\\frac 1 2}) ^\\mathrm {T }\

</Mathematik>

Der letzte Ausdruck ist das Produkt einer niedrigeren Dreiecksmatrix und seines stellen um, wie der LL factorization ist.

Block-Variante

Ohne das sorgfältige Drehen, wie man bekannt, ist der LDL factorization, wenn verwendet, auf unbestimmtem matrices nicht stabil; spezifisch können die Elemente des factorization willkürlich wachsen. Eine mögliche Verbesserung soll den factorization auf dem Block sub-matrices, allgemein 2x2 durchführen:

:{\\mathbf {A=LDL} ^\\mathrm {T}} =\begin {pmatrix }\

\mathbf I & 0 & 0 \\

\mathbf L_ {21} & \mathbf I & 0 \\

\mathbf L_ {31} & \mathbf L_ {32} & \mathbf I \\

\end {pmatrix }\\begin {pmatrix }\

\mathbf D_1 & 0 & 0 \\

0 & \mathbf D_2 & 0 \\

0 & 0 & \mathbf D_3 \\

\end {pmatrix }\\begin {pmatrix }\

\mathbf I & \mathbf L_ {21} ^\\mathrm T & \mathbf L_ {31} ^\\mathrm T \\

0 & \mathbf I & \mathbf L_ {32} ^\\mathrm T \\

0 & 0 & \mathbf I \\

\end {pmatrix} =\begin {pmatrix }\

\mathbf D_1 & & (\mathrm {symmetrisch}) \\

\mathbf L_ {21} \mathbf D_1 & \mathbf L_ {21} \mathbf D_1 \mathbf L_ {21} ^\\mathrm T + \mathbf D_2& \\

\mathbf L_ {31} \mathbf D_1 & \mathbf L_ {31} \mathbf D_ {1} \mathbf L_ {21} ^\\mathrm T + \mathbf L_ {32} \mathbf D_2 & \mathbf L_ {31} \mathbf D_1 \mathbf L_ {31} ^\\mathrm T + \mathbf L_ {32} \mathbf D_2 \mathbf L_ {32} ^\\mathrm T + \mathbf D_3

\end {pmatrix }\</Mathematik>

wo jedes Element im matrices oben eine Quadratsubmatrix ist. Davon folgen diese analogen rekursiven Beziehungen:

::

Bemerken Sie die Anwesenheit von Matrixprodukten und ausführliche Inversion, das beschränkt die praktische Block-Größe.

Beweis für positiven halbbestimmten matrices

Die obengenannten Algorithmen zeigen, dass jede positive bestimmte Matrix A eine Zergliederung von Cholesky hat. Dieses Ergebnis kann zum positiven halbbestimmten Fall durch ein Begrenzungsargument erweitert werden. Das Argument ist nicht völlig konstruktiv, d. h. es gibt keine ausführlichen numerischen Algorithmen, für Faktoren von Cholesky zu schätzen.

Wenn A eine n-by-n positive halbbestimmte Matrix ist, dann die Folge = {+ (1/k) bestehe ich} aus positivem bestimmtem matrices. (Das ist eine unmittelbare Folge, zum Beispiel, der geisterhafte kartografisch darstellende Lehrsatz für die polynomische funktionelle Rechnung.) Außerdem

:

\mathbf {Ein} _k \rightarrow \mathbf \,

</Mathematik>

in der Maschinenbediener-Norm. Vom positiven bestimmten Fall hat jeder A Zergliederung von Cholesky = LL*. Durch das Eigentum der Maschinenbediener-Norm,

:

So ist {L} ein begrenzter Satz im Banachraum von Maschinenbedienern, deshalb relativ kompakt (weil der zu Grunde liegende Vektorraum dimensional begrenzt ist). Folglich hat es eine konvergente Subfolge, die auch durch {L}, mit der Grenze L angezeigt ist. Es kann leicht überprüft werden, dass dieser L die gewünschten Eigenschaften hat, d. h. = sind LL* und L dreieckig mit nichtnegativen diagonalen Einträgen niedriger: für den ganzen x und y,

:

\langle \mathbf {Ein} x, y \rangle = \langle \lim \mathbf {Ein} _k x, y \rangle = \langle \lim \mathbf {L} _k \mathbf {L} _k^* x, y \rangle = \langle \mathbf {L} \mathbf {L} ^*x, y \rangle.

</Mathematik>

Deshalb = LL*. Weil der zu Grunde liegende Vektorraum dimensional begrenzt ist, sind alle Topologien auf dem Raum von Maschinenbedienern gleichwertig. So neigt L zu L in Norm-Mittel-L, neigt zu L entrywise. Das deutet der Reihe nach an, dass da jeder L dreieckig mit nichtnegativen diagonalen Einträgen niedriger ist, ist L auch.

Generalisation

Cholesky factorization kann zu (nicht notwendigerweise begrenzt) matrices mit Maschinenbediener-Einträgen verallgemeinert werden. Lassen Sie, eine Folge von Räumen von Hilbert zu sein. Denken Sie die Maschinenbediener-Matrix

:

\mathbf =

\begin {bmatrix }\

\mathbf _ {11} & \mathbf _ {12} & \mathbf _ {13} & \; \\

\mathbf _ {12} ^* & \mathbf _ {22} & \mathbf _ {23} & \; \\

\mathbf _ {13} ^* & \mathbf _ {23} ^* & \mathbf _ {33} & \; \\

\; & \; & \; & \ddots

\end {bmatrix }\

</Mathematik>

das Folgen der direkten Summe

:

wo jeder

:

ist ein begrenzter Maschinenbediener. Wenn A (halbbestimmt) im Sinn das für den ganzen begrenzten k und für einen positiv ist

:

wir haben, dann dort besteht eine niedrigere Dreiecksmaschinenbediener-Matrix L solch dass = LL*. Man kann auch die diagonalen Einträge von L nehmen, um positiv zu sein.

Reihen Sie einen Update und Downdate auf

Eine besondere schwierige Aufgabe zu tun ist die Reihe ein Update und Downdate. Tatsächlich ist es leicht, es zu tun, wenn Sie sich über die numerische Stabilität nicht sorgen, weil es die folgende Operation ist:

• Aktualisierung: R ist eine Zergliederung von Cholesky, X der Aktualisierungsvektor, Ru die aktualisierte Zergliederung: Ru=chol (R*R' +X*X')
• Downdate: R ist eine Zergliederung von Cholesky, X der downdate Vektor, Rd die downdated Zergliederung: Rd=chol (R*R '-X*X')

Diese Ausdrücke schließen vielfache Matrixprodukte und eine neue Cholesky Zergliederung ein.

Hier ist ein bisschen Funktion, die auf geschriebenen in der Syntax von Matlab gestützt ist, die die 2 Operationen begreifen:

Aufmerksamkeit! Wenn Sie versuchen, einen downdate zu begreifen, müssen Sie überzeugt sein, dass R*R '-x*x' noch positiv bestimmt ist. Sie können nachprüfen, dass durch die Prüfung, der im absoluten Wert größer ist: x Element oder das entsprechende Element auf der Diagonale von R? Wenn es erst ist, ist Ihr downdate nicht möglich.

Siehe auch

• Symbolische Cholesky Zergliederung
• Minimaler Grad-Algorithmus
• Matrixzergliederung
• Das Gesetz von Sylvester der Trägheit
• Zyklus-Reihe

Referenzen

• .

.

• Gene H. Golub und Charles F. Van Loan, Matrixberechnung (3. Hrsg.), Abschnitt 4.2, Universität von Johns Hopkins Presse. Internationale Standardbuchnummer 0-8018-5414-8.
• Roger A. Horn und Charles R. Johnson. Matrixanalyse, Abschnitt 7.2. Universität von Cambridge Presse, 1985. Internationale Standardbuchnummer 0-521-38632-2.
• S. J. Julier und J. K. Uhlmann. "Eine allgemeine Methode, um nichtlinearen Transformationen von ProbabilityDistributions näher zu kommen".
• S. J. Julier und J.K. Uhlmann, "Eine neue Erweiterung des Filters von Kalman zu nichtlinearen Systemen," in Proc. AeroSense: 11. Interne Nummer. Symp. Abfragung des Weltraums/Verteidigung, Simulation und Steuerungen, 1997, Seiten 182-193.

Außenverbindungen

Information

• Cholesky Zergliederung, die Datenanalyse BriefBook
• Modul für Cholesky Factorization
• Cholesky Zergliederung auf www.math-linux.com

Computercode

• LAPACK ist eine Sammlung von FORTRAN Unterprogrammen, um dichte geradlinige Algebra-Probleme zu beheben
• ALGLIB schließt einen teilweisen Hafen des LAPACK zu C ++, C#, Delphi, Visuell Grundlegend usw. ein.
• libflame ist eine C Bibliothek mit der LAPACK Funktionalität
• Zeichen und Video auf der Hochleistungsdurchführung von Cholesky factorization an Der Universität Texas an Austin.
• Cholesky: TBB + Fäden + SSE ist ein Buch, die Durchführung VGL mit TBB, Fäden und SSE (in Spanisch) erklärend

Gebrauch der Matrix in der Simulation

• Simulation von aufeinander bezogenen normalen zufälligen Variablen
• Aufeinander bezogene zufällige Variablen, Martin Haugh, Universität von Columbia erzeugend

Online-Rechenmaschinen

• Online-Matrixrechenmaschine Führt Cholesky Zergliederung von matrices online Durch.