N2 · 소거의 재해석: 분해, 피벗, 오차

1. 같은 계수에 여러 수요를 넣는 계산

두 상태 \(x_1,x_2\)를 정한 금액 단위의 기준값 대비 변화로 기록하고 두 균형 제약을

\[ 2x_1+x_2=b_1,\qquad4x_1+3x_2=b_2 \]

로 나타냅시다. 계수는 무차원이고 변화량이므로 \(x_i\)의 음수도 허용합니다. 기본 시나리오는 \(b=(1,1)^T\)입니다. 둘째 식에서 첫째 식의 2배를 빼면 \(x_2=-1\), 다시 첫째에 넣으면 \(x_1=1\)입니다. 이 소거를 매번 반복하는 대신

\[\begin{split} A=\begin{pmatrix}2&1\\4&3\end{pmatrix} =\underbrace{\begin{pmatrix}1&0\\2&1\end{pmatrix}}_L \underbrace{\begin{pmatrix}2&1\\0&1\end{pmatrix}}_U \end{split}\]

로 저장합니다. \(Ly=b\)를 앞에서부터 풀면 \(y_1=b_1\), \(y_2=b_2-2b_1\)이고, \(Ux=y\)를 뒤에서부터 풀면 \(x_2=y_2\), \(x_1=(y_1-x_2)/2\)입니다. \(b=(1,2)^T\)인 새 시나리오에서는 같은 \(L,U\)로 \(x=(1/2,0)^T\)를 얻습니다.

밀집 \(n\times n\)의 분해에는 약 \(2n^3/3\)번의 실수 덧셈·곱셈이 들지만, 우변 하나의 두 삼각계 풀이에는 약 \(2n^2\)번이 듭니다. 분해를 재사용하면 시나리오가 늘어날 때 큰 비용을 반복하지 않습니다. 역행렬도 수학적으로 맞는 표현이지만, 해 하나를 얻기 위해 \(n\)개 우변을 풀어 역행렬 전체를 만들 필요는 없습니다. 어느 방식의 잔차가 모든 입력에서 항상 더 크다는 주장은 하지 않습니다.

2. 작은 피벗에서 무슨 일이 일어나는가

이번에는 \(0<\varepsilon<1\)이고

\[\begin{split} A_\varepsilon=\begin{pmatrix}\varepsilon&1\\1&1\end{pmatrix},\qquad b=(1,2)^T \end{split}\]

를 생각합시다. 정확한 해는 \(x_1=1/(1-\varepsilon)\), \(x_2=(1-2\varepsilon)/(1-\varepsilon)\)입니다. 행을 바꾸지 않고 소거하면 승수는 \(1/\varepsilon\)이며 둘째 행은 \((0,1-1/\varepsilon)\), 우변은 \(2-1/\varepsilon\)가 됩니다. 원래 계수는 1 이하인데 중간값은 \(1/\varepsilon\) 크기입니다.

소수 유효숫자 3자리 최근접 산술, \(\varepsilon=0.0001\)을 예로 들면 \(1-10000\)과 \(2-10000\)은 둘 다 \(-10000\)으로 반올림됩니다. 그래서 \(\widehat x_2=1\), 첫 식의 후진대입은 \(\widehat x_1=(1-1)/\varepsilon=0\)을 줍니다. 실제 해는 두 성분 모두 1에 가깝습니다.

첫째와 둘째 행을 교환하면 승수는 \(\varepsilon\)이고 새 둘째 계수는 \(1-\varepsilon\), 새 우변은 \(1-2\varepsilon\)입니다. 같은 3자리 계산에서는 둘 다 1로 반올림되어 \(\widehat x_2=1\), 첫 행에서 \(\widehat x_1=2-1=1\)입니다. 이 예에서는 피벗팅이 큰 중간값을 없앴습니다. 목적은 0으로 나누기를 피하는 데만 있지 않습니다.

부분피벗팅은 현재 열의 남은 행 중 절댓값이 최대인 피벗을 선택합니다. 따라서 소거 승수의 절댓값이 1 이하입니다. 기본 행렬에 적용하면

