Choleský rozklad

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 23. listopadu 2021; kontroly vyžadují 5 úprav .

Choleského rozklad (metoda odmocniny) je reprezentace symetrické pozitivně definitní matice ve tvaru , kde je nižší trojúhelníková matice s přísně kladnými vstupy na diagonále. Někdy se rozklad zapisuje v ekvivalentním tvaru: , kde je horní trojúhelníková matice. Choleského rozklad vždy existuje a je jedinečný pro jakoukoli symetrickou pozitivně definitní matici. $A$ $A=LL^{T}$ $L$ $A=U^{T}U$ $U=L^{T}$

Existuje také zobecnění tohoto rozšíření na případ komplexních matic. Jestliže je pozitivně definitní hermitovská matice , pak existuje rozklad , kde je nižší trojúhelníková matice s kladnými reálnými prvky na diagonále a je její hermitovská konjugovaná matice. $A$ $A=LL^{*}$ $L$ $L^{*}$

Rozklad je pojmenován po francouzském matematikovi polského původu André-Louis Cholesky (1875-1918).

Algoritmus

Prvky matice lze vypočítat od levého horního rohu matice pomocí vzorců $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}-\součet _{p= 1}^{i-1}l_{ip}l_{jp}\right),\quad i\in [2,n-1],j\in [i+1,n].\end{aligned}}

Výraz pod odmocninou je vždy kladný, pokud jde o reálnou kladně definitní matici.

A

Výpočet je shora dolů, zleva doprava, tedy nejprve a pak . $L_{{ij}}$ $L_{{ii}}$

Pro komplexní hermitovské matice se používají vzorce

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

Aplikace

Tento rozklad lze použít k řešení systému lineárních rovnic , pokud je matice symetrická a kladně definitní. Takové matice často vznikají například při použití metody nejmenších čtverců a numerického řešení diferenciálních rovnic. $sekera = b$ $A$

Po rozšíření lze řešení získat postupným řešením dvou trojúhelníkových soustav rovnic: a . Tento způsob řešení se někdy nazývá metoda druhé odmocniny . [1] Ve srovnání s obecnějšími metodami, jako je Gaussova metoda nebo LU rozklad , je numericky stabilnější a vyžaduje přibližně o polovinu méně aritmetických operací. [2] $A=LL^{T}$ $X$ $Ly=b$ $L^{T}x=y$

Choleského rozklad se také používá v metodách Monte Carlo pro generování korelovaných náhodných proměnných . Nechť je vektor nezávislých standardních normálních náhodných proměnných a je požadovaná kovarianční matice . Pak bude mít vektor vícerozměrné normální rozdělení s nulovým průměrem a kovarianční maticí . [3] $X$ ${\displaystyle \Sigma =LL^{T))$ $Y=LX$ $\Sigma$

Implementace v matematických softwarových balíčcích

SAS používá funkci ROOT(matrix) , která je součástí balíčku SAS IML .
V systémech MATLAB , Octave , R se rozklad provádí příkazem U = chol(A) .
Maple a NumPy mají proceduru cholesky v modulu linalg .
Mathematica používá postup CholeskyDecomposition [A] .
MathCAD používá pro rozklad funkci cholesky (A).
GSL používá funkci gsl_linalg_cholesky_decomp .
V knihovně od Google ceres-solver [4] .
Knihovna Apache Commons Math (od verze 2.0) používá třídu CholeskyDecomposition [5] .
Knihovna Torch má funkci torch.potrf [6] .
V knihovně JAMA programovacího jazyka java.
Knihovna Intel Data Analytics Acceleration Library obsahuje algoritmuscholesky::Batch.

Poznámky

↑ Verzhbitsky V. M. Základy numerických metod. - M . : Vyšší škola , 2009. - 840 s. — ISBN 9785060061239 .
↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. 2.9 Cholesky Decomposition // Numerical Recipes in C. - 2nd edition. — Cambridge: Cambridge University Press. - ISBN 0-521-43108-5 .
↑ Martin Haugh . Archivováno z originálu 5. ledna 2012. Generování korelovaných náhodných proměnných .
↑ Ceres Solver – Knihovna nelineární optimalizace ve velkém měřítku (odkaz není dostupný) . Získáno 7. září 2017. Archivováno z originálu 2. září 2017. (neurčitý)
↑ CholeskyDecomposition Archived 7. listopadu 2017 na Wayback Machine .
↑ torch.potrf Archivováno 20. srpna 2017 na Wayback Machine .

Vektory a matice

vektory

Základní pojmy	Vektor v geometrii Základ Ortogonální základ Vektorové souřadnice Kolinearita Ortogonalita Lineární závislost Prostor sloupců
Druhy vektorů	Jednotkový vektor Axiální vektor izotropní vektor Normální Kolinearita Nulový vektor Vektor poloměru Vlastní vektor
Operace s vektory	Skalární součin vektorový produkt smíšený produkt Pseudoskalární produkt Dvojitý křížový produkt
Typy prostoru	vektorový prostor afinní prostor Euklidovský prostor Pseudoeuklidovský prostor Normovaný prostor Minkowského prostor

matrice

Základní pojmy	Maticové násobení Transponovaná matice Hermitovská konjugovaná matice Symetrická matice inverzní matice Vlastní hodnota Charakteristický polynom matice
Speciální matrice	Matice identity Nulová matice Diagonální matice lambda matrice
Maticové rozklady	LU rozklad Choleský rozklad QR rozklad rozklad LUP singulární rozklad hodnoty Spektrální rozklad matice

jiný

Metody řešení SLAE
Přímé metody	Maticová metoda Gaussova metoda Gauss-Jordanova metoda Cramerova metoda LU rozklad Choleský rozklad Metoda zametání
Iterační metody	Jacobiho metoda Gauss-Seidelova metoda Iterační metoda Relaxační metoda Metoda konjugovaného gradientu Metoda bikonjugovaného gradientu Metoda stabilizovaného bikonjugátového gradientu
Všeobecné	inverzní matice Projekční metody pro řešení SLAE Předběžná úprava