[수치해석] LU decomposition/factorization (LU 분해법)

이번 포스팅에서는 선형대수방정식을 풀기 위한 방법 중 하나인

 

LU decomposition/factorization (LU 분해법)에 대해 알아보겠습니다.

(출처: Chapra의 응용수치해석 3rd edition, Steven C. Chapra 저)

 LU decomposition/factorization (LU 분해법)이란?

앞에서 살짝 말씀드렸듯이 LU 분해법 또한

 

선형대수방정식의 해를 구하기 위한 방법 중 하나입니다.

 

이전 포스팅에서 선형대수방정식을 풀기 위한 다른 방법인 Gauss elimination을

 

알아보았는데요.

 

우선 선형대수방정식의 일반적인 형태는 아래와 같습니다.

 

$$[A]\left\{x\right\}=\left\{b\right\} \tag{1}$$

 

Gauss elimination은 분명 시스템의 해를 구하는데에 좋은 방법이긴 하지만,

 

동일한 시스템 $[A]$에 대하여 우변의 벡터 ${b}$가 다른 경우에 대해 풀 때엔

 

비효율적입니다.

 

바뀔 때 마다 전진소거와 후진대입을 반복하여야 하기 때문입니다.

 

전진소거 자체가 많은 계산을 필요로 하는데, 시스템이 크면 더 문제가 되기 때문에

 

이런 경우 LU 분해법을 사용하면 효율적으로 해를 구할 수 있습니다.

 

 LU decomposition/factorization 하는 방법

LU 분해법을 하는 방법에 대해 알아보죠.

 

다행히 우리는 이미 그 방법을 알고 있습니다.

 

바로 Gauss elimination 자체를 LU 분해법으로 표현가능하기 때문이죠.

 

식 (1)은 아래와 같이 표현 가능합니다.

 

$$[A]\left\{x\right\}-\left\{b\right\}=0 \tag{2}$$

 

식 (2)를 상삼각행렬의 형태 시스템으로 표시할 수 있다면 아래와 같이 표현할 수 있습니다.

 

$$\begin{bmatrix}u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \end{bmatrix} \left\{\begin{array}{c}x_{1}\\ x_{2} \\x_{3}\end{array}\right\} = \left\{\begin{array}{c}d_{1}\\d_{2} \\d_{3}\end{array}\right\} \tag{3}$$

 

즉, 아래의 형태로 표현할 수 있습니다.

 

$$[U]\left\{x\right\}-\left\{d\right\}=0 \tag{4}$$

 

이번엔 대각요소가 모두 1인 하삼각행렬을 아래와 같이 나타내어 봅시다.

 

$$[L] = \begin{bmatrix}1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{bmatrix} \tag{5}$$

 

식 (5)를 식 (4)의 앞에 곱했을 때 식 (2)가 된다고 가정하면

 

$$[L]\left\{[U]\left\{x\right\}-\left\{d\right\}\right\} = [A]\left\{x\right\}-\left\{b\right\}$$

 

즉, 아래와 같은 성질을 유도할 수 있습니다.

 

$$[L][U] = [A]$$

$$[L]\left\{d\right\}=\left\{b\right\}$$

 

그런데 사실 행렬 $[U]$는 Gauss elimination에서 전진소거로 구할 수 있고

 

$[L]$ 또한 그 과정에서 계산되기 때문에

 

우리는 Gauss elimination과 LU decomposition을 따로 생각할 필요가 없습니다.

 

$[L]$을 구하기 위해 Gauss elimination을 다시 살펴보죠.

 

$$\begin{bmatrix}a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} \left\{\begin{array}{c}x_{1}\\ x_{2} \\x_{3}\end{array}\right\} = \left\{\begin{array}{c}b_{1}\\b_{2} \\b_{3}\end{array}\right\} \tag{4}$$

 

Gauss elimination을 위해선 식 (4)에서 첫번째 행에 아래 인자를 각각 곱해서

 

두번째 행과 세번째 행의 $a_{21}$, $a_{31}$을 각각 소거하여야 합니다.

 

$$l_{21}=\frac{a_{21}}{a_{11}}$$

$$l_{31}=\frac{a_{31}}{a_{11}}$$

 

그리고 $a_{21}$이 소거된 두번째 행에 아래 인자를 곱하여 세번째 행의 $a'_{32}$를 소거하여야 합니다.

 

$$l_{32}=\frac{a'_{32}}{a'_{22}}$$

 

Gauss elimination에 대한 자세한 내용은 아래 포스트를 참고하세요.

[수치해석] Gaussian elimination(가우스 소거법)

소거를 마치면 행렬 $[A]$는 아래와 같이 표현되며,

 

$$\begin{bmatrix}a_{11} & a_{12} & a_{13} \\ l_{21} & a'_{22} & a'_{23} \\ l_{31} & l_{32} & a''_{33} \end{bmatrix}$$

 

아래와 같은 관계를 만족합니다.

 

$$[L][U]=[A]$$

 

이 때,

 

$$[L] = \begin{bmatrix}a_{11} & a_{12} & a_{13} \\ 0 & a'_{22} & a'_{23} \\ 0 & 0 & a''_{33} \end{bmatrix}$$

$$[U] = \begin{bmatrix}1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{bmatrix}$$

 

입니다.

 

 

여기까지 LU 분해법에 대해 알아보았습니다.