앤더슨 가속

1. 개요

앤더슨 가속 Anderson Acceleration
고안	도널드 G. 앤더슨 (1965)
다른 이름	앤더슨 혼합, DIIS(풀라이, 1980), 다중 할선 갱신의 한 형태
대상	고정점 반복 x = g(x)
손잡이	창 깊이 m, 혼합 계수 β
반복당 비용	g 평가 1회 + 크기 m 최소제곱
선형 문제에서	m = ∞ 이면 GMRES와 본질적으로 동치

고정점 반복이 느리면, 지난 $m$ 번의 실수를 모아서 다음 수를 고른다.

앤더슨 가속(Anderson acceleration)은 고정점 반복 $\mathbf x_{k+1} = g(\mathbf x_k)$ 의 수렴을 빠르게 하려고, 최근 $m+1$ 개 반복의 잔차 $\mathbf f_j = g(\mathbf x_j) - \mathbf x_j$ 를 가장 작게 만드는 선형결합을 최소제곱으로 고르고 그 결합으로 다음 반복점을 만드는 기법이다. 야코비안이 필요 없고 기존 코드의 $g$ 를 블랙박스로 감싸기만 하면 되며, 반복당 추가 비용은 $m$ 차원 최소제곱 하나뿐이다.

1965년 앤더슨이 비선형 적분방정식용으로 내놓았고, 1980년 풀라이(Pulay)가 양자화학의 SCF 반복에 독립적으로 같은 아이디어를 DIIS(direct inversion in the iterative subspace)라는 이름으로 도입했다.¹ 이후 수십 년간 계산화학에서는 DIIS·앤더슨 혼합으로, 응용수학에서는 거의 잊힌 채로 살다가, 워커·니(2011)의 논문이 선형 문제에서 GMRES와 동치임을 보이면서 수치해석 주류로 돌아왔다. 브로이던 방법이 그 SCF 혼합기 계보를 짧게 언급하는데, 이 문서는 그 알고리즘 자체와 수렴 성질, 그리고 깊이 $m$ 을 고르는 실무를 판다.

2. 알고리즘

고정점 문제 $\mathbf x = g(\mathbf x)$ 와 잔차 $\mathbf f(\mathbf x) = g(\mathbf x) - \mathbf x$ 를 생각한다. 그냥 반복(피카르 반복)은 $g$ 가 축약 사상이면 바나흐 고정점 정리에 따라 수렴하지만, 축약률 $\rho$ 가 1 에 가까우면 기어간다.

앤더슨 가속 AA($m$)은 $k$ 번째 반복에서 창 깊이 $m_k = \min(m,k)$ 를 두고

1. 최근 잔차들 $\mathbf f_{k-m_k},\dots,\mathbf f_k$ 로 다음 제약 최소제곱을 푼다.

$$\min_{\alpha}\Bigl\|\sum_{j=0}^{m_k}\alpha_j\,\mathbf f_{k-m_k+j}\Bigr\|_2 \quad\text{s.t.}\quad \sum_j \alpha_j = 1.$$

2. 같은 계수로 $g$ 값을 섞는다.

$$\mathbf x_{k+1} = \sum_{j=0}^{m_k}\alpha_j\,g(\mathbf x_{k-m_k+j}).$$

합이 1 인 제약은 차분으로 바꾸면 사라진다. $\Delta\mathbf f_j = \mathbf f_{j+1}-\mathbf f_j$ 를 열로 모은 $\mathcal F_k$, 마찬가지로 $g$ 차분을 모은 $\mathcal G_k$ 를 두면

$$\gamma_k = \arg\min_\gamma \|\mathbf f_k - \mathcal F_k\gamma\|_2, \qquad \mathbf x_{k+1} = g(\mathbf x_k) - \mathcal G_k\gamma_k$$

가 된다. 실제 구현은 이 비제약형을 쓰고, 최소제곱은 정규방정식이 아니라 $\mathcal F_k$ 의 QR 분해를 창이 밀릴 때마다 갱신·하향 갱신하며 푼다. 차분 열들이 거의 선형종속이 되기 쉬워 정규방정식은 조건수를 제곱해 버리기 때문이다.

