셔먼-모리슨 공식

1. 개요

셔먼-모리슨 공식 Sherman–Morrison Formula
발표	잭 셔먼 · 윈프리드 모리슨 (1949 초록, 1950 논문)
하는 일	랭크-1 수정된 행렬의 역행렬을 원래 역행렬로 표현
비용	역행렬 갱신 O(n2), 풀이 2회로 쓰면 원 솔버 비용 × 2
일반화	우드버리 항등식 (랭크-k)
조건	1 + vTA−1u ≠ 0

행렬 하나를 살짝 고쳤다고 역행렬을 처음부터 다시 구할 필요는 없다.

셔먼-모리슨 공식(Sherman–Morrison formula)은 가역행렬 $A$ 에 랭크-1 행렬 $\mathbf u\mathbf v^{\mathsf T}$ 를 더한 행렬의 역을 $A^{-1}$ 로부터 닫힌꼴로 주는 항등식이다.

$$(A + \mathbf u\mathbf v^{\mathsf T})^{-1} = A^{-1} - \frac{A^{-1}\mathbf u\,\mathbf v^{\mathsf T}A^{-1}}{1 + \mathbf v^{\mathsf T}A^{-1}\mathbf u}.$$

공식 자체는 한 줄이지만 쓰임새는 넓다. 브로이던 방법·BFGS 같은 준-뉴턴법이 역 야코비안·역 헤시안을 $O(n^2)$ 에 고치는 근거이고, 주기경계조건이 걸린 순환 삼중대각계를 토머스 알고리즘 두 번으로 푸는 트릭이며, 칼만 필터·재귀 최소제곱의 갱신식이 이것의 행렬판이다. 이 문서는 공식이 역행렬을 안 만들고 쓰일 때 진짜 힘을 낸다는 점, 그리고 분모가 0 에 가까워질 때의 함정을 중심으로 정리한다.

2. 유도와 검증

증명은 곱해 보면 끝난다. $\alpha = 1 + \mathbf v^{\mathsf T}A^{-1}\mathbf u$ 라 두고 우변을 $A+\mathbf u\mathbf v^{\mathsf T}$ 에 곱하면

$$(A+\mathbf u\mathbf v^{\mathsf T})\Bigl(A^{-1} - \tfrac{1}{\alpha}A^{-1}\mathbf u\mathbf v^{\mathsf T}A^{-1}\Bigr) = I + \mathbf u\mathbf v^{\mathsf T}A^{-1} - \tfrac{1}{\alpha}\bigl(1 + \mathbf v^{\mathsf T}A^{-1}\mathbf u\bigr)\mathbf u\mathbf v^{\mathsf T}A^{-1} = I.$$

괄호 안의 스칼라가 정확히 $\alpha$ 라서 상쇄된다. 유도 쪽으로 보면, 랭크-1 수정은 “스칼라 $1/(1+x)$ 를 행렬로 올린 것”이다. $(I + \mathbf a\mathbf b^{\mathsf T})^{-1} = I - \mathbf a\mathbf b^{\mathsf T}/(1+\mathbf b^{\mathsf T}\mathbf a)$ 는 $(\mathbf a\mathbf b^{\mathsf T})^k = (\mathbf b^{\mathsf T}\mathbf a)^{k-1}\mathbf a\mathbf b^{\mathsf T}$ 를 이용해 노이만 급수를 더하면 바로 나오고, $A + \mathbf u\mathbf v^{\mathsf T} = A(I + A^{-1}\mathbf u\mathbf v^{\mathsf T})$ 로 묶으면 위 공식이 된다.

가역 조건도 같은 자리에서 나온다. 행렬식 보조정리

$$\det(A + \mathbf u\mathbf v^{\mathsf T}) = \bigl(1 + \mathbf v^{\mathsf T}A^{-1}\mathbf u\bigr)\det A$$

에 따라, 분모 $\alpha$ 가 0 이면 수정된 행렬이 특이하다. 분모는 장식이 아니라 가역성 판정식이다.

2.1. 우드버리 항등식

$U$, $V$ 가 $n\times k$ 이고 $C$ 가 $k\times k$ 일 때 랭크-$k$ 수정으로 일반화한 것이 우드버리 항등식(Woodbury, 1950)이다.

