V lineární algebře, a rozklad matrice nebo maticová faktorizace je rozklad matice na součin matic. Existuje mnoho různých maticových rozkladů. Jedním z nich je Choleský rozklad .
The Choleský rozklad nebo Choleského faktorizace je rozklad hermitovské pozitivně definitní matice na součin nižší trojúhelníkové matice a její konjugované transpozice. Choleského rozklad je zhruba dvakrát účinnější než rozklad LU rozklad pro řešení soustav lineárních rovnic.
Choleského rozklad hermitovské pozitivně definitní matice A je rozkladem formy A = [L][L]T , kde L je nižší trojúhelníková matice s reálnými a kladnými diagonálními vstupy a LT označuje konjugovanou transpozici L. Každá hermitovská pozitivně-definitní matice (a tedy i každá reálně hodnotná symetrická pozitivně-definitní matice) má unikátní Choleského rozklad.
![left[egin{array}{lll} A_{00} & A_{01} & A_{02} A_{10} & A_{11} & A_{12} A_{20} & A_{ 21} & A_{22} end{array}
ight]=left[egin{array}{lll} L_{00} & 0 & 0 L_{10} & L_{11} & 0 L_{20} & L_{21} & L_{22} end{array}
ight]left[egin{array}{ccc} L_{00} & L_{10} & L_{20} 0 & L_{11} & L_{21} 0 & 0 & L_{22} end{array}
ight]](http://techcodeview.com/img/it-problems-solutions/50/cholesky-decomposition.webp)
Každou symetrickou, pozitivně definitní matici A lze rozložit na součin jedinečné dolní trojúhelníkové matice L a její transpozici: A = L LT
Následující vzorce získáte řešením výše uvedené dolní trojúhelníkové matice a její transpozicí. Toto jsou základem algoritmu Cholesky Decomposition Algorithm:
r v jazyce c
Příklad :
Input :>
![left[egin{array}{ccc} 4 & 12 & -16 12 & 37 & -43 -16 & -43 & 98 end{array}
ight]](http://techcodeview.com/img/it-problems-solutions/50/cholesky-decomposition-3.webp)
Output :>
![left[egin{array}{ccc} 2 & 0 & 0 6 & 1 & 0 -8 & 5 & 3 end{array}
ight]left[egin{array}{ccc} 2 & 6 & -8 0 & 1 & 5 0 & 0 & 3 end{array}
ight]](http://techcodeview.com/img/it-problems-solutions/50/cholesky-decomposition-4.webp)
Níže je implementace Cholesky Decomposition.
C++
// CPP program to decompose a matrix using> // Cholesky Decomposition> #include> using> namespace> std;> const> int> MAX = 100;> void> Cholesky_Decomposition(>int> matrix[][MAX],> >int> n)> {> >int> lower[n][n];> >memset>(lower, 0,>sizeof>(lower));> >// Decomposing a matrix into Lower Triangular> >for> (>int> i = 0; i for (int j = 0; j <= i; j++) { int sum = 0; if (j == i) // summation for diagonals { for (int k = 0; k sum += pow(lower[j][k], 2); lower[j][j] = sqrt(matrix[j][j] - sum); } else { // Evaluating L(i, j) using L(j, j) for (int k = 0; k sum += (lower[i][k] * lower[j][k]); lower[i][j] = (matrix[i][j] - sum) / lower[j][j]; } } } // Displaying Lower Triangular and its Transpose cout << setw(6) << ' Lower Triangular' << setw(30) << 'Transpose' << endl; for (int i = 0; i // Lower Triangular for (int j = 0; j cout << setw(6) << lower[i][j] << ' '; cout << ' '; // Transpose of Lower Triangular for (int j = 0; j cout << setw(6) << lower[j][i] << ' '; cout << endl; } } // Driver Code int main() { int n = 3; int matrix[][MAX] = { { 4, 12, -16 }, { 12, 37, -43 }, { -16, -43, 98 } }; Cholesky_Decomposition(matrix, n); return 0; }> |
>
>
Jáva
// Java program to decompose> // a matrix using Cholesky> // Decomposition> class> GFG {> >// static int MAX = 100;> >static> void> Cholesky_Decomposition(>int>[][] matrix,> >int> n)> >{> >int>[][] lower =>new> int>[n][n];> >// Decomposing a matrix> >// into Lower Triangular> >for> (>int> i =>0>; i for (int j = 0; j <= i; j++) { int sum = 0; // summation for diagonals if (j == i) { for (int k = 0; k sum += (int)Math.pow(lower[j][k], 2); lower[j][j] = (int)Math.sqrt( matrix[j][j] - sum); } else { // Evaluating L(i, j) // using L(j, j) for (int k = 0; k sum += (lower[i][k] * lower[j][k]); lower[i][j] = (matrix[i][j] - sum) / lower[j][j]; } } } // Displaying Lower // Triangular and its Transpose System.out.println(' Lower Triangular Transpose'); for (int i = 0; i // Lower Triangular for (int j = 0; j System.out.print(lower[i][j] + ' '); System.out.print(''); // Transpose of // Lower Triangular for (int j = 0; j System.out.print(lower[j][i] + ' '); System.out.println(); } } // Driver Code public static void main(String[] args) { int n = 3; int[][] matrix = new int[][] { { 4, 12, -16 }, { 12, 37, -43 }, { -16, -43, 98 } }; Cholesky_Decomposition(matrix, n); } } // This code is contributed by mits> |
>
>
Python3
# Python3 program to decompose> # a matrix using Cholesky> # Decomposition> import> math> MAX> => 100>;> def> Cholesky_Decomposition(matrix, n):> >lower>=> [[>0> for> x>in> range>(n>+> 1>)]> >for> y>in> range>(n>+> 1>)];> ># Decomposing a matrix> ># into Lower Triangular> >for> i>in> range>(n):> >for> j>in> range>(i>+> 1>):> >sum1>=> 0>;> ># summation for diagonals> >if> (j>=>=> i):> >for> k>in> range>(j):> >sum1>+>=> pow>(lower[j][k],>2>);> >lower[j][j]>=> int>(math.sqrt(matrix[j][j]>-> sum1));> >else>:> > ># Evaluating L(i, j)> ># using L(j, j)> >for> k>in> range>(j):> >sum1>+>=> (lower[i][k]>*>lower[j][k]);> >if>(lower[j][j]>>0>):> >lower[i][j]>=> int>((matrix[i][j]>-> sum1)>/> >lower[j][j]);> ># Displaying Lower Triangular> ># and its Transpose> >print>(>'Lower Triangular Transpose'>);> >for> i>in> range>(n):> > ># Lower Triangular> >for> j>in> range>(n):> >print>(lower[i][j], end>=> ' '>);> >print>('>', end = '> ');> > ># Transpose of> ># Lower Triangular> >for> j>in> range>(n):> >print>(lower[j][i], end>=> ' '>);> >print>('');> # Driver Code> n>=> 3>;> matrix>=> [[>4>,>12>,>->16>],> >[>12>,>37>,>->43>],> >[>->16>,>->43>,>98>]];> Cholesky_Decomposition(matrix, n);> # This code is contributed by mits> |
>
>
C#
// C# program to decompose> // a matrix using Cholesky> // Decomposition> using> System;> class> GFG {> >// static int MAX = 100;> >static> void> Cholesky_Decomposition(>int>[, ] matrix,> >int> n)> >{> >int>[, ] lower =>new> int>[n, n];> >// Decomposing a matrix> >// into Lower Triangular> >for> (>int> i = 0; i for (int j = 0; j <= i; j++) { int sum = 0; // summation for diagonals if (j == i) { for (int k = 0; k sum += (int)Math.Pow(lower[j, k], 2); lower[j, j] = (int)Math.Sqrt( matrix[j, j] - sum); } else { // Evaluating L(i, j) // using L(j, j) for (int k = 0; k sum += (lower[i, k] * lower[j, k]); lower[i, j] = (matrix[i, j] - sum) / lower[j, j]; } } } // Displaying Lower // Triangular and its Transpose Console.WriteLine( ' Lower Triangular Transpose'); for (int i = 0; i // Lower Triangular for (int j = 0; j Console.Write(lower[i, j] + ' '); Console.Write(''); // Transpose of // Lower Triangular for (int j = 0; j Console.Write(lower[j, i] + ' '); Console.WriteLine(); } } // Driver Code static int Main() { int n = 3; int[, ] matrix = { { 4, 12, -16 }, { 12, 37, -43 }, { -16, -43, 98 } }; Cholesky_Decomposition(matrix, n); return 0; } } // This code is contributed by mits> |
>
>
PHP
// PHP program to decompose // a matrix using Cholesky // Decomposition $MAX = 100; function Cholesky_Decomposition($matrix, $n) { $lower; for ($i = 0; $i <= $n; $i++) for ($j = 0; $j <= $n; $j++) $lower[$i][$j] = 0; // Decomposing a matrix // into Lower Triangular for ($i = 0; $i <$n; $i++) { for ($j = 0; $j <= $i; $j++) { $sum = 0; // summation for diagonals if ($j == $i) { for ($k = 0; $k <$j; $k++) $sum += pow($lower[$j][$k], 2); $lower[$j][$j] = sqrt($matrix[$j][$j] - $sum); } else { // Evaluating L(i, j) // using L(j, j) for ($k = 0; $k <$j; $k++) $sum += ($lower[$i][$k] * $lower[$j][$k]); $lower[$i][$j] = ($matrix[$i][$j] - $sum) / $lower[$j][$j]; } } } // Displaying Lower Triangular // and its Transpose echo ' Lower Triangular' . str_pad('Transpose', 30, ' ', STR_PAD_BOTH) . '
'; for ($i = 0; $i <$n; $i++) { // Lower Triangular for ($j = 0; $j <$n; $j++) echo str_pad($lower[$i][$j], 6, ' ', STR_PAD_BOTH).' '; echo ' '; // Transpose of // Lower Triangular for ($j = 0; $j <$n; $j++) echo str_pad($lower[$j][$i], 6, ' ', STR_PAD_BOTH).' '; echo '
'; } } // Driver Code $n = 3; $matrix = array(array(4, 12, -16), array(12, 37, -43), array(-16, -43, 98)); Cholesky_Decomposition($matrix, $n); // This code is contributed by vt_m. ?>> |
>
>
Javascript
> // javascript program to decompose> // a matrix using Cholesky> // Decomposition> >// function MAX = 100;> function> Cholesky_Decomposition(matrix,n)> {> >var> lower = Array(n).fill(0).map(x =>Array(n).fill(0));> >// Decomposing a matrix> >// into Lower Triangular> >for> (>var> i = 0; i for (var j = 0; j <= i; j++) { var sum = 0; // summation for diagonals if (j == i) { for (var k = 0; k sum += parseInt(Math.pow(lower[j][k], 2)); lower[j][j] = parseInt(Math.sqrt( matrix[j][j] - sum)); } else { // Evaluating L(i, j) // using L(j, j) for (var k = 0; k sum += (lower[i][k] * lower[j][k]); lower[i][j] = (matrix[i][j] - sum) / lower[j][j]; } } } // Displaying Lower // Triangular and its Transpose document.write(' Lower Triangular Transpose '); for (var i = 0; i // Lower Triangular for (var j = 0; j document.write(lower[i][j] + ' '); // Transpose of // Lower Triangular for (var j = 0; j document.write(lower[j][i] + ' '); document.write(' '); } } // Driver Code var n = 3; var matrix = [[ 4, 12, -16 ], [ 12, 37, -43 ], [ -16, -43, 98 ] ]; Cholesky_Decomposition(matrix, n); // This code contributed by Princi Singh> |
>
>
Výstup
Lower Triangular Transpose 2 0 0 2 6 -8 6 1 0 0 1 5 -8 5 3 0 0 3>
Časová náročnost: O(n^3)
Pomocný prostor: O(n^2)