[LA] 예제: LU Factorization (or LU Decomposition) 와 Gauss Elimination

LU Factorization와 Gauss Elimination

LU Factorization은

행렬 $A$ 를 다음과 같이 두 행렬 $L$ (Lower Triangular Matrix)와 $U$ (Upper Triangular Matrix)로 분해하는 기법임:
$$
PA = LU
$$
여기서 $P$ 는 Permutation Matrix로, 피벗팅(pivoting)을 통해 행 교환 정보를 기록함.

Permutation이 없는 경우는 다음과 같음:

$$A = LU$$

 

사실 Square Full Rank Matrix가 아닌 경우에도 LU Factorization은 적용가능하고, 이 경우, $U$는 REF (Row Echelon Form)가 된다.

 

LU Factorization은 LU Decomposition이라고도 불림.

 

---

핵심 개념: $L$과 Elementary Row Operations

가우스 소거법은 Elementary Row Operations (ERO)를 사용하여 $A$를 REF $U$로 변환함.

 

각 단계에서:

1. ERO는 특정 행렬 $E$로 표현됨..
2. 모든 $E$는 가우스 소거의 각 단계에 해당함.
3. $L^{ −1}$ 는 이러한 ERO 행렬 $E_1, E_2, \dots, E_k$ 의 곱으로 정의됨:
   $$L^{-1} = E_k E_{k-1} \cdots E_1$$
4. 따라서 $L$은 다음과 같이 $L^{-1}$의 역행렬로 정의:
   $$L = E_1^{-1}E_2^{-1}\cdots E_k^{-1}$$

즉, $L$은 가우스 소거 과정에서 사용된 소거 연산의 정보를 기록한 Lower Triangular Matrix 임.

2025.01.27 - [.../Linear Algebra] - [LA] Elementary Row Operation Matrix

[LA] Elementary Row Operation Matrix

---

예제

하나의 예제를 통해 LR Factorization과 Gauss Elimination으로 Linear System의 solution을 구해보자.

문제 정의: Augmented Matrix

$$
\begin{aligned} [A|\mathbf{b}] \\ &=\left[ \begin{array}{ccc|c} 0 & 1 & -1 & 8 \\-3 & -1 & 2 & -11 \\-2 & 1 & 2 & -3\end{array} \right] \end{aligned}$$

 

이 행렬은 다음 Linear System(연립 방정식)에 대응함:
$$
\begin{aligned}
0x_1 + x_2 - x_3 &= 8, \\
-3x_1 - x_2 + 2x_3 &= -11, \\
-2x_1 + x_2 + 2x_3 &= -3.
\end{aligned}
$$

---

Step 1: Permutation (행 교환)

행렬 $[A|\mathbf{b}]$의 첫 번째 열의 피벗 값이 $0$이므로, 행 재배치가 필요함.

 

Permutation Matrix $P$는 행렬 $[A|\mathbf{b}]$를 다음과 같은 순서로 재배치:

1. 첫 번째 행을 세 번째 위치로 이동
2. 두 번째 행을 첫 번째 위치로 이동
3. 세 번째 행을 두 번째 위치로 이동