$$(A + UCV^{\mathsf T})^{-1} = A^{-1} - A^{-1}U\bigl(C^{-1} + V^{\mathsf T}A^{-1}U\bigr)^{-1}V^{\mathsf T}A^{-1}.$$

$n\times n$ 역행렬 대신 $k\times k$ 하나만 풀면 된다는 게 요점이다. $k \ll n$ 이면 압도적으로 싸다. 이 블록 버전은 슈어 보수를 두 방향으로 쓴 결과와 같고, 이름이 여럿 붙어 있어 문헌마다 “셔먼-모리슨-우드버리”로 묶어 부르기도 한다.¹

3. 역행렬 없이 쓰는 법

교과서 공식을 그대로 읽으면 ”$A^{-1}$ 을 갖고 있어야 쓸 수 있다”는 오해가 생긴다. 실무의 정석은 반대다. $A$ 에 대한 빠른 솔버만 있으면 된다. $(A + \mathbf u\mathbf v^{\mathsf T})\mathbf x = \mathbf b$ 를 풀려면

1. $A\mathbf y = \mathbf b$ 를 푼다.
2. $A\mathbf z = \mathbf u$ 를 푼다.
3. $\mathbf x = \mathbf y - \dfrac{\mathbf v^{\mathsf T}\mathbf y}{1 + \mathbf v^{\mathsf T}\mathbf z}\,\mathbf z.$

$A$ 가 삼중대각·띠·희소·FFT로 대각화되는 행렬이면 원래 구조를 깨는 랭크-1 꼬리가 붙어도 원래 솔버를 그대로 두 번 돌리면 된다. 수정된 행렬을 직접 분해하면 구조가 깨져 비용이 급등하는데, 이 우회가 구조를 지켜 준다.

3.1. 검산 — 순환 삼중대각계

토머스 알고리즘 문서의 주기경계 처방을 직접 돌렸다. $n=10$, 대각 2.2, 비대각 $-1$, 모서리 $(1,n)$·$(n,1)$ 에 $-1$ 이 붙은 순환 삼중대각 $A$ 에 우변 $b_i = \sin i$ 를 걸었다. 모서리 두 개를 $\mathbf u\mathbf v^{\mathsf T}$ 로 떼어 낸다 — 대각을 $d_i$ 라 쓰고 $\gamma = -d_1$ 로 잡아 $\mathbf u = (\gamma,0,\dots,0,p)^{\mathsf T}$, $\mathbf v = (1,0,\dots,0,q/\gamma)^{\mathsf T}$, 그리고 순수 삼중대각 부분의 첫 대각을 $d_1-\gamma$, 끝 대각을 $d_n - pq/\gamma$ 로 고친다(여기서 $p$ 는 $(n,1)$, $q$ 는 $(1,n)$ 모서리 값). 토머스를 우변 $\mathbf b$ 와 $\mathbf u$ 에 한 번씩 돌린 결과를 위 3단계로 합쳤더니, 부분 피벗 가우스 소거로 푼 기준해와의 최대 차이가 $6.7\times10^{-16}$ 이었다. 기계정밀도 그대로다. $\gamma = -d_1$ 로 잡는 이유는 첫 대각 $d_1-\gamma = 2d_1$ 이 0 근처로 떨어지지 않게 해 토머스의 피벗을 보호하려는 것이다.

4. 분모가 작을 때 — 소거와 불안정

공식이 정확하다는 것과 수치적으로 안전하다는 것은 다른 얘기다. 분모 $\alpha = 1 + \mathbf v^{\mathsf T}A^{-1}\mathbf u$ 가 1 근처의 두 수의 차로 0 에 가까워지면 파국적 상쇄가 일어난다. $\mathbf v^{\mathsf T}A^{-1}\mathbf u = -1 + \varepsilon$ 을 배정밀도로 만들어 1 을 더해 보면

의도한 $\varepsilon$	계산된 $\alpha$	상대오차
$10^{-2}$	$1.0000000000000009\times10^{-2}$	~$10^{-16}$
$10^{-6}$	$1.0000000000287557\times10^{-6}$	~$3\times10^{-11}$
$10^{-10}$	$1.000000082740371\times10^{-10}$	~$8\times10^{-8}$

