În algebra liniară, a descompunerea matricei sau factorizarea matriceală este o factorizare a unei matrice într-un produs de matrice. Există multe descompoziții matrice diferite. Unul dintre ei este Descompunerea Cholesky .
The Descompunerea Cholesky sau Factorizarea Cholesky este o descompunere a unei matrice hermitiene, definită pozitiv în produsul unei matrice triunghiulare inferioară și transpunerea ei conjugată. Descompunerea Cholesky este de aproximativ de două ori mai eficientă decât cea descompunerea LU pentru rezolvarea sistemelor de ecuații liniare.
Descompunerea Cholesky a unei matrici hermitiene definite pozitive A este o descompunere a formei A = [L][L]T , Unde L este o matrice triunghiulară inferioară cu intrări diagonale reale și pozitive și LT denotă transpunerea conjugată a lui L. Fiecare matrice hermitiană pozitiv-definită (și astfel, de asemenea, fiecare matrice simetrică pozitiv-definită cu valoare reală) are o descompunere Cholesky unică.
![left[egin{array}{lll} A_{00} și A_{01} și A_{02} A_{10} și A_{11} și A_{12} A_{20} și A_{ 21} și A_{22} end{array}
ight]=left[egin{array}{lll} L_{00} și 0 și 0 L_{10} și L_{11} și 0 L_{20} și L_{21} și L_{22} end{array}
ight]left[egin{array}{ccc} L_{00} și L_{10} și 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)
Fiecare matrice definită pozitivă simetrică A poate fi descompusă într-un produs al unei matrici triunghiulare inferioare unice L și transpunerea acesteia: A = L LT
Următoarele formule se obțin prin rezolvarea matricei triunghiulare inferioare de mai sus și transpunerea acesteia. Acestea sunt baza algoritmului de descompunere Cholesky:
schimbarea memoriei
Exemplu :
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)
Mai jos este implementarea Cholesky Descomposition.
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]>>>> >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 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>>>
IeșireLower Triangular Transpose 2 0 0 2 6 -8 6 1 0 0 1 5 -8 5 3 0 0 3>Complexitatea timpului: O(n^3)
Spațiu auxiliar: O(n^2)