У лінійній алгебрі а матричне розкладання або матрична факторізація є розкладанням матриці на добуток матриць. Існує багато різних розкладів матриці. Один із них Розкладання Холєського .
The Розкладання Холєського або Розкладання Холєського на множники є розкладанням ермітової позитивно визначеної матриці на добуток нижньої трикутної матриці та її спряженого транспонування. Розклад Холєського приблизно вдвічі ефективніший, ніж LU розкладання для розв'язування систем лінійних рівнянь.
Розклад Холєського ермітової позитивно визначеної матриці A є розкладом виду A = [L][L]Т , де Л є нижньою трикутною матрицею з дійсними та позитивними діагональними елементами, і ЛТ позначає сполучене транспонування L. Кожна ермітова позитивно визначена матриця (і, отже, також кожна дійсна симетрична позитивно визначена матриця) має унікальний розклад Холєського.
![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)
Кожна симетрична позитивно визначена матриця A може бути розкладена на добуток унікальної нижньої трикутної матриці L та її транспонування: A = L LТ
Наступні формули отримано шляхом розв’язування нижньої трикутної матриці та її транспонування. Це основа алгоритму декомпозиції Холєського:
реєструвати пам'ять
приклад :
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)
Нижче наведено реалізацію розкладання Холецкого.
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; }> |
>
>
Java
// 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 =>Масив(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> |
>
>
Вихід
Lower Triangular Transpose 2 0 0 2 6 -8 6 1 0 0 1 5 -8 5 3 0 0 3>
Часова складність: O(n^3)
Допоміжний простір: O(n^2)