슈어 보수

1. 개요[편집]

슈어 보수 Schur complement
정의	$M/A = D - C A^{-1} B$
정체	블록 가우스 소거가 남기는 것
행렬식	$\det M = \det A \cdot \det(M/A)$
양정치	$M \succ 0 \iff A \succ 0$ 이고 $M/A \succ 0$
이름	Haynsworth(1968)가 Schur(1917)의 보조정리에서 명명
주의	슈어 분해와 전혀 다른 개념

미지수 절반을 소거하고 남은 것. 그 “남은 것”에 온갖 물리와 통계가 들어 있다.

슈어 보수(Schur complement)는 블록 분할된 행렬

$$M = \begin{bmatrix} A & B \\ C & D \end{bmatrix}$$

에서 $A$ 가 가역일 때 정의되는 행렬 $M/A = D - CA^{-1}B$ 이다. 이름만 보면 슈어 분해의 친척 같지만 전혀 다른 개념이다. 슈어 분해는 $A = QTQ^H$ 라는 유니터리 삼각화이고, 슈어 보수는 블록 소거의 잔여물이다. 둘 다 이사이 슈어의 이름을 빌렸을 뿐 정리도 용도도 겹치지 않는다.¹ 하나만 기억하자 — 슈어 보수는 “일부 변수를 소거한 뒤 남은 계” 다.

이 문서의 논지는 하나다. 소거라는 지극히 기계적인 조작이 영역분할 솔버의 인터페이스 문제, 안장점 문제의 압력 방정식, 가우스 조건부 분포의 공분산을 전부 같은 식으로 만들어 낸다는 것. 이 셋이 같은 물건이라는 사실을 알고 나면 세 분야의 문헌이 서로 번역된다.

2. 블록 가우스 소거로부터[편집]

$Ax_1 + Bx_2 = b_1$, $Cx_1 + Dx_2 = b_2$ 에서 첫 식으로 $x_1 = A^{-1}(b_1 - Bx_2)$ 를 구해 둘째에 대입하면

$$(D - CA^{-1}B)\,x_2 = b_2 - CA^{-1}b_1$$

이 남는다. 좌변의 계수행렬이 정확히 $M/A$ 다. 슈어 보수 = 블록 단위 가우스 소거를 한 번 돌린 결과이며, 스칼라 가우스 소거법에서 피벗 하나를 소거한 뒤의 부분행렬이 $1\times1$ 슈어 보수인 것과 정확히 같은 일이다.

행렬 항등식으로 쓰면 블록 LDU 분해가 된다.

$$M = \begin{bmatrix} I & 0 \\ CA^{-1} & I \end{bmatrix} \begin{bmatrix} A & 0 \\ 0 & M/A \end{bmatrix} \begin{bmatrix} I & A^{-1}B \\ 0 & I \end{bmatrix}$$

양옆의 삼각행렬은 행렬식이 1이므로 즉시

$$\det M = \det A \cdot \det(M/A)$$

가 따라 나온다. 이것이 1917년 슈어가 실제로 쓴 형태이고, 1968년 헤인즈워스가 여기에 “슈어 보수”라는 이름과 $M/A$ 라는 표기를 붙였다. 계수(rank)에 대해서도 같은 가법성이 성립한다 — $\operatorname{rank} M = \operatorname{rank} A + \operatorname{rank}(M/A)$.

역행렬도 이 분해를 뒤집으면 바로 읽힌다. 특히 우하단 블록이 깔끔하다.

$$M^{-1} = \begin{bmatrix} A^{-1} + A^{-1}B S^{-1} C A^{-1} & -A^{-1}BS^{-1} \\ -S^{-1}CA^{-1} & S^{-1} \end{bmatrix}, \qquad S = M/A$$

즉 $M^{-1}$ 의 $(2,2)$ 블록은 슈어 보수의 역행렬이다. 반대로 $D$ 를 먼저 소거해 $M/D = A - BD^{-1}C$ 를 만들고 좌상단 블록을 두 방식으로 비교하면 셔먼-모리슨-우드베리 항등식

