Lineārajā algebrā a matricas sadalīšanās vai matricas faktorizācija ir matricas faktorizācija matricu reizinājumā. Ir daudz dažādu matricu sadalījumu. Viens no tiem ir Cholesky sadalīšanās .
The Cholesky sadalīšanās vai Cholesky faktorizācija ir hermitiskas, pozitīvi noteiktas matricas sadalīšanās zemākas trīsstūrveida matricas un tās konjugāta transponēšanas reizinājumā. Cholesky sadalīšanās ir aptuveni divas reizes efektīvāka nekā LU sadalīšanās lineāro vienādojumu sistēmu risināšanai.
Hermīta pozitīvas-definētas matricas A Cholesky dekompozīcija ir formas dekompozīcija A = [L][L]T , kur L ir zemāka trīsstūrveida matrica ar reāliem un pozitīviem diagonāles ierakstiem, un LT apzīmē L konjugētu transponēšanu. Katrai Hermita pozitīvā-definētās matricai (un līdz ar to arī katrai reālās vērtības simetriskai pozitīvi noteiktajai matricai) ir unikāla Cholesky dekompozīcija.
![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{masīvs}pa labi]](http://techcodeview.com/img/it-problems-solutions/50/cholesky-decomposition.webp)
Katru simetrisko, pozitīvu noteikto matricu A var sadalīt unikālas apakšējās trīsstūrveida matricas L reizinājumā un tās transponēšanā: A = L LT
Sekojošās formulas iegūst, atrisinot augstāk minēto apakšējo trīsstūrveida matricu un tās transponēšanu. Tie ir Cholesky sadalīšanās algoritma pamatā:
rujira banerjee
Piemērs :
Input :>
![left[egin{masīvs}{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)
Zemāk ir Cholesky Decomposition ieviešana.
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 =>Masīvs(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>>>
IzvadeLower Triangular Transpose 2 0 0 2 6 -8 6 1 0 0 1 5 -8 5 3 0 0 3>Laika sarežģītība: O(n^3)
Palīgtelpa: O(n^2)