[선형대수학] LU Decomposition (LU Factorization)

❗본 포스팅은 한양대학교 이상화 교수님의 '선형대수' 강의를 기반으로 개인적인 정리 목적 하에 재구성하여 작성된 글입니다.

 

$$ 2u + v + w = 5 \\ 4u - 6v \space\space \space\space\space= -2 \\ -2u + 7v + 2w = 9 $$

이전 포스팅에서 위의 연립방정식에서 가우스 소거법으로 Upper Triangular Matrix까지 구해봤었다.

이어서 Ax = b 를 풀기 위해서 A를 LU Decomposition을 하고, 그 의미까지 알아보려고 한다.

 

LU Decomposition

가우스 소거법의 과정을 모두 행렬식으로 표현하면 위와 같이 정리할 수 있다.

 

1. 첫번째 행을 중심으로 두번째 행의 첫번째 요소 0으로 만들기 → 2를 곱하고 빼면 된다.
   
   - 그 과정을 행렬의 곱으로 표현하면 첫번째 행렬 식으로 표현된다. 우리는 여기서 앞에 붙은 행렬을 E21이라고 표현해보자 (1번째 행을 이용해서 2번째 행을 바꿔주겠다는 의미)
   
   
2. 첫번째 행을 중심으로 세번째 행의 첫번째 요소를 0으로 만들기 → 1을 곱하고 더해주면 된다.
   
   - 역시 같은 방법으로 행렬의 곱으로 표현하면 두번째 행렬 식으로 표현되고 이때 행렬은 E31이라고 칭하겠다.

그러면 첫번째 열의 첫번째 행만 남기고 모두 0으로 만들었다.

 

다음으로 두번째 행에 해당하는 pivot variable 아래 요소도 모두 0으로 만드는 과정을 똑같이 진행하면 아래와 같은 식이 나오게 된다.

1. 두번째 열을 중심으로 세번째 행의 두번째 요소를 0으로 만들기 → 1을 곱해서 더하면 된다.
   
   - 앞에 붙는 행을 E32으로 표현하도록 한다.

그렇게 우리는 가우스 소거법을 통해 upper triangular matrix를 얻었다.

 

 

여기서 행렬 E(n, m)에 대한 일반적인 표현을 정의해보자

 

 

행렬 E는 해당 계수가 0이 되도록 곱하고 빼는 값을 $l_{nm}$이라고 할 때 0이 되게 만드려고 하는 위치에 그 값을 넣어주면 된다. 위와 같이 표현할 수 있고 식을 보면 더 이해하기 쉬울 것 같다.

 

여기서 행렬 E의 역행렬을 구해서 원본 A행렬을 다시 복구시킬 수도 있다.

이때 역행렬 만드는건 되게 쉽다. 대각선 방향의 값이 모두 1이기 때문에 $l_{nm}$의 부호만 바꿔서 넘겨주면 된다.

 

행렬 E의 역행렬을 구하는 방법을 왜 알아야 되냐하면!

결국 행렬 A를 정의하려고 사용된다. 아래의 과정을 살펴보자.

 

 

결과적으로 가우스 소거법의 과정을 행렬 E의 곱을 통해($E_{32}E_{31}E_{21}A = U$) Upper Triangular Matrix(U)를 만들었다.

그리고 그 E행렬들의 역행렬을 이용해 A를 정의할 수 있는데, 이때 역행렬 E들의 곱을 하면 Lower Trigangular Matrix(L)가 나온다.

결과적으로 행렬 A는 Lower Triangular Matrix(L)와 Upper Triangular Matrix(U)의 곱으로 표현되고, 우리는 이것을 LU decomposition 혹은 LU Factorization이라고 한다.

 

LU Decomposition이 의미하는 것은?

$$ Ax = b $$

우리는 계속해서 Ax=b를 풀고있다. 우리는 A라는 행렬을 단순히 행렬로만 보지 않고 시스템으로 보면 u,v,w를 가진 x벡터를 input으로 넣으면 b1,b2,b3를 갖는 벡터 b가 output으로 나온다고 보는 것이다.

 

 

예를 들면 4u + 2v + w = 5에서 A를 하나의 선형 모델로 생각하고 계수 u, v, w에 대한 특정 파라미터를 갖는 시스템인 것이다. 그래서 우리가 그 A(system)이 갖는 파라미터를 모두 알면, 어떤 값을 input으로 주어도 output을 얻을 수 있다.

 

그렇다면 여기서 시스템 A에 대해서 알고자 하는데 블랙박스인 A를 모른다고 할지라도 LU Decomposition이 되는 걸 알면 Lower Triangular matrix와 Upper Triangular matrix를 통해 A를 완전하게 구할 수 있다는 것에 의미가 있다.

또 LU 형태로 분할하게 되면 좋은 이유는 직접 역행렬을 계산해서 행렬을 구하는 것보다 더 연산을 쉽게 할 수 있다는 장점이 있다.

 

예시를 통해 A를 알지 못하더라도 미지수로 이루어진 x 벡터를 구하는 방법에 대해서 알아보자.

$$ L^{-1}Ax =L^{-1}b $$

양변에 L의 역행렬을 양쪽에 곱해주면 위와 같이 표현될 수 있고, $L^{-1}A = U$로 변환될 수 있는 것은 쉽게 알 수 있다. 그리고 $L^{-1}b$는 새로운 벡터 c라고 정의할 때 아래와 같이 표현 될 수 있다.

