LU 분해 (LU decomposition)
[References]
1. 수치선형대수(Numerical Linear Algebra)
2. LU 분해 (LU decomposition)
http://matrix.skku.ac.kr/sglee/03-Note/LU-Decom.htm
[강의] https://youtu.be/lKJPnLCiAVU
LU 분해 (LU decomposition)
정리. 행렬 $A\in\mathbb{R}^{n\times n}$의 모든 선도 주축 소행렬식(leading principal minors)이 $0$이 아니라고 하자.
그러면 $A$는 유일하게 LU 분해된다. 즉 $A=LU$.
여기서 $L\in\mathbb{R}^{n\times n}$은 단위 하삼각행렬(unit lower-triangular matrix, 대각원소가 모두 1인 하삼각행렬)이고
$U\in\mathbb{R}^{n\times n}$은 상삼각행렬(upper-triangular matrix)이다.
다음과 같이 행렬 $A$가 있다고 하자. 아래 행렬은 가역(nonsingular)이다.
그러나 가역성은 모든 선도 주축 소행렬식이 $0$이 아님을 의미하지는 않는다.
따라서 LU 분해가 끝까지 진행되는지는 보장할 수 없다. 실제로 LU 분해를 진행할 때는 적절한
행(또는 열)의 교환이 수반된다. 아래 LU 분해 명령어는 이에 따른 치환행렬 $P$도 같이 제공한다.
이제 선형연립방정식 $A{\bf x}={\bf b}$를 생각해보자.
$A$의 LU 분해 ($A=PLU$) 를 알고 있다면 선형연립방정식 $A{\bf x}={\bf b}$은 다음과 같이 계산할 수 있다.
$A{\bf x}={\bf b} \quad \Leftrightarrow \quad PLU{\bf x}={\bf b} \quad \Leftrightarrow \quad LU {\bf x} = P^T{\bf b} \quad$
따라서 다음과 같이 계수행렬이 삼각행렬인 두 개의 선형연립방정식의 해를 이용하여 원 선형연립방정식 $A{\bf x}={\bf b}$의 계산할 수 있다.
$L{\bf y}=P^T{\bf b}$ 이때 사용하는 방법을 전진대입법(Forward Substitution)이라 한다.
$U{\bf x}=y$ 이때 사용하는 방법을 후진대입법(Back Substitution)이라 한다.
아래와 같이 LU 분해를 이용한 것과 실제 명령어를 사용하여 계산한 것이 일치함을 알 수 있다.
위와 같은 방법으로 선형연립방정식을 계산하는 것을 부분 피봇팅에 의한 가우스 소거법(Gaussian Elimination with partial pivoting) 이라 한다.
이 방법은 수치적으로 안정적이며 계산량이 적다. 그래서 small/medium scale의 (계수행렬의) 특별한 구조가 없는 선형연립방정식을 푸는 일반적인 방법이다.
또한 계수행렬 $A$는 일정한데 상수항 벡터 $b$만 바뀌는 선형연립방정식을 계산할 경우 $A$에 대하여 한번 LU 분해를 해놓으면 계속 사용할 수 있으므로 편리하다.
(아래 SageMathCell에 실습해보세요)
Copyright @ 2017 SKKU Matrix Lab. All rights reserved.
Made by Manager: Prof. Sang-Gu Lee and Dr. Jae Hwa Lee
*This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2017R1D1A1B03035865).