LU 분해 문서 원본 보기

{{위키데이터 속성 추적}}
'''LU 분해'''({{llang|en|LU decomposition / factorization}})는 행렬을 [[하삼각행렬]] {{수학|'''L'''}}과 [[상삼각행렬]] {{수학|'''U'''}}의 곱으로 표현하는 [[수치해석학]]의 기술이다. 때때로 [[치환행렬]] {{수학|'''P'''}}도 여기 추가하여 표현하기도 한다. [[가우스 소거법]]을 행렬로 표현한 것으로 이해할 수 있다. 컴퓨터가 [[연립 일차 방정식]] 문제를 풀 때 이 방식을 사용하며, [[역행렬]]과 [[행렬식]]을 구할 때에도 사용한다. 1938년 [[폴란드]]의 수학자 {{Ill|타데우스 바나히에비츠|en|Tadeusz Banachiewicz}}에 의해 처음 사용되었으며, [[앨런 튜링]]에 의해 공학 분야에서 적극적으로 응용되기 시작했다.<ref name="Schwarzenberg">{{저널 인용|title=On matrix factorization and efficient least squares solution|journal=Astronomy and Astrophysics Supplement Series|last1=Schwarzenberg-Czerny|first1=A.|year=1995|volume=110|pages=405|bibcode=1995A&AS..110..405S}}</ref>

== 정의 ==
일반적인 정사각행렬 {{수학|'''A'''}}를 LU분해한다면 다음과 같이 쓸 수 있다.<blockquote>{{수학|1='''A''' = '''LU'''}}</blockquote>3x3 행렬 <math>\, A \, </math>를 LU 분해하면 다음과 같이 되는 것이다.

<math>
  \begin{bmatrix}
    a_{11} & a_{12} & a_{13} \\
    a_{21} & a_{22} & a_{23} \\
    a_{31} & a_{32} & a_{33}
  \end{bmatrix} =
  \begin{bmatrix}
    l_{11} &      0 & 0      \\
    l_{21} & l_{22} & 0      \\
    l_{31} & l_{32} & l_{33}
  \end{bmatrix}
  \begin{bmatrix}
    u_{11} & u_{12} & u_{13} \\
         0 & u_{22} & u_{23} \\
         0 &      0 & u_{33}
  \end{bmatrix}
</math>

행렬의 성분들을 적절하게 정렬해주지 않으면 LU 분해를 처음 의도한 목적대로 사용할 수 없게 될 수도 있다. 가령 <math display="inline">a_{11} = 0</math>이라면 <math display="inline">a_{11} = l_{11} u_{11}</math>이므로 <math display="inline">l_{11}</math>과 <math display="inline">u_{11}</math> 둘 중 하나는 0이 되어야 하는데, 이는 최소 {{수학|'''L'''}}이나 {{수학|'''U'''}} 둘 중 하나는 비가역행렬이라는 것을 의미한다. 만일 {{수학|'''A'''}}가 [[가역행렬]]이라면 불가능한 일이다. 이런 경우에 애당초 바로 LU 분해가 불가능하다. 따라서 {{수학|'''A'''}}의 첫 번째 성분에 0이 아닌 다른 수가 오도록 행교환을 해주어야 한다.

=== 부분적 추축(partial pivoting) ===
위에서 살펴본 바와 같이 적절한 행 또는 열 교환이 필요한 경우, 치환행렬 {{수학|'''P'''}}를 추가하게 되며 이를 '''LUP''' 분해라고 한다. 기존의 {{수학|'''A'''}}가 바로 분해되지 않기 때문에 행을 교환하기 위해 {{수학|'''P'''}}{{수학|'''A'''}}를 LU분해한다. 이 때<blockquote>{{수학|1='''PA''' = '''LU'''}}</blockquote>이렇게 쓸 수 있다. 모든 정사각행렬은 LUP가 가능하며,<ref name="okunev-cor3">{{harvtxt|Okunev|Johnson|1997}}, Corollary 3.</ref> 산술적인 결과도 잘 부합한다.<ref>{{harvtxt|Trefethen|Bau|1997}}, p. 166.</ref>