$$(A - BD^{-1}C)^{-1} = A^{-1} + A^{-1}B(D - CA^{-1}B)^{-1}CA^{-1}$$

이 항등식 조작 없이 튀어나온다. 우드베리 공식을 외우는 대신 “슈어 보수를 양쪽에서 취한 것” 으로 기억하면 부호를 틀리지 않는다.

3. 양정치성과 관성[편집]

대칭 $M = \begin{bmatrix} A & B^\top \\ B & D\end{bmatrix}$ 를 생각하자. 위 LDU는 합동변환 $M = L\,\mathrm{diag}(A, S)\,L^\top$ 이 되고, 실베스터 관성 법칙에 의해 고유값의 부호 분포가 보존된다. 따라서

$$M \succ 0 \iff A \succ 0 \ \text{ 그리고 }\ S = D - BA^{-1}B^\top \succ 0$$

이 성립한다. 더 강하게, 헤인즈워스의 관성 가법 공식은 양·음·영 고유값 개수를 $\mathrm{In}(M) = \mathrm{In}(A) + \mathrm{In}(S)$ 로 쪼갠다. 즉 $A \succ 0$ 이고 $S \prec 0$ 이면 $M$ 은 부정부호이고, 그 음의 고유값 개수는 정확히 $S$ 의 크기다. 안장점 문제의 KKT 행렬이 $\mathrm{LU}$ 를 피벗 없이 때리면 안 되는 이유가 이 한 줄로 설명된다.

이 동치를 볼록 최적화 쪽에서 부르는 이름이 슈어 보수 보조정리이며, 겉보기 비선형인 이차 조건을 선형행렬부등식으로 바꾸는 도구로 쓰인다. 그쪽 세부는 해당 문서와 반정부호 계획법에 있으니 여기서 반복하지 않는다.

4. 안장점 문제 — 압력이 사는 곳[편집]

비압축성 유동, 혼합유한요소법, 라그랑주 승수로 구속을 건 구조 문제는 전부 다음 블록 구조로 떨어진다.

$$\begin{bmatrix} A & B^\top \\ B & 0 \end{bmatrix} \begin{bmatrix} u \\ p \end{bmatrix} = \begin{bmatrix} f \\ g \end{bmatrix} \qquad\Longrightarrow\qquad S = -\,B A^{-1} B^\top$$

$u$ 를 소거하면 압력(또는 승수)만의 방정식 $S p = BA^{-1}f - g$ 가 남는다. 스토크스 문제에서 이 $S$ 는 압력 슈어 보수라 불리고, 여기에 리처드슨 반복을 걸면 우자와 알고리즘, CG를 걸면 슈어 보수 CG다.

핵심은 $S$ 를 조립하지 않는다는 점이다. $A^{-1}$ 은 밀집이므로 $S$ 도 밀집이지만, 벡터 하나 곱하는 데는 $A$ 계 풀이 한 번이면 되니 행렬-프리 크리로프 부분공간법이 그대로 얹힌다. 그리고 $S$ 의 스펙트럼은 이산화 이론의 inf-sup 상수에 갇힌다 — 압력 질량행렬 $M_p$ 기준으로 $\beta^2 \le (Sq,q)/(M_pq,q) \le \Gamma^2$ 이므로, $M_p$ 를 전처리기로 쓰면 반복 수가 격자와 무관해진다. 이산화 상수가 전처리기를 지목하는 이 구조는 혼합유한요소법과 우자와 알고리즘 쪽에 자세히 있다.

실무의 현대적 형태는 소거를 아예 하지 않는 **블록 전처리**다. 전체 계를 MINRES/GMRES에 넣고, 전처리기의 $(2,2)$ 자리에 $S$ 의 근사만 꽂는다. 스토크스면 $M_p$, 대류가 들어간 나비에-스토크스면 PCD·LSC 같은 압력 대류-확산 근사가 표준이고, PETSc의 PCFIELDSPLIT 가 정확히 이 조립을 자동화한다. $A^{-1}$ 을 정확히 적용할 필요가 사라진다는 것이 소거 대비 최대 이점이다.

