노이만 급수

1. 개요

노이만 급수 Neumann series
식	$(I-T)^{-1}=\sum_{k\ge0}T^k$
충분 조건	어떤 유도 노름에서 $\lVert T\rVert<1$
필요충분	스펙트럼 반지름 $\rho(T)<1$
역의 한계	$\lVert(I-T)^{-1}\rVert\le 1/(1-\lVert T\rVert)$
이름	카를 노이만 (19세기 퍼텐셜 이론)
다른 이름	리우빌-노이만 급수, 본 급수, 레온티예프 역행렬 전개

$\frac{1}{1-x}=1+x+x^2+\cdots$ 를 행렬에도 해도 된다. 조건만 지키면.

노이만 급수(Neumann series)는 선형 연산자 $T$ 의 크기가 1보다 작을 때 $I-T$ 의 역을 기하급수 $\sum_{k=0}^{\infty}T^k$ 로 나타내는 전개다. 스칼라 등비급수 $1/(1-x)=\sum x^k$ 의 연산자판이고, 19세기 독일 수학자 카를 노이만이 퍼텐셜 이론의 적분방정식을 풀며 쓴 데서 이름이 왔다.

식 자체는 한 줄이지만 쓰임새가 넓다. 수치해석에서는 세 가지 다른 얼굴로 나타난다. (1) 행렬이 섭동을 받아도 역행렬이 존재하고 얼마나 바뀌는지를 재는 섭동 보조정리, (2) 정상 반복법과 다항식 전처리기의 정체, (3) 적분방정식·산란 이론에서 해를 차수별로 쌓아 가는 반복 대입이다. 이 문서는 세 얼굴을 차례로 보고, 수렴 조건을 숫자로 확인한다. 노름·완비성 같은 기초는 바나흐 공간과 유도 노름 문서에, 그래프 위에서 이 급수를 “모든 경로의 가중합”으로 읽는 해석은 페이지랭크에 있다.

2. 정리와 증명

정리. $X$ 가 바나흐 공간이고 $T$ 가 유계 선형 연산자이며 어떤 유도 노름에서 $\lVert T\rVert<1$ 이면, $I-T$ 는 가역이고

$$(I-T)^{-1}=\sum_{k=0}^{\infty}T^k,\qquad \big\lVert (I-T)^{-1}\big\rVert\le\frac{1}{1-\lVert T\rVert}.$$

증명. 부분합 $S_m=\sum_{k=0}^{m}T^k$ 에 대해 $\lVert T^k\rVert\le\lVert T\rVert^k$ 이므로 $\sum\lVert T^k\rVert$ 는 수렴하는 등비급수로 눌린다. 연산자 공간이 완비이므로 $S_m$ 은 어떤 $S$ 로 수렴한다. 그리고 망원급수(telescoping) 항등식

$$(I-T)S_m = S_m(I-T) = I - T^{m+1}$$

에서 $m\to\infty$ 이면 $T^{m+1}\to0$ 이므로 $(I-T)S=S(I-T)=I$ 다. 노름 한계는 등비급수 합 그대로다. $\blacksquare$

같은 계산에서 절단 오차도 바로 나온다.

$$\Big\lVert (I-T)^{-1}-S_m\Big\rVert=\Big\lVert \sum_{k>m}T^k\Big\rVert\le\frac{\lVert T\rVert^{m+1}}{1-\lVert T\rVert}.$$

2.1. 필요충분 조건은 스펙트럼 반지름이다

$\lVert T\rVert<1$ 은 충분 조건일 뿐이다. 겔판트 공식 $\rho(T)=\lim_k\lVert T^k\rVert^{1/k}$ 와 근 판정법을 쓰면 급수는 $\rho(T)<1$ 일 때만, 그리고 그때 항상 수렴한다. $\rho(T)\ge1$ 이면 $\lVert T^k\rVert\ge\rho(T)^k\ge1$ 이라 항이 0으로 가지 않는다. 유한 차원에서는 ”$\rho(T)<1$ 이면 $\lVert T\rVert_\ast<1$ 인 어떤 노름이 존재한다”는 정리가 성립하므로, 두 조건의 차이는 결국 어느 노름으로 재느냐의 문제다. 스펙트럼 반지름 문서가 이 대목을 자세히 다룬다.

