MINRES

1. 개요

MINRES Minimal Residual Method
대상	대칭(에르미트) 행렬, 부정치·특이 허용
최소화하는 것	크리로프 공간 위 잔차의 2-노름
뼈대	란초스 3항 점화식 + 기븐스 회전
메모리	반복 수와 무관 (벡터 몇 개)
전처리	대칭 양정치 전처리기만
제안	페이지 · 손더스, 1975

GMRES 가 하는 일을 똑같이 하는데, 행렬이 대칭이라는 사실 하나로 메모리 청구서가 사라진다.

MINRES(MINimal RESidual method)는 대칭 행렬 $A$ 에 대한 선형계 $A\mathbf{x} = \mathbf{b}$ 를, $k$ 번째 반복에서 크리로프 공간 $\mathcal{K}_k(A, \mathbf{b})$ 안의 해 중 잔차 $\lVert \mathbf{b} - A\mathbf{x}_k \rVert_2$ 가 가장 작은 것을 고르는 크리로프 부분공간법이다. 크리스 페이지와 마이클 손더스가 1975년 같은 논문에서 형제 기법 SYMMLQ 와 함께 발표했다¹.

$A$ 가 대칭이면 양정치가 아니어도 된다. 이게 핵심이다. 켤레기울기법은 $A$ 가 대칭 양정치(SPD)일 때만 안전하고, 고유값이 양쪽 부호에 걸쳐 있는 대칭 부정치 행렬에서는 $\mathbf{p}^\top A\mathbf{p} = 0$ 근처에서 깨진다. 비대칭용 GMRES 를 쓰면 풀리긴 하지만 기저 벡터를 전부 들고 다니느라 메모리와 직교화 비용이 반복마다 불어난다. MINRES 는 그 사이를 메운다 — GMRES 와 같은 최적성을, CG 와 같은 고정 메모리로 얻는다.

대칭 부정치 계는 생각보다 흔하다. 스토크스 유동·비압축 나비에-스토크스 방정식의 속도-압력 결합, 혼합유한요소법, 등식 제약 최적화의 KKT 계(그래서 라그랑주 승수법 이 나오는 곳마다), 헬름홀츠 방정식처럼 이동(shift)이 걸린 연산자, 고유값 문제의 shift-invert 내부 풀이가 다 그렇다. 이런 행렬들을 묶어 안장점 문제라고 부르는데, MINRES 는 거기서 사실상 기본 선택지다.

2. 유도 — 헤센베르크가 삼중대각으로 무너지면

GMRES 는 아놀디 알고리즘으로 정규직교 기저 $V_{k+1}$ 과 $(k+1)\times k$ 상부 헤센베르크 행렬 $\bar H_k$ 를 만들고, $A V_k = V_{k+1}\bar H_k$ 관계를 이용해 잔차 최소화를 작은 최소자승 문제로 바꾼다.

$A$ 가 대칭이면 $H_k = V_k^\top A V_k$ 도 대칭이다. 대칭인 상부 헤센베르크는 삼중대각밖에 없다. 그러면 아놀디의 긴 직교화가 란초스 알고리즘의 3항 점화식으로 줄어든다.

$$\beta_{k+1}\mathbf{v}_{k+1} = A\mathbf{v}_k - \alpha_k \mathbf{v}_k - \beta_k \mathbf{v}_{k-1}, \qquad A V_k = V_{k+1} \bar T_k .$$

여기서 $\bar T_k$ 는 대각 $\alpha_i$, 부대각 $\beta_i$ 를 가진 $(k+1)\times k$ 삼중대각 행렬이다. $\mathbf{x}_k = V_k \mathbf{y}$ 로 쓰고 $\mathbf{v}_1 = \mathbf{b}/\beta_1$ 이면 $V_{k+1}$ 의 열이 정규직교이므로

$$\lVert \mathbf{b} - A\mathbf{x}_k \rVert_2 = \lVert \beta_1 \mathbf{e}_1 - \bar T_k \mathbf{y} \rVert_2 .$$

즉 $n$ 차원 문제가 $(k+1)\times k$ 최소자승 문제가 된다. 여기까지는 GMRES 와 같다. 차이는 다음 단계에서 난다.

2.1. 기븐스 회전과 짧은 갱신

$\bar T_k$ 의 QR 분해를 기븐스 회전으로 한 열씩 갱신한다. 새 열이 들어올 때마다 직전 두 개의 회전을 적용하고 회전 하나를 새로 만들면 된다. 결과 $R_k$ 는 대각과 위쪽 두 줄만 0이 아닌 띠 폭 3짜리 상삼각이다.

해는 $\mathbf{x}_k = V_k R_k^{-1} \mathbf{t}_k$ 인데, $D_k = V_k R_k^{-1}$ 의 열 $\mathbf{d}_k$ 는 $R_k$ 의 띠 구조 덕에 3항 점화식으로 나온다.

