Cholesky-ontleding: Matrix-ontleding
In lineaire algebra is a matrix-ontleding of matrixfactorisatie is een factorisatie van een matrix in een product van matrices. Er zijn veel verschillende matrixontledingen. Een van hen is Cholesky-ontbinding .
De Cholesky-ontbinding of Cholesky-factorisatie is een ontleding van een Hermitische, positief bepaalde matrix in het product van een lagere driehoekige matrix en de geconjugeerde transpositie ervan. De Cholesky-ontleding is ongeveer twee keer zo efficiënt als de LU-ontleding voor het oplossen van stelsels van lineaire vergelijkingen.
De Cholesky-ontleding van een Hermitische positief-bepaalde matrix A is een ontleding van de vorm EEN = [L][L] T , waar L is een onderste driehoekige matrix met reële en positieve diagonale ingangen, en L T geeft de geconjugeerde transpositie van L aan. Elke Hermitische positief-definitieve matrix (en dus ook elke symmetrische positief-definiete matrix met reële waarde) heeft een unieke Cholesky-ontbinding.
![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)
Elke symmetrische, positief bepaalde matrix A kan worden ontleed in een product van een unieke onderste driehoekige matrix L en zijn getransponeerde: A = L L T
De volgende formules worden verkregen door de bovenstaande onderste driehoekige matrix op te lossen en de transponering ervan. Dit vormen de basis van het Cholesky-decompositiealgoritme:
Voorbeeld :
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)
Hieronder vindt u de implementatie van 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; }> |
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 =>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> |
Uitvoer
Lower Triangular Transpose 2 0 0 2 6 -8 6 1 0 0 1 5 -8 5 3 0 0 3
Tijdcomplexiteit: O(n^3)
Hulpruimte: O(n^2)
