LU 분해

3. 존재성과 유일성

일반적인 정사각행렬 '''A'''의 LU 분해는 항상 가능한 것은 아니다. 예를 들어, 행렬 곱셈의 정의에 따라 ''a''₁₁ = ''l''₁₁''u''₁₁이 성립하는데, 만약 ''a''₁₁ = 0이라면 ''l''₁₁ 또는 ''u''₁₁ 중 적어도 하나는 0이어야 한다. 이는 하삼각행렬 '''L''' 또는 상삼각행렬 '''U''' 중 적어도 하나가 특이 행렬(비가역행렬)임을 의미하며, 만약 '''A'''가 가역행렬이라면 이는 불가능하다. 이런 경우 '''A'''는 바로 LU 분해될 수 없다. 이 문제를 해결하기 위해 '''A'''의 행 순서를 바꾸어 첫 번째 성분 ''a''₁₁이 0이 아니도록 만들어야 한다.

이처럼 행 교환이 필요한 경우, 치환행렬 '''P'''를 도입하여 '''PA''' = '''LU''' 형태로 분해하며, 이를 LUP 분해라고 한다. 모든 정사각행렬 '''A'''는 LUP 분해가 가능하다.^[9][12][1] 산술적인 결과도 잘 부합한다.^[10]

만약 '''A'''가 가역행렬이고 모든 선도 주 소행렬식(leading principal minor)이 0이 아니라면, 치환행렬 '''P''' 없이 바로 LU 분해가 가능하다.^[13][2] 역으로, '''A'''가 가역 행렬일 때 LU 분해가 가능하려면 모든 선도 주 소행렬식이 0이 아니어야 한다.^[2] 예를 들어, 첫 행이 [0 1], 둘째 행이 [1 0]인 2x2 행렬은 가역행렬이지만 첫 번째 선도 주 소행렬식이 0이므로 LU 분해가 불가능하다. 만약 '''A'''가 랭크 ''k''인 특이 행렬(비가역 행렬)이라면, 처음 ''k''개의 선도 주 소행렬식이 0이 아닌 경우에 한해 LU 분해가 가능하다. 그러나 그 역은 성립하지 않는다.^[14]

LU 분해는 LDU 분해로 확장될 수 있다. 이는 대각 행렬 '''D'''를 이용하여 '''A''' = '''LDU'''와 같이 분해하는 것이다. 여기서 '''L'''과 '''U'''는 주대각선 성분이 모두 1인 하삼각행렬과 상삼각행렬이다.

분해의 유일성에 관해서는 다음과 같다. 만일 정사각행렬이며 가역행렬인 '''A'''가 LDU 분해될 수 있다면 (즉, '''L'''과 '''U'''의 주대각선 성분이 모두 1인 분해), 그 분해는 유일하다.^[13][2] 따라서 '''L'''이나 '''U''' 중 하나의 주대각선 성분을 모두 1로 제한하면, LU 분해도 유일하게 결정된다.^[2]

일반적으로, 모든 정사각 행렬 ''A''_{''n'' × ''n''}은 다음 세 가지 경우 중 하나에 해당한다:

# 고유한 LU 분해를 가짐 (위에서 언급한 조건 만족 시).

# 처음 (''n''−1)개의 열 중 어느 하나라도 선형 종속인 경우, 무한히 많은 LU 분해를 가짐.

# 처음 (''n''−1)개의 열이 선형 독립이지만, 최소한 하나의 선도 주 소행렬식이 0인 경우, LU 분해가 존재하지 않음.

세 번째 경우, 0인 선도 주 소행렬식을 피하기 위해 대각선 요소 ''a''_''jj''를 ''a''_''jj'' ± ε (아주 작은 값 ε)으로 변경하여 LU 분해를 근사적으로 구할 수 있다.^[3]

4. 예시

다음과 같은 2x2 행렬을 LU 분해해 보자.



이 행렬 A를 하삼각행렬 L과 상삼각행렬 U의 곱으로 나타내야 한다.



행렬 곱셈을 수행하면 다음과 같은 연립방정식을 얻는다.



이 방정식 시스템은 미지수가 6개(l11, l21, l22, u11, u12, u22)인데 방정식은 4개뿐이므로 해가 유일하게 결정되지 않는 부정 방정식이다. 고유한 LU 분해를 찾기 위해서는 L 또는 U 행렬에 제약을 가해야 한다. 일반적으로 하삼각행렬 L의 주대각선 성분을 모두 1로 설정하는 방법을 사용한다 (드울리틀 분해). 즉, $\backslash ell\_\{11\}\; =\; 1,\; \backslash ell\_\{22\}\; =\; 1$로 둔다.