=== 완전 추축(full pivoting) ===
완전 추축이라는 것은 열뿐만 아니라 행의 순서도 바꿔주는 것을 의미한다. 이 때 행을 바꿔주기 위한 치환행렬 {{수학|'''Q'''}}를 포함해서 다음과 같이 쓸 수 있다.<blockquote>{{수학|1='''PAQ''' = '''LU'''}}<ref>{{harvtxt|Trefethen|Bau|1997}}, p. 161.</ref></blockquote>

=== LDU 분해 ===
LDU 분해는 [[대각 행렬]] {{수학|'''D'''}}를 추가하여 다음과 같이 분해하는 것이다.<blockquote>{{수학|1='''A''' = '''LDU'''}}</blockquote>

== 존재성과 유일성 ==

=== 정사각행렬 ===
모든 정사각행렬 {{수학|'''A'''}}는 LUP 분해가 가능하다.<ref name="okunev-cor32">{{harvtxt|Okunev|Johnson|1997}}, Corollary 3.</ref> {{수학|'''A'''}}가 [[가역행렬]]인 경우 모든 선도주[[소행렬식]](leading principal minor)이 0이 아닌 값을 가지게 되는데, 이런 경우 {{수학|'''P'''}} 없이 LU 분해가 바로 가능하다.<ref name="horn-cor355">{{harvtxt|Horn|Johnson|1985}}, Corollary 3.5.5</ref> 만일 {{수학|'''A'''}}가 [[계수 (선형대수학)|랭크]] k인 비가역 행렬이라면, 처음 k개의 선도주소행렬식이 0이 아닌 경우에 한해 LU 분해가 가능하다. 역은 성립하지 않는다.<ref>{{harvtxt|Horn|Johnson|1985}}, Theorem 3.5.2</ref>

만일 정사각행렬이며 가역행렬인 {{수학|'''A'''}}가 LDU 분해될 수 있다면, 그 경우의 수는 유일하다.<ref name="horn-cor355" /> 따라서 L이나 U 중 하나의 [[주대각선]]이 1이어야 한다고 하면 LU 분해도 유일하다고 할 수 있다.

== 예시 ==
<math>
  \begin{bmatrix}
    4 & 3 \\
    6 & 3
  \end{bmatrix} =
  \begin{bmatrix}
    1 & 0      \\
    l_{21} & 1
  \end{bmatrix}
  \begin{bmatrix}
    u_{11} & u_{12} \\
         0 & u_{22}
  \end{bmatrix}
</math>

[[삼각행렬|하삼각행렬]] {{수학|'''L'''}} 의 [[주대각선]]을 <math>1</math>로 놓음으로써 다음과 같이 쓸 수 있다.

<math>\begin{align}
            1 \cdot u_{11} + 0 \cdot 0 &= 4 \\
       1 \cdot u_{12} + 0 \cdot u_{22} &= 3 \\
       l_{21} \cdot u_{11} + 1 \cdot 0 &= 6 \\
  l_{21} \cdot u_{12} + 1 \cdot u_{22} &= 3
\end{align}</math>

이를 차례로 계산하여 다음의 결과를 얻을 수 있다.

<math>\begin{align}
  l_{21} &=  1.5 \\
  u_{11} &=  4   \\
  u_{12} &=  3   \\
  u_{22} &= -1.5
\end{align}</math>

따라서 다음과 같이 분해된다.

<math>
  \begin{bmatrix}
    4 & 3 \\
    6 & 3
  \end{bmatrix} =
  \begin{bmatrix}
    1   & 0 \\
    1.5 & 1
  \end{bmatrix}
  \begin{bmatrix}
    4 &  3 \\
    0 & -1.5
  \end{bmatrix}
</math>

== <math> LU</math> 분해 ==
[[사다리꼴행렬]]을 이용한 <math> LU</math> 분해
:<math>
 I =   \begin{pmatrix}
   1 & 0 & 0  \\
   0 & 1 & 0  \\
   0 & 0 & 1
\end{pmatrix} ,
A=  \begin{pmatrix}
   2 & 1 & 1   \\
   4 & -6 & 0   \\
   -2 & 7 & 2
\end{pmatrix} </math>
<!--  첫째 열을 사다리꼴로 만들기 위해 첫째행을 이용하여 나머지 행들을 변형시킨다.-->