\[\begin{split} PA=LU,\quad P=\begin{pmatrix}0&1\\1&0\end{pmatrix},\quad L=\begin{pmatrix}1&0\\1/2&1\end{pmatrix},\quad U=\begin{pmatrix}4&3\\0&-1/2\end{pmatrix}. \end{split}\]

우변에도 같은 순열 \(Pb\)를 적용합니다. 뒤 단계에서 행을 바꾸면 이미 기록한 \(L\)의 앞 열들도 같은 행끼리 교환해야 합니다. 완전피벗팅은 남은 부분행렬 전체에서 최대값을 골라 열도 교환하며 \(PAQ=LU\)가 됩니다. 이 경우 마지막에 변수 순열을 되돌려야 합니다.

그림 91 \(A_\varepsilon\)를 정확한 산술로 소거한 중간값의 크기. 가로축과 세로축 모두 로그 눈금이다. 피벗 후 곡선이 1인 것은 원래 행렬의 최대 성분도 포함했기 때문이다.

3. 승수는 작아도 성장할 수 있다

성장인자 \(\rho_n\)은 소거 과정의 활성 부분행렬과 원래 행렬에서 나타나는 최대 성분 절댓값을 원래 최대 성분으로 나눈 값입니다. \(L\)에 저장하는 승수는 이 정의에 포함하지 않습니다. 부분피벗팅은 정확한 산술에서 \(\rho_n\le2^{n-1}\)을 보장합니다. 지수 상한이 실제로 달성되는 예도 있습니다.

\[\begin{split} W_4=\begin{pmatrix} 1&0&0&1\\-1&1&0&1\\-1&-1&1&1\\-1&-1&-1&1 \end{pmatrix}. \end{split}\]

동률이면 위 행을 유지하는 부분피벗 규칙을 사용합니다. 첫 열 승수는 모두 \(-1\)이고 남은 마지막 열은 2가 됩니다. 둘째 소거 후에는 4, 셋째 후에는 8이 됩니다. 최종 \(U\)의 대각은 \(1,1,1,8\)이므로 \(\rho_4=8\)입니다. 일반 \(W_n\)도 대각 아래 모든 성분이 \(-1\)이고 마지막 열은 모두 1입니다. 첫 열만 \(-1\)인 다른 행렬과 혼동하면 이 성장이 나오지 않습니다.

그림 92 직접 구현한 부분피벗 소거의 측정값과 이론값. 차수는 정수이고 세로축은 밑 2의 로그 눈금이다. 이 특수 계열은 최악 예이며 일반 자료의 전형적 성장률을 주장하지 않는다.

성장인자의 역할과 최악 예에 대한 추가 설명은 Higham의 Gaussian elimination 성장인자 해설에서도 확인할 수 있습니다. 여기서는 “실제에서는 항상 작다”는 경험적 문구를 오차 보장으로 사용하지 않습니다.

N1의 언어로 계산된 분해는 \(P(A+\Delta A)=\widehat L\widehat U\)이며, 통상적인 순차 소거의 성분별 분석은 \(|P\Delta A|\le\gamma_{c n}|\widehat L||\widehat U|\) 형태입니다. 상수 \(c\)는 내적형·갱신형 구현과 연산의 결합 방식에 따라 달라집니다. 마지막 절에서는 아래에 제시하는 내적형 구현에 대해 명시적인 \(\gamma_{n+1}\) 상한을 증명합니다. 노름으로 바꿀 때에는 차원 인자가 생깁니다. \(|l_{ij}|\le1\)인 정확한 부분피벗 분해에서는

\[ \||L||U|\|_\infty\le n^2\rho_n\|A\|_\infty. \]

따라서 성장인자만 적고 차원 상수나 반올림 가정을 생략해서는 안 됩니다. 후진오차가 작아도 전진오차에는 다시 \(\kappa(A)\)가 곱해집니다.

4. Schur 보원은 남은 방정식이다

\(A_{11}\)이 가역이면 첫 블록식에서 \(x_1=A_{11}^{-1}(b_1-A_{12}x_2)\)입니다. 둘째 식에 대입하면

\[ Sx_2=b_2-A_{21}A_{11}^{-1}b_1,\qquad S=A_{22}-A_{21}A_{11}^{-1}A_{12}. \]

