[선형대수학] LU-Decompositions

 

 

linear system(연립방정식)을 풀 때, 가우스 소거법과 가우스-조르당 소거법 2가지 방법을 통해 문제를 풀 수 있었다.

 

[Review]
가우스 소거법: 기본행연산을 통해 행사다리꼴(row echelon form)로 만드는 알고리즘
가우스-조르당 소거법: 기본행연산을 통해 기약행사다리꼴(reduced row echelon form)로 만드는 알고리즘

행사다리꼴: leading 1 아래의 모든 수가 0인  행렬
기약행사다리꼴: leading 1 위 아래 모든 수가 0인 행렬

위의 소거법의 경우 small-scale에서는 괜찮을지 모르나, 실제 large-scale에서 컴퓨터의 연산을 사용해도 roundoff error, memory usage, speed 면에서 효과적이지 못하다.

$n$개의 미지수를 포함하는 $n$개의 방정식을 상삼각행렬과 하삼각행렬로 분해하는 방법을 LU-분해라고 부르고, 많은 컴퓨터 알고리즘이 실제 사용된다.

 

The Method of LU-decomposition

(1) 방정식 $A \mathbf{x} = \mathbf{b}$ 을 아래처럼 재구성한다.
\[ LU \mathbf{x} = \mathbf{b} \]

(2) 아래 식을 만족하는 $n \times 1$ 행렬 $\mathbf{y}$를 정의한다.
\[ U \mathbf{x} = \mathbf{y} \]

(3) $\mathbf{y}$에 대한 방정식 $L \mathbf{y} = \mathbf{b}$를 푼다. 
(4) (3)에서 구한 $\mathbf{y}$를 (2)의 $U \mathbf{x} = \mathbf{y}$에 대입하여 $\mathbf{x}$에 대한 방정식을 푼다.

 

Example 1

$A = \begin{bmatrix} 2 & 6 & 2 \\ -3 & -8 & 0 \\ 4 & 9 & 2 \end{bmatrix}, \mathbf{b} = \begin{bmatrix} 2 \\ 2 \\ 3 \end{bmatrix}$인 방정식 $A \mathbf{x} = \mathbf{b}$를 풀어보자.

 

$A = \begin{bmatrix} 2 & 6 & 2 \\ -3 & -8 & 0 \\ 4 & 9 & 2 \end{bmatrix}$를 LU-분해하면 (방법은 추후 설명)

\[ \begin{bmatrix} 2 & 6 & 2 \\ -3 & -8 & 0 \\ 4 & 9 & 2 \end{bmatrix} = \begin{bmatrix} 2 & 0 & 0 \\ -3 & 1 & 0 \\ 4 & -3 & 7 \end{bmatrix} \begin{bmatrix} 1 & 3 & 1 \\ 0 & 1 & 3 \\ 0 & 0 & 1 \end{bmatrix} \]

\[ A \qquad = \qquad L \qquad U \]

 

먼저 $L \mathbf{y} = \mathbf{b}$를 풀면

\[ \begin{bmatrix} 2 & 0 & 0 \\ -3 & 1 & 0 \\ 4 & -3 & 7 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} =  \begin{bmatrix} 2 \\ 2 \\ 3 \end{bmatrix} \]

forward substitution(전진대입법)을 적용하면

\[ y_1 = 1, \qquad y_2 = 5, \qquad y_3 = 2 \]

를 얻는다. 이렇게 구한 $\mathbf{y}$를 $U \mathbf{x} = \mathbf{y}$에 대입하면

\[ \begin{bmatrix} 1 & 3 & 1 \\ 0 & 1 & 3 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} =  \begin{bmatrix} 1 \\ 5 \\ 2 \end{bmatrix} \]

back substitution(후진대입법)을 적용하면

\[ x_1 = 2, \qquad x_2 = -1, \qquad x_3 = 2 \]

를 얻는다. $\blacksquare$

 

 

Example 1을 통해 LU-분해를 이용하면 선형연립방정식을 두번의 대입만으로 풀 수 있다는 것을 알았다. 이제 직접 LU-분해를 하는 방법을 알아보자.

정사각행렬 $A$가 하삼각행렬 $L$과 상삼각행렬 $U$의 곱인 $A=LU$로 나타낼 때, 이를 LU-decomposition (또는 LU-factorization, LU-분해)이라 한다.

