Choleského rozklad

Choleského rozklad matice na součin dolní trojúhelníkové matice a její transpozice.

Choleského rozklad (také Choleského dekompozice nebo Choleského faktorizace) je metoda lineární algebry, kterou lze každou reálnou pozitivně definitní matici rozložit na součin dolní trojúhelníkové matice a její transpozice. Obecněji lze pojem zavést i pro komplexní matice.

Rozklad je pojmenován po francouzském matematikovi André-Louisovi Choleském (1875–1918, výslovnost [šoleski], [ʃəˈlɛski]IPA), který jej vyvinul před rokem 1914 při triangulaci Kréty francouzskou Service géographique de l’armée.

Pro řešení soustav lineárních rovnic s pozitivně definitní maticí je Choleského rozklad zhruba dvakrát efektivnější než LU rozklad.

Definice

Pro každou pozitivně semidefinitní komplexní matici existuje dolní trojúhelníková matice taková, že platí:

Uvedený zápis matice jako součin se nazývá Choleského rozklad matice . Dolní trojúhelníková matice se nazývá Choleského faktor matice . Symbol značí matici hermitovsky sdruženou k matici (též nazývanou hermitovská transpozice).

Ten samý rozklad lze zapsat ve tvaru , kde je horní trojúhelníková, neboť .

Reálné pozitivně definitní matice mají Choleského faktory reálné. Pro ně platí: , a proto lze rozklad zapsat ve tvaru:

Ukázka

Symetrická reálná matice

má Choleského rozklad :

Vlastnosti

  • Choleského faktor je regulární právě když je daná matice regulární.
  • Má-li matice Choleského rozklad , je hermitovská, resp. u reálných symetrická, protože .
  • Má-li matice Choleského rozklad s regulárním Choleského faktorem je pozitivně definitní. Pro libovolné vyplývá z regularity matice , že také , a potom
, přičemž v předposlední výraz značí standardní skalární součin na .
  • Choleského rozklad není jednoznačný, např. matici lze rozložit čtyřmi způsoby s Choleského faktory: a .
  • Choleského faktory pozitivně semidefinitních (i komplexních) matic mají na diagonále vždy reálná čísla.
  • Pouze jeden z Choleského faktorů pozitivně definitních matic má všechny prvky na diagonále kladné.
  • Pokud je hermitovská matice pouze pozitivně semidefinitní, a nikoli pozitivně definitní, pak má stále Choleského rozklad, kde alespoň jeden prvek na diagonále je nulový. Choleského faktorů může být i nekonečně mnoho, například rozkladem matice je každá matice , kde .
  • Mezi Choleského faktory pozitivně semidefinitních matic hodnosti lze nalézt právě jeden takový, že má kladných prvků na diagonále a sloupců se samými nulami. Jinak řečeno, v tomto případě existuje alespoň jedna permutační matice taková, že matice má jednoznačný Choleského rozklad ve tvaru , kde je dolní trojúhelníková matice hodnosti s kladnou diagonálou.

LDL rozklad

S Choleského rozkladem úzce souvisí rozklad dané matice na součin:

,

kde je dolní trojúhelníková s 1 na diagonále a je diagonální.

LDL rozklad lze vypočítat a použít v podstatě stejnými algoritmy jako klasický Choleského rozklad, ovšem bez použití odmocnin.

Ukázka

Matice z předchozí ukázky má LDL rozklad:

Choleského faktor z předchozí ukázky lze spočítat pomocí součinu s odmocninou z diagonální matice:

LDL rozklad může mít například i matice, která je negativně semidefinitní.

Vlastnosti

  • Je-li pozitivně definitní, pak jsou všechny prvky na diagonále kladné. Z LDL rozkladu lze pak odvodit klasický Choleského rozklad s faktorem pomocí vztahu:
  • Naopak, má-li pozitivně definitní matice klasický Choleského rozklad , a matice je diagonální matice, která obsahuje hlavní diagonálu , pak lze rozložit jako , kde:
, tím se sloupce naškálují tak, aby prvky na diagonále byly rovny 1,
.
  • Pozitivně semidefinitní matice mají LDL rozklad právě když se hodnosti matic a shodují.
  • Pro existenci LDL rozkladu hermitovské (ne nutně pozitivně definitní) matice například stačí, aby prvních hlavních vedoucích minorů matice bylo nenulových.
  • Není-li matice pozitivně semidefinitní, čili je negativně (semi)definitní nebo indefinitní, a přitom má LDL rozklad, potom se na diagonále vyskytne alespoň jedno záporné číslo.
  • Matice a mají shodný determinant a ten je roven součinu prvků na diagonále matice .

Výpočet

Z rozepsání součinu pro matice řádu 3

vyplývá, že Choleského faktor s kladnou diagonálou je dán výrazem:

Obecně je možné prvky matice počítat po sloupcích zleva doprava a v každém sloupci odshora dolů.

Pro první sloupec platí následující.

Pro druhý sloupec platí:

Pro prvky na diagonále lze, vzhledem ke znalosti celého řádku vlevo od prvku, odvodit následující vzorec:

Pro prvky pod diagonálou vyplývá podobně následující vztah:

pro

U prvků na diagonále je možné vzít hodnotu odmocniny se záporným znaménkem, což vyvolá změnu na nich závisejících prvků mimo diagonálu.

Pro komplexní pozitivně definitní matice platí analogické vztahy (pruhem je značeno komplexně sdružené číslo):

pro

Výraz pod odmocninou je pro pozitivně definitní matice vždy kladný.

Vzor čtení (bíle) a zápisu (žlutě) pro výpočet Choleského rozkladu na místě podle Choleského–Banachiewiczova algoritmu pro matici řádu 5

Pseudokód

Výpočty ve výše uvedených vzorcích lze provádět různými způsoby. Varianta pojmenovaná po Tadeuszi Banachiewiczovi vypočte dolní trojúhelníkovou matici řádek po řádku a přitom na místě. V pseudokódu je uveden postup rozkladu matice do tvaru :

  Input: hermitovská matice A řádu n reprezentovaná svou dolní trojúhelníkovou polovinou
  Output: dolní trojúhelníková část Choleského faktoru L 
  For i = 1 To n
    For j = 1 To i
      Suma = a(i, j)
      For k = 1 To j-1
        Suma = Suma - a(i, k) * conj(a(j, k))
      If i > j Then
        a(i, j) = Suma / a(j, j)  // Prvek je pod diagonálou.
      Else If Suma > 0 Then       // Prvek na diagonále
        a(i, i) = Sqrt(Suma)      // … musí být vždy nezáporný.
      Else
        ERROR("Matice není pozitivně definitní.")
  Return: L=A

Algoritmus pracuje na místě: postupně mění matici na , aniž by bylo třeba alokovat další paměť pro zápis výsledné matice. Navíc využívá pouze dolní trojúhelníkovou matici, protože hodnoty prvků nad diagonálou lze dopočítat s využitím vlastnosti, že daná matice je hermitovská. Výsledný Choleského faktor je třeba vzít tak, že má prvky nad diagonálou nulové.

Výpočetní složitost

Časová složitost běžně používaných algoritmů pro výpočet Choleského rozkladu je obecně .  Přesněji, na reálných maticích jde o aritmetických operací s prvky dané matice, konkrétně součinů i součtů, dělení a odmocnin. Komplexní matice oproti tomu vyžadují součinů i součtů.

Pro srovnání, LU rozklad coby implementace Gaussovy eliminace, vyžaduje přibližně dvakrát více aritmetických operací.

Numerické záležitosti

Choleského rozklad je bezpodmínečně zpětně stabilní.

Je-li daná matice pozitivně definitní, jsou čísla pod odmocninami vždy kladná v přesné aritmetice. Zaokrouhlovací chyby mohou tuto vlastnost porušit a v takovém případě algoritmus nemůže pokračovat. Tento případ však může nastat, jen je-li matice velmi špatně podmíněna.

LDL rozklad

Výpočtu odmocnin se lze vyhnout ve výpočtu LDL rozkladu. Ten lze spočítat i v přesné zlomkové aritmetice, jak lze odvodit následovně. Pro rozklad reálné matice řádu 3 platí:

Obecně jsou prvky matic a i vyšších řádů dány následujícími rekurentními vzorci:

pro .

Pro komplexní matice je třeba výrazy na pravé straně upravit následovně:

pro .

Vzorec přístupu k prvkům matice opět umožňuje, aby byl v případě potřeby celý výpočet proveden na místě.

Aplikace

Numerické řešení soustavy lineárních rovnic

Choleského rozklad se používá především pro numerické řešení lineárních rovnic s pozitivně definitní maticí soustavy a to tak, že se nejprve provede Choleského rozklad , potom se dopřednou substitucí určí řešení soustavy a nakonec se zpětnou substitucí vyřeší soustava .

Vzhledem k tomu, že matice obou soustav jsou trojúhelníkové, je řešení uvedených soustav snadné. Choleského rozklad (nebo jeho LDL varianta, kde ani není třeba odmocňovat) je u těchto soustav oblíbenou pro svou účinnost a numerickou stabilitu. Ve srovnání s LU rozkladem je zhruba dvakrát efektivnější.

Inverzní matice

Matici inverzní k pozitivně definitní matici lze spočítat pomocí Choleského rozkladu podobným způsobem jako při řešení soustav lineárních rovnic v čase . Postup lze provést i na místě.

Libovolná komplexní regulární matice může být invertována pomocí následující identity, protože je vždy pozitivně definitní:

Metoda nejmenších čtverců