블록 LU는 이를

\[\begin{split} \begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix} =\begin{pmatrix}I&0\\A_{21}A_{11}^{-1}&I\end{pmatrix} \begin{pmatrix}A_{11}&A_{12}\\0&S\end{pmatrix} \end{split}\]

로 기록합니다. 실제 구현에서 \(A_{11}^{-1}\)는 선형계를 푼다는 표기이지 역행렬을 따로 만들라는 지시가 아닙니다. 대칭 양의 정부호라면 H7의 Schur 보원 정리에서 증명한 보원의 양의 정부호성이 다음 소거 피벗을 양수로 유지합니다.

5. 대칭 양의 정부호에서는 Cholesky

공분산 또는 볼록 이차비용의 행렬 \(H=\begin{pmatrix}2&1\\1&2\end{pmatrix}\)를 다시 사용합시다. 변수들이 같은 기준단위로 정규화되어 있다고 가정합니다. 대칭성을 보존하는 분해는

\[\begin{split} H=LL^T,\qquad L=\begin{pmatrix}\sqrt2&0\\1/\sqrt2&\sqrt{3/2}\end{pmatrix}. \end{split}\]

성분식은 \(l_{jj}=\sqrt{h_{jj}-\sum_{k<j}l_{jk}^2}\), \(l_{ij}=(h_{ij}-\sum_{k<j}l_{ik}l_{jk})/l_{jj}\)입니다. 앞서 만든 한쪽 삼각형을 대칭으로 공유하여 연산량은 약 \(n^3/3\)입니다. 행렬식을 직접 곱하는 대신

\[ \log\det H=2\sum_j\log l_{jj} \]

를 계산하면 매우 크거나 작은 양수들의 곱이 범위를 벗어나는 문제를 피할 수 있습니다. 예를 들어 \(10^{-4}I_{200}\)의 행렬식은 \(10^{-800}\)이라 binary64에서 0으로 언더플로하지만 로그는 \(-800\log10\)으로 표현됩니다.

정확한 산술에서는 양의 정부호가 모든 단계의 양의 피벗을 보장합니다. 부동소수점에서는 거의 특이한 입력의 반올림 때문에 제곱근 안이 0 또는 음수가 될 수 있습니다. 완료된 Cholesky의 후진안정성과 모든 수학적으로 양의 정부호 입력에서 무조건 완료됨은 다른 주장입니다. 다음 절의 노름 상한은 완료된 결과에 관한 것입니다.

대칭 부정치에서는 \(LDL^T\)가 적합하며 \(D\)에 \(1\times1\)뿐 아니라 \(2\times2\) 블록을 허용합니다. \(K=\begin{pmatrix}0&1\\1&0\end{pmatrix}\)는 가역이지만 첫 대각 피벗이 0입니다. 전체를 \(2\times2\)의 \(D=K\), \(L=I\)로 두면 분해가 됩니다. Bunch–Kaufman은 대칭 순열과 이러한 블록 피벗을 고르는 표준 방식입니다. 구체적인 선택 상수와 구현의 안정성 정리는 후속 전문 알고리즘의 조망이며, 일반 LU에 행교환만 넣은 것을 그 알고리즘이라고 부르지 않습니다.

6. 상관행렬을 고친다는 말의 세 가지 뜻

각 쌍에서 따로 추정한 상관계수를 모아

\[\begin{split} C=\begin{pmatrix}1&0.9&0.9\\0.9&1&-0.9\\0.9&-0.9&1\end{pmatrix} \end{split}\]

를 얻었다고 합시다. 상관계수는 무차원이며 개별 값이 \([-1,1]\)에 있다고 해서 전체가 상관행렬은 아닙니다. 이 행렬의 고윳값은 \(1.9,1.9,-0.8\)입니다. 따라서 어떤 포트폴리오 또는 선형결합의 “분산”이 음수가 되어 공분산 모형으로 허용되지 않습니다.

