LU 분해와 Cholesky (촐레스키) 분해

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]⎡⎢⎣100−310−201⎤⎥⎦⎡⎢⎣12438142613⎤⎥⎦⎡⎢⎣xyz⎤⎥⎦=⎡⎢⎣100−310−201⎤⎥⎦⎡⎢⎣3134⎤⎥⎦


  • ⇒[124022025][xyz]=[34−2]⇒⎡⎢⎣124022025⎤⎥⎦⎡⎢⎣xyz⎤⎥⎦=⎡⎢⎣34−2⎤⎥⎦


  • 이 때, 여기서 사용된 행렬은 이후에 LU 분해 시 사용됩니다.


  • [100−310−201]⎡⎢⎣100−310−201⎤⎥⎦


  • 가우스 소거법을 계속 진행해 보도록 하겠습니다.


  • [124022025][xyz]=[34−2]⎡⎢⎣124022025⎤⎥⎦⎡⎢⎣xyz⎤⎥⎦=⎡⎢⎣34−2⎤⎥⎦


  • 이번에는 3행에서 2행을 빼면 (3행 = 3행 - 2행) 다음과 같습니다.


  • [124022003][xyz]=[34−6]⎡⎢⎣124022003⎤⎥⎦⎡⎢⎣xyz⎤⎥⎦=⎡⎢⎣34−6⎤⎥⎦


  • 이 결과는 다음 행렬을 곱한 것과 같습니다.


  • [1000100−11]⎡⎢⎣1000100−11⎤⎥⎦


  • 따라서 다음과 같이 해석할 수 있습니다.


  • [1000100−11][124022025][xyz]=[1000100−11][34−2]⎡⎢⎣1000100−11⎤⎥⎦⎡⎢⎣124022025⎤⎥⎦⎡⎢⎣xyz⎤⎥⎦=⎡⎢⎣1000100−11⎤⎥⎦⎡⎢⎣34−2⎤⎥⎦


  • ⇒[124022003][xyz]=[34−6]⇒⎡⎢⎣124022003⎤⎥⎦⎡⎢⎣xyz⎤⎥⎦=⎡⎢⎣34−6⎤⎥⎦


  • 이 때, 가우스 소거법을 정의하는 행렬을 표시하면 다음과 같습니다.


  • [1000100−11]⎡⎢⎣1000100−11⎤⎥⎦


  • 가우스 소거법을 통해 정의된 빨간색과 파란색 행렬을 순서대로 곱하면 다음과 같습니다.


  • [1000100−11][100−310−201]=[100−3101−11]⎡⎢⎣1000100−11⎤⎥⎦⎡⎢⎣100−310−201⎤⎥⎦=⎡⎢⎣100−3101−11⎤⎥⎦


  • 따라서 다음과 같이 위 행렬을 이용하면 다음과 같이 상삼각행렬을 구할 수 있습니다.


  • [100−3101−11][12438142613]=[124022003]⎡⎢⎣100−3101−11⎤⎥⎦⎡⎢⎣12438142613⎤⎥⎦=⎡⎢⎣124022003⎤⎥⎦


  • ⇒[100−3101−11]A=[124022003]⇒⎡⎢⎣100−3101−11⎤⎥⎦A=⎡⎢⎣124022003⎤⎥⎦


  • 위 식에서 좌변의 행렬에 역행렬을 곱하여 우변으로 넘기면 다음과 같습니다.


  • A=[100−3101−11]−1[124022003]A=⎡⎢⎣100−3101−11⎤⎥⎦−1⎡⎢⎣124022003⎤⎥⎦


  • 이 때, 하삼각 행렬의 역행렬은 다음과 같이 정형화 할 수 있습니다.


Drawing


  • [100a10bc1]−1=[100−a10ac−b−c1]⎡⎢⎣100a10bc1⎤⎥⎦−1=⎡⎢⎣100−a10ac−b−c1⎤⎥⎦


  • 따라서 다음과 같이 정리할 수 있습니다.


  • A=[100−3101−11]−1[124022003]=[100310211][124022003]A=⎡⎢⎣100−3101−11⎤⎥⎦−1⎡⎢⎣124022003⎤⎥⎦=⎡⎢⎣100310211⎤⎥⎦⎡⎢⎣124022003⎤⎥⎦


  • 분해된 행렬의 왼쪽은 하삼각행렬로 분해되고 오른쪽은 상삼각행렬로 분해됩니다. 그리고 하삼각행렬의 대각성분은 모두 1로 표현할 수 있습니다.


  • A=LU=[100j10kl1][mno0pq00r]A=LU=⎡⎢⎣100j10kl1⎤⎥⎦⎡⎢⎣mno0pq00r⎤⎥⎦


  • LU 분해는 지금까지 살펴본 바와 같이 가우스 소거법을 행렬로 표현한 것입니다. 따라서 다음과 같이 2 x 2 행렬과 3 x 3 행렬에 대하여 정형화 할 수 있습니다. 아래 내용은 가우스 소거법을 통하여 구한 것입니다.


  • A=LUA=LU
  •  where A=[abcd],L=[10ca1],U=[ab0d−bca] where A=[abcd],L=[10ca1],U=[ab0d−bca]


  • A=LUA=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]


  • 이와 같이 앞에서 다룬 결과와 동일한 값을 얻을 수 있습니다.


선형대수학 관련 글 목차


Twitter Facebook Google+
# Linear algebra # 선형대수학 # LU 분해 # Cholesky 분해 # 촐레스키 # 숄레스키