안장점 문제

1. 개요

안장점 문제(saddle point problem)는 수치선형대수에서 다음 블록 구조를 가진 선형계를 말한다.

$$\mathcal K \begin{bmatrix} u \\ p \end{bmatrix} = \begin{bmatrix} A & B^\top \\ B & 0 \end{bmatrix} \begin{bmatrix} u \\ p \end{bmatrix} = \begin{bmatrix} f \\ g \end{bmatrix}, \qquad A\in\mathbb R^{n\times n},\; B\in\mathbb R^{m\times n},\; m \le n$$

이름은 이 계가 이차 라그랑지안 $\mathcal L(u,p) = \tfrac12 u^\top A u - f^\top u + p^\top(Bu - g)$ 의 정류점 조건이고, 그 정류점이 $u$ 방향으로는 최소·$p$ 방향으로는 최대인 **안장점**이라서 붙었다.¹ 기하학적 안장점(헤세 행렬 고유값의 부호가 섞인 임계점) 자체는 그 문서에서 다루고, 여기서는 그런 점을 찾기 위해 풀어야 하는 선형계를 다룬다.

이 구조는 서로 다른 동네에서 똑같이 나온다.

• 비압축성 유동. 스토크스·나비에-스토크스 방정식을 이산화하면 $u$ 는 속도, $p$ 는 압력, $B$ 는 발산 연산자, $B^\top$ 는 기울기다. 압력은 비압축 구속 $\nabla\cdot u = 0$ 의 라그랑주 승수다.
• 혼합유한요소법. 다르시 유동의 플럭스-압력, 비압축 탄성의 변위-압력.
• 등식 제약 최적화. 이차계획법의 KKT 조건. 라그랑주 승수법·내점법·순차 이차계획법의 매 반복이 이 계 하나를 푼다.
• 접촉·다물체 구속. 구속 반력이 승수다.

공통점은 하나다 — 구속을 승수로 걸었다. 그리고 그 대가로 행렬이 부정치가 된다.

2. 언제 풀리는가

2.1. 관성 — 음수 고유값은 정확히 m개

$A$ 가 대칭 양정치이고 $B$ 가 행 계수 가득($\mathrm{rank}\,B = m$)이면 블록 소거로

$$\mathcal K = \begin{bmatrix} I & 0 \\ BA^{-1} & I \end{bmatrix} \begin{bmatrix} A & 0 \\ 0 & -S \end{bmatrix} \begin{bmatrix} I & A^{-1}B^\top \\ 0 & I \end{bmatrix}, \qquad S = BA^{-1}B^\top$$

이 되고, $S$ 는 양정치다. 실베스터 관성 법칙에 의해 $\mathcal K$ 는 양의 고유값 $n$개, 음의 고유값 $m$개를 갖는다. $n=40$, $m=12$ 짜리 무작위 예제를 만들어 고유값을 세어 보면 정확히 40개·12개가 나온다.

이 사실 하나로 쓸 수 있는 도구가 갈린다. 켤레기울기법은 양정치를 전제로 하므로 그대로 쓰면 안 되고, 대칭 부정치용 MINRES나 비대칭까지 받는 GMRES를 쓴다. 직접법이라면 피벗 없는 촐레스키가 아니라 번치-카우프만 피벗을 쓰는 대칭 부정치 $LDL^\top$ 이다.

2.2. A 가 특이해도 된다

실무에서는 $A$ 가 양정치가 아닌 경우가 많다(최적화의 헤세 행렬이 반정치, 순수 노이만 경계의 스토크스 등). 필요충분조건은 더 약하다:

$$\mathcal K\ \text{가역} \iff \ker A \cap \ker B = \{0\}\ \text{이고}\ \mathrm{rank}\,B = m$$

(단 $A$ 가 대칭 반양정치일 때). 최적화 용어로는 “헤세 행렬이 구속의 영공간 위에서 양정치”면 되는 것이고, 이것이 2차 충분조건과 정확히 같은 말이다.

2.3. B 의 계수 결손 — 압력이 떠다닐 때

$B$ 의 행이 선형종속이면 $\mathcal K$ 는 특이하다. 위 예제에서 $B$ 의 마지막 행을 첫 행과 같게 바꾸면 조건수가 $3.1\times10^2$ 에서 $4.1\times10^{17}$ 로 뛴다 — 배정밀도 기준 사실상 특이다.

비압축성 유동에서 이건 가상의 걱정이 아니다. 경계 전체에 속도를 지정하면 압력은 상수만큼 정해지지 않고(상수 압력은 $B^\top$ 의 영공간), 이걸 고정하지 않으면 직접 솔버가 영 피벗으로 죽는다. 압력 한 점 고정이나 평균 0 구속, 또는 크리로프 법에 영공간을 알려 주는 것이 국룰이다.²