고윳값의 음수 부분을 0으로 바꾸는 PSD 클리핑은 대칭 양의 준정부호 행렬 중 Frobenius 거리로 가장 가깝습니다. 그러나 이 예의 대각은 \(1+0.8/3=19/15\)가 되어 1이 아닙니다. 양의 준정부호와 단위대각을 모두 요구하는 최근접 상관행렬은 다른 문제입니다. 이 예의 정답은

\[\begin{split} C_* =\begin{pmatrix}1&1/2&1/2\\1/2&1&-1/2\\1/2&-1/2&1\end{pmatrix} \end{split}\]

이고 고윳값은 \(3/2,3/2,0\)입니다. 아래에서 최적성을 직접 증명합니다. 거리가 최소여도 행렬은 특이할 수 있습니다.

항등행렬로의 축소 \(C_\alpha=(1-\alpha)C+\alpha I\), \(0\le\alpha\le1\)는 단위대각을 보존하며 최소 고윳값은 \(-0.8+1.8\alpha\)입니다. 따라서 \(\alpha>4/9\)이면 양의 정부호입니다. 이것은 특정 표본분포에서 최적인 축소계수를 추정한 것이 아니라, 이 행렬의 스펙트럼을 바탕으로 선택 가능한 범위를 구한 것입니다. 표본오차 모형을 추가하지 않고 Ledoit–Wolf 추정이라고 부를 수는 없습니다.

그림 93 왼쪽은 양의 정부호가 되는 경계, 오른쪽은 원래 \(C\)에서의 거리이다. 수직선의 \(\alpha=4/9\)는 최근접 상관행렬과 같지만 여전히 특이하다. 두 세로축은 서로 다른 양을 나타낸다.

일반적인 최근접 상관행렬에는 PSD 원뿔과 단위대각 아핀집합을 번갈아 사영하되 Dykstra 보정항을 유지하는 방법을 씁니다. 단순 교대사영은 교집합의 한 점으로 가는 것과 원래 행렬에서 가장 가까운 점으로 가는 것을 구별하지 못합니다. 일반 Dykstra 수렴 정리는 Higham의 최근접 상관행렬 논문에서 설명하는 외부 결과로 두고, 이 장의 수치 결과는 아래의 직접 증명된 \(C_*\)와 비교합니다. 종료 허용오차 때문에 계산한 최소 고윳값이 작은 음수일 수 있으며, 이 구현의 결과를 정확한 PSD 인증으로 쓰지는 않습니다.

import numpy as np
def psd_projection(A):
    values, vectors = np.linalg.eigh((A+A.T)/2)
    return (vectors*np.maximum(values, 0)) @ vectors.T

def nearest_correlation(A, tol=1e-12, limit=10000):
    Y = np.array(A, dtype=float, copy=True)
    correction = np.zeros_like(Y)
    for iteration in range(limit):
        R = Y-correction
        X = psd_projection(R)
        correction = X-R
        previous = Y.copy()
        Y = X.copy(); np.fill_diagonal(Y, 1.)
        step = np.linalg.norm(Y-previous, 'fro')
        feasibility = max(0., -np.linalg.eigvalsh(Y)[0])
        if step <= tol and feasibility <= tol:
            return Y, iteration+1
    raise RuntimeError("지정한 반복 횟수 안에 수렴하지 않았습니다")

C = np.array([[1., .9, .9], [.9, 1., -.9], [.9, -.9, 1.]])
expected = np.array([[1., .5, .5], [.5, 1., -.5], [.5, -.5, 1.]])
fixed, iterations = nearest_correlation(C)
assert np.allclose(fixed, expected, atol=2e-12, rtol=0)
print("반복 횟수와 최소 고윳값:", iterations, np.linalg.eigvalsh(fixed)[0])

반복 횟수와 최소 고윳값: 26 -3.149702720861569e-13

7. 0으로 저장했던 자리에 왜 새 값이 생기는가

\[\begin{split} H=\begin{pmatrix}4&1&1&1\\1&2&0&0\\1&0&2&0\\1&0&0&2\end{pmatrix} \end{split}\]

