Choleského dekompozice

Kategorie: Nezařazeno (celkem: 23179 referátů a seminárek)

Informace o referátu:

Příbuzná témata



Choleského dekompozice

Choleského dekompozice (také Choleského rozklad) je metoda rozložení symetrické pozitivně definitní čtvercové matice A na součin dolní a horní trojúhelníkové matice, přičemž jedna trojuhélníková matice je transpozicí matice druhé.

old A = old L cdot old L^T

Dolní trojúhelníková matice L z tohoto rozkladu se nazývá Choleského trojúhelník matice A.

Obsah

Využití

Výpočet inverzní matice

Inverzní matici A-1 lze vypočítat z inverzní matice L-1 podle následujícího vztahu.

old A^{-1} = {left(old L^{-1}
ight)}^T cdot old L^{-1}

Samotný výpočet inverzní matice L-1 není příliš obtížný, neboť to je také dolní trojúhelníková matice a lze ji vypočítat užitím vztahu L-1 L = E, kde E je jednotková matice.

Pro prvky na hlavní diagonále lze odvodit následující vztah.

l_{kk}^{-1} l_{kk} = 1  longrightarrow  l_{kk}^{-1} = 1 / l_{kk}

Prvky pod diagonálou lze počítat postupně zprava doleva následovně.

 sum_{i=c}^{r} l_{ri}^{-1} l_{ic} = 0  longrightarrow  l_{rc}^{-1} = - 1/l_{cc} cdot sum_{i=c+1}^{r} l_{ri}^{-1} l_{ic}

Řešení soustavy lineárních rovnic

Soustavu lineárních rovnic Ax = b lze řešit převodem na dvě soustavy rovnic.

old L old y = old b
old L^T old x = old y

Vzhledem k tomu, že matice soustavy jsou trojúhelníkové, je řešení uvedených rovnic zpětným dosazením velmi snadné.

Algoritmus rozkladu

Prvky matice L je možné počítat po sloupcích zleva a v každém sloupci odshora dolů.

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

a_{11} = l_{11} l_{11}  longrightarrow  l_{11} = sqrt{a_{11}}
a_{21} = l_{21} l_{11}  longrightarrow  l_{21} = a_{21} / l_{11}
 vdots
a_{n1} = l_{n1} l_{11}  longrightarrow  l_{n1} = a_{n1} / l_{11}

Pro druhý sloupec platí:

a_{22} = l_{21} l_{21} + l_{22} l_{22}  longrightarrow  l_{22} = sqrt{a_{22} - l_{21}^2}
a_{32} = l_{31} l_{21} + l_{32} l_{22}  longrightarrow  l_{32} = left( a_{32} - l_{31} l_{21} 
ight) / l_{22}
 vdots
a_{n2} = l_{n1} l_{21} + l_{n2} l_{22}  longrightarrow  l_{n2} = left( a_{n2} - l_{n1} l_{21} 
ight) / l_{22}

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

a_{kk} = sum_{i=1}^{k} l_{ki}^2  longrightarrow  l_{kk} = sqrt{a_{kk} - sum_{i=1}^{k-1} l_{ki}^2}

Pro prvky pod diagonálou lze odvodit následující vztah.

a_{rc} = sum_{i=1}^{c} l_{ri} l_{ci}  longrightarrow  l_{rc} = left( a_{kk} - sum_{i=1}^{c-1} l_{ri} l_{ci} 
ight) / l_{cc}

V jazyku C lze uvedený postup 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];
  }
}


Nový příspěvek


Ochrana proti spamu. Kolik je 2x4?



Na-mobil.cz

Spřátelené weby

Přidat stránku k oblíbeným

Nejnovější v diskusi

Diskusní fórum »

TIP: Chcete zkrátit dlouho chvíli sobě nebo blízkému?
Klikněte na Puzzle-prodej.cz a vyberte si z 5000 motivů skladem!
TIP: Hračky a hry za dobré ceny?
Klikněte na Hračky obchod.cz a vyberte si z tisícovky hraček skladem!