정의 2.3.1.
행렬 \(A\)의 LU분해란, 분해
\begin{equation*}
A=LU
\end{equation*}
로서 \(L\)은 대각성분이 1인 아랫삼각행렬이고 \(U\)는 윗삼각행렬인 것을 뜻한다.
Section 2.3 LU분해
Subsection 2.3.1 \(EA=U\)에서 \(A=LU\)로
절 2.1에서 연립일차방정식
\begin{equation*}
A \boldsymbol x = \boldsymbol b
\end{equation*}
의 해를 구하기 위해 소거법으로
\begin{equation}
EA=U\tag{2.3.1}
\end{equation}
을 구해 (2.1.13)로 환원하였다.
\begin{equation}
A=LU\tag{2.3.2}
\end{equation}
가 된다. 이는 LU분해이다.
1
중요한 분해.
LU분해의 장점을 살펴보기 위해 \(3 \times 3\)행렬 \(A\)의 소거 결과 \(EA=U\)를 생각해보자. 적당한 행렬
\begin{equation*}
E_1=\begin{bmatrix}1\amp0\amp0\\a\amp1\amp0\\0\amp0\amp1\end{bmatrix},
E_2=\begin{bmatrix}1\amp0\amp0\\0\amp1\amp0\\b\amp0\amp1\end{bmatrix},
E_3=\begin{bmatrix}1\amp0\amp0\\0\amp1\amp0\\0\amp c\amp1\end{bmatrix}
\end{equation*}
과 윗삼각행렬 \(U\)가 있어
\begin{equation*}
E=E_3E_2E_1=\begin{bmatrix}1\amp0\amp0\\a\amp1\amp0\\b+ac\amp c\amp1\end{bmatrix}
\end{equation*}
일 때
\begin{equation*}
EA=U
\end{equation*}
가 성립한다. 한편 \(L\)은
\begin{equation*}
L=E_1^{-1}E_2^{-1}E_3^{-1}=\begin{bmatrix}1\amp0\amp0\\-a\amp1\amp0\\-b\amp -c\amp1\end{bmatrix}
\end{equation*}
이다. \(E\)와 \(L\)을 비교하면 \(E\)를 구하기 위해서는 곱셈 \(ac\)가 추가로 필요함을 알 수 있다. 이것이 LU분해를 선호하는 이유이다.
2
곱셈에 비하면 부호 차이로 발생하는 비용은 미미하다.
Subsection 2.3.2 LU분해
LU분해도 재귀적으로 접근할 수 있다. \(A\)를 \(n \times n \)행렬이라 하자.
\(n=1\)인 경우 \(A=\begin{bmatrix}a\end{bmatrix}\)이면 \(L=\begin{bmatrix}1\end{bmatrix}\text{,}\) \(U=\begin{bmatrix}a\end{bmatrix}\)로 놓는다.
\(n=2\)인 경우
\begin{equation*}
A = \begin{bmatrix}a \amp * \\ * \amp *\end{bmatrix}
\end{equation*}
일 때
3
*는 불특정 성분을 나타낼 때 즐겨 쓴다.
\begin{equation*}
A-\boldsymbol l \boldsymbol u^T=\begin{bmatrix}0 \amp 0 \\ 0 \amp *\end{bmatrix}
\end{equation*}
인 \(\boldsymbol l, \boldsymbol u \in \mathbf R^2\)를 찾는다. 구석의 \([*]\)는 재귀에 의해 \(n=1\)경우로 환원한다.
\(n=3\)인 경우
\begin{equation*}
A = \begin{bmatrix}a \amp * \amp * \\ * \amp *\amp *\\ * \amp *\amp *\end{bmatrix}
\end{equation*}
일 때
\begin{equation*}
A-\boldsymbol l \boldsymbol u^T=\begin{bmatrix}0 \amp 0 \amp 0\\ 0 \amp *\amp* \\0\amp*\amp*\end{bmatrix}
\end{equation*}
인 \(\boldsymbol l, \boldsymbol u \in \mathbf R^3\)를 찾는다. 구석의 \(\begin{bmatrix}* \amp * \\ * \amp *\end{bmatrix}\)는 재귀에 의해 \(n=2\)경우로 환원한다.
재귀를 마치면
\begin{equation*}
A = \boldsymbol l_1 \boldsymbol u_1^{\operatorname T} + \boldsymbol l_2 \boldsymbol u_2^{\operatorname T} + \cdots +\boldsymbol l_n \boldsymbol u_n^{\operatorname T}
\end{equation*}
혹은
\begin{equation*}
A = \begin{bmatrix}\boldsymbol l_1\amp \cdots \amp \boldsymbol l_n\end{bmatrix}
\begin{bmatrix}\boldsymbol u_1^{\operatorname T} \\ \vdots \\ \boldsymbol u_n^{\operatorname T}\end{bmatrix}
\end{equation*}
를 얻는다. 여기서
\begin{equation*}
L=\begin{bmatrix}\boldsymbol l_1\amp \cdots \amp \boldsymbol l_n\end{bmatrix},\hskip{5pt}
U=\begin{bmatrix}\boldsymbol u_1^{\operatorname T} \\ \vdots \\ \boldsymbol u_n^{\operatorname T}\end{bmatrix}
\end{equation*}
이다.
예시 2.3.2. \(2 \times 2\)행렬의 \(LU\)분해.
\begin{equation*}
\begin{bmatrix}
1 \amp -1 \\ 2 \amp 1
\end{bmatrix}
=
\begin{bmatrix}
1 \\ 2
\end{bmatrix}
\begin{bmatrix}
1 \amp -1
\end{bmatrix}
+
\begin{bmatrix}
0 \\ 1
\end{bmatrix}
\begin{bmatrix}
0 \amp 3
\end{bmatrix}
=
\begin{bmatrix}
1 \amp 0 \\ 2 \amp 1
\end{bmatrix}
\begin{bmatrix}
1 \amp -1 \\ 0 \amp 3
\end{bmatrix}
\end{equation*}
는 \(LU\)분해이다.
예시 2.3.3. \(2 \times 2\)행렬의 \(LU\)분해 - 불가능한 경우.
\begin{equation*}
\begin{bmatrix}
0 \amp 0 \\ 1 \amp 0
\end{bmatrix}
\end{equation*}
은 \(LU\)분해를 갖지 않는다. \(LU\)분해가 불가능한지 어떻게 확인할까?
\begin{equation*}
\begin{bmatrix}
0 \amp 0 \\ 1 \amp 0
\end{bmatrix}
=
\begin{bmatrix}
1 \amp 0
\\
x \amp 1
\end{bmatrix}
\begin{bmatrix}
y \amp z
\\
0 \amp w
\end{bmatrix}
\end{equation*}
를 만족하는 \(x,y,z,w \in \mathbf R\)이 없음을 보이면 충분하다. 우변을 계산하면
\begin{equation*}
\begin{bmatrix}
y \amp z
\\
xy \amp w + xz
\end{bmatrix}
\end{equation*}
인데
\begin{equation*}
\begin{bmatrix}
0 \amp 0 \\ 1 \amp 0
\end{bmatrix}
=
\begin{bmatrix}
y \amp z
\\
xy \amp w + xz
\end{bmatrix}
\end{equation*}
은 성립할 수 없다. (1,1)성분에서 \(y=0\)임을 얻고 이로부터 (2,1)성분에 대하여 \(xy=0\)를 얻기 때문이다.
예시 2.3.4. \(3 \times 3\)행렬의 \(LU\)분해.
\begin{align*}
\begin{bmatrix}
3 \amp 0 \amp 2
\\
-3 \amp 0 \amp -5
\\
6 \amp 0 \amp 1
\end{bmatrix}
=
\amp
\begin{bmatrix}
1 \\ -1 \\ 2
\end{bmatrix}
\begin{bmatrix}
3 \amp 0 \amp 2
\end{bmatrix}
+
\begin{bmatrix}
0 \\ 1 \\ 1
\end{bmatrix}
\begin{bmatrix}
0\amp 0 \amp -3
\end{bmatrix}\\
=
\amp
\begin{bmatrix}
1 \amp 0 \amp 0 \\ -1 \amp 1 \amp 0 \\ 2 \amp 1 \amp 1
\end{bmatrix}
\begin{bmatrix}
3 \amp 0 \amp 2 \\ 0 \amp 0 \amp -3 \\ 0 \amp 0 \amp 0
\end{bmatrix}
\end{align*}
는 \(LU\)분해이다. \(U\) 위치에 정사각행렬을 사용했으나 영인 3행을 생략해
\begin{equation*}
\begin{bmatrix}
3 \amp 0 \amp 2
\\
-3 \amp 0 \amp -5
\\
6 \amp 0 \amp 1
\end{bmatrix}
=
\begin{bmatrix}
1 \amp 0 \\ -1 \amp 1 \\ 2 \amp 1
\end{bmatrix}
\begin{bmatrix}
3 \amp 0 \amp 2 \\ 0 \amp 0 \amp -3
\end{bmatrix}
\end{equation*}
로 분해할 수도 있다.
예제 2.3.5. \(2 \times 2\) 행렬의 LU분해 구하기 연습.
행렬 \(\begin{bmatrix}1\amp 1 \\ 1 \amp 0\end{bmatrix}\)의 LU분해를 구하시오.
예제 2.3.6. \(3\times 3\) 행렬의 LU분해 구하기 연습.
행렬
\begin{equation*}
\begin{bmatrix}
1\amp 1 \amp 0
\\
1 \amp 0 \amp 1
\\
2 \amp 1 \amp 0
\end{bmatrix}
\end{equation*}
의 LU분해를 구하시오.
예제 2.3.7. \(4\times 4\) 행렬의 LU분해 구하기 연습.
행렬
\begin{equation*}
\begin{bmatrix}
1\amp 1 \amp 0 \amp 0
\\
1 \amp 0 \amp 0 \amp 0
\\
0 \amp 0 \amp 2 \amp 3
\\
0 \amp 0 \amp 4 \amp 5
\end{bmatrix}
\end{equation*}
의 LU분해를 구하시오.
단서.
\(2 \times 2\) 행렬의 LU분해를 두 번 하면 충분하다
예제 2.3.8. \(4\times 4\) 행렬의 LU분해 구하기 연습 2.
행렬
\begin{equation*}
\begin{bmatrix}
1\amp 1 \amp 0 \amp 0
\\
0 \amp 1 \amp 1 \amp 0
\\
0 \amp 0 \amp 1 \amp 1
\\
1 \amp 0 \amp 0 \amp 1
\end{bmatrix}
\end{equation*}
의 LU분해를 구하시오.
Subsection 2.3.3 대칭행렬의 LU분해
정의 2.3.9.
\(A=A^{\operatorname T}\)이면 \(A\)를 대칭행렬이라 한다.
대칭행렬 \(S\)의 LU분해
\begin{equation*}
S=LU
\end{equation*}
를 생각하자. 과연 \(U=L^{\operatorname T}\)인가? 꼭 그렇지는 않으나 비슷하게 꼴
\begin{equation*}
S=LDL^{\operatorname T}
\end{equation*}
로 분해할 수 있다. 단, \(D\)는 대각행렬이다.
예를 들어 알아보자. 대칭행렬
\begin{equation*}
S
=\begin{bmatrix}
1 \amp 2 \amp 0 \\ 2 \amp 2 \amp -4 \\ 0 \amp -4 \amp 0
\end{bmatrix}
\end{equation*}
을 생각하자. 소거 중간 단계로
\begin{equation*}
\begin{bmatrix}
1 \amp 2 \amp 0 \\ 2 \amp 2 \amp -4 \\ 0 \amp -4 \amp 0
\end{bmatrix}
=
\begin{bmatrix}
1 \amp 0 \amp 0 \\ 2 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1
\end{bmatrix}
\begin{bmatrix}
1 \amp 2 \amp 0 \\ 0 \amp -2 \amp -4 \\ 0 \amp -4 \amp 0
\end{bmatrix}
\end{equation*}
를 얻는다. L위치의 행렬
\begin{equation*}
L_1=\begin{bmatrix}
1 \amp 0 \amp 0 \\ 2 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1
\end{bmatrix}
\end{equation*}
을 전치하면
\begin{equation*}
L_1^{\operatorname T}=
\begin{bmatrix}
1 \amp 2 \amp 0 \\ 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1
\end{bmatrix}
\end{equation*}
이다. 관찰
\begin{equation*}
\begin{bmatrix} \boldsymbol v_1 \amp \boldsymbol v_2 \amp \boldsymbol v_3 \end{bmatrix}
\begin{bmatrix}
1 \amp 2 \amp 0 \\ 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1
\end{bmatrix}
=
\begin{bmatrix} \boldsymbol v_1 \amp 2 \boldsymbol v_1+\boldsymbol v_2 \amp \boldsymbol v_3 \end{bmatrix}
\end{equation*}
에 기반해(단, \(\boldsymbol v_i\)는 열벡터)
\begin{equation*}
\begin{bmatrix}
1 \amp 2 \amp 0 \\ 2 \amp 2 \amp -4 \\ 0 \amp -4 \amp 0
\end{bmatrix}
=
\begin{bmatrix}
1 \amp 0 \amp 0 \\ 2 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1
\end{bmatrix}
\begin{bmatrix}
1 \amp 0 \amp 0 \\ 0 \amp -2 \amp -4 \\ 0 \amp -4 \amp 0
\end{bmatrix}
\begin{bmatrix}
1 \amp 2 \amp 0 \\ 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1
\end{bmatrix}
\end{equation*}
를 얻는다. 소거를 계속하여
\begin{equation*}
\begin{bmatrix}
1 \amp 2 \amp 0 \\ 2 \amp 2 \amp -4 \\ 0 \amp -4 \amp 0
\end{bmatrix}
=
\begin{bmatrix}
1 \amp 0 \amp 0 \\ 2 \amp 1 \amp 0 \\ 0 \amp 2 \amp 1
\end{bmatrix}
\begin{bmatrix}
1 \amp 0 \amp 0 \\ 0 \amp -2 \amp 0 \\ 0 \amp 0 \amp 8
\end{bmatrix}
\begin{bmatrix}
1 \amp 2 \amp 0 \\ 0 \amp 1 \amp 2 \\ 0 \amp 0 \amp 1
\end{bmatrix}
\end{equation*}
을 얻는다. 즉,
\begin{equation*}
L=
\begin{bmatrix}
1 \amp 0 \amp 0 \\ 2 \amp 1 \amp 0 \\ 0 \amp 2 \amp 1
\end{bmatrix}
,
D=
\begin{bmatrix}
1 \amp 0 \amp 0 \\ 0 \amp -2 \amp 0 \\ 0 \amp 0 \amp 8
\end{bmatrix}
\end{equation*}
로 \(S=LDL^{\operatorname T}\)를 얻었다.
예제 2.3.10. \(3 \times 3\) 대칭 행렬의 분해 연습.
행렬
\begin{equation*}
A=
\begin{bmatrix}
1\amp 1 \amp 0
\\
1 \amp 3 \amp 1
\\
0 \amp 1 \amp 5
\end{bmatrix}
\end{equation*}
의 \(A=LDL^{\operatorname{T}}\)분해를 구하시오.
Subsection 2.3.4 직사각행렬의 LU분해
\(A\)가 정사각행렬이 아니더라도 \(A=LU\)분해를 고려할 수 있다. 분해를 얻기 위해서는 정사각행렬과 마찬가지로 소거법을 적용한다.
행교환이 필요 없다면 소거법은
\begin{equation*}
EA=U
\end{equation*}
로 표현할 수 있다. 단, \(E\)는 대각성분이 1인 아랫삼각행렬이다. \(U\)는 \(A\)와 같은 크기의 행렬로, 문자 \(U\)는 윗삼각행렬의 머릿글자이다. 소거가 완료된 \(U\)의 형태를 조건으로 표현해보자. \(U\)의 \(i\)번째 행벡터 \(\boldsymbol u_i\)의 성분을 나열하여
\begin{equation}
\begin{bmatrix} u_{i1} &u_{i2} & \cdots u_{in} \end{bmatrix}\tag{2.3.3}
\end{equation}
라 하고, 처음으로 0이 아닌 성분이 나타나는 위치를 \(t_i\in\{1,2,\cdots,n\}\)라 하자. 즉, (2.3.3)은
\begin{equation*}
\begin{bmatrix} 0 & \cdots & 0 & t_{it_i} & \cdots u_{in} \end{bmatrix}
\end{equation*}
이고 \(u_{it_i}\not=0\)이다. 만약
\begin{equation}
t_1 \le t_2 \cdots \le t_n\tag{2.3.4}
\end{equation}
연습문제 2.3.5 연습문제
1.
- 0
- 1
- 2
- 4
- 7
행렬 \(\begin{bmatrix}1&0&0\\2&1&0\\0&3&1\end{bmatrix}\) 의 역행렬을 찾아, 모든 성분의 합을 구하시오.
2.
- 0
- 1
- 2
- 4
- 7
행렬 \(A=\begin{bmatrix}1&0&-1\\1&1&-1\\-1&1&3\end{bmatrix}\) 의 LU분해가 \(A=LU\)일 때, \(L\)의 모든 성분의 합을 구하시오.
3.
- 0
- 1
- 2
- 4
- 7
LU분해의 덧셈꼴
\begin{align*}
\begin{bmatrix}1&0&3&0\\0&-1&0&4\\1&0&2&0\\0&-2&0&9\end{bmatrix}
\amp
=
\begin{bmatrix}1&0&0&0\\0&1&0&0\\1&0&1&0\\0&2&0&1\end{bmatrix}
\begin{bmatrix}1&0&3&0\\0&-1&0&4\\0&0&-1&0\\0&0&0&1\end{bmatrix}\\
\amp
=
\boldsymbol l_1 \boldsymbol u_1+\boldsymbol l_2 \boldsymbol u_2+\boldsymbol l_3 \boldsymbol u_3+\boldsymbol l_4 \boldsymbol u_4
\end{align*}
이 주어졌다. \(\boldsymbol l_1 \boldsymbol u_1\)의 성분 중 영이 아닌 것은 몇 개인가?
4.
- 모든 정사각행렬은 LU분해를 가진다.
- LU분해 \(A=LU\)에서 \(L\)은 항상 가역이다.
- LU분해 \(A=LU\)에서 \(A\)의 랭크는 \(U\)의 대각성분으로부터 알 수 있다.
LU분해에 관한 설명으로 틀린 것을 고르시오.