는 엄격한 대각우세 대칭 양의 정부호 행렬입니다. 첫 변수를 먼저 소거하면 남은 Schur 보원은 \(2I_3-\frac14\mathbf1\mathbf1^T\)입니다. 원래 0이던 비대각 성분에 \(-1/4\)이 생깁니다. 이를 fill-in이라고 합니다. 반대로 연결이 하나뿐인 변수 \(2,3,4\)를 먼저 소거하면 이들 사이에는 새 연결이 생기지 않고 마지막 첫 변수의 대각만 \(4-3/2=5/2\)로 바뀝니다.

띠 반폭 \(p\)인 양의 정부호 행렬의 Cholesky는 자연 순서에서 같은 띠를 유지합니다. 각 행에는 최대 \(p\)개의 비대각 출력이 있고 각 내적 길이가 최대 \(p\)이므로 비용은 \(O(np^2)\), 저장은 \(O(np)\)입니다. 일반 희소행렬에서는 적절한 재배열이 이 비용을 크게 바꿉니다. N8에서 희소 자료구조와 반복법으로 이어집니다.

8. 연습과 전체 풀이

1. 첫 \(A\)에서 \(PA=LU\)와 \(b=(1,1)^T\)의 두 삼각계 풀이를 확인하세요.

풀이. \(LU=\begin{pmatrix}4&3\\2&1\end{pmatrix}=PA\)입니다. \(Ly=Pb\)에서 \(y_1=1\), \(y_2=1-1/2=1/2\)입니다. \(Ux=y\)에서 \(-x_2/2=1/2\)이므로 \(x_2=-1\), \(4x_1-3=1\)이므로 \(x_1=1\)입니다.

2. \(\begin{pmatrix}0&1\\1&0\end{pmatrix}\)가 행교환 없는 단위하삼각 LU를 갖지 못함을 보이세요. 특이한 \(\operatorname{diag}(0,1)\)과 비교하세요.

풀이. \(L=\begin{pmatrix}1&0\\l&1\end{pmatrix}\)와 \(U=\begin{pmatrix}u&v\\0&w\end{pmatrix}\)의 곱에서 좌상단이 \(u=0\)이면 좌하단도 \(lu=0\)입니다. 교환행렬의 좌하단 1을 만들 수 없습니다. 반면 \(\operatorname{diag}(0,1)\)에서는 \(U=\operatorname{diag}(0,1)\)과 임의의 \(l\)이 모두 가능합니다. LU의 선행 주행렬식 동치와 유일성에는 가역성 가정을 붙여야 합니다.

3. \(H=\begin{pmatrix}2&1\\1&2\end{pmatrix}\)의 Cholesky로 \(\det H\)와 로그를 구하세요.

풀이. 두 대각의 곱은 \(\sqrt2\sqrt{3/2}=\sqrt3\)입니다. \(\det H=(\det L)^2=3\)이고 \(2(\log\sqrt2+\log\sqrt{3/2})=\log3\)입니다.

4. \(C\)의 PSD 클리핑과 최근접 상관행렬까지의 거리를 구하세요.

풀이. 클리핑은 한 고윳값 \(-0.8\)을 0으로 바꾸므로 Frobenius 거리는 \(0.8\)입니다. \(C_*\)는 여섯 비대각 성분을 크기 \(0.4\)만큼 바꾸므로 거리는 \(\sqrt{6(0.4)^2}=0.4\sqrt6\)입니다. 후자가 큰 것은 제약이 하나 더 있기 때문이며 두 최적화는 서로 모순되지 않습니다.

5. \(C_{1/2}\)의 조건수를 구하세요.

풀이. 고윳값은 \(1.45,1.45,0.1\)입니다. 대칭 양의 정부호이므로 \(\kappa_2=1.45/0.1=14.5\)입니다. \(\alpha=4/9\)의 행렬은 최소 고윳값이 0이어서 유한 조건수가 없습니다.

6. 위 희소 \(H\)에서 두 순서의 행렬식을 확인하세요.

풀이. 첫 변수를 먼저 소거하면 \(\det H=4\det(2I_3-\mathbf1\mathbf1^T/4)\)입니다. 이 Schur 보원의 고윳값은 \(2,2,5/4\)이므로 결과는 20입니다. 잎 변수를 먼저 소거하면 피벗은 \(2,2,2,5/2\)이고 곱은 역시 20입니다. 순서는 중간 희소성을 바꾸지만 행렬식은 바꾸지 않습니다.