Soustavy s pozitivně definitní maticí soustavy se v aplikacích objevují poměrně často. Například normálové rovnice v lineárních úlohách nejmenších čtverců mají tento tvar a ostatně i vedly k objevu Choleského rozkladu.

Může se také stát, že matice pochází z energetického funkcionálu, který musí být z fyzikálních důvodů kladný. Podobný případ často nastává při numerickém řešení parciálních diferenciálních rovnic .

Nelineární optimalizace

Nelineární vícerozměrné funkce mohou být minimalizovány přes jejich parametry pomocí variant Newtonovy metody nazývané kvazi-Newtonovy metody. Při -té iteraci se postupuje k řešení ve směru definovaným řešením soustavy , kde je gradient a je pozitivně definitní aproximace Hessovy matice.

Další aplikace

Mimo matematiku se Choleského rozklad využívá také v ekonometrickém výzkumu makroekonomických vztahů. V tzv. vektorových autoregresních modelech (VAR) se určuje pořadí, ve kterém se endogenní proměnné navzájem ovlivňují.

Kromě toho se také používá v metodě Monte Carlo k přenesení předem určených korelací do nezávisle generovaných sekvencí náhodných čísel jako diskretizace náhodných procesů.

Implementace

V jazyku C lze výpočet rozkladu zapsat následovně:

for (c=0; c<n; c++) {
  for (sum=0, i=c-1; i>=0; i--)
    sum += sqr(L[c][i]);
  L[c][c] = sqrt(A[c][c] - sum);
  for (r=c+1; r<n; r++) {
    for (sum=0, i=c-1; i>=0; i--)
      sum += L[r][i]*L[c][i];
    L[r][c] = (A[r][c] - sum) / L[c][c];
  }
}

Implementace v programovacích knihovnách

  • Programovací jazyk C : Vědecká knihovna GNU poskytuje několik implementací Choleského rozkladu.
  • Systém počítačové algebry Maxima : funkce cholesky počítá Choleského rozklad.
  • Systém numerických výpočtů GNU Octave poskytuje několik funkcí pro výpočet, aktualizaci a aplikaci Choleského rozkladu.
  • Knihovna LAPACK poskytuje vysoce výkonnou implementaci Choleského rozkladu, která je přístupná z Fortranu, C a většiny jazyků.
  • V Pythonu provádí funkce cholesky z modulu numpy.linalg Choleského rozklad.
  • V Matlabu dává funkce chol Choleského rozklad. Všimněte si, že chol standardně vrací Choleského faktor v horním trojúhelníkovém tvaru, tj. počítá rozklad . Lze předat příznak, aby se místo toho použil dolní trojúhelníkový faktor.
  • V R dává funkce chol Choleského rozklad.
  • V Julia poskytuje funkce cholesky ze standardní knihovny LinearAlgebra Choleského rozklad.
  • V Mathematice lze na matici aplikovat funkci „CholeskyDecomposition“.
  • V C++ podporuje tento rozklad několik knihoven lineární algebry:
    • Armadillo (knihovna C++) poskytuje příkaz chol k provedení Choleského rozkladu.
    • Knihovna Eigen poskytuje Choleského rozklady pro řídké i husté matice.
    • V balíčku ROOT je k dispozici třída TDecompChol .

Odkazy

Reference

V tomto článku byly použity překlady textů z článků Cholesky decomposition na anglické Wikipedii a Cholesky-Zerlegung na německé Wikipedii.

Literatura

  • REKTORYS, Karel. Přehled užité matematiky: II. 7. vyd. Praha: Prometheus, 2000. 874 s. ISBN 80-7196-181-7. Kapitola 30. Numerické metody lineární algebry. 
  • BEČVÁŘ, Jindřich. Lineární algebra. 1.. vyd. Praha: Matfyzpress, 2019. 436 s. ISBN 978-80-7378-392-1. 
  • HLADÍK, Milan. Lineární algebra (nejen) pro informatiky. 1.. vyd. Praha: Matfyzpress, 2019. 328 s. ISBN 978-80-7378-378-5. 
  • OLŠÁK, Petr. Lineární algebra [online]. Praha: 2007 [cit. 2023-02-20]. Dostupné online. 
  • MOTL, Luboš; ZAHRADNÍK, Miloš. Pěstujeme lineární algebru [online]. [cit. 2023-02-20]. Dostupné online. 

Související články

Média použitá na této stránce

Chol.gif
Autor: Erzbischof, Licence: CC BY-SA 3.0
Access and write pattern of the in-place Cholesky–Banachiewicz (Cholesky by row) algorithm on a 5x5 matrix

.

Yellow: Writing. White: Reading. Orange modified.
Cholesky decomposition example.svg
Autor: Jirka Fiala, Licence: CC BY-SA 4.0
An example of Cholesky decompositionof real symmetric matrix of order 3