[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 = \begin{bmatrix} 2 & 1 &1 \\ 4 & 3 & 7 \\ -2 &1 & 3 \end {bmatrix} $$

 

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

 

$$\begin{align}  Ax &= b\\ \begin{bmatrix} 2 & 1 &1 \\ 4 & 3 & 7 \\ -2 &1 & 3 \end {bmatrix} \begin{bmatrix}u \\v\\w \end{bmatrix} &= \begin{bmatrix} 0 \\ 16\\14\end{bmatrix}  \end{align}$$

 

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

 

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

$$E_{21}A = \begin{bmatrix} 1 & 0 &0 \\ -2 & 1 & 0 \\ 0 &0 & 1 \end {bmatrix}\begin{bmatrix} 2 & 1 &1 \\ 4 & 3 & 7 \\ -2 &1 & 3 \end {bmatrix} = \begin{bmatrix} 2 & 1 &1 \\ 0 & 1 & 5 \\ -2 &1 & 3 \end {bmatrix}$$

 

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

$$E_{31}E_{21}A = \begin{bmatrix} 1 & 0 &0 \\ 0 & 1 & 0 \\ 1 &0 & 1 \end {bmatrix}\begin{bmatrix} 1 & 0 &0 \\ -2 & 1 & 0 \\ 0 &0 & 1 \end {bmatrix}\begin{bmatrix} 2 & 1 &1 \\ 4 & 3 & 7 \\ -2 &1 & 3 \end {bmatrix} = \begin{bmatrix} 2 & 1 &1 \\ 0 & 1 & 5 \\ 0 &2 & 4 \end {bmatrix}$$

 

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

 

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

 

$$E_{32}E_{31}E_{21}A = \begin{bmatrix} 1 & 0 &0 \\ 0 & 1 & 0 \\ 0 &-2 & 1 \end {bmatrix}\begin{bmatrix} 1 & 0 &0 \\ 0 & 1 & 0 \\ 1 &0 & 1 \end {bmatrix}\begin{bmatrix} 1 & 0 &0 \\ -2 & 1 & 0 \\ 0 &0 & 1 \end {bmatrix}\begin{bmatrix} 2 & 1 &1 \\ 4 & 3 & 7 \\ -2 &1 & 3 \end {bmatrix} = \begin{bmatrix} 2 & 1 &1 \\ 0 & 1 & 5 \\ 0 &0 & -6 \end {bmatrix}$$

 

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

 

$$E_{32}E_{31}E_{21}A = \begin{bmatrix} 2 & 1 &1 \\ 0 & 1 & 5 \\ 0 &0 & -6 \end {bmatrix} = 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} = \begin{bmatrix} 1 & 0 &0 \\ 2 & 1 & 0 \\ -1 & 2 & 1 \end {bmatrix} = L$$

 

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

 

$$ \begin{align} A&=LU  \\ \begin{bmatrix} 2 & 1 &1 \\ 4 & 3 & 7 \\ -2 &1 & 3 \end {bmatrix} &= \begin{bmatrix} 1 & 0 &0 \\ 2 & 1 & 0 \\ -1 & 2 & 1 \end {bmatrix}\begin{bmatrix} 2 & 1 &1 \\ 0 & 1 & 5 \\ 0 &0 & -6 \end {bmatrix} \end{align}$$

 

---

이 형태가 중요한 이유

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

 

$$ L  = \begin{bmatrix} 1 & 0 &0 \\ 2 & 1 & 0 \\ -1 & 2 & 1 \end {bmatrix}$$

 

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

 

$$ \begin{align}  E = E_{32}E_{31}E_{21} &= \begin{bmatrix} 1 & 0 &0 \\ 0 & 1 & 0 \\ 0 &-2 & 1 \end {bmatrix}\begin{bmatrix} 1 & 0 &0 \\ 0 & 1 & 0 \\ 1 &0 & 1 \end {bmatrix}\begin{bmatrix} 1 & 0 &0 \\ -2 & 1 & 0 \\ 0 &0 & 1 \end {bmatrix} \\ &= \begin{bmatrix} 1 & 0 &0 \\ -2 & 1 & 0 \\ 5 &-2 & 1 \end {bmatrix}\end{align}$$

 

결과값에서 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{align}  Ax &= b\\ \begin{bmatrix} 2 & 1 &1 \\ 4 & 3 & 7 \\ -2 &1 & 3 \end {bmatrix} \begin{bmatrix}u \\v\\w \end{bmatrix} &= \begin{bmatrix} 0 \\ 16\\14\end{bmatrix}  \end{align}$$

 

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

 

$$ \begin{align} Lc&=b  \\  \begin{bmatrix} 1 & 0 &0 \\ 2 & 1 & 0 \\ -1 & 2 & 1 \end {bmatrix} \begin{bmatrix}c_1 \\c_2\\c_3 \end{bmatrix} &=  \begin{bmatrix} 0 \\ 16\\14\end{bmatrix}\end{align}$$ 

 

를 풀면, 

 

$$ c= \begin{bmatrix} 0 \\ 16\\-18\end{bmatrix} $$

 

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

 

$$ \begin{align} Ux&=c  \\  \begin{bmatrix} 2 & 1 &1 \\ 0 & 1 & 5 \\ 0 &0 & -6 \end {bmatrix} \begin{bmatrix}u \\v\\w \end{bmatrix} &=  \begin{bmatrix} 0 \\ 16\\-18\end{bmatrix} \end{align}$$

 

를 풀면, 

 

$$ x= \begin{bmatrix} -2 \\ 1\\ 3\end{bmatrix}$$

 

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

 

---

PA = LU

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

 

$$ A = \begin{bmatrix} 0 & 2 \\ 3 & 4\end{bmatrix}$$

 

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

 

$$ P = \begin{bmatrix} 0 & 1 \\ 1 & 0\end{bmatrix}$$

 

---

A = LDU

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

 

$$ \begin{align} A&=LU  \\ \begin{bmatrix} 2 & 1 &1 \\ 4 & 3 & 7 \\ -2 &1 & 3 \end {bmatrix} &= \begin{bmatrix} 1 & 0 &0 \\ 2 & 1 & 0 \\ -1 & 2 & 1 \end {bmatrix}\begin{bmatrix} 2 & 1 &1 \\ 0 & 1 & 5 \\ 0 &0 & -6 \end {bmatrix} \end{align}$$

 

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

 

$$ \begin{align} A&=LDU'  \\ \begin{bmatrix} 2 & 1 &1 \\ 4 & 3 & 7 \\ -2 &1 & 3 \end {bmatrix} &= \begin{bmatrix} 1 & 0 &0 \\ 2 & 1 & 0 \\ -1 & 2 & 1 \end {bmatrix} \begin{bmatrix} 2 & 0 &0 \\ 0 & 1 &0 \\ 0 &0 & -6 \end {bmatrix}  \begin{bmatrix} 1 & {1 \over 2} &{1 \over 2} \\ 0 & 1 & 5 \\ 0 &0 & 1 \end {bmatrix} \end{align}$$

 

이렇게 하면 diagonal entry만 가지고 있는 $D$가 가운데로 분리되어 나간다. 그리고 main diagonal은 $L$과 균형을 이루어 모두 1인 $U'$로 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으로 바로 해를 구할 수 있기 때문에 중요한 형태이다. [본문으로]