5. 영역분할 — 인터페이스 문제가 곧 슈어 보수[편집]

도메인을 부분영역으로 쪼개고 미지수를 “내부”와 “인터페이스”로 정렬하면 강성행렬이

$$\begin{bmatrix} K_{II} & K_{I\Gamma} \\ K_{\Gamma I} & K_{\Gamma\Gamma}\end{bmatrix}$$

꼴이 되고, 내부 미지수를 소거하면 인터페이스만의 계 $S = K_{\Gamma\Gamma} - K_{\Gamma I}K_{II}^{-1}K_{I\Gamma}$ 가 남는다. $K_{II}$ 는 부분영역별로 블록 대각이므로 소거가 완전 병렬이고, $S$ 에 벡터를 곱하는 것은 부분영역마다 국소 디리클레 문제를 한 번 푸는 일이다.

이득은 두 가지다. 미지수 수가 인터페이스 크기로 줄고, 조건수가 $O(h^{-2})$ 에서 $O(h^{-1})$ 로 개선된다. 비중첩형 영역분할(FETI·BDDC)과 구조해석의 부분구조법이 전부 이 위에 서 있으며, 알고리즘 세부는 영역 분할법 문서에 있다. 구조 쪽에서 부르는 정적 응축(static condensation), 즉 내부 자유도를 소거해 슈퍼요소를 만드는 조작도 문자 그대로 같은 연산이다.²

여기서 나오는 실무적 함의 하나. 슈어 보수는 희소성을 보존하지 않는다. $K_{II}^{-1}$ 이 밀집이므로 $S$ 도 밀집이고, 그래서 인터페이스를 작게 유지하는 그래프 분할 품질이 성능을 좌우한다. 희소행렬 직접법에서 채움(fill-in)이 생기는 현상도 결국 소거가 만드는 슈어 보수를 국소적으로 관찰한 것이다.

6. 조건부 확률 — 통계 쪽의 같은 얼굴[편집]

$x = (x_1, x_2)$ 가 결합 가우스이고 공분산 행렬이

$$\Sigma = \begin{bmatrix} \Sigma_{11} & \Sigma_{12} \\ \Sigma_{21} & \Sigma_{22}\end{bmatrix}$$

일 때, $x_2$ 를 관측한 뒤 $x_1$ 의 조건부 분포는 여전히 가우스이고 그 공분산은

$$\Sigma_{1|2} = \Sigma_{11} - \Sigma_{12}\Sigma_{22}^{-1}\Sigma_{21} = \Sigma/\Sigma_{22}$$

슈어 보수 그 자체다. 조건부 평균 $\mu_1 + \Sigma_{12}\Sigma_{22}^{-1}(x_2 - \mu_2)$ 의 계수도 소거 과정에서 나온 $CA^{-1}$ 항이다. 이 한 줄이 여러 분야를 동시에 설명한다.

• 칼만 필터의 갱신 단계. 사후 공분산 $P^+ = P^- - P^-H^\top(HP^-H^\top + R)^{-1}HP^-$ 는 상태와 관측의 결합 공분산에 대한 슈어 보수이고, 칼만 이득 $K$ 는 그 $\Sigma_{12}\Sigma_{22}^{-1}$ 이다. “관측을 소거한다”와 “관측으로 조건부화한다”가 같은 연산이라는 뜻.
• 가우시안 프로세스 회귀. 예측 공분산 $k_{**} - k_*^\top(K + \sigma^2 I)^{-1}k_*$ 가 정확히 같은 꼴이다. 관측점이 늘수록 예측 분산이 줄어드는 것은 슈어 보수가 항상 $\Sigma_{11}$ 이하($\preceq$)라는 사실의 통계적 번역이다.³
• 정밀도 행렬과 조건부 독립. 반대로 공분산의 역행렬(정밀도 행렬)에서는 $(1,1)$ 블록이 $\Sigma_{1|2}^{-1}$ 이다. 위에서 본 “역행렬의 $(2,2)$ 블록 = 슈어 보수의 역” 공식과 같은 말이며, 가우스 그래프 모형에서 정밀도 행렬의 0 성분이 조건부 독립을 뜻한다는 정리가 여기서 나온다.