9. 지금까지의 내용을 수학의 언어로 정리해 봅시다

앞의 소거를 분해의 존재 조건과 오차식으로 정리합니다. 정확한 산술의 정리와 반올림된 알고리즘의 정리를 분리하며, N1의 반올림 보조정리의 \(\gamma_k\)를 그대로 사용합니다.

정리 1. 가역행렬의 LU와 성장인자

가역 \(A\in\mathbb F^{n\times n}\)에 단위하삼각 \(L\), 상삼각 \(U\)의 분해 \(A=LU\)가 존재할 필요충분조건은 크기 \(1,\ldots,n-1\)의 선행 주행렬식이 모두 0이 아닌 것입니다. 존재하면 유일합니다. 부분피벗 소거는 가역행렬에서 완료되며 정확한 산술의 성장인자는 \(2^{n-1}\) 이하입니다.

증명. 분해가 있으면 \(U\)는 가역이어서 모든 대각이 0이 아닙니다. 선행 \(k\)블록의 곱은 \(L_kU_k\)이며 행렬식은 \(u_{11}\cdots u_{kk}\ne0\)입니다. 역으로 \(a_{11}\ne0\)로 첫 열을 소거하면 Schur 보원의 선행 \(k\)행렬식은 원래 선행 \(k+1\)행렬식을 \(a_{11}\)로 나눈 것이므로 모두 0이 아닙니다. 차수 귀납으로 남은 LU를 얻고 첫 열 승수를 붙여 전체를 얻습니다. \(n=1\)은 \(L=[1]\), \(U=A\)입니다.

\(L_1U_1=L_2U_2\)이면 \(L_2^{-1}L_1=U_2U_1^{-1}\)입니다. 왼쪽은 단위하삼각, 오른쪽은 상삼각이므로 둘 다 \(I\)이고 유일합니다. 가역인 활성 Schur 보원의 첫 열은 영열일 수 없어 부분피벗은 0이 아닌 값을 선택합니다. 다음 보원도 행렬식의 곱 공식으로 가역이므로 끝까지 갑니다.

한 소거 단계의 새 성분은 \(a'_{ij}=a_{ij}-l_{ik}a_{kj}\)이고 \(|l_{ik}|\le1\)입니다. 현재 최대 성분이 \(M_k\)이면 \(|a'_{ij}|\le2M_k\)입니다. 최대 \(n-1\)단계를 거치므로 \(\rho_n\le2^{n-1}\)입니다. \(W_n\)에서는 매 단계 마지막 열이 두 배가 되므로 상한을 달성합니다. ∎

정리 2. 내적형 LU와 삼각계의 후진오차

실수 산술에서 순열을 고정한 \(B=PA\)에 다음 내적형 식을 적용한다고 하자.

\[ u_{ij}=\operatorname{fl}\left(b_{ij}-\sum_{k<i}l_{ik}u_{kj}\right)\ (i\le j),\qquad l_{ij}=\operatorname{fl}\left(\frac{b_{ij}-\sum_{k<j}l_{ik}u_{kj}}{u_{jj}}\right)\ (i>j). \]

합은 \(b_{ij}\)에서 각 반올림된 곱을 순서대로 빼는 방식이며 \(l_{ii}=1\)입니다. 모든 피벗이 0이 아니고 정상 범위이며 \((n+1)u<1\)이면 계산된 인자에 대해

\[ \widehat L\widehat U=B+E,\qquad |E|\le\gamma_{n+1}|\widehat L||\widehat U|. \]

삼각계의 순차 대입도 \((T+F)\widehat x=b\), \(|F|\le\gamma_{n+1}|T|\)로 설명됩니다. 따라서 두 대입을 이어 실행한 해에는 \(P(A+\Delta A)\widehat x=Pb\)가 성립하며

\[ |P\Delta A|\le(3g+g^2)|\widehat L||\widehat U|,\qquad g=\gamma_{n+1} \]

라는 상한을 쓸 수 있습니다.

