SYMMLQ

1. 개요

SYMMLQ SYMMetric LQ method
대상	대칭(부정치 가능) 선형계 Ax = b
뼈대	란초스 삼중대각 Tk 의 LQ 분해
최소화하는 것	오차의 2-노름 ‖x* − xk‖ (부분공간 A𝒦 위에서)
보장	반복값이 항상 존재, 오차 단조 감소
보너스	CG 점이 존재하면 값싸게 옮겨 탈 수 있다
제안	페이지·손더스, 1975 (MINRES 와 같은 논문)

MINRES 의 쌍둥이. 형이 「잔차를 줄이자」고 할 때 동생은 「아니, 오차를 줄이자」고 했다. 둘 다 같은 날 같은 논문에서 태어났다.

SYMMLQ(SYMMetric LQ)은 대칭 행렬 $A$ — 양정치가 아니어도 된다 — 에 대한 선형계 $A\mathbf x = \mathbf b$ 를 푸는 크리로프 부분공간법으로, 란초스 과정이 만든 삼중대각 행렬을 LQ 분해해서 반복값을 만든다. 페이지(Chris Paige)와 손더스(Michael Saunders)가 1975년 MINRES와 같은 논문에서 발표했다¹.

출발점은 켤레 기울기법(CG)이 부정치 행렬에서 겪는 문제다. CG 는 란초스 삼중대각 $T_k$ 로 $T_k\mathbf y = \beta\mathbf e_1$ 을 푸는 갤러킨 방법인데, $A$ 가 부정치면 $T_k$ 가 중간 단계에서 특이해질 수 있다. 그러면 CG 반복값이 존재하지 않고, 특이에 가까우면 반복값이 엉뚱한 곳으로 튄다. 페이지·손더스는 두 가지 처방을 냈다. 하나는 잔차를 최소화하는 MINRES, 다른 하나는 $T_k$ 를 LQ 로 분해해 항상 풀리는 삼각계만 쓰는 SYMMLQ 다. 후자는 결과적으로 오차의 2-노름을 최소화하는 반복이 된다.

2. 유도

2.1. 란초스와 CG 점

대칭 $A$, $\mathbf v_1 = \mathbf b/\beta$ 로 란초스 알고리즘을 돌리면 직교 기저 $V_k$ 와

$$AV_k = V_{k+1}\bar T_k, \qquad \bar T_k = \begin{pmatrix} T_k \\ \beta_{k+1}\mathbf e_k^{\mathsf T}\end{pmatrix}$$

을 얻는다. 해를 $\mathbf x_k = V_k\mathbf y$ 로 찾을 때 선택지는 셋이다.

• 갤러킨(CG): $T_k\mathbf y = \beta\mathbf e_1$. 잔차가 $V_k$ 에 직교. $T_k$ 가 특이하면 해가 없다.
• 최소 잔차(MINRES): $\min\lVert\beta\mathbf e_1 - \bar T_k\mathbf y\rVert$. 항상 존재, 잔차 단조 감소.
• 최소 오차(SYMMLQ): 아래.

2.2. LQ 분해

SYMMLQ 는 $T_k$ 에 오른쪽에서 기븐스 회전을 차례로 걸어 하삼각 형태로 만든다.

$$T_k\,Q_k^{\mathsf T} = \bar L_k$$

$\bar L_k$ 는 대각과 그 아래 두 줄만 있는 하삼각 행렬이다. 이 분해의 요점은 앞쪽 $(k-1)\times(k-1)$ 블록 $L_{k-1}$ 의 대각이 0이 아니라는 것이다 — 회전으로 만든 대각 성분은 $\gamma_i = \sqrt{\bar\gamma_i^2 + \beta_{i+1}^2}$ 꼴이라, 란초스가 끝나지 않은 한($\beta_{i+1} > 0$) 양수다. 0이 될 수 있는 건 아직 다음 $\beta$ 를 받지 못한 마지막 대각 하나뿐이다. 그래서 SYMMLQ 는 마지막 성분을 빼고

$$L_{k-1}\mathbf z = \beta\mathbf e_1, \qquad \mathbf x_k^{L} = W_{k-1}\mathbf z, \quad W_k = V_k Q_k^{\mathsf T}$$

로 반복값을 만든다. 삼각계라 앞에서부터 풀리고, $\mathbf z$ 의 앞 성분은 $k$ 가 늘어도 바뀌지 않으므로 짧은 점화식으로 $\mathbf x^{L}$ 을 갱신한다. 메모리는 벡터 몇 개다.

