
LU 분해와 Cholesky (촐레스키) 분해
2017, Jan 01
- 이번 글에서는 선형대수학에서 많이 사용되는
LU 분해
와LU 분해
의 특수 형태인Cholesky 분해
에 대하여 다루어 보도록 하겠습니다.
목차
LU 분해
- 어떤 행렬 AA 가 주어졌을 때, AA 를 2개 이상의 행렬의 곱으로 나타내는 것을 행렬의 분해라고 합니다. 많이 쓰는 용어로는
factorization
또는decomposition
이라고 합니다. - 만약 어떤 행렬 AA 를 다음과 같이 분해하였을 때, 이를
LU 분해
라고 합니다.
- A=[abcdefghi]=[100j10kl1][mno0pq00r]=LUA=⎡⎢⎣abcdefghi⎤⎥⎦=⎡⎢⎣100j10kl1⎤⎥⎦⎡⎢⎣mno0pq00r⎤⎥⎦=LU
- L=[100j10kl1]L=⎡⎢⎣100j10kl1⎤⎥⎦
- U=[mno0pq00r]U=⎡⎢⎣mno0pq00r⎤⎥⎦
- 위 식에서 LL 은
하삼각 행렬 (lower triangle matrix)
를 의미하며 대각선 원소는 모두 1이 됩니다. UU 는상삼각 행렬 (upper triangle matrix)
라고 합니다.
LU 분해
는 가우스 소거법을 통해 도출할 수 있습니다. 3×33×3 행렬의 예시를 통해 가우스 소거법을 통한LU
분해를 진행해 보도록 하겠습니다.
- [12438142613][xyz]=[3134]⎡⎢⎣12438142613⎤⎥⎦⎡⎢⎣xyz⎤⎥⎦=⎡⎢⎣3134⎤⎥⎦
- 가우스 소거법을 적용해 보도록 하겠습니다. 위 행렬에서 ① 1 행을 3배를 한 뒤 2행에서 빼고 (2행 = 2행 - 3 x 1행) ② 1행의 2배를 해서 3행에서 빼주면 (3행 = 3행 - 2 x 1행) 다음과 같습니다.
- [124022025][xyz]=[34−2]⎡⎢⎣124022025⎤⎥⎦⎡⎢⎣xyz⎤⎥⎦=⎡⎢⎣34−2⎤⎥⎦
- 이 때,
① 1 행을 3배를 한 뒤 2행에서 빼는 것
과② 1행의 2배를 해서 3행에서 빼는 것
을 행렬식으로 표현하면 다음과 같습니다.
- [100−310−201]⎡⎢⎣100−310−201⎤⎥⎦
- 따라서 앞에서 가우스 소거법을 적용한 것은 위 행렬식을 좌/우변에 곱하는 것과 같은 작업입니다.
- [100−310−201][12438142613][xyz]=[100−310−201][3134]
- ⇒[124022025][xyz]=[34−2]
- 이 때, 여기서 사용된 행렬은 이후에
LU
분해 시 사용됩니다.
- [100−310−201]
- 가우스 소거법을 계속 진행해 보도록 하겠습니다.
- [124022025][xyz]=[34−2]
- 이번에는 3행에서 2행을 빼면 (3행 = 3행 - 2행) 다음과 같습니다.
- [124022003][xyz]=[34−6]
- 이 결과는 다음 행렬을 곱한 것과 같습니다.
- [1000100−11]
- 따라서 다음과 같이 해석할 수 있습니다.
- [1000100−11][124022025][xyz]=[1000100−11][34−2]
- ⇒[124022003][xyz]=[34−6]
- 이 때, 가우스 소거법을 정의하는 행렬을 표시하면 다음과 같습니다.
- [1000100−11]
- 가우스 소거법을 통해 정의된 빨간색과 파란색 행렬을 순서대로 곱하면 다음과 같습니다.
- [1000100−11][100−310−201]=[100−3101−11]
- 따라서 다음과 같이 위 행렬을 이용하면 다음과 같이 상삼각행렬을 구할 수 있습니다.
- [100−3101−11][12438142613]=[124022003]
- ⇒[100−3101−11]A=[124022003]
- 위 식에서 좌변의 행렬에 역행렬을 곱하여 우변으로 넘기면 다음과 같습니다.
- A=[100−3101−11]−1[124022003]
- 이 때, 하삼각 행렬의 역행렬은 다음과 같이 정형화 할 수 있습니다.