3. 숫자로 확인

정규에 가까운 경우. $T=\begin{pmatrix}0.5&0.2\\0.1&0.4\end{pmatrix}$ 이면 고유값이 $0.6,\,0.3$ 이라 $\rho=0.6$, 2-노름은 $\lVert T\rVert_2\approx0.611$ 이다. 정확한 역은

$$(I-T)^{-1}=\frac{1}{0.28}\begin{pmatrix}0.6&0.2\\0.1&0.5\end{pmatrix}\approx\begin{pmatrix}2.143&0.714\\0.357&1.786\end{pmatrix}$$

이고, 부분합 $S_{m}$ (항 $m+1$ 개)의 2-노름 오차를 직접 계산하면 다음과 같다.

항 개수	1	5	10	20	40
오차	1.55	0.205	1.59e-2	9.6e-5	3.5e-9
한계 $\lVert T\rVert^{m+1}/(1-\lVert T\rVert)$	1.57	0.219	1.86e-2	1.4e-4	7.1e-9

오차가 10항마다 대략 $0.6^{10}\approx0.006$ 배씩 줄어든다. 수렴 속도를 정하는 게 $\rho$ 라는 것이 보이고, 노름 한계는 살짝 위에서 오차를 잘 덮는다. $\lVert(I-T)^{-1}\rVert_2=2.537$ 도 한계 $1/(1-0.611)=2.57$ 아래다.

비정규인 경우. $T=\begin{pmatrix}0.5&10\\0&0.5\end{pmatrix}$ 는 $\rho=0.5$ 로 더 작지만 $\lVert T\rVert_2\approx10.02$ 다. 노름 판정은 아무것도 보장하지 못하는데, $\rho<1$ 이니 급수는 수렴한다. 정확한 역은 $\begin{pmatrix}2&40\\0&2\end{pmatrix}$ 이고 오차는

항 개수	1	2	3	5	10	20
오차	40.0	30.0	20.0	7.50	0.430	8.0e-4

로, 처음 몇 항은 오차가 거의 줄지 않는다. $T^k$ 의 비대각 성분이 $10k\cdot0.5^{k-1}$ 꼴로 한동안 커지기 때문이다. 스펙트럼 반지름은 점근 속도만, 노름은 전 구간을 말한다. 이 차이가 비정규 행렬 문서의 주제 “고유값은 안정한데 과도 성장한다”의 급수판이다.¹

4. 첫 번째 얼굴 — 섭동 보조정리

$A$ 가 가역이고 섭동 $E$ 가 $\lVert A^{-1}E\rVert<1$ 을 만족하면 $A+E=A(I+A^{-1}E)$ 이고, 괄호가 노이만 급수로 가역이므로 $A+E$ 도 가역이다. 이게 흔히 바나흐 보조정리라 부르는 결과이고, 정리하면

$$\big\lVert (A+E)^{-1}\big\rVert\le\frac{\lVert A^{-1}\rVert}{1-\lVert A^{-1}\rVert\,\lVert E\rVert},\qquad \frac{\lVert (A+E)^{-1}-A^{-1}\rVert}{\lVert A^{-1}\rVert}\le\frac{\kappa(A)\,\frac{\lVert E\rVert}{\lVert A\rVert}}{1-\kappa(A)\frac{\lVert E\rVert}{\lVert A\rVert}}$$

다. $\kappa(A)=\lVert A\rVert\lVert A^{-1}\rVert$ 는 조건수다. 두 가지 결론이 바로 나온다.