3. 이산화가 만드는 함정 — inf-sup

연속 문제가 잘 정의돼도 이산화가 나쁘면 $B$ 가 사실상 계수 결손이 된다. 브레치(1974)와 바부슈카(1973)가 정리한 조건은

$$\inf_{q_h \ne 0}\ \sup_{v_h \ne 0}\ \frac{(q_h,\ \nabla\cdot v_h)}{\|q_h\|\,\|v_h\|_{1}} \ \ge\ \beta > 0$$

이 격자 크기 $h$ 와 무관하게 성립해야 한다는 것이다(inf-sup 조건, LBB 조건). 행렬로 옮기면 “압력 질량행렬로 정규화한 $S$ 의 최소 고유값이 $\beta^2$ 이상” 이다.

속도·압력을 같은 차수로 놓은 $P_1$–$P_1$ 이나 $Q_1$–$Q_0$ 요소는 이 조건을 어겨서 체커보드 모양 가짜 압력 모드가 생긴다. 테일러-후드 $P_2$–$P_1$ 은 만족한다. 유한체적에서 같은 병이 동위치 격자의 체커보드이고, 그 처방이 Rhie-Chow 보간이나 엇갈림 격자다. 안정화 기법(PSPG 등)은 $(2,2)$ 블록의 0 자리에 작은 음반정치 항 $-C$ 를 넣어 이 문제를 우회한다 — 그러면 계의 모양이 $\begin{bmatrix}A & B^\top\\ B & -C\end{bmatrix}$ 로 바뀌고, 이것도 넓은 의미의 안장점 문제로 친다.

4. 푸는 법

4.1. 소거 계열

• 슈어 보수 축약. $u$ 를 소거해 $Sp = BA^{-1}f - g$ 를 푼다. $S$ 는 밀집이라 조립하지 않고 행렬-프리로 곱한다. 거기에 단순 반복을 걸면 우자와 알고리즘이다. 자세한 유도와 압력 슈어 보수의 스펙트럼은 그 문서에 있다.
• 영공간법. $B Z = 0$ 인 기저 $Z$ 를 만들어 $u = u_0 + Zy$ 로 놓으면 $Z^\top A Z y = Z^\top(f - Au_0)$ 라는 양정치 축약계가 남는다. 최적화에서 “축약 헤세 행렬” 이 이것이다. 2차원 비압축 유동의 유선함수 공식화가 영공간법의 연속판이다. $Z$ 를 희소하게 만들기 어려운 것이 약점이다.
• 증강 라그랑주법. $A$ 를 $A + \gamma B^\top W^{-1} B$ 로 바꾸면 해는 그대로인데 $A$ 블록이 양정치가 되고 $S$ 의 조건수가 좋아진다. 대신 $\gamma$ 가 크면 $A$ 블록 풀이가 어려워진다 — 공짜는 없다.

4.2. 블록 전처리 — 현대의 표준

전체 계를 크리로프 법에 넣고, 전처리기만 블록 구조로 짠다. 머피·골럽·워슨(2000)의 결과가 출발점이다. 이상적 블록 대각 전처리기

$$\mathcal P_D = \begin{bmatrix} A & 0 \\ 0 & S \end{bmatrix}$$

를 쓰면 $\mathcal P_D^{-1}\mathcal K$ 의 고유값은 딱 세 개, $1$ 과 $\tfrac{1\pm\sqrt5}{2}$ 뿐이다. 위 $n=40,m=12$ 예제에서 계산하면 고유값이 정확히 $\{-0.618034,\ 1,\ 1.618034\}$ 로 모인다. 그러니 MINRES 가 최대 3번 만에 끝난다. 블록 상삼각 전처리기

$$\mathcal P_T = \begin{bmatrix} A & B^\top \\ 0 & -S \end{bmatrix}$$

는 더 세다. $T = \mathcal P_T^{-1}\mathcal K$ 의 고유값이 전부 1이고 $(T - I)^2 = 0$ 이다 — 같은 예제에서 $\|T-I\|_F = 16.8$ 인데 $\|(T-I)^2\|_F = 1.4\times10^{-14}$ 다. 최소다항식 차수가 2이므로 GMRES 가 2번 만에 끝난다. 대신 비대칭이라 MINRES 는 못 쓴다.