혼합 계수 $\beta \in (0,1]$ 를 넣으면 $\mathbf x_{k+1} = (\text{위 식}) - (1-\beta)(\mathbf f_k - \mathcal F_k\gamma_k)$ 꼴로, 결합된 잔차의 일부만 반영한다. SCF 코드의 “mixing parameter”가 이것이다. $m=0$ 이면 단순 혼합 $\mathbf x_{k+1} = \mathbf x_k + \beta\mathbf f_k$ 로 돌아간다.

3. 무엇을 하고 있는가 — 세 가지 얼굴

다중 할선 준뉴턴. 팡·사드(2009)는 AA 가 역 야코비안 근사 $H_k$ 에 대해 최근 $m$ 개 할선 조건 $H_k\Delta\mathbf f_j = \Delta\mathbf x_j$ 를 한꺼번에 만족시키는 최소 변경 갱신과 같음을 보였다. 브로이던 방법이 마지막 관측 하나에 맞추는 랭크-1 갱신이라면, AA 는 $m$ 개에 동시에 맞추는 랭크-$m$ 갱신이다. 1차원 할선법에서 출발한 계보의 다변수·다점 버전인 셈. 이 관점에서 앤더슨 쪽은 “2형(나쁜) 브로이던”에 해당하는 역행렬 직접 갱신에 가깝다.

선형 문제에서는 GMRES. $g(\mathbf x) = M\mathbf x + \mathbf c$ 이면 고정점 문제는 선형계 $(I-M)\mathbf x = \mathbf c$ 이고, 워커·니(2011)는 창을 자르지 않은 AA($\infty$)의 반복점이 같은 계에 대한 GMRES 반복점과 한 스텝 어긋나 정확히 대응함을 보였다(정체가 없다는 조건 아래). 잔차를 지난 잔차들의 결합으로 최소화한다는 점에서 GMRES 가 크리로프 부분공간에서 하는 일과 같다. AA 는 행렬 없이 쓰는 비선형 GMRES 라고 요약할 수 있다.

외삽. 수열 가속의 관점에서는 리처드슨 외삽법·에이트킨 $\Delta^2$ 의 벡터판, 특히 최소다항식 외삽(MPE)·축소 랭크 외삽(RRE)과 가까운 친척이다. 차이는 외삽 결과를 반복에 다시 넣는다는 것 — AA 는 사후 처리가 아니라 반복 자체를 바꾼다.

4. 수렴 — 무엇이 보장되고 무엇이 안 되나

토스·켈리(2015)가 처음 정리한 국소 결과는 냉정하다. $g$ 가 축약률 $c<1$ 인 축약이면 AA($m$)는 국소적으로 수렴하고, 잔차의 R-선형 수렴률이 피카르의 $c$ 보다 나쁘지 않다. 즉 이론이 보장하는 건 “느려지지 않는다”이지 “빨라진다”가 아니다. 실제 가속량은 문제의 스펙트럼과 창 깊이에 달려 있고, 이후 연구들이 그 가속 인자를 최소제곱 이득으로 정량화했다.

수렴 보장이 약한 대신 축약이 아닌 $g$ — 피카르 반복이 아예 발산하는 경우 — 에서도 AA 가 수렴하는 사례가 흔하다. 다중 할선 관점에서 보면 이건 뉴턴 비슷한 일을 하고 있으니 이상한 일이 아니다. 하지만 전역 수렴은 보장되지 않으므로 실무 코드는 잔차가 늘면 창을 비우고 다시 시작하는 안전장치를 둔다.

4.1. 검산 — 야코비 반복을 가속해 본다

1차원 푸아송 $-u''=1$ 을 내부점 $n=50$ 개로 이산화하고 야코비 방법을 고정점 사상 $g$ 로 삼았다. 야코비 반복 행렬의 스펙트럼 반지름은 $\cos(\pi/51)\approx0.9981$ 이라 극단적으로 느리다. 잔차를 초기의 $10^{-10}$ 배로 줄이는 데 걸린 반복 수(비제약형, QR 최소제곱, $\beta=1$):

방법	반복 수
피카르(야코비 그대로)	12,079
AA(1)	5,000 회 안에 미달
AA(2)	2,246
AA(5)	3,059
AA(10)	734
AA(20)	206
AA(50)	26
참고: 재시작 없는 GMRES, 같은 선형계	25