2.3. 왜 오차를 최소화하나

$W_{k-1}$ 의 열이 펼치는 공간은 $A$ 를 크리로프 공간에 곱한 $A\mathcal K$ 이고, $\mathbf x^{L}_k$ 는 그 공간에서 참해 $\mathbf x_*$ 에 가장 가까운 점, 곧

$$\mathbf x^{L}_k = \arg\min_{\mathbf x\,\in\,A\mathcal K}\ \lVert \mathbf x_* - \mathbf x\rVert_2$$

이다. 참해를 모르는데 어떻게 오차를 최소화하나? 비밀은 $A$ 의 대칭성이다. $\mathbf x = A V\mathbf c$ 꼴이면 정규방정식이 $(AV)^{\mathsf T}(AV)\mathbf c = (AV)^{\mathsf T}\mathbf x_* = V^{\mathsf T}A\mathbf x_* = V^{\mathsf T}\mathbf b$ 가 되어 $\mathbf x_*$ 대신 $\mathbf b$ 만 있으면 된다. LQ 분해는 이 정규방정식을 제곱 조건수 없이 푸는 방법이다. 부분공간이 반복마다 커지므로 오차 노름이 단조 감소한다 — 부정치 행렬에서 이 성질을 갖는 짧은 점화식 방법은 드물다².

2.4. CG 점으로 옮겨 타기

$\bar L_k$ 의 마지막 대각이 0이 아니면(곧 $T_k$ 가 정칙이면) CG 반복값이 존재하고, 그것은 SYMMLQ 점에서 한 방향만큼 떨어져 있다.

$$\mathbf x_k^{C} = \mathbf x_k^{L} + \bar\zeta_k\,\bar{\mathbf w}_k$$

벡터 하나 더하는 비용이다. 페이지·손더스 구현은 반복 내내 SYMMLQ 점을 갱신하다가, 끝날 때 CG 점이 존재하고 잔차가 더 작으면 CG 점을 답으로 내준다. 즉 SYMMLQ 는 실무에서 「CG 를 부정치에서도 안전하게 굴리는 방법」에 가깝다. CG 점의 잔차 노름도 따로 계산하지 않고 추적된다.

3. 검산 — 부정치 라플라시안

$30\times30$ 내부 격자의 2차원 5점 라플라시안($n = 900$)을 6번째와 7번째 고유값 사이로 이동시켜 음의 고유값 6개를 가진 대칭 부정치 행렬을 만들었다(헬름홀츠형, $\min\lvert\lambda\rvert = 14.7$, $\kappa = 513$). 무작위 참해로 우변을 만들고, 완전 재직교화한 란초스 기저 위에서 세 반복값(갤러킨·최소 잔차·최소 오차)을 정의대로 계산해 정확 산술의 거동을 재현했다.

$k$	CG 오차	MINRES 오차	SYMMLQ 오차	CG 잔차	MINRES 잔차	SYMMLQ 잔차
10	0.149	0.152	0.169	$5.6\times10^{-3}$	$3.1\times10^{-3}$	$3.3\times10^{-2}$
40	0.095	0.104	0.104	$1.9\times10^{-3}$	$5.8\times10^{-4}$	$8.1\times10^{-3}$
80	0.073	0.061	0.027	$2.0\times10^{-3}$	$2.3\times10^{-4}$	$2.6\times10^{-3}$
100	$1.8\times10^{-4}$	$2.3\times10^{-4}$	$1.4\times10^{-3}$	$1.2\times10^{-5}$	$6.5\times10^{-6}$	$4.9\times10^{-4}$
120	$1.7\times10^{-6}$	$3.9\times10^{-6}$	$5.4\times10^{-5}$	$2.5\times10^{-7}$	$1.6\times10^{-7}$	$2.4\times10^{-5}$
150	$4.3\times10^{-12}$	$6.2\times10^{-12}$	$4.3\times10^{-10}$	$1.2\times10^{-12}$	$1.0\times10^{-12}$	$2.6\times10^{-10}$

(오차·잔차 모두 상대값.) 단조성을 세면 이렇다.

	오차가 늘어난 반복 수	잔차가 늘어난 반복 수	최대 상대오차
CG	37	34	1.36
MINRES	10	0	0.49
SYMMLQ	0	43	1 (초기값)

