gyeo-ri.com

*LU분해의 과정에 관한 내용은 이전 포스팅 참조 가우스-조르당 소거법 포스팅에서 $Ax = b$를 다음과 같이 정의하였다. $ \begin{pmatrix} 2 & 2 & 1 \\ 2 & 1 & 3 \\ 1 & 2 & 3 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} 11 \\ 11 \\ 10 \end{pmatrix} $ 이때, LU 분해를 통해 행렬 A를 분해할 수 있다. $A = L \cdot U = \begin{pmatrix} 2 & 0 & 0 \\ 2 & -1 & 0 \\ 1 & 1 & 9/2 \end{pmatrix} \cdot \begin{pmatrix} 1 & 1 & 1/2 \\ 0 & 1 & -2 \\ 0 ..

LU 분해 LU 분해는 연립방정식의 해를 푸는 방법 중 하나로, 일반적으로 $O(n^3)$의 시간복잡도를 가지는 가우스-조르당 소거법에 비해 적은 소요시간을 가지는 것으로 알려져 있다(실제로는 LU 분해를 사용해도 $O(n^3)$ 정도의 시간이 소요될 수 있다). LU 분해는 주어진 연립방정식 $Ax = b$에서의 $A$를 $L$, $U$로 표현되는 하삼각행렬(Lower Triangular Matrix)과 상삼각행렬(Upper Triangular Matrix)의 행렬곱으로 표현하는 과정과, 분해된 $L$,$U$ 행렬을 대입 연산(Back Substitution/Forward Substitution)을 통해 해를 구하는 두 과정으로 나뉘는데, 이번 포스트에서는 분해 과정에 대하여 설명하고, 해를 구하는 과..