$$\mathbf{d}_k = \frac{\mathbf{v}_k - \varepsilon_k \mathbf{d}_{k-2} - \delta_k \mathbf{d}_{k-1}}{\gamma_k}, \qquad \mathbf{x}_k = \mathbf{x}_{k-1} + \tau_k \mathbf{d}_k .$$

그래서 과거의 $\mathbf{v}$ 들을 저장할 필요가 없다. 반복당 비용은 행렬-벡터 곱 1회와 길이 $n$ 벡터 연산 몇 개로 고정되고, 저장도 벡터 7개 안팎이다. 잔차 노름은 회전의 사인값을 곱해 가며 공짜로 갱신된다($\lvert\phi_k\rvert = \lvert\phi_{k-1}\rvert\,\lvert s_k\rvert$). 그래서 잔차가 단조 감소한다는 성질이 구조적으로 따라온다².

$A$ 가 SPD 이면 MINRES 는 정확 산술에서 켤레잔차법(conjugate residual, CR)과 같은 반복열을 낸다. CG 가 $A$-노름 오차를, MINRES/CR 이 잔차 2-노름을 최소화한다는 차이뿐이다.

3. 수렴 — 부정치는 값을 치른다

MINRES 의 잔차는 다항식 최소화 문제로 쓸 수 있다.

$$\frac{\lVert \mathbf{r}_k \rVert}{\lVert \mathbf{r}_0 \rVert} \le \min_{p_k(0)=1}\ \max_{\lambda \in \sigma(A)} \lvert p_k(\lambda) \rvert .$$

고유값이 $[a, b]$ ($0<a$) 에만 있으면 CG 와 같은 $\bigl(\tfrac{\sqrt\kappa - 1}{\sqrt\kappa + 1}\bigr)^k$ 류 수렴이 나온다. 문제는 부정치다. 고유값이 원점 양쪽 대칭 구간 $[-b, -a] \cup [a, b]$ 에 있으면, $p(0)=1$ 을 유지하면서 양쪽을 동시에 눌러야 하므로 고전적 상한이

$$\frac{\lVert \mathbf{r}_k \rVert}{\lVert \mathbf{r}_0 \rVert} \le 2\left(\frac{\kappa - 1}{\kappa + 1}\right)^{\lfloor k/2 \rfloor}, \qquad \kappa = b/a$$

가 된다. 루트가 사라졌고 지수가 절반이 됐다. 대략 말하면 조건수 $\kappa$ 인 부정치 문제는 조건수 $\kappa^2$ 인 정치 문제처럼 수렴한다.

3.1. 실측

$n = 4000$, 고유값을 구간에 등간격으로 깐 대각행렬, 무작위 우변으로 SciPy minres 를 돌려 상대잔차 $10^{-8}$ 에 닿는 반복 수를 쟀다.

스펙트럼	조건수	반복 수
$[1, 100]$ (SPD)	100	87
$[1, 10^4]$ (SPD)	$10^4$	359
$[-100, -1] \cup [1, 100]$ (부정치)	100	1647

같은 조건수 100인데 부정치가 19배 더 돈다³. 위 상한으로 계산하면 $10^{-8}$ 까지 약 1910회라 실측 1647회와 같은 크기다. SPD 쪽은 등간격 스펙트럼의 덕을 봐서 상한보다 훨씬 빠르다.

3.2. 유한 정밀도의 그림자

$n = 400$ 짜리 조밀 대칭 부정치 행렬(같은 스펙트럼 $[-100,-1]\cup[1,100]$ 을 무작위 직교 회전)로 MINRES 와 재시작 없는 GMRES 를 나란히 돌리면, 처음 100회까지는 잔차가 유효숫자 14자리 이상 일치한다(정확 산술에서는 같은 반복열이다). 150회에서는 10번째 유효숫자부터, 200회에서는 셋째 자리부터 갈라지고, 상대잔차 $10^{-8}$ 도달은 GMRES 가 정확히 $n = 400$ 회, MINRES 가 541회다. 란초스의 3항 점화식은 반올림으로 직교성을 잃고, 그 손실이 수렴 지연으로 나타난다. 같은 문제에 CG 를 걸면 잔차가 566회 동안 281번이나 증가하며 널뛰었다 — CG 는 부정치에서 잔차를 줄여 준다는 보장 자체가 없다.

4. 전처리 — 양정치만 받는다

