LU Decomposition

LU 분해는 근본적으로 가우스 소거법의 방법을 차용한다. 가우스 소거법은 행의 조작을 통해, Upper Triangle Matrix 를 만드는 것이 핵심이다.

이 과정에서 우리는 행의 조작을 하는데, 윗삼각행렬을 만들기 위해 상수배와 더하기 빼기를 하는데,

이 과정을 행렬을 곱하는 것으로 대치하는 것이 전부이다. 먼저 가우스 소거법을 대치하는 행렬을 어떻게 만들지 부터 생각해보자.

E 행렬

A; =; 2 - 1 4 12 - 3 1 - 1 1

\\begin{bmatrix} 2 & 1 & 1\\ -1 & 2 & -1\\ 4 & -3 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} ;=; \begin{bmatrix} 6 \\ 0 \\ 2 \end{bmatrix}

1행 * (1/2) + 2행의 결과를 2행에 넣어야 한다. 이 때, A 행렬을 다음과 같이 바라보자.

A; =; 2 - 1 4 12 - 3 1 - 1 1; =; a_{1} \to a_{2} \to a_{3} \to

각각의 벡터는 행을 의미한다. 우리는 1, 3행은 그대로,

2행을 위의 연산을 수행한 뒤 넣어줘야 하므로,

\\begin{bmatrix} 1 & 0 & 0\\ {1\over 2} & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} \overset{\rightarrow}{a_1} \\ \overset{\rightarrow}{a_2} \\ \overset{\rightarrow}{a_3} \end{bmatrix}

다음과 같다. 이 행렬을 다음과 같이 사용하겠다.

E_{1}; =; 1 \frac{1}{2} 0 010001

그렇다면,

\\begin{bmatrix} 1 & 0 & 0\\ {1\over 2} & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 2 & 1 & 1\\ -1 & 2 & -1\\ 4 & -3 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} ;=; \begin{bmatrix} 1 & 0 & 0\\ {1\over 2} & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 6 \\ 0 \\ 2 \end{bmatrix}

E_{1} A x \to; =; E_{1} b \to

이 수행된 결과에 대해 다음 단계를 이와 같이 나타내면,

E_{2}; =; 10 - 2 010001;;;;;; E_{3}; =; 100012001

따라서 가우스 소거법은 다음과 같이 나타낼 수 있다.

E_{3} E_{2} E_{1} A x \to; =; E_{3} E_{2} E_{1} b \to

이 때,

E; =; E_{3} E_{2} E_{1}; =; 100012001 10 - 2 010001 1 \frac{1}{2} 0 010001; =; 1 \frac{1}{2} - 1 012001

결론적으로,

E A x \to; =; E_{3} E_{2} E_{1} A x \to; =; E_{3} E_{2} E_{1} b \to; =; E b \to

여기서 EA의 결과 행렬은 Upper Triangle Matrix 이다.

E A; =; U

자, 이렇게 가우스 소거법이 행렬로 분해가 될 수 있다는 사실 까지 알았다. 그렇다면 항등식으로 부터 A행렬을 L과 U로 분해해보자.

A; =; A

여기서, 양쪽에 위에서 배운 E1, E2, E3 행렬을 곱해보자.

E_{3} E_{2} E_{1} A; =; U

오른쪽 은 세 행렬이 곱해졌을 때 Upper triangle 행렬이 된 것을 의미한다.

이 식은 다음과 같이 요약되고,

E A; =; U

여기서 Lower triangle matrix의 inverse matrix는,

Lower Triangle Matrix 이다.

E^{- 1}; =; 1 - \frac{1}{2} 2 01 - 2 001; =; L

따라서,

E A; =; U; A; =; E^{- 1} U; =; LU

다음과 같이 분해가 완료 되었다.

이런 경우 LU 분해의 결과는,

A; =; L L^{T}

대부분의 다물체 동역학 시스템은 위의 두 가정을 만족한다.

1.;;;; U x \to; =; y \to;

2.;;;; L y \to; =; b \to

두번의 back-subsitution process를 걸치면 원하는 결과가 나온다.