LU 분해(LU factorization)

행렬분해(matrix factorization)

하나의 행렬을 여러개의 행렬의 곱으로 표현하는것

ex)

$$\begin{bmatrix}
 3&-1\\9&-5
\end{bmatrix}=
\begin{bmatrix}
1 & 0 \\ 3& 1
\end{bmatrix}
\begin{bmatrix}
3&-1\\0&-2
\end{bmatrix}$$

 

$LU$ 분해($LU$ factorization)

$A$가 정사각행렬이라고 하자. $L$은 단위하삼각행렬이고 $U$는 상삼각행렬인 분해 $A=LU$를 $A$의  $\bf LU$분해(LU factorization)라고 한다.

$L$은 대각성분이 1이고 위의 모든 성분이 0인 아래와 같은 형태의 행렬이다.
$$L=\begin{bmatrix} 1&0&\cdots&0\\ *&1&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ *&*&\cdots&1 \end{bmatrix}
$$

주의

$\bullet$ $A$가 $LU$분해를 가지기 위해선 행줄임의 수행에서 어떠한 행교환도 있어서는 안된다.

행교환이 없으므로 행줄임에 적용되는 모든 기본행렬은 단위하삼각행렬이다. 단위 하삼각행렬들의 역행렬과 곱은 다시 단위하삼각행렬이므로 $L$은 단위하삼각행렬이 된다.

$\bullet$ 행렬 $U$를 단지 행사다리꼴만 요구한다면 정사각행렬이 아닌 행렬에도 $LU$분해를 적용 할 수 있다.

$\bullet$ 개념서에 따라서는 $LU$분해에서 $L$이 하삼각행렬이고 $U$는 상삼각행렬인 임의의 분해 $A=LU$로 정의하기도 한다.

 

가우스소거법으로 행렬을 분해하여 연립방정식을 효율적으로 풀 수 있다.

가령 $Ax=b$ 꼴의 연립방정식이 있다. $A$는 $n \times n$ 행렬이다. 이 $A$를 행렬분해 하여 해를 손쉽게 얻을 수 있다.

 

$A$가 어떤 행교환도 하지 않고 행사다리꼴로 변형될 수 있는 정사각행렬이면, $A$는 $LU$분해를 갖는다.

 

 

$LU$분해의 어디가 유용한것인지 알아보자.

연립일차방정식 $Ax=b$를 생각해보자. 여기서, 계수행렬은 $LU$분해 $A=LU$를 갖는다. $Ax=b$는 $LUx=b$ 또는 $L(Ux)=b$로 나타낼 수 있다. 만일 $y=Ux$로 두면, 다음의 두 단계로 $x$를 구할 수 있다.

1. 전진대입법으로 $Ly=b$를 $y$에 대하여 푼다.

2. 후진대입법으로 $Ux=y$를 $x$에 대하여 푼다.

$L$과 $U$는 삼각행렬이므로 방정식을 쉽게 풀 수 있다.

 

앞선 과정에서 행렬 $L$을 기본행렬의 곱으로 구하였다. 하지만 이렇게 할 필요 없이 행줄임 과정 만으로 연립일차방정식의 직접 계산이 가능하다. $A$는 행교환을 하지 않고 행사다리꼴로 유도될 수 있다고 가정한다. 그렇다면 $R_i-kR_j$ 형태의 기본 행변환만을 사용하면 된다. 대각성분을 1로 강제할 필요가 없기 때문에 $kR_i$의 기본 행변환은 안해도 된다. 변환 $R_i-kR_j$에서 스칼라 $k$를 승수(multiplier)라고 한다.

예를통해 확인하자

행렬$\begin{bmatrix}2&1&3\\4&-1&3\\-2&5&5\end{bmatrix}$ 을 단위 하삼각행렬 $L$로 바꾸기 위한 기본 행변환은 아래와 같다.

$$\begin{align*}
&R_2-2R_1 & &(multiplier=2)&\\
&R_3+R_1=R_3-(-1)R_1 & &(multiplier = -1)&\\
&R_3+2R_2=R_3-(-2)R_2& &(multiplier=-2)&
\end{align*}$$

이때 승수는 $L$의 대각성분 아래의 성분이다.

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

실제로 $L_{21}=2, L_{31}=-1, L_{32}=-2$ 이다.

즉, 기본 행변환 $R_i-kR_j$는 $L$의 $(i,j)$성분에 위치한 승수 $k$를 갖는다.

 

주의

