Kolesky nedbrydning

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 23. november 2021; checks kræver 5 redigeringer .

Cholesky-nedbrydningen (kvadratrodsmetoden) er en repræsentation af en symmetrisk positiv bestemt matrix i form , hvor er en lavere trekantet matrix med strengt positive indgange på diagonalen. Nogle gange skrives nedbrydningen på den tilsvarende form: , hvor er en øvre trekantet matrix. Cholesky-nedbrydningen eksisterer altid og er unik for enhver symmetrisk positiv bestemt matrix. $EN$ $A=LL^{T}$ $L$ $A=U^{T}U$ $U=L^{T}$

Der er også en generalisering af denne udvidelse til tilfældet med komplekst værdisatte matricer. Hvis er en positiv-bestemt Hermitian matrix , så er der en dekomponering , hvor er en lavere trekantet matrix med positive reelle elementer på diagonalen, og er dens Hermitian konjugerede matrix. $EN$ $A=LL^{*}$ $L$ $L^{*}$

Nedbrydningen er opkaldt efter den polskfødte franske matematiker André-Louis Cholesky (1875-1918).

Algoritme

Matrixelementer kan beregnes, startende fra det øverste venstre hjørne af matricen, ved hjælp af formlerne $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}-\sum _{p= 1}^{i-1}l_{ip}l_{jp}\right),\quad i\in [2,n-1],j\in [i+1,n].\end{aligned}}

Udtrykket under roden er altid positivt, hvis er en reel positiv bestemt matrix.

EN

Beregningen er fra top til bund, fra venstre mod højre, altså først og derefter . $L_{{ij}}$ $L_{{ii}}$

For hermitiske matricer med kompleks værdi anvendes formlerne

{\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}-\sum _{p= 1 }^{i-1}l_{ip}l_{jp}^{*}\right),\quad i\in [2,n-1],j\in [i+1,n].\end { aligned}}

Ansøgninger

Denne dekomponering kan anvendes til at løse et system af lineære ligninger, hvis matrixen er symmetrisk og positiv bestemt. Sådanne matricer opstår f.eks. ofte ved brug af mindste kvadraters metode og numerisk løsning af differentialligninger. $økse = b$ $EN$

Efter udvidelse kan løsningen opnås ved successivt at løse to trekantede ligningssystemer: og . Denne måde at løse på kaldes undertiden kvadratrodsmetoden . [1] Sammenlignet med mere generelle metoder som Gauss-metoden eller LU-dekomponering , er den numerisk mere stabil og kræver cirka halvt så mange regneoperationer. [2] $A=LL^{T}$ $x$ $Ly=b$ $L^{T}x=y$

Cholesky-nedbrydningen anvendes også i Monte Carlo-metoder til at generere korrelerede tilfældige variabler . Lade være en vektor af uafhængige standard normale stokastiske variable og være den ønskede kovariansmatrix . Så vil vektoren have en multivariat normalfordeling med nul middelværdi og kovariansmatrix . [3] $x$ ${\displaystyle \Sigma =LL^{T))$ $Y=LX$ $\Sigma$

Implementering i matematiske softwarepakker

SAS bruger ROOT(matrix) -funktionen , som er en del af SAS IML -pakken .
I MATLAB , Octave , R - systemer udføres dekomponering ved kommandoen U = chol(A) .
Maple og NumPy har den kræsne procedure i linalg - modulet .
Mathematica bruger CholeskyDecomposition [A] proceduren .
MathCAD bruger cholesky (A) -funktionen til nedbrydning
GSL'en bruger gsl_linalg_cholesky_decomp - funktionen .
I biblioteket fra Google ceres-solver [4] .
Apache Commons Math-biblioteket (siden version 2.0) bruger klassen CholeskyDecomposition [5] .
Torch - biblioteket har en funktion torch.potrf [6] .
I java-programmeringssprogets JAMA - bibliotek .
Intel Data Analytics Acceleration Library indeholder en algoritmecholesky::Batch.

Noter

↑ Verzhbitsky V. M. Grundlæggende om numeriske metoder. - M . : Higher School , 2009. - 840 s. — ISBN 9785060061239 .
↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. 2.9 Cholesky Decomposition // Numeriske opskrifter i C. - 2. udgave. — Cambridge: Cambridge University Press. - ISBN 0-521-43108-5 .
↑ Martin Haugh . Arkiveret fra originalen den 5. januar 2012. Generering af korrelerede tilfældige variabler .
↑ Ceres Solver - Et ikke-lineært optimeringsbibliotek i stor skala (link ikke tilgængeligt) . Hentet 7. september 2017. Arkiveret fra originalen 2. september 2017. (ubestemt)
↑ CholeskyDecomposition Arkiveret 7. november 2017 på Wayback Machine .
↑ torch.potrf Arkiveret 20. august 2017 på Wayback Machine .

Vektorer og matricer

Vektorer

Basale koncepter	Vektor i geometri Basis Ortogonalt grundlag Vektorkoordinater Kolinearitet Ortogonalitet Lineær afhængighed Søjleplads
Slags vektorer	Enhedsvektor Aksial vektor isotrop vektor Normal Kolinearitet Nul vektor Radius vektor Egenvektor
Operationer på vektorer	Skalært produkt vektor produkt blandet produkt Pseudoskalært produkt Dobbelt kryds produkt
Rumtyper	vektor rum affint rum Euklidisk rum Pseudo-euklidisk rum Normeret rum Minkowski plads

matricer

Basale koncepter	Matrix multiplikation Transponeret matrix Hermitisk konjugeret matrix Symmetrisk matrix omvendt matrix Egenværdi Karakteristisk polynomium af en matrix
Særlige matricer	Identitetsmatrix Nul matrix Diagonal matrix lambda matrix
Matrix nedbrydninger	LU nedbrydning Kolesky nedbrydning QR-nedbrydning LUP nedbrydning singular værdi nedbrydning Spektral nedbrydning af en matrix

Andet

Metoder til løsning af SLAE
Direkte metoder	Matrix metode Gauss metode Gauss-Jordan metode Cramer metode LU nedbrydning Kolesky nedbrydning Feje metode
Iterative metoder	Jacobi metode Gauss-Seidel metode Iterationsmetode Afslapningsmetode Konjugeret gradientmetode Bikonjugeret gradientmetode Stabiliseret bikonjugat gradientmetode
Generel	omvendt matrix Projektionsmetoder til løsning af SLAE Forkonditionering