선형대수 05 - LU분해

LU 분해 (LU Decomposition)

어떤 Matrix A는 항상 L(하삼각행렬, Lower Triangluar Matrix)와 U(상삼각행렬, Upper Triangular Matrix)의 곱으로 표현할 수 있다는 것이 LU 분해(LU Decomposition)입니다. 여기서 하삼각행렬이란

[200370194]\begin{bmatrix} 2 & 0 & 0 \\ 3 & 7 & 0 \\ 1 & 9 & 4 \end{bmatrix}

와 같이 대각선을 기준으로 위쪽 성분들이 모두 0인 행렬을 말하고,
상삼각행렬이란 반대로

[194037002]\begin{bmatrix} 1 & 9 & 4 \\ 0 & 3 & 7 \\ 0 & 0 & 2 \end{bmatrix}

와 같이 대각선을 기준으로 아래쪽 성분들이 모두 0인 행렬을 말합니다.

A=[2168]  E21A=[1031][2168]=[2105]=UA = \begin{bmatrix} 2 & 1 \\ 6 & 8 \end{bmatrix} \; E_{21}A = \begin{bmatrix} 1 & 0 \\ -3 & 1 \end{bmatrix} \begin{bmatrix} 2 & 1 \\ 6 & 8 \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 0 & 5 \end{bmatrix} = U and  E211U=[1031][2105]=Aand \; E_{21}^{-1}U = \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} 2 & 1 \\ 0 & 5 \end{bmatrix} = A

어떤 Matrix A를 Upper Triangular Matrix로 변환해줄 때 사용된 Elementary Matrix를 모두 곱해 역행렬을 취하면 Lower Triangular Matrix가 나옵니다.

LU Decomposition을 하는 이유

  • Ax=bAx = b를 푸는 과정. 만약 A가 L과 U로 주어진다면, LUx=bLUx = b가 됩니다. (예를 들어서 Ux=yUx = y라고 두면 Ly=bLy = b의 형태가 됨.)
    Ly=bLy=b문제는, L이 Lower Triangular Matrix이기 때문에, Forward Subtitution이 가능해진다. Triangular 형태이기 때문에 Solution을 구하기 쉬워진다는 장점이 있습니다.
  • Ax=bAx = b를 풀 때 나타나는 Stability 문제. 1 conditioned 문제에서 숫자의 마이너한 Approximation도 Solution에 아주 큰 영향을 미칠 수 있는데, 이것을 Stable(안정성) 문제라고 합니다. 안정성이 의심되는 연립방정식을 풀 때, LU로 분할해주면서 안정성을 높일 수 있습니다. 좀 더 Solution의 오차의 값을 줄일 수 있는 가능성을 높입니다.
© 2020 leshleekor