$\bullet$ 이 방법은기본 행변환 $R_i-kR_j$시에 위로부터 아래로 그리고 왼쪽 열에서 오른쪽열로 행해져야한다. 이 규칙을 따르지 않으면 결과가 틀리게 나온다.

 

$\bullet$ $L$을 만드는 다른 방법은 pivot을 이용하는것이다.

$$A=
\begin{bmatrix}2&1&3\\4&-1&3\\-2&5&5\end{bmatrix}
\overset{\displaystyle R_2-2R_1}{-----\triangleright}
\begin{bmatrix}2&1&3\\0&-3&-3\\0&6&8\end{bmatrix}
\overset{\displaystyle R_3+R_2}{-----\triangleright}
\begin{bmatrix}2&1&3\\0&-3&-3\\0&0&2\end{bmatrix}$$

첫 번째 pivot 성분은 2이므로 이것을 pivot이 속한 열의 모든 성분에다가 나누어 주면

$$\frac{1}{2}\begin{bmatrix}2\\4\\-2\end{bmatrix}=\begin{bmatrix}1\\2\\-1\end{bmatrix}$$

다음 pivot 성분은 -3으로 마찬가지로 속한 열에 있는 모든 성분에 나누어 준다.

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

마지막 pivot 성분은 2이므로 속한 열에 있는 모든 성분을 나누어 준다.

$$\frac{1}{2}\begin{bmatrix}\\\\2\end{bmatrix}=\begin{bmatrix}\\\\1\end{bmatrix}$$

이렇게 구한 3개의 열벡터를 행렬로 나타내면

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

$\blacksquare$

 

행렬의 행사다리꼴은 유일하지 않다. 그러나 가역행렬 $A$가 $LU$분해 $A=LU$를 갖는다면 이 분해는 유일하다. 

$A$가 $LU$분해를 갖는 가역행렬이면, $L$과 $U$는 유일하다.

증명

$A$의 분해인 $L$과 $U$가 유일하지 않다고 가정한다. 즉, $A=LU$와 $A=L_1U_1$가 두 $LU$분해라고 가정하자. 여기서, $L$와 $L_1$은 단위 하삼각행렬이고 $U$와 $U_1$은 상삼각행렬이다. 사실 $U$와 $U_1$는 $A$의 두 개의 행사다리꼴이다.

 

$L$은 기본행렬들의 곱이므로 가역이다.

 

$U$가 가역인지 증명하는 방법은 2가지 있다.

1. $A=LU$ 는 $U=L^{-1}A$가 될 수 있다. $L$과 $A$가 둘다 가역이므로 $(L^{-1}A)^{-1}=A^{-1}L$ 로써  $L^{-1}A$도 가역이다. 그러므로  $U^{-1}$이 존재하므로 $U$ 또한 가역이다.

2. $A$가 가역행렬이므로 가역행렬의 기본정리에 의해 기약 행 사다리꼴은 단위행렬 $I$이다. 그러므로 $U$는 $L$이외에 추가적인 기본행렬을 곱함으로써 $I$의 기약행사다리꼴로 변형될 수 있다. 따라서 $U$는 가역행렬이다.

 

$L$과 $U$가 둘다 가역이므로

${L_1}^{-1}(LU)U^{-1}={L_1}^{-1}(L_1U_1)U^{-1}$에서 $({L_1}^{-1}L)(UU^{-1})=({L_1}^{-1}L_1)(U_1U^{-1})$ 이므로

$$({L_1}^{-1}L)I=I(U_1U^{-1}),\;\;\;\;\; \therefore {L_1}^{-1}L=U_1U^{-1}$$

가 성립한다.

 

$L$과 ${L_1}^{-1}$은 둘다 기본행렬의 곱이므로 단위하삼각행렬이다. 그러므로 $L{L_1}^{-1}$ 또한 단위하삼각행렬이다.

그리고 $U$는 상삼각행렬이며 $U^{-1}=A^{-1}L$로써 $U^{-1}$은 임의의 행렬 $A^{-1}$에 단위하삼각행렬 $L$을 곱한것이므로 $U^{-1}$ 상삼각행렬이다.(수정 필요)

결국 ${L_{1}}^{-1}L$ 는 단위하삼각행렬이며, $U_1U^{-1}$은 상삼각행렬이므로  ${L_{1}}^{-1}L=U_1U^{-1}$를 만족하는 행렬은 단위행렬 밖에 없다. 따라서 ${L_1}^{-1}L=I=U_1U^{-1}=I$ 이므로 이 식을 이항하면 $L=L_1$ 이고 $U=U_1$이다. 따라서 $A$는 $LU$분해는 유일하다.

 

 

