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

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

2017, Jan 01    


선형대수학 관련 글 목차


  • 이번 글에서는 선형대수학에서 많이 사용되는 LU 분해LU 분해의 특수 형태인 Cholesky 분해에 대하여 다루어 보도록 하겠습니다.


목차



LU 분해


  • 어떤 행렬 AA 가 주어졌을 때, AA 를 2개 이상의 행렬의 곱으로 나타내는 것을 행렬의 분해라고 합니다. 많이 쓰는 용어로는 factorization 또는 decomposition 이라고 합니다.
  • 만약 어떤 행렬 AA 를 다음과 같이 분해하였을 때, 이를 LU 분해라고 합니다.


  • A=[abcdefghi]=[100j10kl1][mno0pq00r]=LUA=abcdefghi=100j10kl1mno0pq00r=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]12438142613xyz=3134


  • 가우스 소거법을 적용해 보도록 하겠습니다. 위 행렬에서 ① 1 행을 3배를 한 뒤 2행에서 빼고 (2행 = 2행 - 3 x 1행) ② 1행의 2배를 해서 3행에서 빼주면 (3행 = 3행 - 2 x 1행) 다음과 같습니다.


  • [124022025][xyz]=[342]124022025xyz=342


  • 이 때, ① 1 행을 3배를 한 뒤 2행에서 빼는 것② 1행의 2배를 해서 3행에서 빼는 것을 행렬식으로 표현하면 다음과 같습니다.


  • [100310201]100310201


  • 따라서 앞에서 가우스 소거법을 적용한 것은 위 행렬식을 좌/우변에 곱하는 것과 같은 작업입니다.


  • [100310201][12438142613][xyz]=[100310201][3134]


  • [124022025][xyz]=[342]


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


  • [100310201]


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


  • [124022025][xyz]=[342]


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


  • [124022003][xyz]=[346]


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


  • [100010011]


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


  • [100010011][124022025][xyz]=[100010011][342]


  • [124022003][xyz]=[346]


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


  • [100010011]


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


  • [100010011][100310201]=[100310111]


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


  • [100310111][12438142613]=[124022003]


  • [100310111]A=[124022003]


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


  • A=[100310111]1[124022003]


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


Drawing


  • [100a10bc1]1=[100a10acbc1]


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


  • A=[100310111]1[124022003]=[100310211][124022003]


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


  • A=LU=[100j10kl1][mno0pq00r]


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


  • A=LU
  •  where A=[abcd],L=[10ca1],U=[ab0dbca]


  • A=LU
  •  where A=[abcdefghi],
  • L=[100da10gahbgaebda1],U=[abc0ebdafcda00icga(hbga)(fcda)ebda]


LDU 분해


  • LDU 분해LU 분해의 확장판이며 DDiagonal Matrix를 뜻하며 LU 분해U에 해당하는 Upper Triangular Matrix를 다음과 같이 분해하는 것입니다.


  • U=[mno0pq00r]=[m000p000r][1n/mo/m01q/p001]


  • 위 식을 보면 UDU 로 분해한 형태이고 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 로 분해되는 것을 확인해 보도록 하겠습니다.
  • 이 성질이 많이 사용되는 이유는 임의의 행렬 BBBT 로 곱하면 항상 대칭행렬이 되기 때문입니다. 즉, 다음과 같은 형태로 식 전개 시 많이 사용됩니다.


  • BBT=A=LDLT


  • 먼저 기본적인 내용을 예제를 통하여 좀 더 자세하게 살펴보도록 하겠습니다. 먼저 다음 행렬 A 를 분해해 보도록 하겠습니다.


  • A=[224212421]=[100110221][224012003]=LU1=[100110221][200010003][112012001]=LDLT


  • 위 형태의 일반화를 위하여 3×3 크기의 행렬을 대수적으로 표현해 보도록 하겠습니다.


  • A=[axyxbzyzc]


  • 먼저 1열에 대하여 가우스 소거법을 통하여 LU 분해를 진행해 보도록 하겠습니다.


  • [100xa10ya01]A=[100xa10ya01][axyxbzyzc]=[axy0x2a+bxya+z0xya+zy2a+c]


  • α=x2a+b
  • β=xya+z
  • γ=y2a+c


  • [axy0x2a+bxya+z0xya+zy2a+c]=[axy0αβ0βγ]


  • 이번에는 2열에 대하여 가우스 소거법을 진행해 보도록 하겠습니다.


  • [1000100βα1][axy0αβ0βγ]=[axy0αβ00β2α+γ]


  • 지금까지 적용한 가우스 소거법을 행렬로 표현하면 다음과 같습니다.


  • [1000100βα1][100xa10ya01]A=[axy0αβ00β2α+γ]
  • L1=[1000100βα1][100xa10ya01]=[100xa10xaβαyaβα1]
  • L1A=[axy0αβ00β2α+γ]=U1
  • U1=[axy0αβ00β2α+γ]=[a000α000β2α+γ][1xaya01βα001]=DU2


  • 앞에서 다음 관계를 보였었습니다.


  • [100a10bc1]1=[100a10abbc1]


  • 따라서 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=[d100dn]
  • D=[d100dn]
  • (D)2=D


  • L1=LD
  • L1LT1=LDDTLT=LDLT=A


  • 따라서 A양의 정부호 행렬이면 L 이 존재하여 A=LLT 로 분해됩니다.
  • 아래는 예제를 통하여 A=LLT 로 분해되는 과정을 살펴본 결과입니다.


  • A=[24441484814]=[100210201][244060006]=[100210201][200060006][122010001]=[100210201][220006200062][122010001]=[100210201][200060006][200060006][122010001]=[20022602206][22222060006]=LLT


  • 앞에서 언급한 바와 같이 양의 정부호 행렬 ACholesky 분해가 유일한 값으로 분해된다는 점을 이용하여 사용된다고 하였습니다. 이 내용을 살펴보면 다음과 같습니다.


  • A=LDLT
  • A=L1LT1(L1=LD)
  • 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=a22l221
  • l31=a31/l11
  • l32=(a32l31l21)/l22
  • l33=a33l231l322


  • 앞에서 다룬 예제를 다시 위 식을 통해 구하면 다음과 같습니다.


  • A=[24441484814]
  • l11=a11=2
  • l21=a21/l11=4/2=22
  • l22=a22l221=148=6
  • l31=a31/l11=4/2=22
  • l32=(a32l31l21)/l22=(82222)/6=0
  • l33=a33l231l322=1480=6
  • L=[20022602206]


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


선형대수학 관련 글 목차