이를 수행하기 위한 Permutation Matrix $P$는 다음과 같이 정의됨:
$$
P = \begin{bmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0
\end{bmatrix}
$$

$P$를 $[A|\mathbf{b}]$에 곱하면, 다음과 같은 재배치된 행렬 $P[A|\mathbf{b}]$를 얻음:
$$
P[A|\mathbf{b}] = \begin{bmatrix}
-3 & -1 & 2 & -11 \\
-2 & 1 & 2 & -3 \\
0 & 1 & -1 & 8
\end{bmatrix}
$$

Solution $\mathbf{x}$도 다음과 같이 재배치됨.

$$P\mathbf{x}= \begin{bmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0
\end{bmatrix}\begin{bmatrix}
x_1 \\
x_2 \\
x_3
\end{bmatrix}= \begin{bmatrix}
x_2 \\
x_3 \\
x_1\end{bmatrix}$$

---

Step 2: LU Factorization 과정

1. 첫 번째 열을 기준으로 소거

• 소거 연산:
  • $A$ 의 두 번째 행 ($R_2$)에서 첫 번째 행 ($R_1$)의 배를 뺍니다:

$$
m_{21} = \frac{A_{21}}{A_{11}} = \frac{-2}{-3} = 0.6667
$$
$$
R_2 \to R_2 - m_{21} \cdot R_1
$$

• Elementary Row Operation Matrix:

$$
E_1 = \begin{bmatrix}
1 & 0 & 0 \\
-0.6667 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
$$

• $E_1^{-1}$ (역행렬):
  $$
  E_1^{-1} = \begin{bmatrix}
  1 & 0 & 0 \\
  0.6667 & 1 & 0 \\
  0 & 0 & 1
  \end{bmatrix}
  $$
• 소거 후 행렬:
  $$
  E_1 \cdot PA = \begin{bmatrix}
  -3 & -1 & 2  \\
  0 & 1.6667 & 0.6667  \\
  0 & 1 & -1 
  \end{bmatrix}
  $$
• $L$ 갱신
  • 초기값 $L = I$ (단위 행렬)에서 업데이트:

$$
L = E_1^{-1} = \begin{bmatrix}
1 & 0 & 0 \\
0.6667 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
$$

---

2. 두 번째 열을 기준으로 소거

• 세 번째 행 ($R_3$)에서 두 번째 행 ($R_2$)의 배를 뺌:

$$
m_{32} = \frac{A_{32}}{A_{22}} = \frac{1}{1.6667} \approx 0.6
$$
$$
R_3 \to R_3 - m_{32} \cdot R_2
$$

• 소거:

$$R_3 \to R_3 - m_{32} \cdot R_2 $$

• Elementary Row Operation Matrix $E_2$:
  $$
  E_2 = \begin{bmatrix}
  1 & 0 & 0 \\
  0 & 1 & 0 \\
  0 & -0.6 & 1
  \end{bmatrix}
  $$
• $E_2^{-1}$ (역행렬):
  $$
  E_2^{-1} = \begin{bmatrix}
  1 & 0 & 0 \\
  0 & 1 & 0 \\
  0 & 0.6 & 1
  \end{bmatrix}
  $$
• 소거 후 행렬:

$$
E_2 \cdot (E_1 \cdot PA) = \begin{bmatrix}
-3 & -1 & 2 \\
0 & 1.6667 & 0.6667  \\
0 & 0 & -1.4 
\end{bmatrix}
$$

• $L$ 업데이트:
  • 기존 $L$에 $E_2^{-1}$를 곱하여 업데이트:

$$
L = E_2^{-1} \cdot L = \begin{bmatrix}
1 & 0 & 0 \\
0.6667 & 1 & 0 \\
0 & 0.6 & 1
\end{bmatrix}
$$

---

Step 3: 해 구하기

최종적으로 $U$ 와 $L$ 을 사용하여 해를 구함.

 

1. Forward Substitution

$L \mathbf{y} = P \mathbf{b} $를 먼저 풀어냄 (Forward Substitution):

$$
L = \begin{bmatrix}
1 & 0 & 0 \\
0.6667 & 1 & 0 \\
0 & 0.6 & 1
\end{bmatrix}, \quad P \mathbf{b} = \begin{bmatrix}
-11 \\
-3 \\
8
\end{bmatrix}
$$

• Forward Substitution 결과:
  • $y_1 = -11$
  • $y_2 = -3 - (0.6667 \cdot -11) = 4.3333$
  • $y_3 = 8 - (0.6 \cdot 4.3333) = 5.4$

---

2. Backward Substitution

$U \mathbf{x} = \mathbf{y} $를 풀기 (Backward Substitution):

$$
U = \begin{bmatrix}
-3 & -1 & 2 \\
0 & 1.6667 & 0.6667 \\
0 & 0 & -1.4
\end{bmatrix}, \quad \mathbf{y} = \begin{bmatrix}
-11 \\
4.3333 \\
5.4
\end{bmatrix}
$$

• Backward Substitution 결과:
  • $x_3 = \frac{5.4}{-1.4} \approx -3.8571$
  • $x_2 = \frac{4.3333 - (0.6667 \cdot -3.8571)}{1.6667} \approx 4.1429$
  • $x_1 = \frac{-11 - (-1 \cdot 4.1429) - (2 \cdot -3.8571)}{-3} \approx -0.2857$

---

최종 Solution

$$
\mathbf{x} = \begin{bmatrix}
-0.2857 \\
4.1429 \\
-3.8571
\end{bmatrix}
$$

---

같이보면 좋은 자료들

2024.02.17 - [.../Linear Algebra] - [LA] Gauss-Jordan Elimination (including Gauss Elimination) and LU Factorization

[LA] Gauss-Jordan Elimination (including Gauss Elimination)

https://gist.github.com/dsaint31x/13068abe1fb68e6f8c5a0c4ff4f86655

la_lu_decomposition.ipynb

---

2025.01.21 - [.../Linear Algebra] - [Summary] Linear Algebra (작성중)

[Summary] Linear Algebra (작성중)

---