• 상대 섭동이 $1/\kappa$ 보다 작으면 가역성은 안전하다. 거꾸로, 가장 가까운 특이 행렬까지의 상대 거리는 $1/\kappa$ 이상이다(2-노름에서는 정확히 $1/\kappa_2$ 이고, 그 특이 행렬은 특이값 분해의 최소 특이값을 지운 것이다).
• 역행렬의 상대 오차는 입력 상대 오차의 약 $\kappa$ 배다. 선형계 오차 해석의 “조건수 곱하기 기계 엡실론” 규칙이 정확히 여기서 나온다.

5. 두 번째 얼굴 — 반복법과 다항식 전처리

$A=M-N$ 으로 쪼개고 $x_{k+1}=M^{-1}Nx_k+M^{-1}b$ 를 반복하는 정상 반복법(반복법의 야코비·가우스-자이델이 이것)에서 $T=M^{-1}N$, $c=M^{-1}b$ 로 두고 $x_0=0$ 에서 출발하면

$$x_k=\sum_{j=0}^{k-1}T^j c .$$

정상 반복법은 노이만 급수의 부분합을 한 항씩 계산하는 것과 정확히 같다. 수렴 조건이 $\rho(T)<1$ 인 것도, 수렴 속도가 $\rho(T)$ 로 정해지는 것도 위 정리에서 그대로 따라온다. 가장 단순한 경우 $M=\omega^{-1}I$ 가 리처드슨 반복이다.

같은 관찰을 거꾸로 쓰면 다항식 전처리기가 된다. $A=D(I-T)$ 꼴로 쓰고($D$ 는 대각, $T=I-D^{-1}A$)

$$A^{-1}\approx\Big(\sum_{k=0}^{m}T^k\Big)D^{-1}$$

를 전처리기로 쓴다. 이 근사는 행렬-벡터 곱만으로 적용되므로 삼각 풀이처럼 순차적인 부분이 없다. 1979년 뒤부아·그린바움·로드리그가 벡터 슈퍼컴퓨터에서 바로 이 이유로 제안했고, 지금은 GPU 에서 같은 이유로 다시 쓰인다. 다만 절단 노이만 급수는 차수 $m$ 짜리 다항식 중 최적이 아니다. 고유값이 들어 있는 구간을 알면 체비쇼프 다항식으로 같은 차수에서 더 좋은 근사를 얻고, 크리로프 부분공간법은 아예 매 단계 최적 다항식을 자동으로 고른다. 크리로프 방법이 정상 반복법을 이기는 이유를 한 줄로 말하면 “노이만 다항식에 고정되지 않아서”다.

6. 세 번째 얼굴 — 적분방정식과 본 급수

제2종 프레드홀름 적분방정식

$$u(x)=f(x)+\lambda\int_a^b K(x,y)\,u(y)\,dy,\qquad u=f+\lambda\mathcal K u$$

에서 $\lvert\lambda\rvert\,\lVert\mathcal K\rVert<1$ 이면 $u=\sum_k\lambda^k\mathcal K^k f$ 로 풀린다. 이걸 리우빌-노이만 급수라 하고, 실제 계산은 ”$u_0=f$, $u_{k+1}=f+\lambda\mathcal K u_k$” 의 반복 대입이다. 적분 구간이 $x$ 까지로 잘린 볼테라형 핵이면 $\lVert\mathcal K^k\rVert\le M^k(b-a)^k/k!$ 이 되어 모든 $\lambda$ 에서 수렴한다. 반복 적분이 계승으로 눌리기 때문이고, 상미분방정식 해의 존재를 보이는 피카르 반복이 같은 구조다. 경계요소법이 다루는 경계 적분방정식도 제2종으로 세우면 이 성질 덕분에 반복 풀이기가 잘 듣는다.

양자 산란에서는 리프만-슈윙거 방정식 $\psi=\phi+G_0V\psi$ 가 같은 꼴이다. $G_0$ 는 자유 입자의 그린 함수, $V$ 는 퍼텐셜이다. 이걸 펼친