읽을거리가 셋이다. 첫째, 창이 문제 차원만큼 깊으면 GMRES 와 한 스텝 차이로 일치한다(26 대 25) — 워커·니 동치가 숫자로 보인다. 둘째, $m$ 이 작을 때 단조롭지 않다. AA(5) 가 AA(2) 보다 느렸고 AA(1) 은 사실상 정체했다. 야코비 행렬의 고유값이 $\pm$ 대칭으로 붙어 있어 짧은 창이 그 쌍을 제대로 못 잡는 탓으로 보이며, 재시작 GMRES 가 짧은 재시작 길이에서 정체하는 현상과 같은 계열이다. 셋째, 그럼에도 AA(10) 만 돼도 피카르의 1/16 이다. 이 문제는 원래 켤레기울기법이나 다중격자법으로 풀어야 할 대상이지만, 선형 솔버를 갈아끼울 수 없는 레거시 고정점 코드를 바깥에서 감싸 이만큼 얻는다는 게 AA 의 효용이다.²

5. 실무 — 어디서 쓰고 어떻게 고르나

• 전자구조 SCF. 콘-샴 방정식·하트리-폭 방법의 자기일관 반복이 최대 고객이다. 양자화학 코드의 DIIS 는 대개 잔차로 포크 행렬과 밀도 행렬의 교환자 $FPS - SPF$ 를 쓰고, 평면파 DFT 코드(VASP 등)의 풀라이·브로이던 혼합은 전하 밀도 잔차에 커플링 전처리(커커 전처리)를 얹어 쓴다. 금속·큰 셀에서 “전하 출렁임”(charge sloshing)을 잡는 건 깊이보다 전처리의 몫이다.
• 다물리 연성. 유체-구조 연성(유체-구조 연성)의 분할 해법은 유체 솔버와 구조 솔버를 번갈아 부르는 고정점 반복이다. 두 솔버를 고치지 않고 경계 변위만 AA 로 가속하는 것이 preCICE 같은 연성 라이브러리의 표준 기능이 됐다(IQN-ILS 라는 이름으로 불리는 준뉴턴 계열이 같은 뿌리다).
• 비선형 PDE·최적화. 피카르 선형화로 푸는 비뉴턴 유동, 교대 최적화(ADMM 등), 기댓값 최대화 알고리즘도 고정점 반복이라 AA 가 그대로 붙는다. PETSc 의 SNESANDERSON, SUNDIALS KINSOL 의 앤더슨 옵션처럼 범용 비선형 솔버 라이브러리에 내장돼 있다.

깊이 $m$ 은 경험적으로 3~10 이 국룰이다.³ 너무 크면 차분 열이 선형종속에 가까워져 최소제곱이 나빠지고(QR 에서 작은 대각을 버리는 필터링이 필요해진다), 너무 작으면 위 검산처럼 가속이 빈약하다. $\beta$ 는 SCF 에서 0.1~0.5 처럼 작게 시작하는 경우가 많고, 일반 고정점에서는 1 에서 시작해 발산 기미가 보이면 줄인다.

6. 관련 문서

• 브로이던 방법 · 할선법 · 준-뉴턴법 · 뉴턴-크리로프법
• GMRES · 크리로프 부분공간법 · 야코비 방법 · 바나흐 고정점 정리
• 고정점 반복 · 피카르 반복 · 리처드슨 외삽법 · QR 분해
• 콘-샴 방정식 · 하트리-폭 방법 · VASP · 유체-구조 연성

7. Footnotes

1. 같은 알고리즘이 분야마다 이름이 달라서, 화학자에게 “앤더슨 가속 써 봤어?”라고 물으면 모른다고 하고 “DIIS 켰어?”라고 물으면 당연하다고 한다. 풀라이가 앤더슨을 모른 채 같은 걸 다시 만든 것부터가 이 분야 이름 혼란의 시작이다. ↩

2. “솔버는 20년 된 포트란이고 아무도 못 건드린다, 근데 빨리 돌려야 한다” — 이게 앤더슨 가속이 2010년대에 부활한 진짜 이유라는 우스개가 있다. 우스개치고는 꽤 정확하다. ↩

3. “m 은 얼마로 하죠?”에 대한 정답은 늘 “5 넣고 돌려 봐”다. 수렴은 신에게 맡기되, 창 깊이는 5에게 맡긴다. ↩