$$ Ux = c $$

새로운 벡터 c에 대해서 $Lb=c$로 다시 표현 할 수 있게 되고, 이 식을 풀어서 c를 구한다.

$Ux=c$에서 U와 c를 알고있으니 x를 구해서 해를 구할 수 있다.

 

LU Decomposition의 성질

LU decomposition을 할 수 있으면 그 조합은 유니크하다. 경우가 하나밖에 없다는 의미고, 행렬 A를 하나의 시스템으로 본다고 했고 그 LU의 조합은 하나의 경우이기 때문에 역행렬도 가능함을 의미한다.

 

Lower Triangular Matrix의 특징

$$  \begin{bmatrix}1 & 0 & 0 \\l_{21} & 1 & 0 \\l_{31} & l_{32} & 1 \\\end{bmatrix} $$

Lower Triangular Matrix는 위의 형태로 생겼다. 이것은 행렬 A(system)에 대해서 가우스 소거법의 과정이 담겨있다. ($lmn$가 뭔지 생각해보자)

 

추가로 만약 행렬 A가 Lower Triangular Matrix와 비슷한 형태로 대각 요소는 모두 1이고, non-zero값이 왼쪽 아래에만 있다면, $A = LU$에서 L은 행렬 A와 같은 값일테니 U는 Identity matrix($I)$가 된다는 것을 알아두자.

 

Upper Triangular Matrix의 분해

 

우리는 A=LU에서 Upper Triangular Matrix(U)를 대각행렬(Diagonal Matrix) D와 여전히 Upper Triangular Matrix인 새로운 U로 분해해 볼 수 있다.

$$ U = \begin{bmatrix} d_1 & u_{12} & u_{13} & ... & u_{1n} \\ 0 & d_2 & u_{23} & ... & u_{2n} \\ 0 & 0 & d_3 & ... & ...\\ 0 & 0 & 0 & ... & d_n \\ \end{bmatrix}= \begin{bmatrix} d_1 & 0 & 0 & ... & 0 \\ 0 & d_2 & 0 & ... & 0 \\ 0 & 0 & d_3 & ... & ...\\ 0 & 0 & 0 & ... & d_n \\ \end{bmatrix} \begin{bmatrix} 1 & \frac{u_{12}}{b_1} & \frac{u_{13}}{b_1} & ... & \frac{u_{1n}}{b_1} \\ 0 & 1 & \frac{u_{23}}{b_2} & ... & ... \\ 0 & 0 & 1 & ... & ...\\ 0 & 0 & 0 & ... & 1 \\ \end{bmatrix} $$

그러면 $A = LU = LDU$으로 바꿔볼 수 있다.

 

이렇게 분해한 Diagonal Matrix(D)는 pivot 값만 모아서 표현했다는 것에 의미가 있고 나중에 더 복잡한 문제를 풀때 대각선에만 값이 있기 때문에 계산에 용이하게 사용할 수 있다.

 

Permutation Matrix (P)

 

permutation Matrix는 가우스소거법 과정에서 pivoting이 필요한 상황에서 행렬로 표현한 것이다.

$$ {\begin{bmatrix}0 & 1 & 0 \\1 & 0 & 0 \\0 & 0 & 1 \\\end{bmatrix}} \begin{bmatrix} 2 & 1 & 1 \\ 4 & -6 & 0 \\ -2 & 7 & 2 \\ \end{bmatrix} = \begin{bmatrix} 4 & -6 & 0 \\ 2 & 1 & 1 \\ -2 & 7 & 2 \\ \end{bmatrix} $$

위의 행렬 A에서 가우스 소거법을 하기 위해 첫번째와 두번째 행렬을 바꿔주면 (pivoting) 계산할 수 있다. 그래서 Permutation Matrix(P)는 Identity matrix와 비슷하게 각 row에 1이 한번만 나오는 형태이다.

바꾸고자 하는 행에 1이 들어가면 되는데 아래의 예제를 통해 연습해보자.

$$ P_{32}P_{21} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ \end{bmatrix}\begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} = {\begin{bmatrix} 0 & 1& 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ \end{bmatrix}} $$

먼저, 첫번째 Matrix는 3번째 행과 2번째 행을 바꾸는 pivoting 상황이고,

두번째 Matrix는 2번째 행과 1번째 행을 바꾸는 pivoting이다. 그래서 최종적으로 맨 오른쪽 행렬이 나오게 된다.

 

쉽게 생각해서 P를 각 행의 입장이 되어보자.

1번 행 : 처음 이동 없음 → 2번째 행으로 이동

2번 행 : 3번 행으로 이동 → 이동 없음

3번 행 : 2번 행으로 이동 → 1번 행으로 이동

그러면 최종적으로

1 → 2

2 → 3

3 → 1

이렇게 이동을 하게 된다. 한번에 행렬로 표현하면, 바로 표현할 수 있겠죠?

 

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

 

만약 행렬 A에 pivoting이 필요하면 $PA = LU$로 표현하면 된다.

그리고 행렬 P는 P의 역행렬과 P의 transpose가 같다는 성질이 있기 때문에 최종적으로 $A = P^{\top}LU$로 표현이 가능하다.