같은 \(A\), 여러 \(\mathbf{b}\)
\(AX=B\)를 \(LY=B\), \(UX=Y\)로 분리 · 한 번만 계산하는 \(L,U\)
정의와 조건
LU 분해와 두 번의 대입
\(A\)는 가역 정사각행렬이다. \(A=LU\)에서 \(L\)은 대각성분이 1인 아래삼각행렬, \(U\)는 위삼각행렬이다. \(y=Ux\)라는 중간벡터를 두면 다음 순서로 푼다.
\[Ax=b\iff Ly=b,\quad Ux=y\]
아래삼각식은 첫 식부터 차례로 미지수를 구하는 전진대입, 위삼각식은 마지막 식부터 구하는 후진대입을 사용한다. 우변이 바뀌어도 \(L,U\)는 재사용할 수 있다.
근거와 유도
소거행렬의 역이 L에 기록되는 이유
\[A=\begin{bmatrix}2&1\\4&3\end{bmatrix},\quad E=\begin{bmatrix}1&0\\-2&1\end{bmatrix},\quad EA=\begin{bmatrix}2&1\\0&1\end{bmatrix}=U\]
\[A=E^{-1}U=LU,\qquad L=E^{-1}=\begin{bmatrix}1&0\\2&1\end{bmatrix}\]
소거할 때는 첫 행의 2배를 뺐다. 그 과정을 되돌리는 \(L\)에는 더할 배수 2가 들어간다. 두 부호가 다른 이유를 역연산으로 설명할 수 있다.
직접 계산 · LU
소거 한 번으로 \(L\)과 \(U\)를 만들어 봅시다
$A=\begin{bmatrix}2&1\\4&3\end{bmatrix}$
첫 피벗 \(2\)
$m_{21}=\frac42=2$
$R_2\leftarrow R_2-2R_1$
첫 열 아래의 4를 없앱니다.
삼각 연립방정식 풀이
\(A\mathbf{x}=\mathbf{b}\)를 두 삼각 연립방정식으로 나눠 봅시다
$\mathbf{b}=\begin{bmatrix}3\\7\end{bmatrix},\qquad L\mathbf{y}=\mathbf{b},\quad U\mathbf{x}=\mathbf{y}$
먼저 \(L\mathbf{y}=\mathbf{b}\)
$\begin{bmatrix}1&0\\2&1\end{bmatrix}\begin{bmatrix}y_1\\y_2\end{bmatrix}=\begin{bmatrix}3\\7\end{bmatrix}$
$y_1=3,\qquad 2y_1+y_2=7\Rightarrow y_2=1$
아래삼각 연립방정식은 위에서 아래로 계산합니다.
적용과 논증
행을 바꾸면 우변도 바뀌어야 한다
\[A=\begin{bmatrix}0&1\\2&3\end{bmatrix},\quad b=\binom14,\quad P=\begin{bmatrix}0&1\\1&0\end{bmatrix}\]
- \(PA\)와 \(Pb\)를 구하고 해를 계산하라.
- \(PA\)만 바꾸고 우변을 \(b\)로 둔 풀이의 결과를 계산하여 원식에 대입하라.
풀이와 판단 근거
\[PA=\begin{bmatrix}2&3\\0&1\end{bmatrix},\quad Pb=\binom41,\quad x_2=1,\ x_1=\tfrac12\]
우변을 바꾸지 않으면 \(x_2=4\), \(x_1=-11/2\)가 나온다. 이를 원래 \(A\)에 곱하면 \((4,1)^T\)이므로 \(b\)와 다르다. 행 교환은 방정식 전체를 교환하는 연산이다.
재사용과 한계
한 번 만든 분해의 재사용
새 우변의 계산
각 열 \(\mathbf{b}_j\)에 반복하는 전진대입과 후진대입
행을 바꾸었을 때의 분해와 풀이: \(PA=LU,\quad Ly=Pb,\quad Ux=y\)
부분 피벗팅은 현재 열의 남은 행에서 절댓값이 가장 큰 원소를 피벗으로 고르는 방법입니다. 가역행렬에서는 0인 피벗을 피하고 작은 피벗 때문에 반올림오차가 커지는 일을 줄입니다.
정의와 조건
대칭행렬, 이차형식, 양의 정부호
\(H^T=H\)인 실수 정사각행렬을 대칭행렬이라 한다. \(z^THz\)처럼 변수의 제곱과 두 변수의 곱으로 이루어진 식을 이차형식이라 한다.
\[z^THz>0\quad\text{가 모든 }z\ne0\text{에서 성립하면 }H\succ0\]
이 조건을 양의 정부호라 한다. 대각성분이 양수라는 것만으로는 충분하지 않다. 모든 0이 아닌 벡터에 대해 검사하는 조건임에 주의한다.
정의와 조건
촐레스키 분해와 실제 인수 계산
실수 대칭 양의 정부호 행렬은 \(H=LL^T\)로 쓸 수 있다. \(L\)이 아래삼각행렬이고 대각성분을 양수로 정한 이 분해를 촐레스키 분해라 한다.
\[H=\begin{bmatrix}4&2\\2&2\end{bmatrix},\quad L=\begin{bmatrix}a&0\\b&c\end{bmatrix},\quad LL^T=\begin{bmatrix}a^2&ab\\ab&b^2+c^2\end{bmatrix}\]
성분을 비교하면 \(a^2=4,ab=2,b^2+c^2=2\)이다. \(a,c>0\)에서 \(a=2,b=1,c=1\)을 얻는다. 양의 정부호 여부는 다음 제곱합으로 직접 검산한다.
대칭 양의 정부호 · 촐레스키(Cholesky) 분해
\(H=LL^\mathsf T\)가 만드는 제곱합
$H=\begin{bmatrix}4&2\\2&2\end{bmatrix},\qquad L=\begin{bmatrix}2&0\\1&1\end{bmatrix}$
촐레스키 곱
$LL^\mathsf T=\begin{bmatrix}2&0\\1&1\end{bmatrix}\begin{bmatrix}2&1\\0&1\end{bmatrix}=\begin{bmatrix}4&2\\2&2\end{bmatrix}$
$H=LL^\mathsf T$
촐레스키 분해는 실수 대칭행렬 \(H\)가 모든 \(\mathbf{z}\ne\mathbf{0}\)에서 \(\mathbf{z}^\mathsf TH\mathbf{z}>0\)일 때 적용합니다.
근거와 유도
이차함수의 최소점을 대수로 증명
\(H\succ0\), \(f(z)=\tfrac12z^THz-b^Tz\)라 하자. \(Hh=0\)이면 \(h^THh=0\)이므로 \(h=0\)이다. 따라서 \(H\)는 가역이고 \(Hz_*=b\)에는 유일한 해가 있다.
\[f(z_*+h)-f(z_*)=h^THz_*-b^Th+\tfrac12h^THh=\tfrac12h^THh\]
\(Hz_*=b\)이므로 일차항이 사라진다. \(h\ne0\)이면 남는 값이 양수이므로 \(z_*\)는 유일한 전체 최소점이다. 이 증명에는 미분이 필요하지 않다.
이차함수와 연립방정식
최소점을 중심으로 이차함수 다시 쓰기
$f(x,y)=2x^2+2xy+y^2-6x-4y$
이차항은 \(\tfrac12z^THz\), 일차항은 \(-b^Tz\)로 적는다. \(H=\begin{bmatrix}4&2\\2&2\end{bmatrix},b=(6,4)^T\)이다.
이차항과 일차항의 계수
\(f(z)=\tfrac12z^THz-b^Tz\)
\(Hz_*=b\)를 풀면 이동 후의 일차항이 사라진다.
\(H\)가 양의 정부호이므로 앞의 차이식으로 유일한 최소점을 판정한다.
적용과 논증
양의 대각성분만으로는 충분하지 않다
\[K=\begin{bmatrix}1&2\\2&1\end{bmatrix},\qquad g(z)=\tfrac12z^TKz\]
두 대각성분은 모두 양수이다. \(z=(1,1)\)과 \(z=(1,-1)\)에서 \(g\)를 계산하여 원점이 최소점인지 판정하라. 실수 촐레스키 분해 \(K=LL^T\)가 가능하다고 할 수 있는가?
풀이와 판단 근거
\[g(1,1)=3,\quad g(1,-1)=-1,\quad g(t,-t)=-t^2\]
원점의 값 0보다 작은 값이 있으므로 최소점이 아니며, \(|t|\)가 커지면 아래로 한없이 작아진다. \(LL^T\)라면 \(z^TKz=\|L^Tz\|^2\ge0\)이어야 하는데 음수가 나오므로 실수 인수 \(L\)이 존재할 수 없다.
정리
분해와 최소점 계산에 필요한 조건
- LU: 소거를 기록하고 \(Ly=Pb\), \(Ux=y\)를 순서대로 푼다. 행 교환이 없으면 \(P=I\)이다.
- 촐레스키: 실수 대칭 양의 정부호라는 가정에서 \(H=LL^T\)로 분해한다.
- 이차함수: \(Hz_*=b\)를 푼 뒤 \(f(z_*+h)-f(z_*)>0\)으로 최소점을 증명한다.