다시 행렬 곱셈을 하여 방정식을 세우면 다음과 같다.



위 방정식들을 차례로 풀면 다음과 같은 결과를 얻는다.

• $u\_\{11\}\; =\; 4$
• $u\_\{12\}\; =\; 3$
• $\backslash ell\_\{21\}\; \backslash cdot\; 4\; =\; 6\; \backslash implies\; \backslash ell\_\{21\}\; =\; 6/4\; =\; 1.5$
• $1.5\; \backslash cdot\; 3\; +\; u\_\{22\}\; =\; 3\; \backslash implies\; 4.5\; +\; u\_\{22\}\; =\; 3\; \backslash implies\; u\_\{22\}\; =\; 3\; -\; 4.5\; =\; -1.5$

• 2행 연산: $R\_2\; \backslash leftarrow\; R\_2\; -\; 2\; R\_1$. 승수 2를 $L\_\{21\}$에 기록한다.
• 3행 연산: $R\_3\; \backslash leftarrow\; R\_3\; -\; (-1)\; R\_1$. 승수 -1을 $L\_\{31\}$에 기록한다.

• 3행 연산: $R\_3\; \backslash leftarrow\; R\_3\; -\; (-1)\; R\_2$. 승수 -1을 $L\_\{32\}$에 기록한다.

5. LU 분해 알고리즘

다음 알고리즘은 기본적으로 가우스 소거법의 변형된 형태이다. 이 알고리즘을 사용하여 LU 분해를 계산하는 데에는 하위 차수 항을 무시하고 $\backslash tfrac\{2\}\{3\}\; n^3$ 부동 소수점 연산이 필요하다. 부분 피벗팅(Pivot element)은 2차 항만 추가한다.

행렬 ''A''가 주어졌을 때, 가우스 소거법을 통해 상삼각 행렬 ''U''로 변환하는 과정에서 사용된 기본 행 연산 정보를 이용하여 하삼각 행렬 ''L''을 구성할 수 있다. 구체적으로, ''k''번째 열의 주대각선 아래 원소들을 제거하기 위해 ''i''번째 행($i\; >\; k$)에서 ''k''번째 행의 $\backslash ell\_\{i,k\}$ 배수를 빼는 연산을 수행했다고 하면, ''L'' 행렬의 (''i'', ''k'') 위치에 $\backslash ell\_\{i,k\}$ 값을 저장한다 (두리틀 방식 기준, ''L''의 대각 원소는 1).

수학적으로 이 과정은 일련의 하삼각 행렬 $L\_n$을 곱하는 것으로 표현할 수 있다.

:$A^\{(n)\}\; :=\; L^\{-1\}\_n\; A^\{(n-1)\}$

여기서 $A^\{(0)\}\; =\; A$이고, $L\_n^\{-1\}$은 ''n''번째 단계의 소거 연산을 나타내는 행렬이다. 최종적으로 상삼각 행렬 $U\; =\; A^\{(N-1)\}$를 얻으며, 하삼각 행렬 ''L''은 다음과 같이 정의된다.

:$L\; =\; L\_1\; \backslash dotsm\; L\_\{N-1\}$

여기서 $L\_n\; =\; (L\_n^\{-1\})^\{-1\}$이며, 다음과 같은 형태를 가진다.

:$L\_n\; =$

\begin{pmatrix}

1 & & & & & \\

& \ddots & & & & \\

& & 1 & & & \\

& & \ell_{n+1,n} & & & \\

& & \vdots & & \ddots & \\

& & \ell_{N,n} & & & 1

\end{pmatrix}



이 과정을 통해 $A\; =\; LU$ 분해가 완성된다.

이 알고리즘이 성공적으로 수행되려면 각 단계에서 주대각선 원소(피벗)가 0이 아니어야 한다. 만약 0인 피벗을 만나면, 해당 행을 아래 행 중 피벗 위치에 0이 아닌 원소를 가진 행과 교환하는 피벗팅이 필요하다. 행 교환을 포함하는 경우, 분해는 치환 행렬 ''P''를 사용하여 $PA\; =\; LU$ 형태(LUP 분해)가 된다. 모든 정사각 행렬은 LUP 형태로 분해될 수 있으며, 이 방식은 수치적으로 안정적이다.^[1]

