Cholesky-bomlás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. november 23-án felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

A Cholesky-felbontás (négyzetgyök módszer) egy szimmetrikus pozitív határozott mátrix ábrázolása a formában , ahol egy alsó háromszög mátrix szigorúan pozitív bejegyzésekkel az átlón. Néha a dekompozíciót ekvivalens formában írják le: , ahol egy felső háromszögmátrix. A Cholesky-felbontás mindig létezik, és minden szimmetrikus pozitív határozott mátrixra egyedi. $A$ $A=LL^{T}$ $L$ $A=U^{T}U$ $U=L^{T}$

Ennek a bővítésnek van egy általánosítása is az összetett értékű mátrixok esetére. Ha egy pozitív-definit Hermiti mátrix , akkor van egy dekompozíció , ahol van egy alsó háromszögmátrix pozitív valós elemekkel az átlón, és ennek hermitikus konjugált mátrixa. $A$ $A=LL^{*}$ $L$ $L^{*}$

A dekompozíció a lengyel származású francia matematikus , André-Louis Cholesky (1875-1918) nevéhez fűződik.

Algoritmus

A mátrixelemek a mátrix bal felső sarkától kiindulva számíthatók ki a képletek segítségével $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}\jobbra),\quad i\in [2,n-1],j\in [i+1,n].\end{igazított}}

A gyök alatti kifejezés mindig pozitív, ha valódi pozitív határozott mátrix.

A

A számítás fentről lefelé, balról jobbra történik, azaz először , majd . $L_{{ij}}$ $L_{{ii}}$

A komplex értékű hermitiánus mátrixokhoz a képleteket használjuk

{\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}^{*}\jobbra),\quad i\in [2,n-1],j\in [i+1,n].\end { igazítva}}

Alkalmazások

Ez a dekompozíció alkalmazható lineáris egyenletrendszer megoldására, ha a mátrix szimmetrikus és pozitív határozott. Ilyen mátrixok gyakran előfordulnak például a legkisebb négyzetek módszerének alkalmazásakor és a differenciálegyenletek numerikus megoldása során. $ax = b$ $A$

Bővítés után a megoldást két háromszög egyenletrendszer egymás utáni megoldásával kaphatjuk meg: és . Ezt a megoldási módot néha négyzetgyök módszernek is nevezik . [1] Az általánosabb módszerekkel, például a Gauss-módszerrel vagy az LU-felbontással összehasonlítva numerikusan stabilabb , és körülbelül feleannyi aritmetikai műveletet igényel. [2] $A=LL^{T}$ $x$ $Ly=b$ $L^{T}x=y$

A Cholesky dekompozíciót Monte Carlo módszerekben is alkalmazzák korrelált valószínűségi változók generálására . Legyen független standard normál valószínűségi változók vektora és legyen a kívánt kovarianciamátrix . Ekkor a vektor többváltozós normális eloszlású lesz nulla átlaggal és kovarianciamátrixszal . [3] $x$ ${\displaystyle \Sigma =LL^{T))$ $Y=LX$ $\Sigma$

Megvalósítás matematikai szoftvercsomagokban

A SAS a ROOT(mátrix) függvényt használja, amely a SAS IML csomag része .
A MATLAB , Octave , R rendszerekben a dekompozíciót az U =chol(A) paranccsal hajtjuk végre .
A Maple és a NumPy a cholesky eljárást tartalmazza a linalg modulban .
A Mathematica a CholeskyDecomposition [A] eljárást használja .
A MathCAD a cholesky(A) függvényt használja a felbontáshoz
A GSL a gsl_linalg_cholesky_decomp függvényt használja .
A könyvtárban a Google ceres-solvertől [4] .
Az Apache Commons Math könyvtár (a 2.0-s verzió óta) a CholeskyDecomposition [5] osztályt használja .
A Torch könyvtárnak van egy torch.potrf [6] funkciója .
A java programozási nyelv JAMA könyvtárában .
Az Intel Data Analytics Acceleration Library egy algoritmust tartalmazcholesky::Batch.

Jegyzetek

↑ Verzsbitszkij V. M. A numerikus módszerek alapjai. - M . : Felsőiskola , 2009. - 840 p. — ISBN 9785060061239 .
↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. 2.9 Cholesky -felbontás // Numerical Recipes in C. - 2nd edition. — Cambridge: Cambridge University Press. - ISBN 0-521-43108-5 .
↑ Martin Haugh . Archiválva az eredetiből 2012. január 5-én. Korrelált véletlen változók generálása .
↑ Ceres Solver – Nagyszabású, nemlineáris optimalizálási könyvtár (a hivatkozás nem elérhető) . Letöltve: 2017. szeptember 7. Az eredetiből archiválva : 2017. szeptember 2.. (határozatlan)
↑ CholeskyDecomposition archiválva : 2017. november 7. a Wayback Machine -nál .
↑ torch.potrf Archiválva : 2017. augusztus 20. a Wayback Machine -nál .

Vektorok és mátrixok

Vektorok

Alapfogalmak	Vektor a geometriában Alap Ortogonális alap Vektor koordináták Kollinearitás Ortogonalitás Lineáris függőség Oszlopköz
A vektorok fajtái	Egységvektor Axiális vektor izotróp vektor Normál Kollinearitás Nulla vektor Sugár vektor Sajátvektor
Műveletek vektorokon	Skaláris szorzat vektor termék vegyes termék Pszeudoszkaláris termék Kettős kereszttermék
Tértípusok	vektor tér affin tér Euklideszi tér Pszeudoeuklideszi tér Normált tér Minkowski tér

mátrixok

Alapfogalmak	Mátrixszorzás Transzponált mátrix Hermitikus konjugált mátrix Szimmetrikus mátrix inverz mátrix Sajátérték Mátrix karakterisztikus polinomja
Speciális mátrixok	Identitásmátrix Nulla mátrix Átlós mátrix lambda mátrix
Mátrix dekompozíciók	LU bomlás Cholesky-bomlás QR-bontás LUP bomlás szinguláris érték felbontás Mátrix spektrális lebontása

Egyéb

Az SLAE megoldásának módszerei
Közvetlen módszerek	Mátrix módszer Gauss módszer Gauss-Jordan módszer Cramer módszer LU bomlás Cholesky-bomlás Sweep módszer
Iteratív módszerek	Jacobi módszer Gauss-Seidel módszer Iterációs módszer Relaxációs módszer Konjugált gradiens módszer Bikonjugált gradiens módszer Stabilizált bikonjugátum gradiens módszer
Tábornok	inverz mátrix Vetítési módszerek SLAE megoldására Előkondicionálás