이론이 그대로 보인다. MINRES 는 잔차가, SYMMLQ 는 오차가 단 한 번도 늘지 않는다. CG 는 둘 다 보장이 없고, 76회째에는 오차가 초기 오차의 1.36 배로 튀었다 — $T_k$ 가 특이에 가까워진 순간이다.

그런데 SYMMLQ 반복값 자체는 느리다. 상대잔차 $10^{-8}$ 에 닿는 반복이 CG·MINRES 129회, SYMMLQ 142회이고, 오차 $10^{-8}$ 은 134·135·144회다. 부분공간 $A\mathcal K$ 가 같은 단계의 $\mathcal K$ 보다 한 차원 「뒤처진」 탓이다. 그래서 위의 CG 점 옮겨 타기가 중요하다. 수렴 근처에서 CG 점이 존재하면 위 표처럼 SYMMLQ 점보다 훨씬 좋으므로, 실제 SYMMLQ 프로그램은 끝에서 CG 점을 내준다. 안전성은 SYMMLQ 에서, 최종 정확도는 CG 에서 가져오는 셈이다.

4. 오차 추정이라는 진짜 장점

반복법의 정지 판정은 대개 잔차로 한다. 하지만 사용자가 원하는 건 오차고, 둘은 조건수만큼 어긋날 수 있다. SYMMLQ 는 오차가 단조 감소하고 그 감소량이 반복 중 계산되는 양으로 표현되므로, 오차 노름의 상한을 싸게 추정할 수 있다. 에스트린·오르반·손더스(2019)는 $A$ 의 최소 특이값 하한만 알면 SYMMLQ 와 CG 반복값의 2-노름 오차 상한을 반복마다 계산하는 방법을 정리했다. 잔차가 작아도 오차가 큰 악조건 문제에서 이것이 「언제 멈춰도 되는가」에 대한 정직한 답이다³.

5. MINRES 와 SYMMLQ, 무엇을 쓰나

• 기본값은 MINRES. 잔차가 단조라 정지 판정이 간단하고, 실측에서도 SYMMLQ 점보다 빠르다. 대부분의 라이브러리(SciPy 등)는 MINRES 만 기본 제공한다.
• 오차 노름이 목적이면 SYMMLQ. 역문제의 반복 정규화처럼 「해에 가장 가까운 점」이 의미 있는 경우, 또는 오차 상한으로 멈추고 싶을 때.
• CG 를 쓰고 싶은데 양정치가 의심스러우면 SYMMLQ. CG 점이 있으면 그걸 주고, 없으면 터지지 않고 지나간다.
• 특이·비일관 계는 둘 다 아니다. MINRES-QLP·LSMR 쪽으로 가야 한다.
• 전처리는 MINRES 와 같은 제약을 받는다 — 전처리기는 대칭 양정치여야 한다. 안장점 계의 블록 대각 전처리(슈어 보수)가 그대로 쓰인다.

부정치 대칭계가 직접법으로 감당되는 크기라면 LDL 분해 + 번치-카우프만 피벗이 여전히 가장 확실하다. SYMMLQ 는 행렬을 조립할 수도, 분해할 수도 없는 크기에서 의미가 있다.

6. 관련 문서

• MINRES · 켤레 기울기법 · 란초스 알고리즘 · 크리로프 부분공간법
• 기븐스 회전 · 전처리기 · 슈어 보수 · 안장점 문제
• LDL 분해 · 번치-카우프만 피벗 · 실베스터 관성 법칙
• QMR · GMRES · 헬름홀츠 방정식 · LSQR

7. Footnotes

1. 이름의 LQ 는 쓰이는 분해 그대로다. MINRES 쪽은 QR 을 쓰니 「SYMMQR」이라 불러도 됐을 텐데 그쪽은 목적함수로 이름을 지었다. 같은 논문 안에서 작명 규칙이 갈린 셈. ↩

2. 문헌마다 부분공간 첨자가 하나씩 다르다($A\mathcal K_{k-1}$ 이냐 $A\mathcal K_k$ 냐). 란초스 벡터를 몇 개 만든 시점을 $k$ 로 부르느냐의 차이일 뿐 내용은 같다. 첨자 하나로 리뷰어와 반나절 싸우는 건 수치선형대수계의 국룰이다. ↩

3. 잔차 $10^{-8}$ 을 보고 퇴근했는데 다음 날 오차가 $10^{-3}$ 이었다는 이야기는 조건수 $10^5$ 짜리 문제에서 흔하다. 오차 상한은 그 퇴근을 하루 미뤄 주는 장치다. ↩