LU 분해 (LU decomposition)


[References]

1. 수치선형대수(Numerical Linear Algebra)

   http://matrix.skku.ac.kr/nla/

18. 현대선형대수학 with Sage (Linear Algebra with Sage), 이상구 with 이재화, 김덕선. ISBN 978-89-6105-568-0, 경문사 (2012, 9. 1.).

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).