Cholesky nedbrytning

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 23 november 2021; kontroller kräver 5 redigeringar .

Cholesky-nedbrytningen (kvadratrotsmetoden) är en representation av en symmetrisk positiv bestämd matris i formen , där är en lägre triangulär matris med strikt positiva poster på diagonalen. Ibland skrivs nedbrytningen i motsvarande form: , där är en övre triangulär matris. Cholesky-nedbrytningen existerar alltid och är unik för alla symmetriska positiva bestämda matriser. $A$ $A=LL^{T}$ $L$ $A=U^{T}U$ $U=L^{T}$

Det finns också en generalisering av denna expansion till fallet med komplext värderade matriser. Om är en positiv-definitiv Hermitian matris , då det finns en nedbrytning , där är en lägre triangulär matris med positiva reella element på diagonalen, och är dess Hermitian konjugerade matris. $A$ $A=LL^{*}$ $L$ $L^{*}$

Nedbrytningen är uppkallad efter den polskfödde franske matematikern André-Louis Cholesky (1875-1918).

Algoritm

Matriselement kan beräknas, med början från det övre vänstra hörnet av matrisen, med hjälp av formlerna $L$

{\begin{aligned}l_{11}&={\sqrt {a_{11}}},\\l_{j1}&={\frac {a_{j1}}{l_{11}}} ,\quad j\in [2,n],\\l_{ii}&={\sqrt {a_{ii}-\sum _{p=1}^{i-1}l_{ip}^{2 }}},\quad i\in [2,n],\\l_{ji}&={\frac {1}{l_{ii}}}\left(a_{ji}-\summa _{p= 1}^{i-1}l_{ip}l_{jp}\right),\quad i\in [2,n-1],j\in [i+1,n].\end{aligned}}

Uttrycket under roten är alltid positivt om är en verklig positiv bestämd matris.

A

Beräkningen är från topp till botten, från vänster till höger, dvs först och sedan . $L_{{ij}}$ $L_{{ii}}$

För komplext värderade hermitiska matriser används formlerna

{\begin{aligned}l_{ii}&={\sqrt {a_{ii}-\sum _{p=1}^{i-1}l_{ip}l_{ip}^{*} }}),\quad i\in [2,n],\\l_{ji}&={\frac {1}{l_{ii}}}\left(a_{ji}-\summa _{p= 1 }^{i-1}l_{ip}l_{jp}^{*}\right),\quad i\in [2,n-1],j\in [i+1,n].\end { aligned}}

Applikationer

Denna nedbrytning kan användas för att lösa ett system av linjära ekvationer om matrisen är symmetrisk och positiv definitiv. Sådana matriser uppstår ofta, till exempel när man använder minsta kvadratmetoden och numeriskt löser differentialekvationer. $yxa = b$ $A$

Efter att ha expanderat kan lösningen erhållas genom att successivt lösa två triangulära ekvationssystem: och . Detta sätt att lösa kallas ibland för kvadratrotsmetoden . [1] Jämfört med mer generella metoder som Gauss-metoden eller LU-sönderdelning är den numerärt stabilare och kräver ungefär hälften så många aritmetiska operationer. [2] $A=LL^{T}$ $x$ $Ly=b$ $L^{T}x=y$

Cholesky-nedbrytningen används också i Monte Carlo-metoder för att generera korrelerade slumpvariabler . Låta vara en vektor av oberoende standard normala slumpvariabler och vara den önskade kovariansmatrisen . Då kommer vektorn att ha en multivariat normalfördelning med nollmedelvärde och kovariansmatris . [3] $X$ ${\displaystyle \Sigma =LL^{T))$ $Y=LX$ $\Sigma$

Implementering i matematiska mjukvarupaket

SAS använder funktionen ROOT (matrix) , som är en del av SAS IML -paketet .
I MATLAB , Octave , R -system utförs nedbrytning med kommandot U = chol(A) .
Maple och NumPy har den klumpiga proceduren i linalg- modulen .
Mathematica använder proceduren CholeskyDecomposition [A] .
MathCAD använder funktionen cholesky(A) för nedbrytning
GSL använder funktionen gsl_linalg_cholesky_decomp .
I biblioteket från Google ceres-solver [4] .
Apache Commons Math-biblioteket (sedan version 2.0) använder klassen CholeskyDecomposition [5] .
Torch - biblioteket har en funktion torch.potrf [6] .
I JAMA- biblioteket för programmeringsspråket java.
Intel Data Analytics Acceleration Library innehåller en algoritmcholesky::Batch.

Anteckningar

↑ Verzhbitsky V. M. Grunderna för numeriska metoder. - M . : Higher School , 2009. - 840 sid. — ISBN 9785060061239 .
↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. 2.9 Cholesky Decomposition // Numeriska recept i C. - 2:a upplagan. — Cambridge: Cambridge University Press. - ISBN 0-521-43108-5 .
↑ Martin Haugh . Arkiverad från originalet den 5 januari 2012. Genererar korrelerade slumpmässiga variabler .
↑ Ceres Solver - ett icke-linjärt optimeringsbibliotek i stor skala (länk inte tillgänglig) . Hämtad 7 september 2017. Arkiverad från originalet 2 september 2017. (obestämd)
↑ CholeskyDecomposition Arkiverad 7 november 2017 på Wayback Machine .
↑ torch.potrf Arkiverad 20 augusti 2017 på Wayback Machine .

Vektorer och matriser

Vektorer

Grundläggande koncept	Vektor i geometri Grund Ortogonal grund Vektorkoordinater Kolinearitet Ortogonalitet Linjärt beroende Kolumnutrymme
Typer av vektorer	Enhet vektor Axiell vektor isotrop vektor Vanligt Kolinearitet Noll vektor Radie vektor Egenvektor
Operationer på vektorer	Skalär produkt vektor produkt blandad produkt Pseudoskalär produkt Dubbelkorsprodukt
Utrymmestyper	vektor utrymme affint utrymme Euklidiskt utrymme Pseudo-euklidiskt utrymme Normerat utrymme Minkowski utrymme

matriser

Grundläggande koncept	Matrismultiplikation Transponerad matris Hermitisk konjugatmatris Symmetrisk matris invers matris Eget värde Karakteristiskt polynom för en matris
Specialmatriser	Identitetsmatris Noll matris Diagonal matris lambda matris
Matrisnedbrytningar	LU-nedbrytning Cholesky nedbrytning QR-sönderdelning LUP-nedbrytning singulärvärdesfaktorisering Spektral nedbrytning av en matris

Övrig

Metoder för att lösa SLAE
Direkta metoder	Matrismetod Gauss metod Gauss-Jordan-metoden Cramer metod LU-nedbrytning Cholesky nedbrytning Sopa metod
Iterativa metoder	Jacobi metod Gauss-Seidel-metoden Iterationsmetod Avslappningsmetod Konjugerad gradientmetod Bikonjugerad gradientmetod Stabiliserad bikonjugatgradientmetod
Allmän	invers matris Projektionsmetoder för att lösa SLAE Förkonditionering