- [100a10bc1]−1=[100−a10ac−b−c1]
- 따라서 다음과 같이 정리할 수 있습니다.
- A=[100−3101−11]−1[124022003]=[100310211][124022003]
- 분해된 행렬의 왼쪽은
하삼각행렬
로 분해되고 오른쪽은상삼각행렬
로 분해됩니다. 그리고하삼각행렬
의 대각성분은 모두 1로 표현할 수 있습니다.
- A=LU=[100j10kl1][mno0pq00r]
LU 분해
는 지금까지 살펴본 바와 같이 가우스 소거법을 행렬로 표현한 것입니다. 따라서 다음과 같이 2 x 2 행렬과 3 x 3 행렬에 대하여 정형화 할 수 있습니다. 아래 내용은 가우스 소거법을 통하여 구한 것입니다.
- A=LU
- where A=[abcd],L=[10ca1],U=[ab0d−bca]
- A=LU
- where A=[abcdefghi],
- L=[100da10gah−bgae−bda1],U=[abc0e−bdaf−cda00i−cga−(h−bga)(f−cda)e−bda]
LDU 분해
LDU 분해
는LU 분해
의 확장판이며D
는Diagonal Matrix
를 뜻하며LU 분해
의U
에 해당하는Upper Triangular Matrix
를 다음과 같이 분해하는 것입니다.
- U=[mno0pq00r]=[m000p000r][1n/mo/m01q/p001]
- 위 식을 보면 U 를 DU′ 로 분해한 형태이고 D 의 대각 성분과 U 의 대각 성분이 같습니다. 분해된 식을 살펴보면 U′ 와 같이 분해되는 것은 자명합니다.
- 따라서
LDU 분해
를 적용하면 다음과 같습니다.
- A=[abcdefghi]=[100j10kl1][mno0pq00r]=[100j10kl1][m000p000r][1n/mo/m01q/p001]=LDU
- 따라서 앞에서 구한 예제를
LDU
분해해 보도록 하겠습니다.
- A=LU=[100310211][124022003]=[100310211][100020003][124011001]
대칭행렬의 LDU 분해
대칭행렬
을LDU
분해 하였을 때, A=LDU=LDLT 로 분해되는 것을 확인해 보도록 하겠습니다.- 이 성질이 많이 사용되는 이유는 임의의 행렬 B 를 BBT 로 곱하면 항상
대칭행렬
이 되기 때문입니다. 즉, 다음과 같은 형태로 식 전개 시 많이 사용됩니다.
- BBT=A=LDLT
- 먼저 기본적인 내용을 예제를 통하여 좀 더 자세하게 살펴보도록 하겠습니다. 먼저 다음 행렬 A 를 분해해 보도록 하겠습니다.
- A=[22−421−2−4−21]=[100110−2−21][22−40−1200−3]=LU1=[100110−2−21][2000−1000−3][11−201−2001]=LDLT
- 위 형태의 일반화를 위하여 3×3 크기의 행렬을 대수적으로 표현해 보도록 하겠습니다.
- A=[axyxbzyzc]
- 먼저 1열에 대하여 가우스 소거법을 통하여
LU
분해를 진행해 보도록 하겠습니다.
- [100−xa10−ya01]A=[100−xa10−ya01][axyxbzyzc]=[axy0−x2a+b−xya+z0−xya+z−y2a+c]
- α=−x2a+b
- β=−xya+z
- γ=−y2a+c
- ⇒[axy0−x2a+b−xya+z0−xya+z−y2a+c]=[axy0αβ0βγ]
- 이번에는 2열에 대하여 가우스 소거법을 진행해 보도록 하겠습니다.
- [1000100−βα1][axy0αβ0βγ]=[axy0αβ00−β2α+γ]
- 지금까지 적용한 가우스 소거법을 행렬로 표현하면 다음과 같습니다.
- [1000100−βα1][100−xa10−ya01]A=[axy0αβ00−β2α+γ]
- L−1=[1000100−βα1][100−xa10−ya01]=[100−xa10xaβα−ya−βα1]
- L−1A=[axy0αβ00−β2α+γ]=U1
- U1=[axy0αβ00−β2α+γ]=[a000α000−β2α+γ][1xaya01βα001]=DU2
- 앞에서 다음 관계를 보였었습니다.
- [100a10bc1]−1=[100−a10ab−b−c1]
- 따라서 L 은 다음을 만족하며 LT,D 는 다음과 같이 정의 됩니다.
- L=[100xa10yaβα1]
- LT=[1xaya01βα001]
- D=[a000α000−β2α+γ]
- 위 값들을 이용하여 A=LDLT 를 만족합니다.
Cholesky 분해
Cholesky
분해는 행렬 A 가양의 정부호 행렬 (Positive Difinite Matrix)
임을 가정한 상태에서LU
분해를 하는 방법입니다. A 가양의 정부호 행렬 (Positive Difinite Matrix)
이면대칭 행렬
임을 만족합니다. (역은 성립하지 않음)- 즉
양의 정부호 행렬
A 는 대칭 행렬이므로 A=LDLT 로 분해 가능한데,양의 정부호 행렬
이라는 특성으로 인하여 유일하게 A=LLT 로 분해된다는 특성을 가집니다. - 유일하게 분해된다는 성질을 이용하여
Cholesky
분해는 식의 전개나 해를 구할 때, 자주 사용됩니다. 그러면Cholesky
분해에 대하여 알아보도록 하겠습니다.
- 행렬 A 가
양의 정부호 행렬
이면대칭행렬
이므로 A=LDLT 로 분해가 가능함은 앞에서 다루었습니다. 이 때, D=LTAL 또한양의 정부호 행렬
임을 만족합니다. 따라서 D 의 모든 대각원소는양수
입니다. 따라서 D 는 제곱근으로 분해될 수 있습니다. 이 성질을 이용하면 A=LLT 로 분해 가능합니다.
- D=[d1⋯0⋮⋱⋮0⋯dn]
- √D=[√d1⋯0⋮⋱⋮0⋯√dn]
- (√D)2=D
- L1=L√D
- L1LT1=L√D√DTLT=LDLT=A
- 따라서 A 가
양의 정부호 행렬
이면 L 이 존재하여 A=LLT 로 분해됩니다. - 아래는 예제를 통하여 A=LLT 로 분해되는 과정을 살펴본 결과입니다.
- A=[24441484814]=[100210201][244060006]=[100210201][200060006][122010001]=[100210201][√22000√62000√62][122010001]=[100210201][√2000√6000√6][√2000√6000√6][122010001]=[√2002√2√602√20√6][√22√22√20√6000√6]=LLT
- 앞에서 언급한 바와 같이
양의 정부호 행렬
A 는Cholesky
분해가 유일한 값으로 분해된다는 점을 이용하여 사용된다고 하였습니다. 이 내용을 살펴보면 다음과 같습니다.
- A=LDLT
- A=L1LT1(L1=L√D)
- L : Lower triangular matrix with all diagonal elements being 1
- D : Diagonal matrix. All diagonal matrix elements are positive numbers
- L : Lower triangular matrix with all diagonal elements being positive numbers
- L1LT1=L(√D)(√D)TLT=LDLT=A
- 마지막으로 3×3 행렬과 같이
Cholesky
분해가 많이 사용되는 행렬의 형태에서는 아래와 같이 정형화 하여 사용할 수도 있습니다.
- A=LLT
- [a11a12a13a21a22a23a31a32a33]=[l1100l21l220l31l32l33][l11l21l310l22l3200l33]=[l211l11l21l11l31l11l21l221+l222l21l31+l22l32l11l31l21l31+l22l32l231+l232+l233]
- 위 식을 정리하면 다음 값들을 순차적으로 구할 수 있습니다.
- l11=√a11
- l21=a21/l11
- l22=√a22−l221
- l31=a31/l11
- l32=(a32−l31l21)/l22
- l33=√a33−l231−l322
- 앞에서 다룬 예제를 다시 위 식을 통해 구하면 다음과 같습니다.
- A=[24441484814]
- l11=√a11=√2
- l21=a21/l11=4/√2=2√2
- l22=√a22−l221=√14−8=√6
- l31=a31/l11=4/√2=2√2
- l32=(a32−l31l21)/l22=(8−2√22√2)/√6=0
- l33=√a33−l231−l322=√14−8−0=√6
- ∴L=[√2002√2√602√20√6]
- 이와 같이 앞에서 다룬 결과와 동일한 값을 얻을 수 있습니다.