En algèbre linéaire, un décomposition matricielle ou factorisation matricielle est une factorisation d'une matrice en un produit de matrices. Il existe de nombreuses décompositions matricielles différentes. L'un d'eux est Décomposition de Cholesky .
Le Décomposition de Cholesky ou Factorisation de Cholesky est une décomposition d'une matrice hermitienne définie positive en produit d'une matrice triangulaire inférieure et de sa transposée conjuguée. La décomposition de Cholesky est environ deux fois plus efficace que la décomposition Décomposition LU pour résoudre des systèmes d'équations linéaires.
La décomposition de Cholesky d'une matrice hermitienne définie positive A est une décomposition de la forme UNE = [L][L]T , où L est une matrice triangulaire inférieure avec des entrées diagonales réelles et positives, et LT désigne la transposée conjuguée de L. Chaque matrice hermitienne définie positive (et donc aussi chaque matrice symétrique définie positive à valeur réelle) a une décomposition de Cholesky unique.
![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)
Chaque matrice définie positive et symétrique A peut être décomposée en un produit d'une matrice triangulaire inférieure unique L et de sa transposée : A = L LT
Les formules suivantes sont obtenues en résolvant la matrice triangulaire inférieure ci-dessus et en la transposant. Ce sont les bases de l'algorithme de décomposition de Cholesky :
Jasmine Davis enfant
Exemple :
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)
Vous trouverez ci-dessous l’implémentation de la décomposition de Cholesky.
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 =>Tableau(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> |
>
>
Sortir
Lower Triangular Transpose 2 0 0 2 6 -8 6 1 0 0 1 5 -8 5 3 0 0 3>
Complexité temporelle : O(n^3)
Espace auxiliaire : O(n^2)