LU분해 – 역행렬

1. LU분해

LU 분해는 임의의 행렬 A를 하삼각행렬 L과 상삼각행렬 U 의 곱인 A = LU로 표현하는 것을 LU분해(LU matrix decompose) 또는 LU 행렬분해라고 하고 아래와 같은 행태로 표현한다.

(a) $A = \begin{bmatrix} 1 & 0 & 0 & 0 \\ * & 1 & 0 & 0 \\ * & * & 1 & 0 \\ * & * & * & 1 \end{bmatrix} \begin{bmatrix} a & * & * & * \\ 0 & b & * & * \\ 0 & 0 & c & * \\ 0 & 0 & 0 & d \end{bmatrix}$

(b) $A = \begin{bmatrix} w & 0 & 0 & 0 \\ * & x & 0 & 0 \\ * & * & y & 0 \\ * & * & * & z \end{bmatrix} \begin{bmatrix} 1 & * & * & * \\ 0 & 1 & * & * \\ 0 & 0 & 1 & * \\ 0 & 0 & 0 & 1 \end{bmatrix}$

(c) $A = \begin{bmatrix} i & 0 & 0 & 0 \\ * & j & 0 & 0 \\ * & * & k & 0 \\ * & * & * & l \end{bmatrix} \begin{bmatrix} p & * & * & * \\ 0 & q & * & * \\ 0 & 0 & r & * \\ 0 & 0 & 0 & s \end{bmatrix}$

LU분해 성립할 조건

행렬 A 에 대하여, 한 행에 0 이 아닌 상수를 곱하는 행 연산과, 위쪽 행의 상수배를 어떤 행에 더하는 행 연산을 적용하여 상삼각행렬로 만들 수 있으며느, 해당 행렬은 LU분해할 수 있다.

<증명>

행렬 A에 기본행렬 E를 곱하여 각각의 행 연산을 수행할 수 있다. 행렬 A를 상삼각행렬 U로 변환하는 행 연산은 기본행렬을 곱하는 것으로 나타낼 수 있다.

$E_{n}E_{n-1}\cdot\cdot E_{2}E_{1}A = U$

기본 행렬 $E_{i}$는 역행렬을 갖기 때문에, A 를 아래와 같이 나타낼 수 있다.

$A = E_{1}^{-1}E_{2}^{-1}\cdot\cdot E_{n-1}^{-1}E_{n}^{-1}U$

한 행에 0이 아닌 상수를 곱하는 행 연산에 대응하는 기본행렬 $E_{p}$ 는 대각행렬이고, 이 행렬의 역행렬 $E_{p}^{-1}$도 대각행렬이다. 대각행렬은 하삼각행렬이라 할 수 있다. 한편, 위쪽행의 상수배를 어떤 행에 더하는 행 연산에 대응하는 기본행렬 $E_{q}$는 하 삼각행렬이고, $E_{q}^{-1}$도 하삼각행렬이다. 하삼각행렬의 곱은 하삼각행렬이다. 그러므로 $E_{1}^{-1}E_{2}^{-1}\cdot\cdot E_{n-1}^{-1}E_{n}^{-1}$ 는 하삼각행렬이다. 이 역행렬들의 곱을 L이라고 할 수 있다.

$E_{1}^{-1}E_{2}^{-1}\cdot\cdot E_{n-1}^{-1}E_{n}^{-1} = L$

따라서 A를 하삼각행렬 L과 상삼각행렬 U의 곱으로 나타내는 LU분해를 할 수 있다.

$A = E_{1}^{-1}E_{2}^{-1}\cdot\cdot E_{n-1}^{-1}E_{n}^{-1}U = LU$

LU분해 하삼각행렬과 상삼각행렬

$A = \begin{bmatrix} a_{11} & a_{12} & \cdot\cdot\cdot & a_{1n} \\ a_{21} & a_{22} & \cdot\cdot\cdot & a_{2n} \\ \cdot & \cdot & \cdot & \cdot \\ a_{n1} & a_{n2} & \cdot\cdot\cdot & a_{nn} \end{bmatrix} L = \begin{bmatrix} 1 & 0 & \cdot\cdot\cdot & 0 \\ l_{21} & 1 & \cdot\cdot\cdot & 0 \\ \cdot & \cdot & \cdot & \cdot \\ l_{n1} & l_{n2} & \cdot\cdot\cdot & 1 \end{bmatrix} U = \begin{bmatrix} u_{11} & u_{12} & \cdot\cdot\cdot & u_{1n} \\ 0 & u_{22} & \cdot\cdot\cdot & u_{2n} \\ \cdot & \cdot & \cdot & \cdot \\ 0 & 0 & \cdot\cdot\cdot & u_{nn} \end{bmatrix}$

