[Linear Algebra] LU Factorization

 

Guassian elimination와 upper triangular matrix

non-singular $3\times 3$ matrix $A$가 row exchange없이 upper-triangular matrix $U$로 변환 가능하다고 하자. ^[각주:1] 예를 들어 다음의 matrix $A$가 있다. 

 

$$A=\left[\begin{array}{ccc}2& 1& 1\\ 4& 3& 7\\ -2& 1& 3\end{array}\right]$$

 

이 matrix에 대한 equation $Ax=b$가 다음과 같다.

 

$$\begin{array}{rl}Ax& =b\\ \left[\begin{array}{ccc}2& 1& 1\\ 4& 3& 7\\ -2& 1& 3\end{array}\right]\left[\begin{array}{c}u\\ v\\ w\end{array}\right]& =\left[\begin{array}{c}0\\ 16\\ 14\end{array}\right]\end{array}$$

 

이때 이 equation의 해를 구하기 위해 gaussian elimination을 사용할 수 있다.

 

먼저 row 2에서 row 1의 2배를 뺀다.

$$E_{21}A=\left[\begin{array}{ccc}1& 0& 0\\ -2& 1& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccc}2& 1& 1\\ 4& 3& 7\\ -2& 1& 3\end{array}\right]=\left[\begin{array}{ccc}2& 1& 1\\ 0& 1& 5\\ -2& 1& 3\end{array}\right]$$

 

그 다음 row3에서 row1의 -1배를 뺀다.

$$E_{31}{E}_{21}A=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 1& 0& 1\end{array}\right]\left[\begin{array}{ccc}1& 0& 0\\ -2& 1& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccc}2& 1& 1\\ 4& 3& 7\\ -2& 1& 3\end{array}\right]=\left[\begin{array}{ccc}2& 1& 1\\ 0& 1& 5\\ 0& 2& 4\end{array}\right]$$

 

이러면 첫 번째 column에는 row1의 pivot을 제외하고는 다른 값이 남지 않게 되었다.

 

이어서 계속해보면, row3에서 row2의 2배를 뺀다.

 

$$E_{32}{E}_{31}{E}_{21}A=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& -2& 1\end{array}\right]\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 1& 0& 1\end{array}\right]\left[\begin{array}{ccc}1& 0& 0\\ -2& 1& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccc}2& 1& 1\\ 4& 3& 7\\ -2& 1& 3\end{array}\right]=\left[\begin{array}{ccc}2& 1& 1\\ 0& 1& 5\\ 0& 0& -6\end{array}\right]$$

 

이러면 각 pivot만 남게 되고 elimination process가 모두 종료되어 upper triangular matrix $U$만 남게 된다.

 

$$E_{32}{E}_{31}{E}_{21}A=\left[\begin{array}{ccc}2& 1& 1\\ 0& 1& 5\\ 0& 0& -6\end{array}\right]=U$$

 

이때 row의 subtraction을 수행하는 $E_{21},E_{32}$와 같은 matrix들을 elemantary matrix라고 한다.

 

---

A=LU

만약 위의 equation $E_{32}{E}_{31}{E}_{21}A=U$에서 왼쪽에 $A$만 남기려면 어떻게 해야 할까?

 

양변의 왼쪽에 $(E_{32}{E}_{31}{E}_{21})$의 inverse를 곱하면 될 것이다. 여러 행렬의 곱의 inverse matrix는 그 순서가 반대가 되므로, $E_{21}^{-1}{E}_{31}^{-1}{E}_{32}^{-1}$를 곱하면 된다. 이렇게 되면 $$A=E_{21}^{-1}{E}_{31}^{-1}{E}_{32}^{-1}U$$가 된다.

 

이때, $E_{21}^{-1}{E}_{31}^{-1}{E}_{32}^{-1}$는 항상 main diagonal 아래에만 수가 존재하는 lower triangular matrix이다.

이 경우에는 다음과 같다.

 

$$E_{21}^{-1}{E}_{31}^{-1}{E}_{32}^{-1}=\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ -1& 2& 1\end{array}\right]=L$$

 

따라서 이를 간단하게 $L$로 쓰면, 위의 $A$는 다음과 같이 나타낼 수 있다.

 

$$\begin{array}{rl}A& =LU\\ \left[\begin{array}{ccc}2& 1& 1\\ 4& 3& 7\\ -2& 1& 3\end{array}\right]& =\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ -1& 2& 1\end{array}\right]\left[\begin{array}{ccc}2& 1& 1\\ 0& 1& 5\\ 0& 0& -6\end{array}\right]\end{array}$$

 

---

이 형태가 중요한 이유

$EA=U$와 $A=LU$는 사실 같은 식이다. 하지만 $A=LU$의 형태로 식을 표현하는 것이 더 중요한 이유는 $L$의 diagonal 아래에 있는 각 entry들이 multiplier를 그대로 나타내기 때문이다. 예를 들어 위의 경우에서는, 우리가 gaussian elimination을 하기 위해 2, -1, 2를 곱해서 빼 주었는데 그 수들이 그 위치의 $L$에 있는 것을 볼 수 있다.

 

$$L=\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ -1& 2& 1\end{array}\right]$$

 

이는 $E$에서는 성립하지 않는다. 직접 E를 계산해 보면, 

 

