LU 분해

LU 분해(영어: LU decomposition / factorization)는 행렬을 하삼각행렬 L과 상삼각행렬 U의 곱으로 표현하는 수치해석학의 기술이다. 때때로 치환행렬 P도 여기 추가하여 표현하기도 한다. 가우스 소거법을 행렬로 표현한 것으로 이해할 수 있다. 컴퓨터가 연립 일차 방정식 문제를 풀 때 이 방식을 사용하며, 역행렬과 행렬식을 구할 때에도 사용한다. 1938년 폴란드의 수학자 타데우스 바나히에비츠(영어판)에 의해 처음 사용되었으며, 앨런 튜링에 의해 공학 분야에서 적극적으로 응용되기 시작했다.^[1]

정의

일반적인 정사각행렬 A를 LU분해한다면 다음과 같이 쓸 수 있다.

A = LU

3x3 행렬 ${\displaystyle \,A\,}$를 LU 분해하면 다음과 같이 되는 것이다.

${\displaystyle {\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}}}$

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

부분적 추축(partial pivoting)

위에서 살펴본 바와 같이 적절한 행 또는 열 교환이 필요한 경우, 치환행렬 P를 추가하게 되며 이를 LUP 분해라고 한다. 기존의 A가 바로 분해되지 않기 때문에 행을 교환하기 위해 PA를 LU분해한다. 이 때

PA = LU

이렇게 쓸 수 있다. 모든 정사각행렬은 LUP가 가능하며,^[2] 산술적인 결과도 잘 부합한다.^[3]

완전 추축(full pivoting)

완전 추축이라는 것은 열뿐만 아니라 행의 순서도 바꿔주는 것을 의미한다. 이 때 행을 바꿔주기 위한 치환행렬 Q를 포함해서 다음과 같이 쓸 수 있다.

PAQ = LU^[4]

LDU 분해

LDU 분해는 대각 행렬 D를 추가하여 다음과 같이 분해하는 것이다.

A = LDU

존재성과 유일성

정사각행렬

모든 정사각행렬 A는 LUP 분해가 가능하다.^[5] A가 가역행렬인 경우 모든 선도주소행렬식(leading principal minor)이 0이 아닌 값을 가지게 되는데, 이런 경우 P 없이 LU 분해가 바로 가능하다.^[6] 만일 A가 랭크 k인 비가역 행렬이라면, 처음 k개의 선도주소행렬식이 0이 아닌 경우에 한해 LU 분해가 가능하다. 역은 성립하지 않는다.^[7]

만일 정사각행렬이며 가역행렬인 A가 LDU 분해될 수 있다면, 그 경우의 수는 유일하다.^[6] 따라서 L이나 U 중 하나의 주대각선이 1이어야 한다고 하면 LU 분해도 유일하다고 할 수 있다.

예시

${\displaystyle {\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}}}$

하삼각행렬 L 의 주대각선을 ${\displaystyle 1}$로 놓음으로써 다음과 같이 쓸 수 있다.

${\displaystyle {\begin{aligned}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{aligned}}}$

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

${\displaystyle {\begin{aligned}l_{21}&=1.5\\u_{11}&=4\\u_{12}&=3\\u_{22}&=-1.5\end{aligned}}}$

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

${\displaystyle {\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}}}$

L U {\displaystyle LU} 분해

사다리꼴행렬을 이용한 ${\displaystyle LU}$ 분해

${\displaystyle 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}}}$

${\displaystyle {\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}}}$

${\displaystyle {\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}}}$

${\displaystyle {\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}}}$

${\displaystyle 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}}}$

${\displaystyle LU=A}$이다.

역행렬과정의 불완전한 LU분해

가우스 소거법을 사용해서, 다음과 같은 행렬 ${\displaystyle M}$의 단위행렬 ${\displaystyle I}$을 첨가 행렬로 계산하면, 역행렬${\displaystyle M^{-1}}$를 얻을수있다.

