우자와 알고리즘

수치해석 전산유체역학 최적설계 마지막 수정: 2026-08-12 04:47:36

1. 개요[편집]

우자와 알고리즘 Uzawa's Algorithm
제안	宇沢弘文(Uzawa, 1958) — Arrow·Hurwicz와 공저
대상	안장점 계 — 스토크스, 비압축성 FEM, 접촉 구속
정체	슈어 보수 계에 대한 리처드슨 반복
스텝 범위	0 < α < 2/λ_max(S), S = BA⁻¹B^T
수렴률 지배	inf-sup(LBB) 상수 β — 작을수록 느리다
변형	증강 우자와 · 부정확 우자와 · 전처리 우자와

우자와 알고리즘은 안장점 형태의 선형계를 압력(또는 승수) 변수에 대한 쌍대 상승법으로 푸는 반복법이다. 비압축성 유동의 유한요소법 이산화나 접촉 구속처럼

\begin{pmatrix} A & B^\top \\ B & 0 \end{pmatrix} \begin{pmatrix} u \\ p \end{pmatrix} = \begin{pmatrix} f \\ g \end{pmatrix}

꼴로 나오는 계가 대상이다. 여기서 $A$ 는 대칭 양정부호(점성/강성), $B$ 는 제약 연산자(이산 발산), $p$ 는 제약의 승수(압력·접촉압)다. 이 블록계는 대각에 0 이 들어와 부정부호(indefinite)라 촐레스키 분해나 표준 반복법이 그대로 안 통한다.

우자와의 처방은 단순하다. $p$ 를 고정하면 $u$ -계는 그냥 양정부호 문제라는 사실을 이용해 두 줄로 쪼갠다.

u^{k+1} = A^{-1}\bigl(f - B^\top p^k\bigr), \qquad p^{k+1} = p^k + \alpha\,\bigl(B u^{k+1} - g\bigr)

첫 줄은 “현재 압력장에서 운동량 방정식을 푼다”, 둘째 줄은 “남은 발산만큼 압력을 올린다”이다. 사실상 CFD 하는 사람이라면 손으로 짜 본 적 있는 그 루프이며, 실제로 SIMPLE 알고리즘 계열의 압력-속도 연성이 이 골격의 변형이다.¹

2. 슈어 보수 — 이 알고리즘의 정체[편집]

두 줄을 하나로 합치면 정체가 드러난다. 첫 줄을 둘째 줄에 대입하면

p^{k+1} = p^k - \alpha\bigl(S p^k - \hat{g}\bigr), \qquad S = B A^{-1} B^\top,\quad \hat{g} = BA^{-1}f - g

즉 우자와 알고리즘 = 슈어 보수 계 $Sp=\hat g$ 에 대한 리처드슨 반복이다. $u$ 는 어디로 갔느냐 하면, 매 반복 압력에서 즉시 복원되는 종속 변수로 소거됐다. 이 관점 하나로 나머지가 전부 따라 나온다.

$A\succ 0$ 이고 $B$ 가 행 계수 full 이면 $S\succ 0$ 이므로, 리처드슨의 표준 결과가 그대로 적용된다.

0 < \alpha < \frac{2}{\lambda_{\max}(S)}, \qquad \alpha^\star = \frac{2}{\lambda_{\min}(S)+\lambda_{\max}(S)}, \qquad \text{수렴률} = \frac{\kappa(S)-1}{\kappa(S)+1}

스텝을 넘기면 발산하고, 잘 잡아도 속도는 $\kappa(S)$ 가 정한다. 여기서 $S$ 를 실제로 조립하는 일은 없다는 점이 중요하다 — $S$ 에 벡터를 곱하는 것은 $A$ -풀이 한 번이며, 알고리즘은 그 곱셈만 쓴다. $S$ 는 조밀 행렬이라 조립하면 희소행렬 구조가 통째로 날아간다.

3. 왜 inf-sup 상수에 목을 매는가[편집]

$\kappa(S)$ 를 이산화 이론과 잇는 것이 이 알고리즘의 핵심 정리다. 스토크스 문제에서 이산 inf-sup 조건(LBB 조건)은

\inf_{q_h \ne 0}\ \sup_{v_h \ne 0}\ \frac{(q_h,\ \nabla\!\cdot v_h)}{\lVert v_h\rVert_1\,\lVert q_h\rVert_0}\ \ge\ \beta > 0

이고, 여기서 $\beta$ 가 격자 크기 $h$ 에 무관하게 아래로 유계인 요소쌍을 “안정한” 요소쌍이라 부른다(테일러-후드 요소 등). 이 상수는 그냥 이론적 장식이 아니라 슈어 보수의 스펙트럼을 직접 가둔다. 압력 질량행렬 $M_p$ 를 기준으로 재면

\beta^2 \;\le\; \frac{(Sq,q)}{(M_p q,q)} \;\le\; \Gamma^2 \qquad \Longrightarrow \qquad \kappa\bigl(M_p^{-1}S\bigr) \le \frac{\Gamma^2}{\beta^2}

