QMR

1. 개요

QMR Quasi-Minimal Residual
대상	비대칭(비에르미트) 선형계 Ax = b
뼈대	양측 란초스 — 삼중대각 T̃k, 서로 쌍직교인 두 기저
무엇을 최소화	잔차 자체가 아니라 기저 계수의 노름(준잔차)
보장	‖rk‖ ≤ √(k+1) · 준잔차, 준잔차는 단조 감소
비용	반복당 A 곱 1회 + AT 곱 1회, 메모리 O(n)
제안	프로인트·나흐티갈, 1991
후손	TFQMR(1993), QMRCGSTAB(1994), 대칭 QMR

BiCG 가 잔차 그래프로 심전도를 그리면, QMR 은 같은 데이터를 받아 매끈한 내리막으로 다시 그린다. 정보는 같은데 멘탈이 다르다.

QMR(Quasi-Minimal Residual method, 준최소 잔차법)은 비대칭 선형계 $A\mathbf x = \mathbf b$ 를 푸는 크리로프 부분공간법으로, 양측 란초스 과정이 만든 비직교 기저 위에서 「그 기저가 직교라고 치고」 잔차를 최소화한다. 프로인트(Roland Freund)와 나흐티갈(Noël Nachtigal)이 1991년에 발표했다.

비대칭 크리로프 방법에는 오래된 딜레마가 있다. GMRES는 잔차를 진짜로 최소화하지만 직교 기저를 전부 저장해야 해서 반복마다 메모리와 시간이 늘어난다. 쌍켤레 기울기법(BiCG)은 짧은 점화식으로 메모리가 일정하지만, 최소화를 포기하고 갤러킨 조건을 택한 대가로 잔차가 들쭉날쭉하고 이따금 폭발한다. QMR 은 그 사이를 노린다 — BiCG 와 같은 짧은 점화식 기저를 쓰되, 그 위에서 GMRES 처럼 최소제곱을 푼다. 정확한 최소화는 아니라서 「준(quasi)」이 붙었다¹.

2. 유도

2.1. 양측 란초스

비대칭 $A$ 에 대해 두 크리로프 공간 $\mathcal K_k(A, \mathbf r_0)$, $\mathcal K_k(A^{\mathsf T}, \tilde{\mathbf r}_0)$ 의 기저 $V_k = [\mathbf v_1, \dots, \mathbf v_k]$, $W_k$ 를 서로 쌍직교($W_k^{\mathsf T}V_k$ 가 대각)가 되게 만든다. 이 조건 덕분에 점화식이 3항으로 짧아지고

$$A V_k = V_{k+1}\,\tilde T_k$$

가 성립한다. $\tilde T_k$ 는 $(k+1)\times k$ 삼중대각 행렬이다. 대칭이면 $W = V$ 가 되어 보통의 란초스 알고리즘으로 돌아간다. 비대칭의 대가는 $V_k$ 가 직교가 아니라는 것, 그리고 $A^{\mathsf T}$ 곱이 매 반복 하나 더 든다는 것이다.

2.2. 준최소화

$\mathbf x_k = \mathbf x_0 + V_k\mathbf y$ 로 두면 잔차는

$$\mathbf r_k = \mathbf r_0 - AV_k\mathbf y = V_{k+1}\bigl(\beta\mathbf e_1 - \tilde T_k\mathbf y\bigr), \qquad \beta = \lVert\mathbf r_0\rVert$$

이다(첫 기저벡터를 $\mathbf v_1 = \mathbf r_0/\beta$ 로 잡았으므로). GMRES 라면 $V_{k+1}$ 이 직교라서 $\lVert\mathbf r_k\rVert = \lVert\beta\mathbf e_1 - \tilde T_k\mathbf y\rVert$ 이고, 오른쪽 작은 최소제곱을 풀면 끝이다. QMR 의 $V_{k+1}$ 은 직교가 아니지만, 어차피 계산 가능한 건 오른쪽뿐이니 그것을 최소화한다:

$$\mathbf y_k = \arg\min_{\mathbf y}\ \bigl\lVert \beta\mathbf e_1 - \tilde T_k\mathbf y \bigr\rVert, \qquad \tau_k = \min_{\mathbf y}\bigl\lVert \beta\mathbf e_1 - \tilde T_k\mathbf y \bigr\rVert$$

$\tau_k$ 를 준잔차라 부른다. $\tilde T_k$ 가 삼중대각이므로 MINRES와 똑같이 기븐스 회전 하나씩으로 QR 을 갱신하고, 해도 짧은 점화식으로 갱신된다. 메모리는 벡터 몇 개로 고정이다.

진짜 잔차와의 관계는 $V_{k+1}$ 의 열을 단위 길이로 맞춰 두면

$$\lVert\mathbf r_k\rVert \le \lVert V_{k+1}\rVert\,\tau_k \le \sqrt{k+1}\;\tau_k$$

