대각 우세 행렬

1. 개요

대각 우세 행렬 Diagonally Dominant Matrix
정의 (행)	각 행에서 |대각| ≥ 나머지 성분 절댓값의 합
엄격	모든 행에서 부등호가 강하면 정칙 (레비-데플랑크)
약한 경우	기약 + 한 행 이상 엄격이면 정칙 (타우스키)
보장하는 것	야코비·가우스-자이델 수렴, 피벗 없는 소거의 성장 인자 ≤ 2
일반화	H-행렬, 블록 대각 우세
등장처	확산 이산화, 암시적 시간적분, 풍상 대류, 회로 절점 해석

각 미지수가 자기 방정식에서 제일 큰 목소리를 낸다. 그러면 행렬이 얌전하다는 걸 거의 공짜로 증명할 수 있다.

대각 우세 행렬(diagonally dominant matrix)은 각 행에서 대각 성분의 절댓값이 같은 행의 나머지 성분 절댓값 합보다 작지 않은 정사각행렬이다.

$$\lvert a_{ii} \rvert \ \ge\ \sum_{j \ne i} \lvert a_{ij} \rvert \qquad (i = 1, \dots, n).$$

모든 행에서 등호 없이 $>$ 이면 엄격 대각 우세(strictly diagonally dominant, SDD), 등호를 허용하면 약한 대각 우세라 한다. 행 대신 열로 잰 것이 열 대각 우세이고, $A^\top$ 의 행 대각 우세와 같다.

수치해석에서 이 조건이 사랑받는 이유는 검사가 $O(\text{nnz})$ 로 싸고 결론이 많기 때문이다. 고유값 하나 안 구하고, 행렬식 하나 안 계산하고, 각 행의 절댓값 합만 보면 정칙성·반복법 수렴·피벗 없는 소거의 안전성·역행렬 노름 상한이 한꺼번에 나온다. 게다가 물리 문제를 정직하게 이산화하면 이 조건이 저절로 생기는 경우가 많다.

• 확산 이산화: 포아송 방정식의 표준 5점·7점 스텐실은 내부 행에서 등호(약한 우세), 경계 인접 행에서 엄격 우세가 된다.
• 암시적 시간적분: $(I + \Delta t\,A)$ 꼴은 $A$ 가 약한 우세이고 대각이 양수면 어떤 $\Delta t > 0$ 에서도 엄격 우세다. 시간 스텝이 행렬을 착하게 만든다.
• 풍상 대류: 1차 풍상 차분은 페클레 수와 상관없이 우세를 지킨다. 중앙차분은 격자 페클레 수 2를 넘으면 잃는다 — 이 대목은 M-행렬·토머스 알고리즘 문서에 실측이 있다.
• 회로의 절점 해석: 저항망의 컨덕턴스 행렬은 각 절점의 자기 컨덕턴스가 이웃 컨덕턴스의 합이라 약한 우세이고, 접지로 가는 경로가 있는 절점에서 엄격해진다.
• 스플라인: 자연 3차 스플라인의 삼중대각계는 대각 4, 비대각 1, 1 이라 넉넉하게 엄격 우세다.

2. 정칙성 — 한 줄짜리 증명

레비-데플랑크 정리: 엄격 대각 우세 행렬은 정칙이다¹.

증명은 정말 한 줄이다. $A\mathbf{x} = 0$, $\mathbf{x} \ne 0$ 이라 하고 $\lvert x_i \rvert$ 가 최대인 $i$ 를 고르면

$$\lvert a_{ii} \rvert\,\lvert x_i \rvert = \Bigl\lvert \sum_{j \ne i} a_{ij} x_j \Bigr\rvert \le \sum_{j\ne i} \lvert a_{ij} \rvert\,\lvert x_i \rvert < \lvert a_{ii} \rvert\,\lvert x_i \rvert$$

로 모순이다. 이것을 $A - \lambda I$ 에 적용하면 곧바로 거슈고린 원판 정리가 된다 — 모든 고유값은 중심 $a_{ii}$, 반지름 $\sum_{j\ne i}\lvert a_{ij}\rvert$ 인 원판들의 합집합 안에 있다. 엄격 대각 우세는 「원점이 어느 원판에도 안 들어간다」와 같은 말이다.

여기서 바로 따라오는 것들:

• 엄격 우세이고 대각이 모두 양의 실수면 모든 고유값의 실수부가 양수다.
• 여기에 대칭까지 더하면 대칭 양정치다. 촐레스키 분해를 그대로 쓸 수 있다. 약한 우세면 양반정치까지만 보장된다.

2.1. 약한 우세의 함정과 타우스키 정리