L의 성분 $l_{ij}$와 U의 성분 $u_{ij}$ 는 다음과 같은 값을 갖는다.

i > j 일때, $l_{ij} = \left( a_{ij} – \sum_{k=1}^{j-1}l_{ik}u_{kj} \right) / u_{jj}$
i $\le$ j 일때, $u_{ij} =  a_{ij} – \sum_{k=1}^{i-1}l_{ik}u_{kj}$

문제) 행렬 $A = \begin{bmatrix} 1 & 2 & 3 \\ 1 & 3 & 5 \\ 1 & 5 & 12 \end{bmatrix} $  LU분해하라

$u_{11} = a_{11} = 1$

$u_{12} = a_{12} = 2$

$u_{13} = a_{13} =3$

$u_{22} = a_{22} – l_{21}u_{12}= 3 – 1 \cdot 2 = 1$

$u_{23} = a_{23} – l_{21}u_{13} = 5 – 1 \cdot 3 = 2$

$u_{33} = a_{33} – l_{31}u_{13} – l_{32}u_{23} = 12 – 1 \cdot 3 – 3 \cdot 2 = 3$

$l_{21} = \dfrac{a_{21}}{u_{11}}  = 1$

$l_{31} = \dfrac{a_{31}}{u_{11}} = 1$

$l_{32} = \dfrac{a_{32} – l_{31}u_{12}}{u_{22}} = \dfrac{5 -1 \cdot 2}{1} = 3$

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

따라서 A 를 LU분해를 하면

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

2. LU분해의 활용

LU 분해는 연립선형방정식의 해를 구하거나 역행렬을 구하는 등의 용도로 사용된다.

행렬 A와 벡터 x의 곱인 Ax를, A의 LU 분해인 A = LU를 사용하여 수행하는 과정을 보면

Ax = (LU)x

Ux를 먼저 계산한 다음(y=Ux), Ly를 수행하여 Ax를 다음과 같이 계산할 수 있다.

Ax = (LU)x = L(Ux) = Ly

LU분해를 이용한 연립선형방정식의 풀이법

$\begin{matrix}3x_{1} – 7x_{2} – 2x_{3} + 2x_{4} &=& -9 \\ -3x_{1} + 5x_{2} + x_{3} \qquad \quad &=& 5 \\ 6x_{1} – 4x_{2} \qquad \quad – 5x_{4} &=& 7 \\ -9x_{1} + 5x_{2} – 5x_{3} + 12x_{4} &=& 11 \end{matrix}$

위 연립방정식은 다음과 같이 행렬방정식 Ax = b 로 나타낼 수 있다.

$A = \begin{bmatrix}3 & -7 & -2 & 2 \\ -3 & 5 & 1 & 0 \\ 6 & -4 & 0 & -5 \\ -9 & 5 & -5 & 12 \end{bmatrix}$,  $x = \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{bmatrix}$,  $b = \begin{bmatrix} -9 \\ 5 \\ 7 \\ 11 \end{bmatrix}$

행렬 A를 LU분해

$A = \begin{bmatrix}3 & -7 & -2 & 2 \\ -3 & 5 & 1 & 0 \\ 6 & -4 & 0 & -5 \\ -9 & 5 & -5 & 12 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 2 & -5 & 1 & 0 \\ -3 & 8 & 3 & 1 \end{bmatrix} \begin{bmatrix} 3 & -7 & -2 & 2 \\ 0 & -2 & -1 & 2 \\ 0 & 0 & -1 & 1 \\ 0 & 0 & 0 & -1 \end{bmatrix}$

Ax = LUx = b 에서 Ux = y라 하자. Ly=b의 해인 y를 첨가행렬을 사용하여 구하면 아래와 같다.

$\begin{bmatrix}L|b\end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 & | & -9 \\ 1 & 1 & 0 & 0 & | & 5 \\ 2 & -5 & 1 & 0 & | & 7 \\ -3 & 8 & 3 & 1 & | & 11\end{bmatrix} ~ \begin{bmatrix} 1 & 0 & 0 & 0 & | & -9 \\ 0 & 1 & 0 & 0 & | & -4 \\ 0 & 0 & 1 & 0 & | & 5 \\ 0 & 0 & 0 & 1 & | & 1\end{bmatrix} = \begin{bmatrix}I|y\end{bmatrix} $

$y = \begin{bmatrix}-9 \\ -4 \\ 5 \\ 1\end{bmatrix}$