모든 정사각행렬이 LU-분해가 되는 것은 아니다. 그러나, row interchange 없이 가우스 소거법을 통해 행사다리꼴로 만들 수 있다면, LU분해가 가능하다.(유일성은 보장할 수 없다. 추후 설명)

행연산은 기본행렬의 곱셈으로 표현 가능하므로 위 문장을 수식으로 작성하면

\[ E_k \cdots E_2 E_1 A = U \]

각 기본행렬은 invertible 하므로 역행렬을 계산하면

\[ A = E_1^{-1} E_2^{-1} \cdots E_k^{-1} U \]

행 교환 연산을 하지 않았기 때문에, 각 기본행렬 $E_i$는 lower triangular matrix이다.

상/하삼각행렬끼리의 곱셈의 결과는 항상 상/하삼각행렬이다. 따라서  위의 식 $E_1^{-1} E_2^{-1} \cdots E_k^{-1}$ 역시 하삼각행렬이므로 $L$이 된다.

정사각행렬 $A$가 행교환 없이 가우스 소거법을 통해 사다리꼴행렬 $U$가 되었다면, $A$는 LU-분해가 가능하다.

Example 2

Example 1의 $A = \begin{bmatrix} 2 & 6 & 2 \\ -3 & -8 & 0 \\ 4 & 9 & 2 \end{bmatrix}$를 LU-분해하자.

행교환연산을 제외한 행연산을 통해 $U$을 만들고, 각 단계별로 수행된 행연산에 해당하는 기본행렬들의 역행렬들의 곱을 하면 $L$를 구할 수 있다.

\[ L = \begin{bmatrix} 2 & 0 & 0 \\ -3 & 1 & 0 \\ 4 & -3 & 7 \end{bmatrix} \]

(풀이 생략)

$\blacksquare$

 

잘 생각해보면, 실제 사용되는 연산은 2개인데(1. 0이아닌 상수 곱하기, 2. 상수배 행을 더하기)인데 1)의 경우 leading 1을 만들고, 2)의 경우 leading 1의 아래 숫자들을 모두 0으로 만든다.

$L$의 주대각성분은 $U$를 만들기 위해 곱해진 상수의 역수임을 알 수 있다. 그리고 주대각성분 밑에 있는 음수들은 사$U$를 만들 때 0을 만들기 위해 행에 곱셈을 한 상수의 반대부호임을 알 수 있다. 이러한 점을 통해, 기약행사다리꼴로 $U$를 만들면서 동시에 $L$을 구할 수 있다.

 

Example 3

 $A = \begin{bmatrix} 6 & -2 & 0 \\ 9 & -1 & 1 \\ 3 & 7 & 5 \end{bmatrix}$를 LU-분해하자. $A$를 기본행연산을 이용하여 기약행사다리꼴로 만들면 자연스럽게 $U$와 $L$을 구할 수 있다. (당연히 이때 $U$의 주대각성분은 모두 1임이 보장된다)

$A \to U$	$ L$	적용된 기본행연산
\begin{bmatrix} 6 & 2 & 0 \\  9 & -1 & 1 \\ 3 & 7 & 5 \end{bmatrix}	\begin{bmatrix} * & 0 & 0 \\  * & * & 0 \\ * & * & * \end{bmatrix}	-
\begin{bmatrix} 1 & -\cfrac{1}{3} & 0 \\  9 & -1 & 1 \\ 3 & 7 & 5 \end{bmatrix}	\begin{bmatrix} 6 & 0 & 0 \\  * & * & 0 \\ * & * & * \end{bmatrix}	R1 $\leftarrow$ R1 * (1/6)
\begin{bmatrix} 1 & -\cfrac{1}{3} & 0 \\  0 & 2 & 1 \\ 0 & 8 & 5 \end{bmatrix}	\begin{bmatrix} 6 & 0 & 0 \\  9 & * & 0 \\ 3 & * & * \end{bmatrix}	R2 $\leftarrow$ R2 + R1 * (-9) R3 $\leftarrow$ R3 + R1 * (-3)
\begin{bmatrix} 1 & -\cfrac{1}{3} & 0 \\  0 & 1 & \cfrac{1}{2} \\ 0 & 8 & 5 \end{bmatrix}	\begin{bmatrix} 6 & 0 & 0 \\  9 & 2 & 0 \\ 3 & * & * \end{bmatrix}	R2 $\leftarrow$ R2 * (1/2)
\begin{bmatrix} 1 & -\cfrac{1}{3} & 0 \\  0 & 1 & \cfrac{1}{2} \\ 0 & 0 & 1 \end{bmatrix}	\begin{bmatrix} 6 & 0 & 0 \\  9 & 2 & 0 \\ 3 & 8 & * \end{bmatrix}	R3 $\leftarrow$ R3 + R2 * (-8)
\begin{bmatrix} 1 & -\cfrac{1}{3} & 0 \\  0 & 1 & \cfrac{1}{2} \\ 0 & 0 & 1 \end{bmatrix}	\begin{bmatrix} 6 & 0 & 0 \\  9 & 2 & 0 \\ 3 & 8 & 1 \end{bmatrix}	R3 $\leftarrow$ R3 * (1)