로 묶인다. $\tau_k$ 는 최소화 문제가 반복마다 커지기만 하므로 단조 감소한다. 진짜 잔차가 단조라는 보장은 없지만, 단조로 줄어드는 양에 $\sqrt{k+1}$ 만 곱한 상한 아래에 갇혀 있다. 프로인트·나흐티갈은 같은 틀에서 행마다 가중치를 줘 상한을 조이는 판도 제시했다.

2.3. BiCG 와의 관계

같은 $\tilde T_k$ 의 위쪽 $k\times k$ 블록 $T_k$ 로 $T_k\mathbf y = \beta\mathbf e_1$ 을 풀면 BiCG 반복값이 나온다. 즉 BiCG 와 QMR 은 같은 란초스 기저 위의 갤러킨 해와 준최소제곱 해다. FOM 과 GMRES 의 관계와 정확히 같은 구도이고, 그래서 같은 현상이 나온다. 갤러킨 쪽(BiCG) 잔차가 치솟는 구간에서 최소화 쪽(QMR) 은 평평하게 정체하고, 갤러킨 쪽이 좋아지면 최소화 쪽도 따라 내려간다 — 컬럼·그린바움이 정리한 「봉우리–평원」 대응이다. QMR 은 BiCG 의 정보를 평활화한 것일 뿐 새 정보를 만들지 않는다. 그래서 수렴까지의 반복 수는 대개 비슷하다.

BiCG 의 붕괴 두 종류 가운데, $T_k$ 의 LU 피벗이 0이 되는 「두 번째 붕괴」는 QMR 이 피한다. 최소제곱은 $T_k$ 가 특이해도 풀리기 때문이다. 하지만 $\mathbf w_k^{\mathsf T}\mathbf v_k = 0$ 이 되는 란초스 붕괴는 기저 자체가 망가지는 것이라 QMR 도 그대로 맞는다. 이를 위해 원 논문은 룩어헤드(look-ahead) 란초스와 함께 제시됐다 — 쌍직교가 무너질 듯하면 블록 단위로 건너뛰어 기저를 이어 간다(프로인트·구트크네히트·나흐티갈, 1993).

3. 검산 — 대류-확산

$[0,1]^2$ 위 $-\Delta u + 60(u_x + u_y) = f$ 를 $40\times40$ 내부 격자의 2차 중앙차분으로 이산화했다($n = 1600$, 셀 페클레 수 0.73 이라 중앙차분이 아직 진동하지 않는 영역). 무작위 참해로 우변을 만들고, 룩어헤드 없는 양측 란초스 위에 BiCG(갤러킨)와 QMR(준최소제곱)을 같은 기저로 계산해 진짜 상대잔차 $\lVert\mathbf b - A\mathbf x_k\rVert/\lVert\mathbf b\rVert$ 를 쟀다.

반복 $k$	5	10	20	30	40	50	60	70	80	90	100
BiCG	$3.1\times10^{-1}$	$1.6\times10^{-1}$	$3.9\times10^{-2}$	$7.6\times10^{-2}$	$5.9\times10^{-2}$	$1.9\times10^{-3}$	$2.0\times10^{-2}$	$6.8\times10^{-4}$	$2.3\times10^{-5}$	$1.2\times10^{-5}$	$4.0\times10^{-7}$
QMR	$1.2\times10^{-1}$	$9.4\times10^{-2}$	$1.9\times10^{-2}$	$1.5\times10^{-2}$	$1.3\times10^{-2}$	$2.1\times10^{-3}$	$1.4\times10^{-3}$	$6.9\times10^{-4}$	$2.6\times10^{-5}$	$2.0\times10^{-6}$	$5.1\times10^{-7}$
$\sqrt{k+1}\,\tau_k$	0.28	0.20	$7.2\times10^{-2}$	$5.7\times10^{-2}$	$5.0\times10^{-2}$	$9.2\times10^{-3}$	$5.2\times10^{-3}$	$3.3\times10^{-3}$	$1.7\times10^{-4}$	$9.4\times10^{-6}$	$3.1\times10^{-6}$

읽을 거리는 세 가지다.

• 평활화: BiCG 는 최대 상대잔차가 2.37 (초기값의 2배 넘게)까지 튀고 잔차가 늘어난 반복이 49번이다. QMR 은 최대가 초기값 이하(0.38)이고 늘어난 반복이 30번이다. 30·60회처럼 BiCG 가 튀는 자리에서 QMR 은 평원을 유지한다.
• 같은 속도: $10^{-6}$ 에 닿는 반복은 QMR 97회, BiCG 100회다. 위에서 말한 대로 정보는 같고 평활화만 다르다. 같은 문제에 재시작 없는 GMRES 는 81회 — 직교 기저의 값어치는 16회쯤이고, 그 대신 기저 81개를 저장했다.
• 상한은 진짜다: 모든 반복에서 진짜 잔차가 $\sqrt{k+1}\,\tau_k$ 아래에 있었다. 다만 상한이 진짜 잔차보다 2~6배 비관적이라 정지 판정에 $\tau_k$ 를 쓰면 몇 회 더 돈다. 실무 구현은 수렴 근처에서 진짜 잔차를 한 번 계산해 확인한다.

