같은 \(A\), 여러 \(b\)
\(AX=B\)를 \(LY=B\), \(UX=Y\)로 분리한다. \(L,U\)는 한 번만 계산한다.
20차시 · 삼각분해
같은 \(A\)에 우변만 바뀐다면?
소거 과정은 한 번만 계산하고, 삼각계 풀이는 우변마다 반복한다.
\(A\)
한 번 분해
→
$$A=LU$$
\(b_1\)\(b_2\)\(b_3\)
예상
\(R_2\leftarrow R_2-2R_1\)의 배수 \(2\)는 어디에 저장할까?
$$L=\begin{bmatrix}1&0\\2&1\end{bmatrix}$$
직접 계산 · 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를 제거한다.
삼각계 풀이
\(Ax=b\)를 두 개의 쉬운 계로 분리
$$b=\begin{bmatrix}3\\7\end{bmatrix},\qquad Ly=b,\quad Ux=y$$
먼저 \(Ly=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$$
아래삼각계는 위에서 아래로 계산한다.
재사용과 한계
분해는 재사용하고, 우변만 바꿔 푼다
새 우변의 계산
각 열 \(b_j\)마다 전진대입과 후진대입만 반복한다.
피벗이 0이거나 매우 작으면 행을 바꾼다. 이때 분해는 \(PA=LU\)이다.
부분 피벗팅은 0으로 나누는 문제를 막고 반올림오차의 증폭을 줄인다.
대칭 양의 정부호 · Cholesky
\(H=LL^\mathsf T\)가 만드는 제곱합
$$H=\begin{bmatrix}4&2\\2&2\end{bmatrix},\qquad L=\begin{bmatrix}2&0\\1&1\end{bmatrix}$$
Cholesky 곱
$$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$$
Cholesky 분해는 대칭 양의 정부호 행렬에 적용한다.
이차함수와 선형계
기울기 0의 조건은 \(Hz=b\)
$$f(x,y)=2x^2+2xy+y^2-6x-4y$$
이 화면의 우변은 \(b=(6,4)^\mathsf T\)이다.
미분 정상조건
$$\nabla f(z)=Hz-b=\begin{bmatrix}4x+2y-6\\2x+2y-4\end{bmatrix}$$
$$\nabla f(z)=0\Longleftrightarrow Hz=b$$
양의 정부호 H이므로 정상점은 유일한 전역 최소점이다.
확인 · 정리
Cholesky 분해와 이차함수에 대한 옳은 설명은?
소거배수 저장
\(A=LU\) 두 삼각계
\(Ly=b,\ Ux=y\) 제곱합과 최솟값
\(H=LL^\mathsf T\)
\(A=LU\) 두 삼각계
\(Ly=b,\ Ux=y\) 제곱합과 최솟값
\(H=LL^\mathsf T\)