${\displaystyle M={\begin{pmatrix}-1&1&2\\3&-1&1\\-1&3&4\end{pmatrix}}}$

기본행연산을 가하면, 다음과 같다.

${\displaystyle {\begin{aligned}{\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{aligned}}}$

따라서 ${\displaystyle M^{-1}}$은 다음과 같다.

${\displaystyle M^{-1}={\begin{pmatrix}-0.7&0.2&0.3\\-1.3&-0.2&0.7\\0.8&0.2&-0.2\end{pmatrix}}}$

사다리꼴행렬의 역행렬 중간 과정은 유사한 LU 분해를 보여주지만

그러나, 이것은 완전한 LU 분해가 아니다.

${\displaystyle \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}$

그러나 이러한 역행렬 과정을 통해 추가적인 조작으로 ${\displaystyle LU}$분해를 유도할 수 있다.

응용

선형 연립방정식의 풀이

다음 선형 연립방정식이 주어져 있다.

${\displaystyle Ax=b}$

계수 행렬 ${\displaystyle A}$를 행 교환을 허용한 가우스 소거법을 통해 LU 분해하면 다음과 같은 꼴로 분해된다. 여기서 ${\displaystyle P}$는 치환행렬이다.

${\displaystyle PA=LU}$

따라서 연립방정식은 다음과 같이 나타낼 수 있다.

${\displaystyle PAx=Pb\iff LUx=Pb}$

연립방정식의 해는 2단계에 걸쳐서 풀이한다.

1. 전진 대입: ${\displaystyle Ly=Pb}$를 y에 대해 풀고,
2. 후진 대입: ${\displaystyle Ux=y}$를 x에 대해서 푼다.

LU 분해를 통한 풀이는 계수 행렬이 같고 ${\displaystyle b}$만이 달라질 때, 매번 첨가행렬의 가우스 소거법을 통해 연립방정식의 해를 구하는 것보다 간편하다. 그러나 LU 분해를 하는 과정 자체는 가우스 소거법과 동일한 과정을 거치게 된다.

행렬식 계산

삼각행렬의 행렬식은 주대각 성분의 곱이 행렬식과 같다는 점을 이용하면 LU 분해를 통해 행렬식을 쉽게 계산할 수 있다. 치환행렬은 ${\displaystyle P^{-1}=P^{T}}$를 만족하는 직교 행렬이므로 ${\displaystyle \det {P^{-1}}=\det {P}}$이라는 점을 이용할 수 있다.

${\displaystyle 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)}$

여기서 S는 LU 분해를 할 때 행 교환을 시행한 횟수이다.

각주

1. Schwarzenberg-Czerny, A. (1995). “On matrix factorization and efficient least squares solution”. 《Astronomy and Astrophysics Supplement Series》 110: 405. Bibcode:1995A&AS..110..405S.
2. Okunev & Johnson (1997) harvtxt error: 대상 없음: CITEREFOkunevJohnson1997 (help), Corollary 3.
3. Trefethen & Bau (1997) harvtxt error: 대상 없음: CITEREFTrefethenBau1997 (help), p. 166.
4. Trefethen & Bau (1997) harvtxt error: 대상 없음: CITEREFTrefethenBau1997 (help), p. 161.
5. Okunev & Johnson (1997) harvtxt error: 대상 없음: CITEREFOkunevJohnson1997 (help), Corollary 3.
6. Horn & Johnson (1985) harvtxt error: 대상 없음: CITEREFHornJohnson1985 (help), Corollary 3.5.5
7. Horn & Johnson (1985) harvtxt error: 대상 없음: CITEREFHornJohnson1985 (help), Theorem 3.5.2

같이 보기

• 가우스 소거법
• 사다리꼴행렬
• QR 분해
• 행렬 분해
• 가우스-자이델 방법
• 숄레스키 분해(촐레스키 분해)

참고

• 매스월드