MINRES 는 대칭 구조에 기대므로 전처리도 대칭을 깨면 안 된다. 전처리기 $M$ 은 대칭 양정치여야 하고, 그러면 MINRES 는 $M^{-1}$-노름으로 잰 잔차를 최소화한다($M = LL^\top$ 로 양쪽 전처리한 것과 같다). $A$ 가 부정치라고 $M$ 까지 부정치로 잡으면 안 된다는 점이 실무에서 자주 걸린다 — 그런 전처리기를 쓰고 싶으면 GMRES 나 BiCGSTAB 으로 넘어가야 한다.

안장점 계 $\begin{pmatrix} A & B^\top \\ B & 0 \end{pmatrix}$ 에서는 블록 대각 전처리기 $\mathrm{diag}(A, S)$, $S = BA^{-1}B^\top$ (슈어 보수)가 고전이다. 이 이상적 전처리를 쓰면 전처리된 행렬의 서로 다른 고유값이 $1$, $\tfrac{1\pm\sqrt5}{2}$ 세 개뿐이라 MINRES 가 3회 만에 끝난다(머피·골럽·와선, 2000). 실제로는 $A$ 와 $S$ 를 다중격자법 한 사이클이나 질량행렬 같은 값싼 근사로 바꾸고, 고유값이 세 덩어리 근처에 모여 있는 한 반복 수가 격자 크기와 거의 무관하게 유지된다. 스토크스 솔버의 표준 레시피가 바로 이것이다.

5. 특이 · 비일관 계와 MINRES-QLP

$A$ 가 특이하고 $\mathbf{b}$ 가 치역 밖에 있으면 해가 없다. MINRES 는 이때도 잔차를 최소화하므로 최소자승 해 쪽으로 가지만, 해가 무수히 많을 때 노름이 최소인 해를 고른다는 보장은 없다. 게다가 $R_k$ 가 수치적으로 특이해지면 $\mathbf{d}_k$ 갱신에서 거대한 수로 나누게 되어 해가 폭발할 수 있다.

MINRES-QLP(최·페이지·손더스, 2011)는 $R_k$ 에 오른쪽에서 회전을 한 번 더 걸어 $L_k$ 형태로 만든 뒤(QLP 분해) 랭크를 드러내게 해서, 특이·거의 특이 계에서도 최소 노름 최소자승 해로 간다. 반복당 비용이 조금 더 들어서, 잘 조건화된 계에서는 MINRES 로 시작해 조건이 나빠지면 QLP 로 갈아타는 구현이 쓰인다.

6. 언제 무엇을

• SPD → CG. MINRES 도 되지만 CG 가 오차의 $A$-노름을 직접 줄이고 조금 더 싸다. 잔차가 단조로 줄어야 하는 정지 기준을 쓰면 MINRES 가 유리할 때도 있다.
• 대칭 부정치 → MINRES. 대칭이 아니면 쓸 수 없다. “거의 대칭”은 대칭이 아니다 — 조립 순서나 경계조건 처리 하나로 대칭이 깨지는 경우가 흔하니 $\lVert A - A^\top \rVert$ 를 먼저 재 볼 것.
• 대칭 부정치인데 직접법이 감당되는 크기 → $LDL^\top$ + 번치-카우프만 피벗. 반복법은 큰 희소 문제에서 의미가 있다.
• 비대칭 → GMRES, BiCGSTAB, 쌍켤레 기울기법 계열.
• 특이·비일관 → MINRES-QLP 또는 LSMR 계열.

7. 관련 문서

• 크리로프 부분공간법 · GMRES · 켤레기울기법 · BiCGSTAB · 쌍켤레 기울기법
• 란초스 알고리즘 · 아놀디 알고리즘 · 기븐스 회전 · SYMMLQ
• 전처리기 · 슈어 보수 · 안장점 문제 · 스토크스 유동 · 혼합유한요소법
• 번치-카우프만 피벗 · 다중격자법 · 반복법

8. Footnotes

1. SYMMLQ 는 $A\mathcal{K}_k$ 안에서 오차 2-노름을 최소화하는 쪽이다. 같은 란초스 뼈대에 목적함수만 바꾼 쌍둥이인데, 반세기가 지난 지금 실무에서 살아남은 건 대부분 MINRES 다. 잔차는 잴 수 있고 오차는 못 재기 때문이다. ↩

2. CG 를 돌려 본 사람은 잔차 그래프가 롤러코스터를 타는 걸 본 적이 있을 것이다. MINRES 의 잔차 그래프는 정의상 내려가기만 한다. 대신 평평하게 눕는 구간(정체)이 생길 수는 있다 — 내려가지 않는 것과 올라가는 것은 다르다는 게 MINRES 의 변명이다. ↩

3. 「대칭이니까 CG 랑 비슷하겠지」라고 반복 상한을 SPD 기준으로 잡아 두면 이 19배가 그대로 타임아웃으로 돌아온다. 부정치 계의 반복 예산은 따로 잡을 것. ↩