LU 분해

L은 Lower triangular form, U는 Upper triangular form을 의미한다. 이는 행렬분해의 일종인데, 행렬 계산을 편하게 만들어 준다는 점이 큰 장점이 된다.

행렬 계산은 무조건 Ax = b가 예시가 된다. A, b가 주어지면 x를 구하는 형식이다. 이전에 설명했던 가우스 소거법도 마찬가지이다.

LU 분해는 다음과 같은 과정으로 이루어 진다.

Ax = b
-> (LU)x = b
-> Ly = b (단, Ux = y)

즉, A를 L과 U로 행렬분해 해야한다는 의미이다.
저 과정에서 x를 구하려면 또한 Ly = b에서 y를 먼저 구하고 (1) 그 이후에, Ux = y에서 y값을 구했으므로 x를 구할 수 있다.

(1) forward subtitution
(2) back subtitution

2단계의 과정을 거친다.
이런 식으로 x를 쉽게 구할 수 있기 때문에 가우스 소거법의 forward elimination을 행렬로 코드화 한 것이라고 볼 수 있다.

또한 PLU 분해가 있다. 여기서 PLU 각각은 다음과 같다. 이전의 가우스 소거법의 replacement, scaling, interchange를 상기시켜 보자.

L : replacement, scaling Elementary Row Operation를 기록해둔 행렬
U : forward elimination 후 남은 Upper Triangular Matrix
P : interchange

이를 모두 합쳐서 PLU 분해라고 한다.
P에서 각각의 행을 바꿀 때는 기존의 Identity 행렬에서 바꾸고 싶은 행끼리 바꾼 것을 말한다.

이로써 interchange 까지 코드로 구현이 가능한 것이다.

Ax = b 문제를 A의 역행렬로 푸는 것보다 LU분해가 나음 점은 바로 수치적 안정성(역행렬은 오차가 많이 생김) 또한, b가 자주 update되는 경우에 실시간으로 x를 구할 수 있다는 점이다.

== 왜냐하면 미리 A를 LU로 분해해 놓고 계속 b만 대입하면서 풀 수 있기 때문이다.

다음은 L을 구하는 예제인데, E는 EROs연산 중 하나를 의미한다. A = E^-1U 인데, 왜냐하면 EROs를 통해서 Upper Matrix를 구하기 때문이다.

코드예제

# PLU 분해만 하기
P, L, U = scipy.linalg.lu(A)
# 실제로 LU 분해
lu, piv = scipy.linalg.lu_factor(A)
x = scipy.linalg.lu_solve((lu, piv), b)
# 여기서 piv는 순열행렬 P와 같습니다.