$\begin{bmatrix}U|y\end{bmatrix} = \begin{bmatrix} 3 & -7 & -2 & 2 & | & -9\\0 & -2 & -1 & 2 & | & -4 \\ 0 & 0 & -1 & 1 & | & 5 \\ 0 & 0 & 0 & -1 & | & 1\end{bmatrix} ~ \begin{bmatrix} 1 & 0 & 0 & 0 & | & 3 \\ 0 & 1 & 0 & 0 & | & 4\\0 & 0 & 1 & 0 & | & -6 \\ 0 & 0 & 0 & 1 & | & -1\end{bmatrix} = \begin{bmatrix}I|x\end{bmatrix}$

따라서 주어진 연립선형방정식의 해는 $x = \begin{bmatrix}3 \\ 4 \\ -6 \\ -1 \end{bmatrix}$

LU 분해를 이용한 역행렬 계산

행렬 A의 역행렬을 B라고 하면 AB=I 이다. A의 LU분해를 A = LU라 하고, 행렬 B를 열벡터 $b_{1}, b_{2}, \cdot \cdot \b_{n}$을 사용하여 B = $[b_{1} b_{2} \cdot \cdot b_{n}]$으로 나타내면

AB = A$[b_{1} b_{2} \cdot \cdot b_{n}]$ = I

A와 B의 i열 을 곱하면 다음과 같다

$Ab_{1} = A\begin{bmatrix}b_{11} \\ b_{21} \\ \cdot \\ b_{n1} \end{bmatrix} = \begin{bmatrix}1 \\ 0 \\ \cdot \\ 0 \end{bmatrix}$ ,  $Ab_{2} = A\begin{bmatrix}b_{12} \\ b_{22} \\ \cdot \\ b_{n2} \end{bmatrix} = \begin{bmatrix}0 \\ 1 \\ \cdot \\ 0 \end{bmatrix}$ ,  $Ab_{n} = A\begin{bmatrix}b_{1n} \\ b_{2n} \\ \cdot \\ b_{nn} \end{bmatrix} = \begin{bmatrix}0 \\ 0 \\ \cdot \\ 1 \end{bmatrix}$

$A = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 4 \\ 4 & 2 & 1 \end{bmatrix}$ 의 역행렬을 구하면

A의 역행렬이 $C = \begin{bmatrix} c_{1} & c_{2} & c_{3} \end{bmatrix}$

$Ac_{1} = A\begin{bmatrix} c_{11} \\ c_{21} \\ c_{31} \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}$, $Ac_{2} = A\begin{bmatrix} c_{12} \\ c_{22} \\ c_{32} \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}$, $Ac_{3} = A\begin{bmatrix} c_{13} \\ c_{23} \\ c_{33} \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}$,

A를 LU분해하면

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

LU분해를 이용하여 위 3개의 행렬방정식의 해를 구하면 다음과 같다.

$\begin{bmatrix}L | i_{1} \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & | & 1 \\ 2 & 1 & 0 & | & 0 \\ 4 & 6 & 1 & | & 0 \end{bmatrix}$  ~ $\begin{bmatrix} 1 & 0 & 0 & | & 1 \\ 0 & 1 & 0 & | & -2 \\ 0 & 0 & 1 & | & 8 \end{bmatrix} = \begin{bmatrix}I_{3} | y_{1} \end{bmatrix}$

-> $\begin{bmatrix}U | y_{1} \end{bmatrix} = \begin{bmatrix} 1 & 2 & 3 & | & 1 \\ 0 & -1 & -2 & | & -2 \\ 0 & 0 & 1 & | & 8 \end{bmatrix}$ ~ $\begin{bmatrix} 1 & 0 & 0 & | & 5 \\ 0 & 1 & 0 & | & -14 \\ 0 & 0 & 1 & | & 8 \end{bmatrix} = \begin{bmatrix}I_{3} | c_{1} \end{bmatrix}$

-> $c_{1} = \begin{bmatrix}5 \\ -14 \\ 8 \end{bmatrix}$ 이 된다 $c_{2}, c_{3}$의 값도 위와 같이 구하면

$c_{2} = \begin{bmatrix}-4 \\ 11 \\ 6 \end{bmatrix}$

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

따라서 A의 역행렬 $A^{-1}$ 는

$A^{-1} = C = \begin{bmatrix} c_{1} \\ c_{2} \\ c_{3} \end{bmatrix} = \begin{bmatrix} 5 & -4 & 1 \\ -14 & 11 & -2 \\ 8 & -6 & 1  \end{bmatrix}$

답글 남기기

이메일 주소는 공개되지 않습니다.