[선형대수학] 33. LU분해 (목적,방법)

행렬에서 '분해(decomposition)'은 어떤 행렬 A를 둘 이상의 행렬의 곱으로 나타내는 것을 의미합니다. LU분해란 행렬 A를 Low triangle matrix 와 Upper triangle matrix 의 곱으로 나타내는 것을 말합니다.

 

$A=LU$

 

LU분해의 예는 아래와 같습니다. 

 

$\begin{bmatrix}
1 & 2 & 3 \\ 
2 & 6 & 8\\ 
3 & 6 & 13
\end{bmatrix}
=
\begin{bmatrix}
1 & 0 & 0\\ 
2 & 1 & 0\\ 
3 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 2 & 3\\ 
0 & 2 & 2\\ 
0 & 0 & 4
\end{bmatrix}$

 

몇가지 의문이 생깁니다.

 

어떻게 하는거지? 

어디에 쓰는거지? 

항상 되는건가? 

 

의문을 하나씩 해결해봅시다. 

---

LU 분해는 어떻게 하는걸까? 

아래 행렬을 LU 분해하는 과정을 설명하겠습니다.

 

$A=\begin{bmatrix}
1 & 2 & 3 \\ 
2 & 6 & 8\\ 
3 & 6 & 13
\end{bmatrix}$

 

아래와 같은 등식에서 시작하겠습니다. 우변은 단위행렬 $I$를 곱해준 것입니다. 

 

$\begin{bmatrix}
1 & 2 & 3 \\ 
2 & 6 & 8\\ 
3 & 6 & 13
\end{bmatrix}
=
\begin{bmatrix}
1 & 0 & 0 \\ 
0 & 1 & 0\\ 
0 & 0 & 1
\end{bmatrix}

\begin{bmatrix}
1 & 2 & 3 \\ 
2 & 6 & 8\\ 
3 & 6 & 13
\end{bmatrix}$

 

양변에 기본행렬을 곱하여 좌변을 행사다리꼴로 만들겠습니다. 행사다리꼴은 가우스 소거법의 결과입니다. 

 

먼저 1행에 3을 곱하여 3행에서 빼줍시다. 아래와 같은 기본행렬을 곱하면 됩니다. 

 

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

\begin{bmatrix}
1 & 2 & 3 \\ 
2 & 6 & 8\\ 
3 & 6 & 13
\end{bmatrix}
=
\begin{bmatrix}
1 & 0 & 0 \\ 
0 & 1 & 0\\ 
-3 & 0 & 1
\end{bmatrix}

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

\begin{bmatrix}
1 & 2 & 3 \\ 
2 & 6 & 8\\ 
3 & 6 & 13
\end{bmatrix}$

 

계산 결과는 아래와 같습니다. 

 

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

\begin{bmatrix}
1 & 2 & 3 \\ 
2 & 6 & 8\\ 
3 & 6 & 13
\end{bmatrix}$

 

이번에는 1행에 2을 곱하여 2행에서 빼줍시다. 아래와 같은 기본행렬을 곱하면 됩니다. 

 

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

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

\begin{bmatrix}
1 & 0 & 0 \\ 
0 & 1 & 0\\ 
-3 & 0 & 1
\end{bmatrix}

\begin{bmatrix}
1 & 2 & 3 \\ 
2 & 6 & 8\\ 
3 & 6 & 13
\end{bmatrix}$

 

계산 결과는 아래와 같습니다. 

 

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

\begin{bmatrix}
1 & 0 & 0 \\ 
-2 & 1 & 0\\ 
-3 & 0 & 1
\end{bmatrix}

\begin{bmatrix}
1 & 2 & 3 \\ 
2 & 6 & 8\\ 
3 & 6 & 13
\end{bmatrix}$

 

좌변은 상삼각행렬(U)이 되었고, 우변은 단위행렬과 행렬 A의 곱입니다. 우리는 소거행렬만을 사용했는데, 소거행렬은 항상 하삼각행렬입니다. 따라서 소거행렬들의 곱도 하삼각행렬이 됩니다. 양변에 단위행렬의 역행렬을 곱해줍니다. 

 

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

\begin{bmatrix}
1 & 2 & 3 \\ 
0 & 2 & 2\\ 
0 & 0 & 4
\end{bmatrix}
=
\begin{bmatrix}
1 & 2 & 3 \\ 
2 & 6 & 8\\ 
3 & 6 & 13
\end{bmatrix}$

 

좌우 변을 바꿔써줍니다. 

 

$\begin{bmatrix}
1 & 2 & 3 \\ 
2 & 6 & 8\\ 
3 & 6 & 13
\end{bmatrix}
=
\begin{bmatrix}
1 & 0 & 0 \\ 
2 & 1 & 0\\ 
3 & 0 & 1
\end{bmatrix}

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

 

