LU-분해의 개념
LU-분해(LU decomposition)는 행렬 분해 기법 중 하나로, 정사각행렬 \(A\)를 두 행렬 \(L\)과 \(U\)의 곱으로 나타내는 것이다. 여기서 \(L\)은 하삼각(lower triangular) 행렬이고, \(U\)는 상삼각(upper triangular) 행렬이다. 예를 들어, 임의의 \(n\times n\) 행렬 \(A\)에 대하여 \[ A = L\,U \] 와 같이 분해할 수 있다면, 이를 LU-분해라고 부른다.
정의 1. (LU-분해)
정사각행렬 \(A\)에 대하여, 만약 \[ A = L\,U \] 와 같이 두 행렬의 곱으로 나타낼 수 있을 때, 여기서 \(L\)은 대각선 성분이 모두 1인 하삼각행렬(또는 적당한 형태의 하삼각행렬)이고, \(U\)는 상삼각행렬이라면, 이를 LU-분해라고 한다.
LU-분해 과정
행렬 \(A\)를 LU-분해하기 위한 전형적인 방법은, 연립일차방정식 \(A\mathbf{x} = \mathbf{b}\)를 가우스 소거법으로 푸는 과정을 행렬 형태로 정리한 것과 유사하다. 구체적으로는 다음과 같은 단계를 거친다.
- 가우스 소거법: 행렬 \(A\)에 대해 앞에서부터 열(column)에 대한 소거를 진행하여 상삼각형(upper triangular) 형태인 \(U\)를 얻는다. 이때 사용된 연산(각 행에서 다른 행의 배를 빼는 등)을 모두 기록하면, 그 정보를 모아서 하삼각행렬 \(L\)을 구성할 수 있다.
- 부분 피벗팅(Partial Pivoting): 필요에 따라, 대각선 성분이 \(0\)이 되거나 너무 작아 수치적으로 불안정한 경우가 생길 수 있으므로, 행 교환을 실시하게 된다. 이 경우는 엄밀히 말해 \(PA=LU\) 꼴이 되지만, 편의상 \(A\)가 적절히 행을 교환하지 않고도 LU-분해가 가능한 상황을 가정하기도 한다.
즉, LU-분해의 본질은 가우스 소거법의 소거 과정(곱셈 계수)이 하삼각행렬 \(L\)로 정리되고, 소거 후 남은 상삼각행렬이 \(U\)가 된다는 점에 있다.
보기 1. (LU-분해 과정)
3×3 행렬 \[ A = \begin{pmatrix} 2 & 1 & 1\\ 4 & 3 & 1\\ 6 & 1 & 4 \end{pmatrix} \] 를 LU-분해해 보자.
첫 번째 피벗은 1행 1열의 성분 \(2\)이다.
첫 열을 소거하자.
- \(R_2 \,\leftarrow\, R_2 - (4/2) \cdot R_1 = R_2 - 2R_1\)의 결과는 \( (4 - 2\cdot 2,\; 3 - 2\cdot 1,\; 1 - 2\cdot 1) = (0,\;1,\;-1)\).
- \(R_3 \,\leftarrow\, R_3 - (6/2) \cdot R_1 = R_3 - 3R_1\)의 결과는 \( (6 - 3\cdot 2,\; 1 - 3\cdot 1,\; 4 - 3\cdot 1) = (0,\;-2,\;1)\).
이로써 얻는 행렬은 다음과 같다. \[ \begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & -1 \\ 0 & -2 & 1 \end{pmatrix}. \] 동시에 하삼각행렬 \(L\)의 2행 1열 성분과 3행 1열 성분에는 소거할 때 사용한 계수 \(2\)와 \(3\)을 기입한다. 즉, \(L_{21}=2\), \(L_{31}=3\)이 된다. (1열 이외의 성분은 대각성분을 \(1\)로, 그 외의 성분을 \(0\)으로 채운다.)
다음으로 두 번째 열을 소거하자. 두 번째 피벗은 2행 2열의 성분 \(1\)이다. (피벗의 성분이 \(0\)이 아니므로, 추가 행 교환 없이 소거가 가능하다.) 3행의 두 번째 열을 \(0\)으로 만들기 위해 다음과 같은 연산을 수행한다.
- \(R_3 \,\leftarrow\, R_3 - (-2/1)\cdot R_2 = R_3 + 2R_2 \)의 결과는 \((0,\;-2+2\cdot1,\;1+2\cdot(-1)) = (0,\;0,\;-1)\).
따라서 다음과 같은 상삼각행렬을 얻는다. \[ \begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & -1 \\ 0 & 0 & -1 \end{pmatrix} . \] 이때 \(\mathrm{L}\)에는 3행 2열에 해당하는 계수 \(-2/1 = -2\)를 기록하되, 부호에 유의해야 한다. 즉 \(L_{32} = -2.\)이다. 대각선 성분은 \(1\)이다.
소거가 끝난 뒤의 상삼각행렬은 \[ U = \begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & -1 \\ 0 & 0 & -1 \end{pmatrix} \] 이다. 하삼각행렬 \(L\)은 대각선 성분이 1이고, 2행 1열은 \(2\)로, 3행 1열은 \(3\)으로, 3행 2열은 \(2\)로, 그 외는 \(0\)으로 채운다. 즉, \[ L = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & -2 & 1 \end{pmatrix}. \]
이렇게 구한 \(LU\)분해가 바른 결과인지 직접 확인해 보자. \[ L\,U = \begin{pmatrix} 1&0&0\\ 2&1&0\\ 3&-2&1 \end{pmatrix} \begin{pmatrix} 2 & 1 & 1\\ 0 & 1 & -1\\ 0 & 0 & -1 \end{pmatrix} = \begin{pmatrix} 2&1&1\\ 4&3&1\\ 6&1&4 \end{pmatrix}. \] 이로써 곱 \(LU\)가 원래의 행렬 \(A\)와 일치함을 알 수 있다.
LU-분해는 행렬 \(A\)가 어떤 조건을 만족하면 존재하지만, 그 형태가 꼭 유일하게 정해지는 것은 아니다. 예를 들어, 하삼각행렬 \(L\)에서 대각선 성분을 전부 1로 두는 표준 형식을 사용하면 분해가 유일해지는 편이지만, 그렇지 않은 다른 형식을 도입하면 여러 가지 다른 LU-분해를 구성할 수도 있다. 또한, 필요한 경우 행 교환을 도입하여 \(PA=LU\) 꼴로 확장하는 등 다양한 변형이 존재한다.
보기 2. (LU-분해가 유일하지 않음)
임의의 스칼라 \(\alpha \neq 0\)에 대하여, 만약 우리가 \[ A = (L\,\alpha I)\left(\frac{1}{\alpha}I\,U\right) \] 의 꼴로 분해를 바꾸면, 원래의 하삼각행렬 \(L\)을 \(L\alpha I\)로, 원래의 상삼각행렬 \(U\)를 \(\frac{1}{\alpha} U\)로 변형할 수도 있다. 이로 인해 분해 자체가 여러 형태로 표현될 수 있다. 단, 보통은 \(L\)의 대각선 성분을 1로 고정하여 분해가 유일해지도록 정한다.
LU-분해를 사용한 연립일차방정식 풀이
어떤 행렬의 LU-분해를 알고 있다면, 이를 사용하여 연립일차방정식의 해를 구할 수 있다.
보기 3. (LU-분해를 사용하여 연립방정식 풀기)
보기 1에서 살펴본 행렬 \(A\)와 벡터 \[\mathbf{b} = \begin{pmatrix} 7\\ 10\\ 12 \end{pmatrix}\] 를 사용하여 표현한 연립일차방정식 \(A\mathbf{x} = \mathbf{b}\)를 생각하자. 즉 \[ A = \begin{pmatrix} 2 & 1 & 1\\ 4 & 3 & 1\\ 6 & 1 & 4 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 7\\ 10\\ 12 \end{pmatrix} \] 의 해를 구해 보자. 보기 1에서 구한 LU-분해를 사용하자.
연립방정식 \(A\mathbf{x}=\mathbf{b}\)를 \(LU\mathbf{x}=\mathbf{b}\)로 나누고, 먼저 하삼각행렬 \(L\)에 대해 \(L\mathbf{y} = \mathbf{b}\)를 푼다. 즉 \[ \begin{pmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 3 & -2 & 1 \end{pmatrix} \begin{pmatrix} y_1\\ y_2\\ y_3\end{pmatrix} = \begin{pmatrix} 7\\ 10\\ 12\end{pmatrix}. \] 행렬 곱을 전개하면 다음과 같은 식들을 얻는다.
- (1행) \(1\cdot y_1 + 0\cdot y_2 + 0\cdot y_3 = 7\) ⇒ \(y_1 = 7.\)
- (2행) \(2\,y_1 + 1\,y_2 + 0\,y_3 = 10\) ⇒ \(2\cdot7 + y_2=10\) ⇒ \(y_2= -4.\)
- (3행) \(3\,y_1 + (-2)\,y_2 + 1\,y_3 =12\) ⇒ \(3\cdot7 + (-2)(-4) + y_3 =12\) ⇒ \(21 +8 + y_3=12\) ⇒ \(y_3= -17.\)
따라서 \[ \mathbf{y}= \begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix} = \begin{pmatrix} 7\\ -4 \\ -17 \end{pmatrix}. \] 이제 상삼각행렬 \(U\)에 대하여 \(U\mathbf{x}=\mathbf{y}\)를 푼다. \[ \begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & -1 \\ 0 & 0 & -1 \end{pmatrix} \begin{pmatrix} x_1\\ x_2\\ x_3\end{pmatrix} = \begin{pmatrix} 7\\ -4\\ -17\end{pmatrix}. \]
- (3행) \(-1\cdot x_3 = -17\) ⇒ \(x_3=17.\)
- (2행) \(1\cdot x_2 +(-1)\cdot x_3= -4\) ⇒ \(x_2 -17= -4\) ⇒ \(x_2=13.\)
- (1행) \(2\,x_1 + x_2 + x_3=7\) ⇒ \(2\,x_1 +13 +17=7\) ⇒ \(2\,x_1=7-30= -23\) ⇒ \(x_1= -\tfrac{23}{2}= -11.5.\)
결과적으로 \[\mathbf{x}=\left(-\frac{23}{2},\,\, 13,\,\,17\right)\] 이다.
즉, LU-분해는 가우스 소거법 과정을 행렬 형태로 정리한 것이며, 이를 이용하면 연립일차방정식을 효율적으로 풀 수 있다. 다만 분해가 항상 존재하는 것은 아니며, 부분 피벗팅 등을 고려해 \(PA=LU\)로 확장하기도 하고, 특정 표준 형태(예: \(L\)의 대각선 성분을 \(1\)로 정함)를 취하지 않는 이상 분해가 유일하게 정해지지는 않는다.
보기 4. (LU-분해가 불가능한 경우)
다음 2×2 행렬
\[ A = \begin{pmatrix} 0 & 1 \\ 1 & 2 \end{pmatrix} \]
를 생각해 보자. 이 행렬은 계수가 0이 아닌 해를 갖는 연립방정식을 풀 때, LU-분해가 “부분 피벗팅 없이”는 불가능하다는 것을 확인할 수 있다. 구체적으로, 하삼각행렬 \(L\)에 대각선 성분이 전부 1이라고 가정한 표준적 LU-분해를 시도해 보면, 첫 번째 피벗(맨 위 왼쪽 성분)으로 0이 위치하여, 아래 행을 소거할 수 없는 곤란한 상황이 발생한다.
즉, 가우스 소거법을 행 교환 없이 그대로 적용하면, 첫 피벗이 0이므로 상삼각행렬 \(U\)를 구성할 수 없게 된다. 이 말은 \[ A = \begin{pmatrix} 0 & 1 \\ 1 & 2 \end{pmatrix} \;\stackrel{?}{=}\; L\,U \] 꼴로 나타낼 수 없음을 의미한다(단, \(L\)의 대각선 성분을 모두 1로 두는 전형적 방식의 LU-분해를 가정). 그러나 행을 교환하면(부분 피벗팅) \(\;PA=LU\;\) 꼴로 바꿀 수 있게 된다.
결론적으로, 이 행렬 \(A\)는 자체적으로는 전형적 LU-분해가 불가능하지만, 적절한 행 교환을 도입한 \[ P\,A = L\,U \] 형태로는 분해가 가능하다. 실제 큰 차원 행렬에서도, 만약 첫 피벗 위치가 0이거나 수치적으로 너무 작으면, 행 교환을 통해 이를 해결한다(이 과정을 부분 피벗팅이라고 한다). 따라서 전형적 LU-분해가 존재하려면, 각 단계의 대각성 성분이 0이 아니어야 하는 등 일정한 전제조건이 필요하다.
PLU-분해
행렬을 LU-분해하는 과정에서, 만약 선두 피벗 위치에 0이 오거나, 수치적으로 너무 작은 값이 위치하여 가우스 소거법을 직접 적용하기 어려운 경우, 행 교환을 도입하게 된다. 이 행 교환 과정을 ‘부분 피벗팅(partial pivoting)’이라 부르며, 결과적으로 다음 형태의 분해가 가능해진다.
\[ P\,A = L\,U \]
여기서 \(P\)는 행 교환을 나타내는 Permutation 행렬이며, \(A\)는 원래의 정사각행렬이고, \(L\)은 하삼각행렬(보통 대각선 성분을 1로 정규화), \(U\)는 상삼각행렬이다. 이 식을 \(\displaystyle A = P^{-1} L\,U\)라 쓰기도 하며, 이를 PLU-분해(PLU decomposition)라 한다.
PLU-분해를 구하는 방법은 다음과 같다.
- 가우스 소거법 + 부분 피벗팅: 행렬 \(A\)에 대해 앞에서부터 열(column)에 대한 소거를 진행하되, 해당 열의 피벗(대각선 성분) 위치가 0이거나 너무 작으면, 아래 행 중 적절한 행을 골라 위로 올리는 행 교환을 수행한다. 이를 반영하는 행 교환 연산이 바로 ‘Permutation 행렬’ \(P\)를 생성한다.
- 계수 기록: 소거과정에서 사용된 배수(곱셈 계수)를 하삼각행렬 \(L\)의 성분으로 기입한다. 행을 교환할 때마다 \(P\)가 달라진다. 최종적으로 상삼각행렬 \(U\)를 얻는다.
- 행렬 형태: 최종적으로 \(P\,A = L\,U\)가 성립하며, \(P\)는 열벡터가 단위행렬 \(I\)의 행들을 교환한 순열행렬이다. (이때 \(\det(P)=\pm 1\)이다.) 만약 \(P\)가 단위행렬이면, 부분 피벗팅 없이도 LU-분해가 가능했던 경우이다.
이 과정을 통해 행을 적절히 교환해 가우스 소거를 진행할 수 있으므로, (분할이 불가능한 특수 행렬을 제외하고) 대부분의 정사각행렬에 대해 PLU-분해가 존재한다고 볼 수 있다.
보기 5.
다음 3×3 행렬의 PLU-분해를 생각해 보자.
\[ A = \begin{pmatrix} 0 & 2 & 1 \\ 2 & 4 & 3 \\ 1 & 3 & 2 \end{pmatrix}. \]
이 행렬은 \(A\)의 첫 대각선 성분이 0이므로, 직접 LU-분해를 시도하면 곤란하다. 대신, 부분 피벗팅(행 교환)을 도입하여 PLU-분해를 구해 보자.
- 초기 피벗 선택: 맨 위 왼쪽 성분이 \(0\)이므로, 두 번째 행이나 세 번째 행 중 (절댓값이 더 큰) 두 번째 행을 첫 행으로 올리는 편이 수치적으로 안정적이다. (실제로는 그냥 “두 번째 행으로 올리는 행 교환(R1 ↔ R2)”를 수행한다.)
- 행 교환 → 순열행렬 \(P\) 구성: 이 행 교환은 \[ P = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \] 에 해당한다. 그래서 \(PA\)는 \[ \begin{pmatrix} 2 & 4 & 3 \\ 0 & 2 & 1 \\ 1 & 3 & 2 \end{pmatrix}. \]
- 가우스 소거 진행: 이제 \(PA\)에 대해 LU-분해를 시도한다. 첫 열의 피벗은 2가 되어 소거가 가능해진다. 상세 소거 과정에서 사용된 배수를 \(L\)에 기록하고, 최종 상삼각 행렬을 \(U\)로 얻는다.
행 교환, 소거를 마친 뒤 \[ PA = LU \] 라는 꼴이 나오면, 그 \(L\)과 \(U\)를 통해 이 행렬에 대한 PLU-분해를 얻는다. \[ P = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \quad L = \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ \tfrac{1}{2} & \tfrac{1}{2} & 1 \end{pmatrix}, \quad U = \begin{pmatrix} 2 & 4 & 3\\ 0 & 2 & 1\\ 0 & 0 & 0 \end{pmatrix}. \]