$\Gamma$ 는 연속성 상수다. 결론은 두 가지다.

안정한 요소쌍을 쓰면 반복 횟수가 격자에 무관하다. $\beta$ 가 $h$ 와 무관하고, 준균등 격자에서 $M_p$ 자체의 조건수도 $O(1)$ 이므로 $\kappa(S)$ 가 $h$ 를 타지 않는다. 격자를 100만 셀로 늘려도 우자와 반복 수는 거의 그대로다 — 이 성질 하나로 이 늙은 알고리즘이 살아남았다.
거꾸로 $\beta$ 가 작아지면 즉시 느려진다. LBB 를 아슬아슬하게 만족하는 요소쌍, 극단적 종횡비 격자, 얇은 영역, 강한 이방성 — 이런 곳에서 $\beta$ 가 죽고 반복 수가 폭발한다. “수렴이 안 되는데요”의 진단이 곧 “요소쌍이 불안정한가”가 되는 드문 사례이며, 알고리즘의 수렴 속도가 이산화 이론의 상수를 직접 측정해 주는 셈이다.²

$\mathbb{Q}_1$ – $\mathbb{Q}_1$ 처럼 LBB 를 아예 위반하는 쌍을 쓰면 $S$ 가 특이해져 압력에 체커보드 영모드가 생기고, 우자와는 그 방향으로 영원히 표류한다.

4. 증강 우자와[편집]

스텝 튜닝과 느린 수렴을 한 번에 손보는 표준 처방이 증강 라그랑주법을 얹는 것이다. 목적함수에 $\frac{\rho}{2}\lVert Bu-g\rVert^2$ 를 더하면 $u$ -계가 $A_\rho = A+\rho B^\top B$ 로 바뀌고, 승수 스텝을 $\alpha=\rho$ 로 고정한다.

(A + \rho B^\top B)\,u^{k+1} = f - B^\top p^k + \rho B^\top g, \qquad p^{k+1} = p^k + \rho\,(Bu^{k+1}-g)

이때 무슨 일이 일어나는지는 손으로 계산된다. 셔먼-모리슨-우드베리 항등식으로 새 슈어 보수를 정리하면

S_\rho = B\,(A+\rho B^\top B)^{-1}B^\top = S\,(I+\rho S)^{-1}

이고, 반복 오차의 전파 행렬이

I - \rho S_\rho = (I+\rho S)^{-1}

가 된다. 고윳값이 $1/(1+\rho\lambda_i(S))$ 이므로 $\rho>0$ 이기만 하면 어떤 값이든 수렴하고, $\rho$ 를 키울수록 빨라진다. 스텝 상한이 통째로 사라졌다. 이 식은 근접점 알고리즘 문서의 이차 예제에 나오는 $(I+\lambda A)^{-1}$ 과 글자 그대로 같은 모양인데, 우연이 아니라 증강 우자와가 쌍대 문제에 돌린 근접점법이기 때문이다.

공짜는 아니다. $\rho$ 를 키우면 $A_\rho$ 의 조건수가 $\rho$ 에 비례해 커진다 — $B^\top B$ 는 제약 방향으로만 거대한 고윳값을 만들고 나머지 방향은 $O(1)$ 로 남기 때문. 바깥 반복을 빠르게 하려고 안쪽 선형계를 병들게 하는 거래이며, $A_\rho$ 를 다중격자법으로 풀던 코드가 $\rho$ 를 키운 순간 수렴을 잃는 사고가 실제로 흔하다. 이 이유로 증강 우자와 전용 완화자·전처리기가 따로 연구된다.

5. 부정확 우자와[편집]

$u$ -단계의 $A^{-1}$ 을 정확히 적용하는 것은 사실상 불가능하다. $A$ 가 벡터 라플라시안이면 포아송 방정식 3개를 매 반복 정확히 푸는 셈이니 그게 계산 비용의 전부다. 그래서 실무 우자와는 전부 부정확 우자와다 — $A^{-1}$ 대신 다중격자법 V-사이클 한두 번이나 불완전 분해 전처리를 쓴 근사 $\hat{A}^{-1}$ 을 넣는다.

문제는 근사가 거칠면 바깥 반복이 깨진다는 것. 표준 안전 조건은 근사 역이 참 역을 위에서 감싸는 형태( $\hat{A}-A \succeq 0$ , 즉 안쪽 솔버가 “덜 푸는” 쪽으로만 틀리게 하는 것)이고, 여기에 스텝 $\alpha$ 를 그만큼 줄이면 수렴이 보존된다. 좀 더 실용적인 규칙은 근접점 알고리즘의 비정확 판정 기준과 같은 감각이다 — 안쪽 잔차 허용치를 바깥 잔차에 비례시켜라. 초반엔 대충, 수렴이 가까워지면 정밀하게. 안쪽 반복 수를 고정 상수로 박아 두는 코드가 마지막 한 자리에서 정체되는 이유가 대개 이것이다.

