[응용선형대수] LU Decomposition

앞에서 작성한 글을 참고하는 것을 추천드립니다.

이번에는 LU Decomposition에 대해서 다루겠습니다. LU Decomposition은 linear equation의 solution을 구할 때 도움이 되기 때문에 소개해드립니다.

 

 

이 글에서 말하는 LU가 무엇을 의미하느냐,

$L\text{ : Lower triangular matrix}$

$U \text{ : Upper triangular matrix}$

입니다.

 

 

LU Decomposition

 

어떤 matrix A가 A = LU로 표현할 수 있다고 해보겠습니다.

 

우리가 앞서서 operation matrix 3가지를 살펴보았는데요, (자세한 내용은 아래 링크)

 

normal-engineer.tistory.com/66?category=964340

[응용선형대수] 역행렬 구하기

 

 

1) $r_{i} \leftarrow cr_{i}$

2) $r_{i} \leftrightharpoons r_{j}$

3) $r_{i} \leftarrow r_{i}+cr_{j}$

 

행을 교체해주는 두번째 operation인 permutation matrix를 제외하고

1)번의 경우에는 diagonal matrix이고

3)번은 Upper triangular matrix로 만든 상태에서 diagonal matrix로 만들지 않는다면, 무조건 Lower triangular matrix로 나옵니다.

 

왜냐하면 Upper triangular matrix를 만든다는 것은 내가 선택한 row에서 pivot을 살리기 위해서 앞의 element를 0으로 만든다는 것인데, 이 경우에는 첫번째 row를 가지고 아래에 있는 모든 row의 첫번째 element를 0으로 만듭니다. 그 경우에 나오는 operation matrix는 Lower triangular matrix가 됩니다.

 

Example)

$r_{2}\leftarrow r_{2}+3r_{1} \Rightarrow$ $\begin{bmatrix}1 & 0 &0 \\ 3 & 1 &0 \\ 0 & 0 &1 \end{bmatrix}$

$r_{3}\leftarrow r_{3}-2r_{1}\Rightarrow$ $\begin{bmatrix}1 & 0 &0 \\ 0 & 1 &0 \\ -2 & 0 &1 \end{bmatrix}$

 

모두 lower triangular matrix가 됩니다.

 

따라서, LU Decomposition이라는 것은 1), 3) operation matrix(Lower triangular matrix)의 조합으로 어떤 matrix를 Upper triangular matrix로 만드는 과정으로 볼 수 있습니다.

 

 

이제 LU Decomposition하는 예시를 보면서 어떻게 하는지 보겠습니다.

 

 

(위 그림의 포스트잇에서 나온 것을 참고해주세요.

Lower triangular matrix의 곱은 Lower이고, Lower의 inverse matrix 역시 Lower triangular matrix가 된다는 성질이 있습니다. 또한 대각선에 있는 element가 1인 triangular matrix끼리 곱하면 대각선이 1인 matrix가 나옵니다.)

 

따라서 A matrix를 operation matrix의 곱으로 Upper triangular matrix로 만들었습니다. operation matrix를 inverse해서 곱하면 A가 Lower triagular matrix와 Upper triangular matrix의 곱으로 나타낼 수 있습니다.

 

이렇게 A matrix를 LU Decomposition 했을 때 방정식을 다른 방식으로 풀 수 있게 됩니다.

 

$\left\{\begin{matrix}2x_{1}+x_{2}+x_{3}=1\\ 4x_{1}+x_{2}+x_{4}=-2\\ -2x_{1}+2x_{2}+x_{3}+x_{4}=7\end{matrix}\right.$

 

다음 equation을 풀어야 할 때 아래와 같이 풀 수 있습니다.

 

마지막 (ii)를 풀면 됩니다.

 

물론 맨 처음부터 식을 가지고 풀어도 되지만, equation을 matrix로 만든 것이 triangular matrix form이면 더 간단하게 풀 수 있습니다. 식이 복잡해질수록 도움이 될 것으로 보입니다.

 

 

마지막으로 LU Decomposition을 할 때 $U$ matrix를 $DU^{'}\text{, where D is diagonal matrix}$로 바꿀 수 있습니다.

 

 

마지막으로, 위에서 operation에 대해서 이야기할 때 2)번 permutation matrix는 Lower triangular matrix가 아니기 때문에 1), 3) operation만 가지고 A matrix를 Upper triangular matrix로 나타냈습니다.

 

하지만 어쩔 수 없이 row와 row를 바꿔줘야만 Upper triangular matrix로 만들 수 있는 case들도 있습니다.

 

따라서 일반적으로 생각했을 때, 어떤 invertible한 matrix든 간에 permutation이 잘 이루어진다면(필요없는 matrix도 포함) LU Decomposition을 할 수 있습니다. invertible이 가정으로 들어간 이유는, invertible하지 않은 matrix는 일부 또는 전체 diagonal이 0이기 때문입니다.

 

$\text{Theorem}$

$\text{Let A be invertible, then for some fixed permutation matrix P, PA=LDU in a unique way}$

 

 

---