$\blacksquare$

 

LU-Decompositions Are Not Unique

이제 LU-분해가 유일한지 확인해보자. 어떤 행렬 $A$가 LU분해하여 아래와 같다고 하자

\[ A = LU = \begin{bmatrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{bmatrix} \begin{bmatrix} 1 & u_{12} & u_{13} \\ 0 & 1 & u_{23} \\ 0 & 0 & 1 \end{bmatrix} \]

 

$L$이 0이 아닌 대각성분을 갖는다면 아래처럼 shift하여 재구성할 수 있다

\[ A = \begin{bmatrix} 1 & 0 & 0 \\ l_{21}/l_{11} & 1 & 0 \\ l_{31}/l_{11} & l_{32}/l_{22} & 1 \end{bmatrix} \begin{bmatrix} l_{11} & 0 & 0 \\ 0 & l_{22} & 0 \\ 0 & 0 & l_{33} \end{bmatrix} \begin{bmatrix} 1 & u_{12} & u_{13} \\ 0 & 1 & u_{23} \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ l_{21}/l_{11} & 1 & 0 \\ l_{31}/l_{11} & l_{32}/l_{22} & 1 \end{bmatrix} \begin{bmatrix} l_{11} & l_{11}u_{12} & l_{11}u_{13} \\ 0 & l_{22} & l_{22}u_{23} \\ 0 & 0 & l_{33} \end{bmatrix} \]

이것은 새로운 LU-분해의 형태이다. 따라서 일반적으로 LU-분해는 유일하지 않다.(다시말해, $L$과 $U$의 주대각성분이 모두 1인 경우에만 유일성이 보장된다.)

 

LDU-Decomposition

위에서 잠시 살펴봤는데, 하삼각행렬의 주대각성분이 1이길 원한다면(당연히 $U$의 주대각성분은 모두 1로 만들 수 있다.) $L$의 주대각성분을 shift 하여 

\[ L = L'D \]

로 재구성 할 수 있다. 이 경우에 $L'$의 주대각성분이 모두 1이므로 유일성이 보장된다.

LDU-Decomposition

정사각행렬 $A$가 행교환연산 없이 기약행사다리꼴(RREF)로 만들 수 있다면, $A$는 주대각성분이 모두 1인 하삼각행렬, 대각행렬, 주대각성분이 모두 1인 상삼각행렬의 곱의 형태인
\[ A = LDU \]
로 나타낼 수 있고, 이런 분해 형태는 유일하다.

 

PLU-Decomposition

실제 많은 컴퓨터 알고리즘은 roundoff error를 줄이기 위해 행교환 연산을 한다. 앞서 보았듯이 행교환 연산을 하게되면 LU-분해 가능성이 보장되지 않는다. 하지만 $A$에 어떤 '전처리'를 하면 LU-분해가 가능하다. 이때 전처리를 하는 행렬 $Q$를 permutation matrix(치환행렬, 순열행렬)라 한다. 

$Q$는 기본행렬의 곱셈으로 행교환과 동일한 행렬을 구성할 수 있으며, 당연히 invertible하다. 따라서 

\[ QA = LU \]

로 분해 가능함이 보장된다.

일반적으로 $P = Q^{-1}$를 곱한 형태인 

\[ A = PLU \]

형태로 작성하며 PLU-분해라고 부른다.

 

 

참고

Howard Anton, Chris Rorres. Elementary Linear Algebra with Supplemental Applications, Eleventh Edition, International Student Version. Wiely.