LU factorization 을 조금 변형한 형태. (U가 REF인 LU factorization과 달리, LDU의 경우 RREF임)
[LA] Gauss-Jordan Elimination (including Gauss Elimination) and LU Factorization
System of Linear Equations (연립방정식)의 Solution를 구하는 가장 표준적인 방법.Gauss Elimination을 좀 더 보강한 방법(컴퓨터 없이 연립일차방정식 계산할 경우 가장 일반적으로 사용됨)System의 Augmented Matr
dsaint31.tistory.com
- LU Factorization은 행렬을 두 개의 삼각행렬로 분해하여 계산을 효율적으로 수행하는 방법
- LDU Factorization은 LU Factorization을 기반으로 보다 정규화된 형태를 갖도록 변형한 것
LU Factorization과 LDU 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 Factorization의 유도
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와 LDU Factorization의 기본성질
다음의 성질을 다시 한번 기억할 것.
- 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하지 않음.
같이보면 좋은 자료들
https://colab.research.google.com/gist/dsaint31x/4e4a77e1a5640b2fbe652f0ada53037e/lu_factorization_plu_factorization.ipynb
Run, share, and edit Python notebooks
colab.research.google.com
[LA] 예제: LU Factorization (or LU Decomposition) 와 Gauss Elimination
LU Factorization와 Gauss EliminationLU Factorization은행렬 $A$ 를 다음과 같이 두 행렬 $L$ (Lower Triangular Matrix)와 $U$ (Upper Triangular Matrix)로 분해하는 기법임:$$PA = LU$$여기서 $P$ 는 Permutation Matrix로, 피벗팅(pivoti
dsaint31.tistory.com
'... > Linear Algebra' 카테고리의 다른 글
| [LA] A $\mathbf{x}=\mathbf{b}$ 에서의 4개의 Subspace 와 Complete Solution (0) | 2025.02.06 |
|---|---|
| [LA] 예제: Eigenvalue, Eigenvector 구하기 (기초) (0) | 2025.01.28 |
| [LA] Elementary Row Operation Matrix (0) | 2025.01.27 |
| [LA] 예제: LU Factorization (or LU Decomposition) 와 Gauss Elimination (0) | 2025.01.27 |
| [LA] Gram-Schmidt Process and QR Decomposition (0) | 2025.01.26 |