반대 사례도 하나 남긴다. 같은 행렬에서 우변만 $A\cdot(1,\dots,1)^{\mathsf T}$ 로 바꾸면 BiCG 잔차가 $4\times10^{9}$ 까지 치솟았고, 룩어헤드 없는 QMR 은 폭발하지 않는 대신 0.39 에서 100회 넘게 정체했다. 그 사이 쌍직교 내적 $\lvert\mathbf w_k^{\mathsf T}\mathbf v_k\rvert$ (단위 벡터 기준)은 14회째에 $10^{-9}$ 아래, 이후 $3\times10^{-13}$ 까지 떨어졌다 — 근붕괴다. 같은 계를 GMRES 는 83회에 풀었다. QMR 의 평활화가 란초스 기저의 고장까지 고쳐 주지는 않는다는 실례다².

4. 후손들

• TFQMR(프로인트, 1993): CGS 의 반복값 위에서 준최소화를 해 $A^{\mathsf T}$ 곱을 없앴다. $A^{\mathsf T}$ 를 짜기 어려운 행렬 자유(matrix-free) 코드, 예컨대 뉴턴-크리로프법의 야코비안-벡터 곱에서 유리하다.
• QMRCGSTAB(챈 외, 1994): BiCGSTAB에 같은 준최소화를 얹어 잔차 곡선을 매끈하게 만든다.
• 대칭 QMR: $A$ 가 복소 대칭($A^{\mathsf T} = A$, 에르미트가 아님)이면 $W = \bar V$ 로 잡아 $A^{\mathsf T}$ 곱이 필요 없어진다. 손실 있는 매질의 맥스웰 방정식을 유한요소 전자기로 이산화하면 정확히 이 구조가 나와서 전자기 해석 코드에서 자주 쓰인다.
• 란초스 기반 모델 축소: 같은 양측 란초스가 전달함수의 파데 근사를 만든다는 사실을 이용한 PVL(Padé via Lanczos, 펠트만·프로인트 1995)이 회로 시뮬레이션의 상호연결 축소에 쓰였다. QMR 과 같은 연구 계보다.

5. 언제 쓰나

솔직히 말하면 오늘날 범용 비대칭 솔버의 기본값은 BiCGSTAB·GMRES(재시작)·IDR(s) 쪽이고, QMR 원판은 $A^{\mathsf T}$ 곱이 필요해 손이 덜 간다. 그래도 자리는 분명하다.

• 잔차 곡선이 매끄러워야 할 때 — 정지 판정·적응 허용오차가 잔차의 단조성에 기대는 바깥 루프(비정확 뉴턴, 적응 시간 적분)에서 BiCG 계열의 들쭉날쭉함은 판정 오류를 부른다.
• $A^{\mathsf T}$ 가 공짜일 때 — 명시적으로 조립한 희소 행렬이면 전치 곱은 같은 자료 구조를 거꾸로 훑을 뿐이다. 수반 문제를 같이 푸는 코드(수반법)라면 $A^{\mathsf T}$ 곱이 이미 있다.
• 복소 대칭 — 대칭 QMR 이 사실상 정답이다.

전처리기는 BiCG 와 똑같이 좌·우·분할 어느 쪽이든 붙는다. 분할 전처리 $M_1^{-1}AM_2^{-1}$ 로 쓰면 준잔차가 전처리된 계의 잔차를 재므로, 정지 판정이 원래 잔차와 어떻게 대응하는지 한 번 따져 둬야 한다³.

6. 관련 문서

• 쌍켤레 기울기법 · BiCGSTAB · GMRES · MINRES · SYMMLQ
• 란초스 알고리즘 · 크리로프 부분공간법 · 기븐스 회전 · 전처리기
• 대류-확산 방정식 · 페클레 수 · 뉴턴-크리로프법 · 유한요소 전자기
• CGS · TFQMR · IDR(s) · 파데 근사

7. Footnotes

1. 「준최소」를 처음 들으면 “최소인데 최소가 아님”이라는 형용모순 같지만, 정확히는 “다른 노름으로 재면 최소”다. 기저가 직교였다면 진짜 최소였을 것이라는 아쉬움이 이름에 그대로 남아 있다. ↩

2. 룩어헤드를 붙이면 이런 근붕괴를 블록으로 건너뛸 수 있지만, 쌍직교가 영원히 회복되지 않는 「치유 불가능한 붕괴」도 이론상 존재한다. 그럴 땐 그림자 벡터 $\tilde{\mathbf r}_0$ 를 바꿔 처음부터 다시 돌리는 게 국룰이다. 수렴은 신에게 맡기고 시드를 바꾼다. ↩

3. “QMR 이 $10^{-8}$ 에서 멈췄다길래 믿었는데 원래 계 잔차는 $10^{-5}$ 였다”는 분할 전처리 + 준잔차 판정 조합의 고전적인 사고다. 상한의 $\sqrt{k+1}$ 과 전처리기 조건수가 곱으로 끼어든다. ↩