LU Decomposition

저번 포스팅에서 Decomposition의 개념에 대해 알아보았으니, 이제부터 구체적인 예시를 하나하나 살펴보자. 

첫 번째로 살펴볼 것은 LU 분해이다. 연립방정식에서 출발해 LU분해까지 계산해 보자.

 

연립방정식을

LU-Decomposition (LU 분해)

어떤 행렬 A를 A=LU 모양. 즉 Lower / Upper matrix의 곱으로 분해한다. 

좌변의 행렬 A를 우변처럼 두 삼각 행렬로 만들어야 한다. 첫 번째로는 연립방정식, 행렬과 역행렬을 활용한 근본적인 LU분해법을 소개하겠다.

차근차근 단계별로 진행해 보자. 우선, 다음과 같은 연립방정식을 풀어보도록 하자.

 

다양한 방법이 있겠지만, 중학교때부터 우리는 아래와 같은 과정을 통해 연립방정식을 풀 수 있었다.

 

이러한 과정을 일컬어 "Back substitution"이라고 한다.

이번엔 이를 행렬로 표현해보자. 처음의 연립방정식은 다음과 같은 행렬로 표현된다.

우리가 앞서 수행한 연산들을 종합하여 행렬화하면 다음과 같다. 

위 행렬식에서 A|b 꼴 대신 행렬 A만을 사용하여도 같은 결과를 낼 수 있다.

이때 우변의 경우 이미 상삼각 행렬(U) 꼴이 완성된다. 

 

남은 과정은 행렬 A를 제외한 좌변을 모두 우변으로 보내는 일. 여기에 바로 역행렬이 사용된다. 기본적으로, 어느 행렬과 그 역행렬을 곱하면 단위행렬이 되어 사라지기 때문에 위 식의 양 변에 역행렬을 곱한다면 아래와 같이 식을 변화시킬 수 있다.

역행렬을 순서대로 곱하는 데 주의하자

계산을 위한 기본적인 역행렬의 성질은 다음과 같다.

변환 후 계산하여 최종적인 A = LU꼴의 분해를 행할 수 있다.

아래와 같이 약간의 편법이 섞인 다른 방법으로도 LU분해를 행할 수 있다. 

1) L행렬 : 우선 단위행렬을 만들어 둔다. U행렬 : A와 동일하게 둔다.

2) 이제 우리의 지상과제는, U행렬을 U행렬에 걸맞게 좌하단 값을 0으로 만드는 일이다. 우선 1열 2행의 값인 4를 0으로 만들어야 하는데, 이를 위해 1행에 특정 상수 a를 곱한 값들을 2행에서 빼주고, 이 a가 L행렬의 1열 2행에 들어간다. 

4-2*a = 0이므로 상수 a = 2가 된다.

위 식에서 , a는 4-a*2 = 0 을 충족해야 하므로, a = 2이다.

3) 원리를 알았으니 다음은 간단하다. U행렬의 1열 3행의 값인 -2를 0으로 만드는 a가 필요한데, -2-a*2 = 0 이므로 이번 상수의 값은 a = -1이다. 이 값 역시 L행렬의 1열 3행에 들어가게 된다.

이번엔 U행렬의 2열 3행의 값인 8을 0으로 만들어야 한다. 2열의 경우 2행의 값들을 대상으로 하며, 8-a*(-8) = 0 이므로 이번 a는 -1이다.

.

여기까지가 LU decomposition의 과정이다. 다음은 이를 통해 연립방정식을 푸는 과정이다.

아래와 같은 연립방정식은, 앞서 풀이했던 대로 LU decomposition을 통해 분해된다.

위 행렬은 아래와 같이 합쳐질 수 있다.

이 연립방정식은 굉장히 풀기 쉽다.

z1 = 5임이 바로 나오기 때문에 z2= -12, z3=2 또한 바로 계산된다. 이제 앞서 z로 합쳤던 값들도 풀 수 있다.

x3 =2로부터 x2 = 1, x1 = 1 또한 계산해낼 수 있다. 지금이야 간단한 연립방정식을 푸니 더 번거롭게 느껴질 수 있지만, 더 복잡한 방정식의 경우 LU decomposition을 통해 더 쉽게 풀 수 있게 될 것이다. 

 

추가적으로, 아래의 A와 같은 행렬을 분해하면 상삼각 행렬이 출력되지 않는다.

 따라서 우리는 행의 순서를 치환하기 위해 다른 행렬을 곱해주는데, 이를 행 교환이라고 한다.

행 교환을 거친 후에는 정상적인 LU분해가 가능한데, 이렇게 행 교환을 거쳐 행한 LU분해를 "PLU분해"라고 한다. 물론 원래의 행렬 A를 계산할 때에는 P의 역행렬을 곱해주면 되는데, 마침 P의 역행렬은 자기 자신과 똑같이 생겼으므로 같은 값을 곱해주면 된다.