약한 우세만으로는 정칙이 보장되지 않는다. $\begin{pmatrix} 1 & 1 \\ 1 & 1\end{pmatrix}$ 은 약한 우세인데 특이하다. 더 중요한 예가 주기 경계·순수 노이만 경계의 라플라시안이다. 모든 행이 등호라 상수 벡터가 영공간에 들어간다($n = 6$ 주기 라플라시안의 최소 고유값을 재면 $-7\times10^{-16}$, 즉 0이다).

이를 메우는 것이 타우스키 정리(1949)다.

기약이고, 약한 대각 우세이며, 적어도 한 행에서 엄격하면 정칙이다.

기약(irreducible)은 행렬을 그래프로 봤을 때 모든 절점이 서로 연결돼 있다는 뜻이다. 디리클레 경계의 라플라시안이 정확히 이 경우다 — 내부 행은 등호지만 경계에 닿은 행이 엄격하고, 격자가 연결돼 있으니 그 「여유」가 전체로 퍼진다($n=6$ 에서 최소 고유값 0.198). 「경계 어딘가에 디리클레 조건이 하나는 있어야 해가 유일하다」는 PDE 쪽 직관의 행렬판이다².

3. 반복법 수렴 — 상한은 상한일 뿐

반복법의 야코비 반복행렬 $G_J = -D^{-1}(L+U)$ 에 대해

$$\lVert G_J \rVert_\infty = \max_i \frac{\sum_{j\ne i}\lvert a_{ij} \rvert}{\lvert a_{ii} \rvert} < 1$$

이므로 엄격 우세면 야코비가 수렴한다. 가우스-자이델도 수렴하고, 기약 + 약한 우세 + 한 행 엄격인 경우에도 둘 다 수렴한다(바르가).

그런데 이 노름은 최악의 부호 배치를 가정한 상한이다. $n = 50$ 무작위 행렬의 대각을 「비대각 절댓값 합 + 0.1」로 맞춰 엄격 우세 여유를 거의 0으로 만들고, 비대각 부호만 바꿔 비교했다.

비대각 부호	$\lVert G_J\rVert_\infty$	$\rho(G_J)$	$\rho(G_{GS})$
무작위 ±	0.998	0.187	0.093
전부 음수 (M-행렬)	0.998	0.997	—

여유는 똑같이 빠듯한데, 부호가 섞이면 이웃의 기여가 상쇄돼 실제 수렴률이 0.19 로 빠르다. 부호가 한쪽으로 몰린 M-행렬에서는 상한이 거의 그대로 실현된다. 확산 이산화가 바로 그 M-행렬 부호 패턴이라, 실전 PDE 행렬은 대개 상한에 붙어서 느리게 수렴한다. 대각 우세의 여유는 수렴 보장이지 수렴 속도 예측이 아니다.

4. 역행렬 노름 — 바라 상한

바라(Varah, 1975)는 엄격 우세 여유 $\alpha = \min_i \bigl(\lvert a_{ii} \rvert - \sum_{j\ne i}\lvert a_{ij}\rvert\bigr)$ 로 역행렬 노름을 묶었다.

$$\lVert A^{-1} \rVert_\infty \le \frac{1}{\alpha}.$$

위와 같은 $n=50$ 행렬에서 재면:

• M-행렬 부호, 여유 0.1 → $\lVert A^{-1}\rVert_\infty = 10.000$ (상한 10과 정확히 일치), 여유 1.0 → $1.000$ (상한 1)
• 무작위 부호, 여유 0.1 → $0.0577$ (상한 10)

M-행렬에서는 행 합이 모두 $\alpha$ 이면 $A\mathbf{1} = \alpha\mathbf{1}$ 이라 $A^{-1}\mathbf{1} = \mathbf{1}/\alpha$ 이고, $A^{-1} \ge 0$ 이니 상한이 그대로 달성된다. 이 상한 덕에 조건수를 행렬을 풀지도 않고 어림할 수 있다 — $\kappa_\infty \le \lVert A \rVert_\infty / \alpha$.

5. 피벗 없는 가우스 소거

가우스 소거법은 보통 부분 피벗팅이 필요하지만 대각 우세면 필요 없다. 핵심은 슈어 보수가 대각 우세를 물려받는다는 것이다. 첫 열을 소거한 뒤 남은 $(n-1)\times(n-1)$ 슈어 보수도 대각 우세이므로 다음 피벗도 0이 아니고, 이것이 끝까지 이어진다.

• 행 또는 열 대각 우세인 정칙 행렬은 피벗 없이 LU 분해가 존재하고 성장 인자가 2 이하다(윌킨슨; 하이엄 정리 9.9).
• 열 대각 우세면 부분 피벗팅을 켜도 행 교환이 한 번도 일어나지 않는다.