즉 수치해석의 “미지수 소거”와 통계의 “주변화/조건부화”는 같은 대수 조작의 두 이름이다. 최소자승법의 정규방정식을 확대계로 쓰고 잔차를 소거하는 것도 같은 그림에 들어간다.

7. 계산상 주의[편집]

• $A^{-1}$ 을 만들지 마라. $A^{-1}B$ 는 다중 우변 삼각계 풀이로 얻는다. 명시적 역행렬은 비용이 3배이고 정확도도 나쁘다.
• $S$ 를 조립할지 말지는 크기가 정한다. 인터페이스가 작으면 조립 후 촐레스키 분해가 이기고, 크면 행렬-프리 + 전처리 CG가 이긴다. 조립 비용은 $S$ 의 열 수만큼 $A$ 계를 푸는 것이다.
• $A$ 가 나쁘면 $S$ 도 나빠진다. 소거는 조건수를 개선해 주는 마법이 아니다. 영역분할에서 조건수가 좋아지는 것은 $A$(= $K_{II}$)가 국소 문제라 잘 조건화돼 있기 때문이지, 소거 자체의 효능이 아니다.
• $A$ 가 특이하면 정의 자체가 없다. 이때는 유사역행렬을 쓴 일반화 슈어 보수 $D - CA^{+}B$ 로 넘어가는데, 성질이 상당수 깨진다(랭크 조건이 붙는다). 부동 부분영역이 생기는 FETI가 라그랑주 승수와 강체모드 처리를 따로 두는 이유다.

8. 관련 문서[편집]

• 슈어 분해 · 가우스 소거법 · LU 분해 · 촐레스키 분해
• 영역 분할법 · 부분구조법 · 희소행렬 · 조건수
• 혼합유한요소법 · 우자와 알고리즘 · 안장점 · GMRES · PETSc
• 선형행렬부등식 · 반정부호 계획법 · 라그랑주 승수법
• 칼만 필터 · 가우시안 프로세스 · 최소자승법
• 행렬 곱셈 · 크리로프 부분공간법 · 전처리기

9. Footnotes[편집]

1. 이사이 슈어는 프로베니우스의 제자로 슈어 보조정리·슈어 곱·슈어 검사법 등 온갖 곳에 이름을 남겼고, 그 결과 “슈어 무엇”이라는 용어를 만나면 일단 어느 슈어인지 확인하는 습관이 생긴다. 참고로 슈어 본인은 이 행렬을 “보수”라고 부른 적이 없다. 1917년 논문에서 유계 해석함수 문제를 다루다 행렬식 항등식으로 잠깐 썼을 뿐이고, 이름은 51년 뒤 에밀리 헤인즈워스가 붙였다. ↩

2. 그래서 상용 구조해석 코드의 “슈퍼요소”·“부분구조” 기능을 쓰는 엔지니어는 자기도 모르게 슈어 보수를 쓰고 있다. 참고로 동역학에서 관성항까지 함께 응축하는 구얀 축약은 이것과 비슷해 보이지만 근사다 — 내부 관성을 버리기 때문에 주파수가 높아질수록 틀린다. 정적 응축은 정확하고 구얀은 근사라는 구분을 놓치면 모드 해석 결과가 조용히 틀린다. ↩

3. 대칭 양정치에서는 $S \preceq D$ 가 항상 성립한다. 정보를 더 받았는데 불확실성이 늘어나는 일은 없다는 뜻이고, 이 부등식이 칼만 필터의 공분산이 갱신 단계마다 줄어드는 것을 보장한다. 반대로 코드에서 $P^+$ 가 커지거나 비대칭이 되면 그건 물리가 아니라 반올림이며, 조지프 형식으로 갱신식을 다시 쓰는 것이 표준 처방이다. ↩