$P^TLU$ 분해($P^TLU$ factorization)

가우스 소거법을 적용할때, 행교환이 가능한 경우에 사용되는 행렬분해이다.

가령 $A=\begin{bmatrix}1&2&-1\\3&6 &2\\-1&1&4\end{bmatrix}$ 에 행줄임 과정을 적용하면

$$A \rightarrow  B = \begin{bmatrix} 1&2&-1 \\ 0&0&5 \\ 0&3&3 \end{bmatrix}$$

인데 이는 상삼각행렬이 아니다. 그러나 2행과 3행을 교환하면

$$U = \begin{bmatrix} 1&2&-1 \\ 0&3&3 \\ 0&0&5 \end{bmatrix}$$

의 상삼각행렬을 얻는다.

 

$U$를 얻기 위해서 행한 행교환을 기본행렬 $P$로 표현한다.

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

 

$PA$를 $U$로 바꾸는 기본행렬의 곱이 $E$이면

$EPA=U$

이므로

$PA=E^{-1}U=LU$

즉, $E^{-1}=L$은 단위하삼각행렬이다.

여기서 $A=(EP)^{-1}U=P^{-1}E^{-1}U=P^{-1}LU$ 이다.

 

일반적으로 행교환 기본행렬 $P$는 순서에 따른 모든 행교환행렬

$P_1,P_2,\cdots,P_k$의 곱 $P=P_k \cdots P_2P_1$이 될것이다.

이러한 행렬 $P$를 치환행렬(Permutation matrix)라고한다.

즉, 치환행렬이란 $P^TLU$분해에 필요한 행교환 기본행렬의 곱이다.

 

치환행렬의 예

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

 

$P$가 치환행렬이면, $P^{-1}=P^T$이다.

증명

$P^TP=I$ 임을 보인다.

$P^T$의 $i$번째 행은 $P$의 $i$번째 열과 같고 $P$는 치환행렬 이므로 이들은 동일한 기본 단위벡터 $e$와 같다.

즉, 하나의 성분만 $1$이고 나머지는 모든 $0$인 벡터이다.

그러므로

$$(P^TP)_{ii}=(P^T의\;i번째\;행)(P의\;i번째\;행)=e^Te=e\cdot e=1$$

즉, $P^TP$의 대각성분은 모두 $1$이다.

 

한편 $j \neq i$이면 $P$의 $j$번째 열은 $P^T$의 $i$번째 열과 다른 $e'$벡터이다.

$e\cdot e' = 0$ 이므로

$(P^TP)_{ij}=(P^T의\;i번째\;행)(P의\;j번째\;행)=e^Te'=e\cdot e'=0$

즉, 대각성분 이외의 모든 성분은 $0$이다.

$\therefore$ $P^TP$는 단위행렬이다. 그러므로 $P^{-1}=P^T$ 이다.

 

$$\begin{align*} A&=P^TLU\\ P&=P_k\cdots P_2P_1&&(P_i:i번째로\;적용한\;행교환의\;기본행렬)&\\ L&={E_1}^{-1}{E_2}^{-1}\cdots{E_k}^{-1},\;단위\;하\;삼각\;행렬&&(E_i:i번째로\;적용한\;행연산의\;기본행렬)&\\ U&=A의\;행사다리꼴,상\;삼각\;행렬 \end{align*}$$

 

$A$가 정사각행렬이라 하자, $P$가 치환행렬, $L$은 단위하삼각행렬, $U$는 상삼각행렬일 때, $A=P^TLU$로서의 $A$분해를 $A$의 $P^TLU$분해($P^TLU$ factorization) 이라 한다.

 

 

모든 정사각행렬은 $P^TLU$분해를 갖는다.

주의

가역행렬 일지라도 $P^TLU$분해는 유일하지 않다.

가령 [예제 3.16]을 보면 풀이와는 달리

$$A\begin{bmatrix}0&0&6 \\ 1&2&3\\ 2&1&4 \end{bmatrix} \overset{R_1 \Leftrightarrow R_3}{---\blacktriangleright} \begin{bmatrix}2&1&4 \\ 1&2&3\\ 0&0&6 \end{bmatrix}
\overset{R_2 - \frac{1}{2}R_1}{---\blacktriangleright} \begin{bmatrix}2&1&4 \\ 1&\frac{3}{2}&1\\ 0&0&6 \end{bmatrix}$$

으로 $R_1 \Leftrightarrow R_3$ 한번의 행교환 만으로 행사다리꼴을 만들수 있다.

하지만 $P$가 결정되면 $L$과 $U$는 유일하다.

 

계산적인 고려