:<math>
 \begin{pmatrix}
   1 & 0 & 0  \\
   2 & 1 & 0  \\
   0 & 0 & 1
\end{pmatrix}
 \begin{pmatrix}
   2 & 1 & 1   \\
   0 & -8 & -2   \\
   -2 & 7 & 2
\end{pmatrix} </math>

:<math> \begin{pmatrix}
   1 & 0 & 0  \\
   2 & 1 & 0  \\
   -1 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
   2 & 1 & 1   \\
   0 & -8 & -2   \\
   0 & 8 & 3
\end{pmatrix} </math>
<!-- 둘째 열을 사다리꼴로 만들기 위해 둘째행을 이용하여 마지막 행을 변형시킨다. -->
:<math> \begin{pmatrix}
   1 & 0 & 0  \\
   2 & 1 & 0  \\
   -1 & -1 & 1
\end{pmatrix}
\begin{pmatrix}
   2 & 1 & 1  \\
   0 & -8 & -2  \\
   0 & 0 & 1
\end{pmatrix} </math>

:<math> L=\begin{pmatrix}
   1 & 0 & 0  \\
   2 & 1 & 0  \\
   -1 & -1 & 1
\end{pmatrix}
U=\begin{pmatrix}
   2 & 1 & 1  \\
   0 & -8 & -2  \\
   0 & 0 & 1
\end{pmatrix} </math>
:<math> LU = A </math>이다.

== 역행렬과정의 불완전한 LU분해 ==
[[가우스 소거법]]을 사용해서,
다음과 같은 행렬 <math>M</math>의 [[단위행렬]] <math>I</math>을 [[첨가 행렬]]로 계산하면,
역행렬<math>M^{-1}</math>를 얻을수있다.
:<math>M = \begin{pmatrix}
   -1 & 1 & 2  \\
   3 & -1 & 1  \\
   -1 & 3 & 4