LU 분해를 구하는 구체적인 방법에는 '''두리틀 방법'''과 '''크라우트 방법'''이 있다. 이들은 ''L'' 또는 ''U'' 행렬의 대각 성분에 제약을 가하여 유일한 해를 구한다.

• '''두리틀 방법''' (Doolittle method): 행렬 ''L''의 대각 성분을 모두 1로 놓는다 ($\backslash ell\_\{ii\}\; =\; 1$). 가우스 소거 과정을 통해 자연스럽게 얻어지는 형태이다. 계산 순서는 보통 ''U''의 행과 ''L''의 열을 번갈아 가며 구한다.
• '''크라우트 방법''' (Crout method): 행렬 ''U''의 대각 성분을 모두 1로 놓는다 ($u\_\{ii\}\; =\; 1$). 계산 순서는 보통 ''L''의 열과 ''U''의 행을 번갈아 가며 구한다. 행렬 ''A''의 전치($A^\backslash textsf\{T\}$)에 대해 두리틀 분해($A^\backslash textsf\{T\}\; =\; L\_0\; U\_0$)를 구한 뒤, $L\; =\; U\_0^\backslash textsf\{T\}$와 $U\; =\; L\_0^\backslash textsf\{T\}$로 설정하여 크라우트 분해를 얻을 수도 있다.

6. 응용

LU 분해는 행렬을 아래 삼각행렬(L)과 위 삼각행렬(U)의 곱으로 나타내는 방법으로, 다양한 수학 및 공학 문제 해결에 효과적으로 활용된다. 주요 응용 분야는 다음과 같다.

• '''선형 연립방정식 풀이''': 복잡한 선형 연립 방정식 시스템 $A\backslash mathbf\{x\}\; =\; \backslash mathbf\{b\}$를 효율적으로 풀 수 있다. 특히 계수 행렬 $A$는 동일하고 우변 벡터 $\backslash mathbf\{b\}$만 달라지는 여러 방정식을 반복해서 풀어야 할 때 계산 효율성이 매우 높다. LU 분해를 통해 가우스 소거법 과정을 저장해두고, 전진 대입과 후진 대입만으로 해를 빠르게 구할 수 있다.
• '''역행렬 계산''': 행렬의 역행렬을 구하는 데 사용될 수 있다. $A\backslash mathbf\{x\}\; =\; \backslash mathbf\{e\}\_i$ 형태의 연립방정식을 각 단위 행렬의 열벡터 $\backslash mathbf\{e\}\_i$에 대해 풀어 역행렬의 각 열을 구할 수 있으며, $A^\{-1\}\; =\; U^\{-1\}L^\{-1\}$ 공식을 이용할 수도 있다.
• '''행렬식 계산''': 삼각행렬의 행렬식은 주대각선 성분들의 곱으로 간단히 계산된다는 성질을 이용한다. $A\; =\; LU$ 또는 $PA\; =\; LU$ 형태로 분해하면, $\backslash det(A)\; =\; \backslash det(L)\backslash det(U)$ 또는 $\backslash det(A)\; =\; (-1)^S\; \backslash det(L)\backslash det(U)$ 와 같이 행렬식을 쉽게 계산할 수 있다. 여기서 $S$는 행 교환 횟수이다.

6. 1. 선형 연립방정식 풀이

6. 2. 역행렬 계산

6. 3. 행렬식 계산

7. 변형

LU 분해는 주어진 행렬을 하삼각 행렬과 상삼각 행렬의 곱으로 나타내는 기본적인 방법 외에 여러 변형된 형태를 가진다.

=== 부분 피벗팅을 사용한 LU 분해 (LUP 분해) ===

행렬 분해 과정에서 특정 원소가 0이 되어 분해가 불가능해지는 문제를 해결하기 위해 행의 순서를 바꾸는 방법을 사용한다. 이를 부분 피벗팅(partial pivoting)이라 하며, 이 방식을 적용한 LU 분해를 '''LUP 분해'''라고 부른다. LUP 분해는 다음과 같은 형태로 표현된다.

:$PA\; =\; LU$

여기서 ''L''은 하삼각 행렬, ''U''는 상삼각 행렬이며, ''P''는 행의 순서를 바꾸는 치환 행렬(permutation matrix)이다. 모든 정사각 행렬은 LUP 분해가 가능하며,^[1] 이 방식은 수치적으로 안정적이어서 실제 계산에서 널리 사용된다.