물론 $A^{-1}$ 과 $S^{-1}$ 을 정확히 쓸 수 있으면 애초에 전처리가 필요 없다. 실무의 기술은 이 둘을 싼 근사로 바꾸고도 반복수가 격자에 무관하게 유지되게 하는 데 있다.

블록	스토크스	나비에-스토크스(오세엔)	최적화(KKT)
$A^{-1}$ 근사	다중격자법 V-사이클 1회	대류-확산용 다중격자	불완전 분해 / 대각
$S^{-1}$ 근사	압력 질량행렬 $M_p$ (대각 근사로도 충분)	PCD, LSC	$B\,\mathrm{diag}(A)^{-1}B^\top$

스토크스에서 $M_p$ 가 좋은 근사인 이유가 바로 inf-sup 이다 — 안정한 요소에서는 $\beta^2 M_p \preceq S \preceq \gamma^2 M_p$ 꼴의 스펙트럼 동치($\gamma$ 는 발산 연산자의 연속 상수로 $d$ 차원에서 $\sqrt d$ 이하)가 $h$ 무관하게 성립한다. 반대로 inf-sup 을 어긴 요소에서는 이 근사가 무너지고 반복수가 격자를 따라 늘어난다. 이산화의 안정성과 솔버의 확장성이 같은 부등식으로 묶여 있는 셈이다.³

PETSc 의 PCFIELDSPLIT(-pc_fieldsplit_type schur)가 이 구조를 옵션 몇 줄로 조립하게 해 준다. 슈어 보수 근사를 selfp(= $B\,\mathrm{diag}(A)^{-1}B^\top$)로 고르는 것이 흔한 출발점이다.

4.3. 직접법

중간 규모(수십만 미지수 이하)에서는 대칭 부정치 희소 직접 솔버가 여전히 가장 튼튼하다. MUMPS·PARDISO 계열이 번치-카우프만식 $2\times2$ 피벗을 쓴다. 주의할 점은 피벗 순서가 희소성 순서와 싸운다는 것이다. $(2,2)$ 블록이 0이라 대각 피벗을 그대로 쓸 수 없고, 수치 안정성을 위해 피벗을 미루면 채움(fill-in)이 예상보다 늘어난다. 최소차수 순서화 결과가 그대로 지켜지지 않는 이유다.

5. 실무 체크리스트

1. 관성부터 확인. 직접 솔버가 보고하는 음수 피벗 수가 $m$ 과 다르면 이산화(inf-sup)나 구속(중복 구속, 떠다니는 압력)이 잘못된 것이다. 최적화에서는 이 수가 2차 조건 위반을 알려 준다.
2. CG 금지. 부정치에 CG 를 걸면 분모가 0이 되어 조용히 깨질 수 있다. 대칭 부정치는 MINRES, 블록 삼각 전처리를 쓰면 GMRES/FGMRES.
3. 전처리기는 양정치로. MINRES 는 양정치 전처리기만 받는다. 그래서 블록 대각에서 $S$ 자리에 $-S$ 가 아니라 $+S$ 근사를 넣는다.
4. 압력 영공간 처리. 순수 디리클레 속도 경계라면 상수 압력 모드를 고정하거나 크리로프 법에 영공간으로 알려 준다.
5. 반복수의 격자 의존성을 잰다. $h$ 를 반으로 줄일 때 반복수가 거의 그대로면 전처리가 제대로 된 것이다. 늘어나면 $S$ 근사나 요소 선택을 의심하라.

6. 관련 문서

• 슈어 보수 · 우자와 알고리즘 · 증강 라그랑주법
• MINRES · GMRES · 전처리기 · 번치-카우프만 피벗
• 혼합유한요소법 · 스토크스 유동 · Rhie-Chow 보간
• 라그랑주 승수법 · 내점법 · 실베스터 관성 법칙
• 안장점 · inf-sup 조건 · 블록 전처리

7. Footnotes

1. 기하학의 안장점과 이 선형계는 이름을 공유할 뿐 문서가 갈린다. 앞쪽은 「찾아야 할 점」, 이쪽은 「그 점을 찾을 때 풀어야 하는 행렬」이다. 둘 다 음수 고유값이 섞여 있다는 공통점이 이름을 이어 준다. ↩

2. 압력은 기울기만 운동방정식에 들어가니 상수를 더해도 아무도 모른다. 비압축 솔버를 처음 짜는 사람이 “직접 솔버가 특이 행렬이래요” 로 한 번씩 겪는 통과의례다. ↩

3. 즉 “솔버가 느리다” 는 보고가 사실은 “요소가 불안정하다” 는 진단일 수 있다. 수치해석에서 문제를 일으킨 범인이 다른 층에 숨어 있는 전형적인 사례다. ↩