증명. 길이 \(r\)의 순차 뺄셈 \(s=\operatorname{fl}(b-\sum_{k=1}^r p_kq_k)\)를 전개하면 \(b\)에는 \(r\)개 반올림 인자의 곱 \(\alpha_0\)이, 각 \(p_kq_k\)에는 곱셈 한 번과 그 뒤 뺄셈들의 인자 \(\alpha_k\)가 붙습니다. \(s=\alpha_0b-\sum\alpha_k p_kq_k\)입니다. 이를 \(b\)에 대해 풀면 \(b=s/\alpha_0+\sum(\alpha_k/\alpha_0)p_kq_k\)입니다. 공통 꼬리 인자를 약분하면 각 계수에는 최대 \(r+1\)개의 인자 또는 역수만 남습니다. 나눗셈으로 얻은 \(l=s/u_{jj}(1+\delta)\)를 쓰면 \(s=lu_{jj}/(1+\delta)\)여서 하나가 더 늘지만 \(r\le n-1\)이므로 최대 \(n+1\)입니다. N1의 곱 보조정리에서 각 계수와 1의 차이는 \(\gamma_{n+1}\) 이하입니다.

따라서 각 \(b_{ij}\)와 \(\sum_k\widehat l_{ik}\widehat u_{kj}\)의 차이는 \(\gamma_{n+1}\sum_k|\widehat l_{ik}\widehat u_{kj}|\) 이하입니다.

삼각대입도 한 행의 식을 같은 방법으로 재배열하면 각 \(t_{ij}\)에 상대 \(\gamma_{n+1}\) 이하의 섭동을 붙여 계산한 \(\widehat x\)를 정확히 만족시킵니다. 두 대입은 \((\widehat L+F_L)\widehat y=Pb\), \((\widehat U+F_U)\widehat x=\widehat y\)입니다. 곱을 전개하면 전체 섭동은 \(E+F_L\widehat U+\widehat L F_U+F_LF_U\)입니다. 각각의 성분 상한을 더하면 \((g+g+g+g^2)|\widehat L||\widehat U|\)를 얻습니다. ∎

이 증명은 명시한 내적형 구현에 대한 것입니다. 피벗 순서를 선택하는 작업은 정확한 행 순열로 취급합니다. 다른 갱신형 코드의 세부 상수까지 이 값과 같다고 주장하지 않습니다. 실제 결과에는 \(\|PA-\widehat L\widehat U\|\)와 정규화한 잔차도 함께 기록합니다.

정리 3. Cholesky의 존재와 완료된 계산의 오차

실수 대칭 양의 정부호 행렬에는 양의 대각을 갖는 유일한 \(A=LL^T\)가 있습니다. 순차 내적형 부동소수점 Cholesky가 양의 피벗으로 완료되고 모든 연산이 N1의 정상 범위 모형을 만족하면

\[ \widehat L\widehat L^T=A+E,\qquad |E|\le g|\widehat L||\widehat L|^T,\qquad g=\gamma_{n+3}<1, \]

이며 \(\|E\|_2\le\frac{ng}{1-g}\|A\|_2\)입니다.

증명. 존재는 \(a_{11}>0\)에서 \(l_{11}=\sqrt{a_{11}}\), \(l_{21}=a_{21}/l_{11}\)을 정하고 양의 정부호 Schur 보원에 귀납하면 됩니다. 각 대각을 양수로 정했으므로 첫 열이 유일하고 보원의 분해도 귀납적으로 유일합니다. 이는 H7의 Cholesky 결과를 계산식으로 다시 쓴 것입니다.

비대각 원소의 오차식은 앞 내적형 LU 증명과 같습니다. 대각에서는 반올림된 제곱근 \(\widehat l_{jj}=\sqrt{s}(1+\delta)\)를 거꾸로 써서 \(s=\widehat l_{jj}^2/(1+\delta)^2\)로 대입합니다. 순차 뺄셈을 재배열한 인자에 역수 두 개가 더해져도 개수는 \(n+3\) 이하입니다. 그러므로 \(|e_{ij}|\le g\sum_k|\widehat l_{ik}\widehat l_{jk}|\)입니다.