\end{pmatrix} </math>
[[기본행렬#기본행연산|기본행연산]]을 가하면, 다음과 같다.
:<math>\begin{align}
  \begin{pmatrix}
   \ I & \vert& M
\end{pmatrix}  &\to \left( \left. \begin{matrix}
  1 & 0 & 0  \\
   0 & 1 & 0  \\
   0 & 0 & 1  \\
\end{matrix} \ \ \right| \ \ \begin{matrix}

  -1 & 1 & 2  \\
   3 & -1 & 1  \\
   -1 & 3 & 4  \\
\end{matrix} \right)\\
 &\to\left(\left. \begin{matrix}
  1 & 0 & 0  \\
   3 & 1 & 0  \\
   -1 & 0 & 1  \\
\end{matrix} \right| \begin{matrix}
    -1 & 1 & 2  \\
   0 & 2 & 7  \\
   0 & 2 & 2  \\
\end{matrix} \right)\\
 &\to\left(\left. \begin{matrix}
    1 & {\color{red}{0}} & {\color{red}{0}}  \\
   3 & 1 & {\color{red}{0}} \\
   -4 & -1 & 1  \\
\end{matrix} \right| \begin{matrix}
  -1 & 1 & 2  \\
  {\color{red}{0}} & 2 & 7  \\
   {\color{red}{0}} & {\color{red}{0}} & -5  \\
\end{matrix}\right)\\
&\to\left( \left. \begin{matrix}
   -1 & {0} & {0}  \\
   1.5 & 0.5 & {0}  \\
   0.8 & 0.2 & -0.2  \\
\end{matrix} \right| \begin{matrix}
   1 & -1 & -2  \\
  {0} & 1 & 3.5  \\
  {0} & {0} & 1  \\
\end{matrix} \right)\\
 &\to\left( \left. \begin{matrix}
    0.6 & 0.4 & -0.4  \\
   -1.3 & -0.2 & 0.7  \\
   0.8 & 0.2 & -0.2  \\
\end{matrix} \ \ \right| \ \ \begin{matrix}
  1 & -1 & 0  \\
   0 & 1 & 0  \\
   0 & 0 & 1  \\
\end{matrix} \right) \\
 & \to \left( \left. \begin{matrix}
    -0.7 & 0.2 & 0.3  \\
   -1.3 & -0.2 & 0.7  \\
   0.8 & 0.2 & -0.2  \\
\end{matrix} \ \ \right| \ \ \begin{matrix}
  1 & 0 & 0  \\
   0 & 1 & 0  \\
   0 & 0 & 1  \\
\end{matrix} \right)
\end{align}</math>
따라서 <math>M^{-1}</math>은 다음과 같다.
:<math>M^{-1}=\begin{pmatrix}
   -0.7 & 0.2 & 0.3  \\
   -1.3 & -0.2 & 0.7  \\
   0.8 & 0.2 & -0.2
\end{pmatrix}</math>
<!-- 여기서 중간 과정에 LU 분해가 일어났었다.  -->
사다리꼴행렬의 역행렬 중간 과정은 유사한 LU 분해를 보여주지만

그러나, 이것은 완전한 LU 분해가 아니다.
:<math>
\left(\left. \begin{matrix}
   1 & {\color{red}{0}} & {\color{red}{0}}  \\
   3 & 1 & {\color{red}{0}} \\
   -4 & -1 & 1  \\
\end{matrix} \right|  \begin{matrix}
   -1 & 1 & 2  \\
  {\color{red}{0}} & 2 & 7  \\
   {\color{red}{0}} & {\color{red}{0}} & -5  \\
\end{matrix}\right)

= \begin{pmatrix}
   1 & {\color{red}{0}} & {\color{red}{0}}  \\
   3 & 1 & {\color{red}{0}} \\
   -4 & -1 & 1  \\
\end{pmatrix}
 \begin{pmatrix}
   -1 & 1 & 2  \\
  {\color{red}{0}} & 2 & 7  \\
   {\color{red}{0}} & {\color{red}{0}} & -5  \\
\end{pmatrix}

\neq \begin{pmatrix}
   -1 & 1 & 2  \\
   3 & -1 & 1  \\
   -1 & 3 & 4
\end{pmatrix} =M</math>

그러나 이러한 역행렬 과정을 통해 추가적인 조작으로 <math>LU</math>분해를 유도할 수 있다.

<!-- ==LU분해값을 사용한 연산==
:<math>M = \begin{pmatrix}
   -1 & 1 & 2  \\
   3 & -1 & 1  \\
   -1 & 3 & 4
\end{pmatrix}
 \begin{pmatrix}
   x_1   \\
   x_2   \\
   x_3
\end{pmatrix} = 
 \begin{pmatrix}
   5   \\
   7   \\
   5
\end{pmatrix}
 </math>
:<math>
M=
\begin{pmatrix}
   -1 & 1 & 2  \\
  {\color{red}{0}} & 2 & 7  \\
   {\color{red}{0}} & {\color{red}{0}} & -5  \\
\end{pmatrix}
 \begin{pmatrix}
   1 & {\color{red}{0}} & {\color{red}{0}}  \\
   3 & 1 & {\color{red}{0}} \\
   -4 & -1 & 1  \\
\end{pmatrix}


 \begin{pmatrix}
   x_1   \\
   x_2   \\
   x_3
\end{pmatrix} = 
 \begin{pmatrix}
   5   \\
   7   \\
   10
\end{pmatrix}
 </math>
* <math>L</math> 분해값 연산
:<math>
\begin{pmatrix}
   -1 & 1 & 2  \\
  {\color{red}{0}} & 2 & 7  \\
   {\color{red}{0}} & {\color{red}{0}} & -5  \\
\end{pmatrix}

 \begin{pmatrix}
   y_1   \\
   y_2   \\
   y_3
\end{pmatrix} = 
 \begin{pmatrix}
   5   \\
   7   \\
   -5
\end{pmatrix}
 </math>

:<math>  - y_1 + y_2  + 2y_3 = 5    </math>
:<math>  2y_2 + 7y_3 = 7    </math>
:<math>  -5y_3 = -10    </math>
:<math>  y_3 = 2   </math>

:<math>  2y_2 + 7 \left( 2  \right) = 7    </math>
:<math>  2y_2  = 7  -14 </math>
:<math>  y_2  = {-7 \over 2}    </math>

:<math>  -y_1 + {-7 \over 2} +2 \left( 2 \right) =5  </math>
:<math>  -y_1 + 7 -2 =5  </math>
:<math>  y_1 - 7 +2 =-5  </math>
:<math>  y_1  =-5 +5 </math>
:<math>  y_1 =0 </math>

:<math>
 \begin{pmatrix}
   y_1   \\
   y_2   \\
   y_3
\end{pmatrix} = 
 \begin{pmatrix}
   0   \\
   7   \\
   -1
\end{pmatrix}
 </math>

* <math>U</math> 분해값 연산
:<math>
 \begin{pmatrix}
   1 & {\color{red}{0}} & {\color{red}{0}}  \\
   3 & 1 & {\color{red}{0}} \\
   -4 & -1 & 1  \\
\end{pmatrix}

 \begin{pmatrix}
   x_1   \\
   x_2   \\
   x_3
\end{pmatrix} = 
 \begin{pmatrix}
   0   \\
   7   \\
   -1
\end{pmatrix}
 </math>

:<math>  x_1 = 0 </math>
:<math>  3\left( 0 \right) + x_2= 7 </math>
:<math> 0 +  x_2= 7  </math>
:<math>   x_2= 7 </math>
:<math>  -4x_1 - x_2 +x_3= -1   </math>
:<math>  -4\left(0 \right)- 7 +x_3= -1  </math>
:<math> 0+ x_3= -1 +7    </math>
:<math> x_3= 6   </math>
:<math>
 \begin{pmatrix}
   x_1   \\
   x_2   \\
   x_3
\end{pmatrix} = 
 \begin{pmatrix}
   0   \\
   7   \\
   6
\end{pmatrix}
 </math>
-->
== 응용 ==
=== 선형 연립방정식의 풀이 ===
다음 선형 연립방정식이 주어져 있다.
:<math>Ax=b</math>
계수 행렬 <math>A</math>를 행 교환을 허용한 가우스 소거법을 통해 LU 분해하면 다음과 같은 꼴로 분해된다. 여기서 <math>P</math>는 [[치환행렬]]이다.
:<math>PA=LU</math>
따라서 연립방정식은 다음과 같이 나타낼 수 있다.
:<math>PAx=Pb \iff LUx=Pb</math>
연립방정식의 해는 2단계에 걸쳐서 풀이한다.
# '''전진 대입''': <math>Ly=Pb</math>를 y에 대해 풀고,
# '''후진 대입''': <math>Ux=y</math>를 x에 대해서 푼다.
LU 분해를 통한 풀이는 계수 행렬이 같고 <math>b</math>만이 달라질 때, 매번 첨가행렬의 가우스 소거법을 통해 연립방정식의 해를 구하는 것보다 간편하다. 그러나 LU 분해를 하는 과정 자체는 가우스 소거법과 동일한 과정을 거치게 된다.

=== 행렬식 계산 ===
[[삼각행렬]]의 [[행렬식]]은 주대각 성분의 곱이 행렬식과 같다는 점을 이용하면 LU 분해를 통해 행렬식을 쉽게 계산할 수 있다. 치환행렬은 <math>P^{-1}=P^{T}</math>를 만족하는 직교 행렬이므로 <math>\det{P^{-1}}=\det{P}</math>이라는 점을 이용할 수 있다.
:<math>PA=LU \implies A=P^{-1}LU \implies \det{A}=\det{P}\det{L}\det{U}=(-1)^{S}\left( \prod_{i=1}^n l_{ii} \right) \left( \prod_{i=1}^n u_{ii} \right)</math>
여기서 ''S''는 LU 분해를 할 때 행 교환을 시행한 횟수이다.

== 각주 ==
{{각주}}
== 같이 보기 ==
* [[가우스 소거법]]
* [[사다리꼴행렬]]
* [[QR 분해]]
* [[행렬 분해]]
* [[가우스-자이델 방법]]
* [[숄레스키 분해]](촐레스키 분해)

== 참고 ==
* [http://mathworld.wolfram.com/LUDecomposition.html 매스월드]

[[분류:행렬 분해]]
[[분류:선형대수학]]
[[분류:수치선형대수학]]