[Linear Algebra] [2-5] Matrix Factorizations

0. Intro

- 행렬분해(Matrix Factorization)이란 어떤 행렬을 두개 이상의 행렬의 곱(product)로 나타내는 것을 의미한다.

- 이번 챕터에서는 LU Factorization(LU 분해)에 대해서 배워볼 것이다. 

 

1.LU 분해(LU Factorization)

- 어느 m x n 행렬 A의 LU분해라는 것은 A = LU 로 분해하는 것을 의미한다.

- L은 m x m 하삼각행렬(lower triangular matrix), L의 주대각성분은 모두 1, invertible함 

- U는 A의 echelon form 즉 A의 REF를 의미함

- L은 invertible 한 행렬이기 때문에 다음과 같은 식을 만족함(해당 식이 만족한다는 걸 잘기억해놓자!)

 

ex) A = LU 꼴은 다음과 같음

 

2. LU Factorization을 이용하여 해(Solution)찾기

- 라고 주어져 있는 행렬방정식(Matrix Equation)이 있다. 

- A라는 행렬을 LU Factorization을 이용하여 A =LU로 분해해보자.

- 그러면 다음과 같은 수식이 만족한다.

 

 

- 즉 구하고자 하는 해를 구하기 위해선

- Ly = b에서 y를 먼저 구하고

- Ux= y에서 x를 구하면 된다. 

 

- 확실하게 이해하기 위해 다음과 같은 예제를 확인해보자

ex)

 

 

 

 

 

- 기존에 알고 있던 RREF를 만들어서 Solution을 만들 때 row operation의 최소 횟수는 62번이다.

- 하지만 LU Factiorization을 이용해서 구한다면 28번의 row operation이 이용된다. 

--> 이렇듯 더욱 효율적이라고 할 수 있다.

 

3. LU Factorization Algorithm

- LU Factorization을 통해 해를 구하는 방법이 되게 효율적이라는 것을 앞의 스텝에서 알게 되었다.

- 이번 스텝에서는 행렬 A를 LU 행렬곱으로 분해하는 알고리즘에 대해서 배워볼 것이다. 

 

- 행렬 U : 행렬 A에 row replacement만 해서 얻은 REF라고 약속하자.

 - 우리는 해당식을 역행렬을 이용해서 L 행렬을 다음과 같이 구할 수 있다.

 

 

- 예제를 같이 풀어보면서 LU Factorization에 대한 내용을 전체적으로 잡아보자!

ex)