성장 인자 2 이하는 곧 후진 오차 해석 의미의 안정성이다. 위 $n=50$ 엄격 우세 행렬에서 피벗 없이 소거하면 성장 인자가 1.002였다. 띠 행렬에서 피벗을 안 해도 된다는 건 띠 폭이 안 늘어난다는 뜻이기도 해서, 토머스 알고리즘이나 띠 솔버가 대각 우세 계에서 피벗 없이 도는 근거가 이것이다.

6. 일반화 — 척도만 바꾸면 우세해지는 행렬

대각 우세는 척도에 의존한다. 미지수 단위를 바꾸면(열에 양수를 곱하면) 우세가 생기거나 사라진다.

$$A = \begin{pmatrix} 1 & 3 \\ 0.1 & 1 \end{pmatrix}$$

은 첫 행이 우세가 아니다. 그런데 $D = \mathrm{diag}(1, 0.2)$ 로 열을 스케일하면 $AD = \begin{pmatrix} 1 & 0.6 \\ 0.1 & 0.2\end{pmatrix}$ 가 엄격 우세가 된다. 이런 양의 대각 $D$ 가 존재하는 행렬을 H-행렬(일반화 대각 우세)이라 한다. 비교 행렬 $\langle A \rangle$ (대각은 $\lvert a_{ii}\rvert$, 비대각은 $-\lvert a_{ij}\rvert$)이 정칙 M-행렬인 것과 동치이고, 대각 우세의 결론 대부분(정칙성, 야코비 수렴, 피벗 없는 소거)이 그대로 성립한다. 위 예는 $\langle A\rangle$ 의 행렬식이 $1 - 0.3 = 0.7 > 0$ 이라 M-행렬 판정을 통과한다.

블록 구조가 있는 계에는 블록 대각 우세(파인골드·바르가, 1962)가 쓰인다. 스칼라 절댓값 대신 블록의 노름을 쓰고, 대각 블록에는 $\lVert A_{ii}^{-1}\rVert^{-1}$ 을 쓴다. 블록 삼중대각 토머스 알고리즘의 안전 조건이 이 꼴이다.

7. 충분조건일 뿐

대각 우세가 아니어도 멀쩡한 행렬은 많다. 대각이 1, 비대각이 모두 0.9인 $3\times3$ 행렬은 고유값이 $2.8, 0.1, 0.1$ 인 대칭 양정치인데, 각 행에서 $1 < 0.9 + 0.9$ 라 우세가 아니다. 고차 유한요소의 강성행렬, 둔각 삼각형이 섞인 메시의 선형 요소 강성행렬, 4차 중앙차분 같은 넓은 스텐실도 비대각에 양수가 끼어 우세가 깨지지만 대부분 SPD 라 CG 가 잘 돈다. 대각 우세는 「이것만 확인하면 안심」의 조건이지 「이게 아니면 위험」의 조건이 아니다³.

반대로 대각 우세가 깨지는 것이 실제로 경고인 경우도 있다. 대류 지배 문제에서 중앙차분이 우세를 잃는 순간은 이산 최대 원리가 깨지고 해가 진동하기 시작하는 순간과 같다. 이때는 우세를 잃었다는 사실이 수치해의 물리적 타당성에 대한 정보다.

8. 관련 문서

• M-행렬 · 거슈고린 원판 정리 · 슈어 보수 · 조건수 · 스펙트럼 반지름
• 반복법 · 가우스 소거법 · 토머스 알고리즘 · 촐레스키 분해 · 후진 오차 해석
• 포아송 방정식 · 대류-확산 방정식 · 풍상차분 · 이산 최대 원리 · 페클레 수

9. Footnotes

1. 레비(1881)와 데플랑크(1886)가 각각 특수한 경우와 일반 경우를 보였고, 이후 민코프스키·아다마르 등이 여러 번 다시 발견했다. 타우스키가 1949년 논문 제목을 「되풀이되는 정리」라고 붙인 게 이 때문이다 — 증명이 너무 짧아서 다들 자기가 처음 찾은 줄 알았다. ↩

2. 노이만 경계만 걸어 놓고 솔버가 수렴을 안 한다고 하소연하는 질문이 포럼마다 있다. 행렬은 정직하게 「해가 상수만큼 안 정해졌다」고 말하고 있는 것이다. 한 점 고정하거나 평균 0 조건을 걸어 주면 해결된다. ↩

3. 「대각 우세가 아니니까 야코비가 발산하겠네」는 논리 오류다. 충분조건의 부정은 아무 말도 하지 않는다. 시험 답안지에서 자주 보이는 실수라 채점자들이 붉은 펜을 아끼지 않는 대목. ↩