6. 전처리 우자와는 사실상 슈어 보수 CG[편집]

$S\succ 0$ 이라는 사실을 알고 나면 자연스러운 질문이 나온다. 왜 리처드슨 같은 원시적인 반복을 쓰나?

\text{우자와} = \text{리처드슨}(S) \quad\longrightarrow\quad \text{켤레기울기법}(S)

$S$ 에 벡터를 곱하는 연산이 이미 있으니 크리로프 부분공간법을 그대로 얹을 수 있고, 그러면 수렴률이 $\frac{\kappa-1}{\kappa+1}$ 에서 $\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}$ 로 개선된다. 이것이 슈어 보수 CG(Uzawa-CG)이며, 전처리기로는 위 스펙트럼 결과가 지목해 주는 압력 질량행렬 $M_p$ 를 쓰는 게 정석이다. $M_p^{-1}S$ 의 스펙트럼이 $[\beta^2,\Gamma^2]$ 안에 갇히니 반복 수가 격자와 무관해진다.

여기서 관점을 뒤집으면 현대적 방법이 보인다. “전처리 우자와”라는 이름을 쓰든 안 쓰든, 이 계열이 하는 일은 결국 슈어 보수의 근사를 어떻게 만드느냐다. 그리고 그렇게 볼 거라면 굳이 $u$ 를 소거할 필요도 없다 — 블록계를 통째로 GMRES나 MINRES 에 넣고, 전처리기의 $(2,2)$ 블록에 $S$ 의 근사를 꽂는 블록 전처리 방식이 그것이다. 이러면 $A^{-1}$ 을 정확히 적용할 필요가 아예 없어진다. 우자와는 이 관점에서 ” $A$ 를 정확히 풀고 $S$ 를 전처리 없이 리처드슨으로 미는” 극단 사례이며, 오늘날 대규모 스토크스·나비에-스토크스 솔버가 블록 전처리 쪽으로 간 이유가 여기 있다.³

SIMPLE 알고리즘도 같은 지도 위에 놓인다. 압력 보정 방정식이 $S$ 를 $B\,\mathrm{diag}(A)^{-1}B^\top$ 로 근사한 것이고, 속도 예측이 부정확한 $u$ -단계에 해당한다. 완화 계수를 못 잡아 SIMPLE 이 진동하는 상황과 $\alpha$ 를 잘못 잡아 우자와가 발산하는 상황은 같은 병이다.

7. 어디서 만나는가[편집]

스토크스 유동·비압축성 FEM. 원래의 무대. 압력이 곧 비압축 제약의 승수다.
접촉 해석. 관통 금지 조건의 승수를 바깥 루프로 갱신하는 증강 라그랑주 접촉이 곧 우자와식 루프다. 수렴 로그에 찍히는 “augmentation 1, 2, 3…”이 그 반복이며, 증강 라그랑주법 문서에 표로 정리돼 있다.
요소 잠김 대책. 비압축성 초탄성 재료의 압력 자유도를 증강 라그랑주로 처리하는 것도 같은 구조다.
최적화 일반. 등식 제약 이차계획에 쌍대 상승법을 돌리면 그게 우자와다. 반대로 원시 최소화를 정확히 하지 않고 근위 스텝 하나로 대체하면 원시-쌍대 알고리즘이 되고, 영상처리 문헌에서 그 계열을 한동안 “분할 부정확 우자와”라 부른 것이 이 연결 때문이다.

8. 관련 문서[편집]

우자와 히로후미는 원래 경제학자이고, 이 알고리즘도 1958년 애로·후르비츠와 함께 낸 비선형 계획법 논문집에 실렸다. 즉 CFD 코드 안에서 매초 수천 번 돌아가는 이 루프의 출처는 일반균형이론이다. 나중에 그는 환경경제학으로 옮겨 갔고, 유체 하는 사람들만 그의 이름을 반복법으로 기억하게 됐다. ↩
그래서 새 요소쌍을 만들었을 때 LBB 를 이론적으로 증명하기 전에 “우자와를 격자 몇 단계로 돌려 보고 반복 수가 늘어나는지” 보는 수치 실험이 관행이다. 반복 수가 $h$ 를 절반으로 줄일 때마다 뚜렷하게 늘면 $\beta \to 0$ 이라는 강력한 정황 증거다. 알고리즘으로 정리를 검증하는 셈. ↩
그렇다고 우자와가 박물관행인 것은 아니다. $A$ -풀이가 압도적으로 싸거나( $\rho$ 를 키운 증강형에서 특히), 코드 구조상 기존 운동량 솔버를 블랙박스로 재사용해야 하거나, 승수의 부호 제약(접촉)처럼 사영을 끼워야 하는 상황에서는 여전히 이쪽이 편하다. 블록 전처리는 우아하지만 기존 솔버를 통째로 뜯어야 한다. ↩