=== 전체 피벗팅을 사용한 LU 분해 ===

부분 피벗팅이 행의 순서만 바꾸는 것과 달리, 전체 피벗팅(full pivoting)은 행과 열의 순서를 모두 바꾼다. 이 분해는 다음과 같은 형태를 가진다.

:$PAQ\; =\; LU$

여기서 ''L'', ''U'', ''P''는 LUP 분해와 동일하게 정의되며, ''Q''는 열의 순서를 바꾸는 치환 행렬이다.

=== LDU 분해 ===

'''LDU 분해'''는 행렬 ''A''를 하삼각 행렬 ''L'', 대각 행렬(diagonal matrix) ''D'', 상삼각 행렬 ''U''의 곱으로 나타내는 방식이다.

:$A\; =\; LDU$

이때 ''L''과 ''U''는 특별히 대각 성분이 모두 1인 단위삼각 행렬(unit triangular matrix)이다.

=== 직사각 행렬로의 일반화 ===

LU 분해 및 그 변형들은 정사각 행렬뿐만 아니라 직사각 행렬에 대해서도 일반화될 수 있다. 이 경우, 행렬 ''A''를 ''m'' × ''n'' 행렬이라고 하면, LDU 분해에서 ''L''과 ''D''는 ''m'' × ''m'' 정사각 행렬이 되고, ''U''는 ''A''와 동일한 ''m'' × ''n'' 차원을 가진다. 이때 '상삼각 행렬' ''U''는 주 대각선 아래의 모든 성분이 0인 행렬, 즉 행 사다리꼴 형태를 의미하는 것으로 해석된다.

=== 분해의 존재성과 유일성 ===

모든 정사각 행렬 ''A''는 LUP 분해 (또는 PLU 분해)가 항상 존재한다.^[1] 그러나 ''LU'' 분해 또는 ''LDU'' 분해는 특정 조건을 만족해야 존재한다. 만약 ''A''가 가역 행렬(invertible matrix)이라면, 모든 선행 주 소행렬식(leading principal minor)이 0이 아닐 경우에만 ''LU'' 분해 (또는 ''LDU'' 분해)가 존재한다.^[2] 예를 들어, 와 같은 행렬은 가역이지만 선행 주 소행렬식 $a\_\{11\}=0$이므로 ''LU'' 또는 ''LDU'' 분해가 존재하지 않는다. 만약 ''A''가 특이 행렬(singular matrix)이고 랭크(rank)가 ''k''라면, 처음 ''k''개의 선행 주 소행렬식이 0이 아닐 경우 ''LU'' 분해가 존재할 수 있지만, 그 역은 성립하지 않는다.

만약 정사각 가역 행렬이 LDU 분해(''L''과 ''U''의 대각 성분이 모두 1)를 가진다면, 그 분해는 유일하다.^[2] 이 경우, ''L'' 또는 ''U'' 중 하나의 대각 성분이 모두 1이라는 조건을 추가하면 ''LU'' 분해도 유일하게 결정된다.

일반적으로 정사각 행렬 $A\_\{n\; \backslash times\; n\}$의 LU 분해는 다음 세 가지 경우 중 하나에 해당한다.

# 유일한 LU 분해가 존재한다.

# 처음 (''n''−1)개 열 중 어느 하나라도 선형 종속인 경우, 무한히 많은 LU 분해가 존재한다.

# 처음 (''n''−1)개 열이 선형 독립이지만 최소한 하나의 선행 주 소행렬식이 0인 경우, LU 분해가 존재하지 않는다.

세 번째 경우처럼 LU 분해가 존재하지 않을 때, 대각 성분 $a\_\{jj\}$에 아주 작은 값 $\backslash varepsilon$를 더하거나 빼서 ($a\_\{jj\}\; \backslash pm\; \backslash varepsilon$) 0인 선행 주 소행렬식을 피함으로써 LU 분해를 근사적으로 구할 수 있다.^[3]

8. 관련 자료

• 매스월드

참조

_[1] harvp
_[2] harvp
_[3] 학술지 Examining Possible LU Decomposition 2021
_[4] 학술지 Randomized LU Decomposition 2016
_[5] 서적 コンピュータによる流体力学 シュプリンガー・フェアラーク東京
_[6] 문서
_[7] 문서
_[8] 저널 On matrix factorization and efficient least squares solution
_[9] harvtxt
_[10] harvtxt
_[11] harvtxt
_[12] harvtxt
_[13] harvtxt
_[14] harvtxt