LU 분해 (LU Decomposition)

https://dev-ryuon.tistory.com/46

# 1. 가우스 소거법 (Gauss Elimination)

이 포스트는 가우스 소거법에 대해 숙지하고 보시는 것을 추천합니다.

 

이론

LU 분해는 Gauss Elimination 을 행렬이라는 자료구조로 표현한 것을 의미한다. 숫자는 인수분해가 가능하다. 행렬도 숫자와 마찬가지로 분해가 가능하다. 행렬을 분해하는 방법에는 대표적으로 세 가지가 있다.

 

• LU Decomposition
• QR Decomposition
• SVD (Singular Value Decomposition) 

 

LU 분해는 인수분해를 하듯 Lower triangular matrix와 Upper triangular matrix의 곱으로 분해하는 것이다.

 

LU Decomposition

이 과정은 실제로 Gauss Elimination의 Forward Elimination과 밀접한 관련이 있다. Upper triangular matrix는 Forward Elimination의 결과물에 해당하고, Lower triangular matrix는 Forward Elimination을 수행하는 과정을 행렬로써 표현한 것이다.

 

Ax = b 형태의 linear system이 있다고 가정해보자. 우리의 궁극적인 목표는 x를 구하는 것이다.

A row vector를 LU Decomposition이 가능하다고 가정하면, LUx = b 과 같은 형태로 표현할 수 있다. 결합법칙을 적용하여 L(Ux) = b로 표현할 수 있다. Ux를 하나의 벡터 y로 가정하면 Ly = b로 정의할 수 있다.

 

Ux = y

Ly = b

위 행렬을 보면 알 수 있듯이 Ly = b 형태를 이용하면, 전방대치법(Forward-substitution)을 통해 y 벡터를 구할 수 있다. 그리고, y 벡터를 Ux = y에 실제값으로써 대입하면 x 벡터도 쉽게 구할 수 있다.

 

• L : A row vector를 전방소거하는데 쓰인 replacement와 scaling에 대한 EROs를 기록한 행렬
• U : A row vector를 전방소거 한 후 남은 upper triangular matrix
• P(Permutation) : A row vector를 전방소거하는데 쓰인 interchange에 대한 EROs를 기록한 행렬 (Optional)

 

코드

import numpy as np

A = np.array([[3, 1, 1], [1, -2, -1], [1, 1, 1]])
P, L, U = scipy.linalg.lu(A)

# P가 항등행렬(Identity matrix)일 경우 Interchange 이력이 존재하지 않음.
print("P:\n", P)
print("L:\n", L)
print("U:\n", U)

>>

P: 
[[1. 0. 0.]
 [0. 1. 0.]
 [0. 0. 1.]]
L: 
[[ 1.          0.          0.        ]
 [ 0.33333333  1.          0.        ]
 [ 0.33333333 -0.28571429  1.        ]]
U: 
[[ 3.          1.          1.        ]
 [ 0.         -2.33333333 -1.33333333]
 [ 0.          0.          0.28571429]]

b = np.array([4, 1, 2])
lu, piv = scipy.linalg.lu_factor(A)
x = scipy.linalg.lu_solve((lu, piv), b)

print(lu, piv)  # lu : LU, piv : P
print("x:", x)

>>

[[ 3.          1.          1.        ]
 [ 0.33333333 -2.33333333 -1.33333333]
 [ 0.33333333 -0.28571429  0.28571429]] [0 1 2]
x: [ 1. -1.  2.]