[알고리즘 구현으로 배우는 선형대수] #13. LU분해

분해해~~~

1. 기본 행렬

• 기본 행렬(E) : 단위 행렬에서 기본 행 연산을 수행한 행렬 
  • 단위행렬에서 n행에 p를 곱해서 j 행에 더하는 등의 연산을 수행한 모든 행렬을 기본 행렬이라고 함 
• 기본 행렬의 역행렬 
  • 대각 행렬일 경우 : 주 대각 원소의 역수를 대각 원소에 대입
  • 대각 행렬이 아닐 경우 : 주 대각 원소가 아닌 값(0이 아님)에 마이너스를 취함 

 

2. LU분해 

개념

• Ax = b 일 때, 
• A = LU 의 곱 형태로 분해하는 것 
  • L : 하삼각행렬, U : 상삼각행렬 

방법

• A를 가우스 행렬 형태인 U로 변환하는 과정에서 L을 구할 수 있음 
• 행렬 A에 기본행렬을 계속 곱해가며 가우스 행렬을 만들어가면서 LU분해 진행 가능 
  • En x En-1 x ...x E2 x E1 x A = U
  • A = (En x En-1 x ...x E2 x E1)의 역행렬 x U
  • L = (En x En-1 x ...x E2 x E1)의 역행렬 

쉽게 하는 방법 

• A를 가우스 행렬로 바꾸는 과정에서, 곱하거나 더한 수를 기억해서 행렬 L에 위치시키는 것 
• 곱했을 경우, 곱한 수의 역수를 더했을 경우 더한 수의 음수를 L에 위치

선형 시스템의 해 

• Ax = b 
• A= LU로 분해 
• LUx = b 
• Ux = y로 치환
• Ly = b 
• y에 대한 방정식을 구함 
• Ux = y 에 구한 y 값을 넣어 x에 대해 풀기 

 

 

3. 파이썬 실습 

#LU 분해 

#1. scipy 

import numpy as np
from scipy.linalg import lu 

A = np.array([~])
P,L,U = lu(A)

#와 끝!