대각에서 \(|e_{ii}|\le g\sum_k\widehat l_{ik}^2\)이고 \(\sum_k\widehat l_{ik}^2=a_{ii}+e_{ii}\)이므로 \((1-g)\sum_k\widehat l_{ik}^2\le a_{ii}\)입니다. 합하면 \(\|\widehat L\|_F^2\le\operatorname{tr}A/(1-g)\le n\|A\|_2/(1-g)\)입니다. 성분 상한과 Cauchy–Schwarz로

\[ \|E\|_2\le\|E\|_F \le g\,\||\widehat L||\widehat L|^T\|_F \le g\|\widehat L\|_F^2 \]

를 얻어 결론입니다. 이 상한에는 LU처럼 큰 중간 \(U\)의 성장인자가 없습니다. 다만 양의 피벗으로 완료했다는 가정은 증명에서 제거되지 않습니다. ∎

정리 4. PSD 사영과 이 예의 최근접 상관행렬

대칭 \(A=Q\operatorname{diag}(\lambda_i)Q^T\)의 가장 가까운 PSD 행렬은 \(A_+=Q\operatorname{diag}(\max(\lambda_i,0))Q^T\)이며 유일합니다. 단위대각 PSD 집합에서도 Frobenius 최근접점은 항상 존재하고 유일합니다. 6절의 \(C\)에서는 그 점이 \(C_*\)입니다.

증명. PSD \(X\)를 \(Y=Q^TXQ\succeq0\)로 옮기면

\[ \|A-X\|_F^2=\sum_i(\lambda_i-y_{ii})^2+\sum_{i\ne j}y_{ij}^2. \]

\(y_{ii}\ge0\)이므로 각 대각항의 최소는 \(y_{ii}=\max(\lambda_i,0)\)이고 비대각은 0에서 최소입니다. 이 선택은 실제 PSD여서 하한을 달성하며 모든 제곱항의 유일한 최소로 유일성도 따릅니다.

단위대각 PSD 집합은 \(I\)를 포함하는 닫힌 볼록집합입니다. 각 \(2\times2\) 주부분행렬의 PSD 조건에서 \(|x_{ij}|\le1\)이므로 유계이며 최근접점이 존재합니다. 서로 다른 최소점의 중점에서는 제곱거리 항등식에 따라 거리가 엄격히 작아져 모순이므로 유일합니다.

특정 예에는 \(D=\operatorname{diag}(1,-1,-1)\)를 써서 \(DCD\)의 모든 비대각을 \(-0.9\)로 만듭니다. 이 행렬과 제약집합은 모든 좌표순열에 불변입니다. 유일한 최적점도 모든 좌표순열에 불변이어야 하므로 대각은 1이고 모든 비대각은 같은 \(r\)입니다. 그 고윳값은 \(1-r\) 두 개와 \(1+2r\) 하나이므로 \(-1/2\le r\le1\)이 정확한 PSD 범위입니다. 거리 제곱은 \(6(r+0.9)^2\)이고 이 구간에서는 \(r=-1/2\)에서 최소입니다. \(D\)로 되돌리면 \(C_*\)입니다. ∎

보조정리 5. 띠 보존

반폭 \(p\)인 SPD 행렬의 Cholesky에서 \(i-j>p\)이면 \(l_{ij}=0\)입니다.

증명. 열 \(j\)에 대한 귀납을 씁니다. \(a_{ij}=0\)이고 \(k<j\)이면 \(i-k>p\)이므로 앞 열에 대한 귀납가정으로 \(l_{ik}=0\)입니다. 따라서 \(l_{ij}=(a_{ij}-\sum_{k<j}l_{ik}l_{jk})/l_{jj}=0\)입니다. 대각 피벗은 양수이므로 나눗셈은 허용됩니다. 이 지지집합을 사용하면 7절의 저장량과 연산량 상한이 따릅니다. ∎

삼각 인자는 같은 선형계를 반복해서 풀 때 계산을 재사용하게 해 줍니다. 다음 장에서는 거의 겹치는 열을 직교화할 때 생기는 오차를 비교하고, 길이를 보존하는 변환으로 QR을 구성합니다. N3로 이어 읽기.