상대오차가 대략 $u/\varepsilon$ ($u\approx1.1\times10^{-16}$) 로 커진다. 이 오차가 보정항 전체에 곱해지므로, $\alpha$ 가 작다는 것은 “수정된 행렬이 거의 특이하다”는 물리적 신호이자 “이 공식으로 얻은 답의 자릿수가 깎였다”는 수치적 신호다. 해거(Hager, 1989)의 리뷰가 강조하듯, 갱신을 연쇄적으로 쌓을 때 이 오차가 누적되는 것이 진짜 문제다.

그래서 실무 규칙이 둘 생겼다.

• 역행렬이 아니라 분해를 갱신하라. 준뉴턴 코드는 $B^{-1}$ 을 직접 들고 다니는 대신 촐레스키나 QR 인자를 랭크-1 갱신한다. 분해 갱신(예: 기븐스 회전 기반)은 역행렬 갱신보다 반올림 오차에 훨씬 강하다.
• 주기적으로 다시 시작하라. 갱신이 수십~수백 번 쌓이면 원래 행렬로 한 번 새로 분해한다. 시뮬레이션에서 시간 스텝마다 행렬이 조금씩 바뀌는 경우에도 같은 원칙이다.

5. 어디에 숨어 있나

• 준-뉴턴 갱신. 좋은 브로이던의 역행렬형, BFGS의 역 헤시안 갱신 $H_{k+1}$ 이 이 공식을 한두 번 적용한 결과다. 덕분에 반복당 비용이 $O(n^3)$ 에서 $O(n^2)$ 로 떨어진다.
• 재귀 최소제곱·칼만 필터. 관측 하나가 들어올 때마다 정규방정식 행렬 $X^{\mathsf T}X$ 에 랭크-1 $\mathbf x\mathbf x^{\mathsf T}$ 가 더해진다. 역공분산을 셔먼-모리슨으로 갱신한 것이 재귀 최소제곱이고, 칼만 이득 식의 $(HPH^{\mathsf T}+R)^{-1}$ 꼴이 우드버리의 흔적이다. 관측 차원 $k$ 가 상태 차원 $n$ 보다 작을 때 $k\times k$ 만 뒤집는 쪽이 이득이라 그 꼴이 표준이 됐다.
• 가우시안 프로세스와 저랭크 근사. 커널 행렬을 대각 + 저랭크($\sigma^2 I + UU^{\mathsf T}$)로 근사하면 우드버리로 $n\times n$ 대신 $k\times k$ 를 뒤집는다. 희소 GP·유도점 방법의 계산 골격이다.
• 교차검증·영향 진단. 데이터 한 점을 뺀 회귀(leave-one-out)를 $n$ 번 다시 풀지 않고, 한 점 제거를 랭크-1 하향 갱신으로 처리하면 모든 LOO 잔차가 한 번에 나온다.²
• 경계요소법·구조 재해석. 구조물의 부재 하나의 강성만 바꾼 설계 변경을 전체 재조립 없이 재해석하는 “구조 재해석”(structural reanalysis) 기법들이 이 갱신의 공학판이다.

6. 관련 문서

• 브로이던 방법 · 준-뉴턴법 · 할선법 · 토머스 알고리즘
• 슈어 보수 · 저랭크 근사 · LU 분해 · 촐레스키 분해
• 칼만 필터 · 재귀 최소제곱 · 가우시안 프로세스 · 조건수
• 주기경계조건 · 순환 축소 · 구조 재해석

7. Footnotes

1. 해거의 리뷰에 따르면 이 계열 공식은 셔먼·모리슨 이전에도 이미 여러 번 발견됐고, 바틀렛(Bartlett, 1951)도 같은 식을 냈다. 이름 붙은 순서와 발견된 순서가 다른 수치해석 국룰이 여기서도 성립. ↩

2. 선형회귀에서 LOO 잔차가 $e_i/(1-h_{ii})$ ($h_{ii}$ 는 해트 행렬 대각)라는 유명한 공식이 바로 이 랭크-1 하향 갱신의 결과다. 교차검증을 $n$ 번 돌리던 사람이 이걸 알면 현생이 길어진다. ↩