$$\psi=\phi+G_0V\phi+G_0VG_0V\phi+\cdots$$

를 본 급수(Born series)라 하고, 첫 보정항까지만 남긴 것이 본 근사다. 항 하나하나가 “퍼텐셜에 한 번, 두 번, … 산란된 파동”으로 읽힌다. 퍼텐셜이 약하거나 에너지가 높을 때 수렴하고, 속박 상태가 생길 만큼 강한 퍼텐셜에서는 저에너지에서 발산한다. 그때는 $G_0V$ 가 크기 1 이상인 고유값을 가져 $\rho(G_0V)<1$ 이 깨지기 때문이다.²

경제학에서도 똑같은 식이 나온다. 레온티예프의 투입산출 모형에서 최종 수요 $d$ 를 만들려면 총산출 $x=Ax+d$, 즉 $x=(I-A)^{-1}d=d+Ad+A^2d+\cdots$ 가 필요하다. $Ad$ 는 ”$d$ 를 만들기 위한 중간재”, $A^2d$ 는 “그 중간재를 만들기 위한 중간재”다. 경제가 굴러간다는 조건이 $\rho(A)<1$ 이라는 점까지 똑같다.³

7. 실전에서 쓸 때

• 수렴 판정은 $\rho$ 로, 오차 한계는 노름으로. $\lVert T\rVert<1$ 인 노름을 찾으면 사후 오차 한계까지 공짜로 얻는다. $\infty$-노름(행 합의 최댓값)은 손으로도 바로 계산된다.
• $\rho$ 가 1에 가까우면 쓰지 마라. 항 수가 대략 $\log\varepsilon/\log\rho$ 이므로 $\rho=0.99$ 면 $10^{-8}$ 까지 1800항이 넘는다. 이때는 크리로프 방법이나 직접 분해로 간다.
• 급수를 섕크스 변환으로 가속할 수 있다. 부분합이 기하수열로 수렴하는 지배 고유값이 하나뿐이면 에이트켄 외삽 한 번이 수렴을 크게 당긴다.
• 역을 통째로 만들지 마라. 필요한 건 대개 $(I-T)^{-1}b$ 라는 벡터이고, $T$ 를 벡터에 반복 적용하면 된다. 행렬 거듭제곱을 저장하면 희소성이 순식간에 사라진다.
• 저랭크 수정 $A+uv^\top$ 의 역은 노이만 급수가 아니라 셔먼-모리슨 공식으로 정확히 구한다. 랭크 1 섭동에서는 급수가 닫힌 꼴로 정리되는 셈이다.

8. 관련 문서

• 바나흐 공간 · 유도 노름 · 스펙트럼 반지름 · 비정규 행렬
• 조건수 · 특이값 분해 · 셔먼-모리슨 공식
• 반복법 · 전처리기 · 체비쇼프 다항식 · 크리로프 부분공간법 · 섕크스 변환
• 그린 함수 · 경계요소법 · 페이지랭크
• 리처드슨 반복 · 볼테라 적분방정식 · 레온티예프 투입산출 모형

9. Footnotes

1. 시험에 “노름이 1보다 크니 발산한다”라고 쓰면 감점이다. 노름이 1보다 큰 건 “이 노름으로는 모른다”는 뜻이지 발산의 증거가 아니다. 이걸 틀리는 게 국룰이라 출제자들이 아주 좋아한다. ↩

2. 그래서 핵물리 쪽 사람들은 본 급수를 “고에너지에서만 믿을 수 있는 친구”라고 부른다. 저에너지 핵력처럼 속박 상태(중양성자)를 만드는 강한 상호작용에서는 급수 대신 방정식을 직접 푼다. ↩

3. 바실리 레온티예프는 투입산출 분석으로 1973년 노벨 경제학상을 받았다. 경제학자가 "$\rho(A)<1$"을 “이 나라가 망하지 않을 조건”으로 읽는 걸 보면 수치해석 쪽 사람은 묘하게 뿌듯해진다. ↩