LU 분해가 끝났습니다. LU분해의 원리는 행렬 A에 하삼각행렬인 소거행렬을 곱하여 가우스 소거법을 적용한다는데 있습니다. 가우스소거법이 적용된 행렬 A는 상삼각행렬 U로 바뀌는데, 이때 곱해진 소거행렬은 항상 하삼각행렬이 됩니다. 그 결과 행렬 A가 상삼각행렬과 하삼각행렬로 분해되는 것입니다. U의 대각선 요소 값을 굳이 1로 만들지 않습니다. 대각선요소를 1로 만드는 분해는 다음 시간에 설명하겠습니다. 

 

이때 주의해야할 점은 행교환연산을 하면 안된다는 것입니다. 행 교환연산은 하삼각행렬이 아니라서 LU 분해가 불가합니다. 따라서 행교환을 해야하는 경우 행교환을 한 행렬 PA 를 LU분해해야 합니다.

 

$PA=LU$

---

LU 분해는 어디에 쓰는걸까? 

LU분해는 연립방정식을 풀 때 사용됩니다. LU 분해를 통해 연립방정식을 풀어봅시다. 우리가 기존에 사용하던 방식인 가우스 소거법, 가우스-조르단 소거법에 비해 어떤 이점이 있나 생각하며 풀어봅시다. 우리가 풀어볼 연립방정식은 아래와 같습니다. 

 

$\begin{bmatrix}
2 & -2 & 2\\ 
6 & -5 & 9\\ 
4 & -4 & 5
\end{bmatrix}
\begin{bmatrix}
x_{1}\\ 
x_{2}\\ 
x_{3}
\end{bmatrix}
=\begin{bmatrix}
6\\ 
25\\ 
14
\end{bmatrix}$

 

먼저 앞에 곱해진 행렬을 LU 분해하겠습니다. 분해 과정은 아래와 같습니다. 

 

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

 

1행의 두배를 3행에서 빼줌

 

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

 

1행의 세배를 2행에서 빼줌. 

 

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

 

우변 기본행렬의 역행렬을 양변에 곱함

 

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

\begin{bmatrix}
2 & -2 & 2\\ 
6 & -5 & 9\\ 
4 & -4 & 5
\end{bmatrix}$

 

좌변 우변 교환

 

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

 

분해 완료입니다. 연립방정식에 넣으면 아래와 같습니다. 

 

$\begin{bmatrix}
1 & 0 & 0\\ 
3 & 1 & 0\\ 
2 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
2 & -2 & 2\\ 
0 & 1 & 3\\ 
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
x_{1}\\ 
x_{2}\\ 
x_{3}
\end{bmatrix}
=\begin{bmatrix}
6\\ 
25\\ 
14
\end{bmatrix}$

 

위 식에서 좌변의 두번째,세번째 항의 곱을 y로 치환합시다. 

 

$\begin{bmatrix}
2 & -2 & 2\\ 
0 & 1 & 3\\ 
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
x_{1}\\ 
x_{2}\\ 
x_{3}
\end{bmatrix}

=\begin{bmatrix}
y_{1}\\ 
y_{2}\\ 
y_{3}
\end{bmatrix}$

 

치환하면 아래와 같습니다. 

 

$\begin{bmatrix}
1 & 0 & 0\\ 
3 & 1 & 0\\ 
2 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
y_{1}\\ 
y_{2}\\ 
y_{3}
\end{bmatrix}

=\begin{bmatrix}
6\\ 
25\\ 
14
\end{bmatrix}$

 

y를 먼저 계산해줍니다. 위에서부터 계산하면 됩니다. 

 

$\begin{bmatrix}
y_{1}\\ 
y_{2}\\ 
y_{3}
\end{bmatrix}
=\begin{bmatrix}
6\\ 
7\\ 
2
\end{bmatrix}$

 

치환 수식에 넣어줍니다.

 

$\begin{bmatrix}
2 & -2 & 2\\ 
0 & 1 & 3\\ 
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
x_{1}\\ 
x_{2}\\ 
x_{3}
\end{bmatrix}

=\begin{bmatrix}
y_{1}\\ 
y_{2}\\ 
y_{3}
\end{bmatrix}$

 

$\begin{bmatrix}
2 & -2 & 2\\ 
0 & 1 & 3\\ 
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
x_{1}\\ 
x_{2}\\ 
x_{3}
\end{bmatrix}

=\begin{bmatrix}
6\\ 
7\\ 
2
\end{bmatrix}$

 

x에 대해 풀어줍니다. 

 

$\begin{bmatrix}
x_{1}\\ 
x_{2}\\ 
x_{3}
\end{bmatrix}

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

 

어떤가요? 가우스소거법으로 한번에 끝날 일을 두번 하는 느낌입니다. 별로 효율적이지 않아보이는데요. 왜쓰는걸까요? LU분해의 쓰임에 대해서는 이어지는 글들에서 다루겠습니다. 

---

LU 분해가 되는 행렬의 조건 

LU분해가 가능한 행렬의 조건입니다.

 

"소거행렬만을 이용하여 행사다리꼴행렬로 변형 가능"