[LA] LDU Factorization (or LDU Decomposition)

LU factorization 을 조금 변형한 형태. (실제적으로 많이 사용되지 않는 편이나, 가끔 나오는 경우가 있음.

LDU를 쉽게 설명하려면 다음의 LU factorization의 형태에서 출발하면 됨.

$$A=\begin{matrix} \begin{bmatrix}1 & 0 & 0 & 0 \\* & 1 & 0 & 0 \\* & * & 1 & 0 \\* & * & * & 1\end{bmatrix} & \begin{bmatrix}\blacksquare & * & * & * & * \\0 & \blacksquare & * & * & * \\0 & 0 & 0 & \blacksquare & * \\0 & 0 & 0 & 0 & 0\end{bmatrix} \\ L & U \end{matrix}$$

• $*$은 어떤수여도 상관없음.
• $\blacksquare$는 0아닌 어떤수를 의미. 

LU facotrization에서 Lower triangular matrix는 main diagonal이 1이나 Upper triangular matrix에서의 pivot 위치는 1이 아니다. (다들 알겠지만, Guassian elimination에 의해 얻어진 $U$이므로 $A$의 pivot과 $U$의 pivot의 위치는 같음)

 

LDU는 $U$, Upper triangular matrix (or row echelon form), 의 pivot들을 1로 만들기 위해 diagonal matrix(대각행렬)을 도입한 것임.

D는 $U$의 pivot을 1로 만들어주는 scaling 을 담당하면 이를 간략하게 나타내면 다음과 같음.

$$U=D U^{'}=\begin{bmatrix} d_1 & & & \\ & d_2 & & \\ & & \ddots & \\ & & & d_n\end{bmatrix} \begin{bmatrix} 1 & \frac{u_{1,2}}{d_1}& \cdots & \frac{u_{1,n}}{d_1}\\  & 1 & \cdots & \frac{u_{2,n}}{d_2}\\ & & \ddots & \vdots\\ & & & 1\end{bmatrix}$$

 

다음의 성질을 다시 한번 확인하자.

• LU factorization이 되려면, $L$은 invertible해야하므로 $L$이 구해지면 $L$의  pivot이 모두 0이 아니므로 main diagonal이 모두 1이 될 수 있음.
• LU facotrization에서의 $U$는 $A$와 row equivalent하며 서로의 pivot의 위치가 같으며 이를 1로 변경하는 row operation을 가해줘도 여전히 $A$와 row equivalent임. (Row echelon form에서 Reduced echolon form이 되는 것을 생각해보자.)

 

때문에 LDU factorizaton에서 얻어지는 $L,D,U$는 $A$에 대해 unique하게 얻어짐. (RREF가 unique하게 구해지는 것과 같음).

REF가 unique하지않은 것처럼 LU factorization에서의 $L,U$는 unique하지 않음.

LDU factorization. form wikipedia

 

https://colab.research.google.com/gist/dsaint31x/4e4a77e1a5640b2fbe652f0ada53037e/lu_factorization_plu_factorization.ipynb

https://colab.research.google.com/gist/dsaint31x/4e4a77e1a5640b2fbe652f0ada53037e/lu_factorization_plu_factorization.ipynb