촐레스키 분해(Cholesky Decomposition) : 행렬 분해
선형대수학에서는 행렬 분해 또는 행렬 분해 행렬을 행렬의 곱으로 인수분해하는 것입니다. 다양한 행렬 분해가 있습니다. 그 중 하나는 촐레스키 분해 .
그만큼 촐레스키 분해 또는 촐레스키 인수분해 에르미트 양의 정부 행렬을 하부 삼각 행렬과 그 공액 전치의 곱으로 분해하는 것입니다. Cholesky 분해는 대략 2배 효율적입니다. LU 분해 선형 방정식 시스템을 풀기 위한 것입니다.
에르미트 양의 정부 행렬 A의 Cholesky 분해는 다음 형식의 분해입니다. A = [엘][엘] 티 , 어디 엘 실수 및 양의 대각선 항목이 있는 하부 삼각 행렬입니다. 엘 티 는 L의 켤레 전치를 나타냅니다. 모든 에르미트 양의 정부 행렬(및 모든 실수 값 대칭 양의 정부 행렬)에는 고유한 Cholesky 분해가 있습니다.
![left[egin{array}{lll} A_{00} & A_{01} & A_{02} A_{10} & A_{11} & A_{12} A_{20} & A_{ 21} & A_{22} end{배열}
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{배열}
ight]](http://techcodeview.com/img/it-problems-solutions/50/cholesky-decomposition.webp)
모든 양의 정부호 대칭 행렬 A는 고유한 하부 삼각 행렬 L과 전치의 곱으로 분해될 수 있습니다. A = LL 티
위의 하삼각행렬과 그 전치를 풀어서 다음 공식을 얻습니다. Cholesky 분해 알고리즘의 기본은 다음과 같습니다.
예 :
Input :
![left[egin{배열}{ccc} 4 & 12 & -16 12 & 37 & -43 -16 & -43 & 98 end{배열}
ight]](http://techcodeview.com/img/it-problems-solutions/50/cholesky-decomposition-3.webp)
Output :
![left[egin{배열}{ccc} 2 & 0 & 0 6 & 1 & 0 -8 & 5 & 3 end{배열}
ight]left[egin{배열}{ccc} 2 & 6 & -8 0 & 1 & 5 0 & 0 & 3 end{배열}
ight]](http://techcodeview.com/img/it-problems-solutions/50/cholesky-decomposition-4.webp)
아래는 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 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> |
파이썬3
# 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# 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 =>배열(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
시간 복잡도: 오(n^3)
보조 공간: 오(n^2)