$$\begin{array}{rl}E=E_{32}{E}_{31}{E}_{21}& =\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& -2& 1\end{array}\right]\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 1& 0& 1\end{array}\right]\left[\begin{array}{ccc}1& 0& 0\\ -2& 1& 0\\ 0& 0& 1\end{array}\right]\\ & =\left[\begin{array}{ccc}1& 0& 0\\ -2& 1& 0\\ 5& -2& 1\end{array}\right]\end{array}$$

 

결과값에서 multiplier의 형태를 찾아볼 수 없음을 알 수 있다. 

 

---

LU factorization를 이용한 equation의 해 찾기

만약 $A=LU$형태로 나타내는 데 성공했다면, 쉽게 $Ax=b$의 해를 찾을 수 있다. 이는 두 가지 과정을 거쳐 진행된다.

 

1. $Lc=b$
2. $Ux=c$

$Ax=b$는 $LUx=b$로 표현할 수 있다. 이때 만약 $Ux=c$라고 둔다면, $Lc=b$가 되는 것이다. 이를 가지고 c의 값을 구한 뒤에, $Ux=c$를 이용하여 $x$의 해를 최종적으로 구할 수 있다. 이 방법이 유용한 이유는, 이미 elimination이 완료된 두 개의 matrix를 가지고 equation을 만들기 때문에 곧바로 back-substitution만 두 번 적용하여 해를 구할 수 있기 때문이다.

 

이를 이용하여 직접 위의 equation의 해를 구해보자.

 

$$\begin{array}{rl}Ax& =b\\ \left[\begin{array}{ccc}2& 1& 1\\ 4& 3& 7\\ -2& 1& 3\end{array}\right]\left[\begin{array}{c}u\\ v\\ w\end{array}\right]& =\left[\begin{array}{c}0\\ 16\\ 14\end{array}\right]\end{array}$$

 

였다. 여기서 1번 과정을 수행한다.

 

$$\begin{array}{rl}Lc& =b\\ \left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ -1& 2& 1\end{array}\right]\left[\begin{array}{c}{c}_1\\ c_2\\ c_3\end{array}\right]& =\left[\begin{array}{c}0\\ 16\\ 14\end{array}\right]\end{array}$$ 

 

를 풀면, 

 

$$c=\left[\begin{array}{c}0\\ 16\\ -18\end{array}\right]$$

 

이다. 이제 2번 과정을 수행한다.

 

$$\begin{array}{rl}Ux& =c\\ \left[\begin{array}{ccc}2& 1& 1\\ 0& 1& 5\\ 0& 0& -6\end{array}\right]\left[\begin{array}{c}u\\ v\\ w\end{array}\right]& =\left[\begin{array}{c}0\\ 16\\ -18\end{array}\right]\end{array}$$

 

를 풀면, 

 

$$x=\left[\begin{array}{c}-2\\ 1\\ 3\end{array}\right]$$

 

으로 손쉽게 해를 구할 수 있다.

 

---

PA = LU

만약 row exchange가 필요한 경우에는 LU factorization을 어떻게 수행할 수 있을까? 간단하다. A 앞에 permutation matrix $P$를 붙여주면 된다. 예를 들어 다음과 같은 matrix $A$가 있다고 하자.

 

$$A=\left[\begin{array}{cc}0& 2\\ 3& 4\end{array}\right]$$

 

이 경우에는 첫 row의 첫 번째 entry가 0이므로 pivot이 될 수 없다. 이런 경우에는 row exchange를 위해서 다음과 같은 permutation matrix $P$를 $A$ 앞에 곱해주면 된다.

 

$$P=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$$

 

---

A = LDU

위에서 LU factorization을 했던 것을 자세히 살펴보면, 

 

$$\begin{array}{rl}A& =LU\\ \left[\begin{array}{ccc}2& 1& 1\\ 4& 3& 7\\ -2& 1& 3\end{array}\right]& =\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ -1& 2& 1\end{array}\right]\left[\begin{array}{ccc}2& 1& 1\\ 0& 1& 5\\ 0& 0& -6\end{array}\right]\end{array}$$

 

필연적으로 아주 곤란하다는 생각이 들 수 밖에 없다. $L$은 diagonal entry가 모두 1인데 반해, $U$는 그렇지 않기 때문이다. 따라서 이러한 asymmetry를 해결하기 위해서, $U$를 $D$와 $U^{\prime }$로 분해하여 다음과 같이 쓸 수 있다.

 

$$\begin{array}{rl}A& =LD{U}^{\prime }\\ \left[\begin{array}{ccc}2& 1& 1\\ 4& 3& 7\\ -2& 1& 3\end{array}\right]& =\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ -1& 2& 1\end{array}\right]\left[\begin{array}{ccc}2& 0& 0\\ 0& 1& 0\\ 0& 0& -6\end{array}\right]\left[\begin{array}{ccc}1& \frac{1}{2}& \frac{1}{2}\\ 0& 1& 5\\ 0& 0& 1\end{array}\right]\end{array}$$

 

이렇게 하면 diagonal entry만 가지고 있는 $D$가 가운데로 분리되어 나간다. 그리고 main diagonal은 $L$과 균형을 이루어 모두 1인 $U^{\prime }$로 symmetric하게 분해되어 대단히 흡족한 모양새가 된다.

 

 

 

---

 

References

• Gilbert Strang. 18.06 Linear Algebra. Spring 2010. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.
• Strang, G. (2012). Linear algebra and its applications. Thomson Brooks/Cole.

 

Footnotes

1. upper-triangular matrix form는 back substitution으로 바로 해를 구할 수 있기 때문에 중요한 형태이다. [본문으로]