스펙트럼 반지름

1. 개요[편집]

스펙트럼 반지름 Spectral radius
정의	$\rho(A) = \max_i |\lambda_i(A)|$
겔판트 공식	$\rho(A) = \lim_{k\to\infty}\lVert A^k\rVert^{1/k}$
노름과의 관계	모든 유도 노름에 대해 $\rho(A) \le \lVert A\rVert$
거듭제곱 소멸	$A^k \to 0 \iff \rho(A) < 1$
노름인가	아니다 — 삼각부등식이 깨진다
함정	비정규 행렬에서는 점근 정보만 준다

“고유값이 다 단위원 안에 있으니 안정합니다.” 맞는 말이다. 다만 그 ‘결국’이 언제인지는 아무 말도 하지 않았다.

스펙트럼 반지름(spectral radius) $\rho(A)$ 는 정사각행렬 $A$ 의 고유값 절댓값 중 최댓값, 즉 복소평면에서 스펙트럼 전체를 담는 최소 원의 반지름이다.

$$\rho(A) = \max\{|\lambda| : \lambda \in \sigma(A)\}$$

이 한 숫자가 하는 일은 하나뿐이지만 그 하나가 크다 — 거듭제곱 $A^k$ 의 점근 거동을 완전히 결정한다. 반복법이 수렴하는지, 이산 동역학계가 안정한지, 시간 전진 스킴이 폭발하는지가 전부 $\rho < 1$ 이라는 부등식 하나로 갈린다.

동시에 이 문서의 절반은 $\rho$ 가 말해 주지 않는 것에 대한 이야기다. $\rho$ 는 $k \to \infty$ 의 정보이고, 비정규 행렬에서는 유한 $k$ 에서의 거동이 그 점근값과 자릿수로 어긋난다. 이 어긋남을 모른 채 “고유값이 다 안쪽에 있으니 됐다”고 결론짓는 것이 이 바닥의 고전적 사고 유형이다.

2. 기본 성질[편집]

정의에서 바로 따라오는 것들부터.

• $\rho(A^k) = \rho(A)^k$, $\rho(cA) = |c|\rho(A)$.
• $A$ 가 가역이면 $\rho(A^{-1}) = 1/\min_i|\lambda_i|$. 즉 $\rho$ 만으로는 조건수를 알 수 없다.
• 삼각행렬이면 $\rho$ 는 대각 원소의 최대 절댓값이다. 슈어 분해 $A = QTQ^H$ 를 계산하면 $\rho$ 가 공짜로 나온다.
• 에르미트 행렬에서는 $\rho(A) = \lVert A\rVert_2$. 더 일반적으로 정규 행렬에서만 이 등호가 성립한다.

가장 자주 쓰이는 부등식은 임의의 유도 노름(더 넓게는 곱셈적 노름)에 대해

$$\rho(A) \le \lVert A \rVert$$

이고, 증명은 고유쌍 $Av = \lambda v$ 를 넣어 $|\lambda|\lVert v\rVert = \lVert Av\rVert \le \lVert A\rVert\lVert v\rVert$ 한 줄이다. 여기에 역방향 결과가 붙는다 — 임의의 $\varepsilon > 0$ 에 대해 $\lVert A\rVert \le \rho(A) + \varepsilon$ 인 유도 노름이 존재한다. 따라서 $\rho$ 는 모든 유도 노름의 최대하계다. 자세한 노름 쪽 논의는 유도 노름 문서에 있다.

주의할 함정 하나. $\rho$ 는 노름이 아니다. $A = \begin{bmatrix}0&1\\0&0\end{bmatrix}$, $B = A^\top$ 이면 $\rho(A) = \rho(B) = 0$ 인데 $\rho(A+B) = 1$ 이고 $\rho(AB) = 1$ 이다. 삼각부등식도 곱셈성도 깨진다. 그래서 ”$\rho$ 가 작으니 섭동해도 작겠지” 같은 추론은 근거가 없다.

3. 겔판트 공식[편집]

$\rho \le \lVert A\rVert$ 의 간격은 $A$ 를 거듭제곱하면 사라진다. 곱셈적 노름 아무거나 잡고

$$\rho(A) = \lim_{k \to \infty} \lVert A^k \rVert^{1/k}$$

이 성립한다는 것이 겔판트 공식(1941)이다. 부등식 한쪽은 $\rho(A)^k = \rho(A^k) \le \lVert A^k\rVert$ 에서 즉시 나오고, 반대쪽은 $\rho(A) < r$ 일 때 $A/r$ 의 거듭제곱이 0으로 가는 것을 보이면 된다.

이 공식은 세 가지를 동시에 말한다.

1. 노름 선택이 점근적으로 무의미하다. 어떤 노름으로 재든 $k$ 제곱근을 취하면 같은 값에 수렴한다.
2. $\rho(A) < 1 \iff A^k \to 0$. 곧 나올 반복법 수렴 정리의 전부다.
3. 수렴은 느릴 수 있다. $\lVert A^k\rVert^{1/k}$ 가 $\rho$ 에 접근하는 속도에 대해서는 아무 보장이 없다. 결손(defective) 행렬에서는 $\lVert A^k\rVert \sim k^{m-1}\rho^k$ ($m$ 은 조르당 블록 크기)라 다항 인자가 오래 살아남는다.

겔판트 공식은 바나흐 대수에서도 그대로 성립하며(원래 그 맥락에서 증명됐다), 그래서 무한차원 작용소의 스펙트럼 반지름도 같은 식으로 정의된다.

4. 반복법 수렴의 필요충분조건[편집]

정지 반복법 $x^{(k+1)} = Gx^{(k)} + c$ 를 생각하자. 참해 $x^*$ 는 고정점이고 오차는 $e^{(k)} = G^k e^{(0)}$ 이므로,

$$\text{모든 } e^{(0)} \text{에 대해 } e^{(k)}\to 0 \iff G^k \to 0 \iff \rho(G) < 1$$

이것이 필요충분조건이라는 점이 핵심이다. 실무에서 흔히 쓰는 $\lVert G\rVert_\infty < 1$ (엄격 대각 우세 등)은 충분조건일 뿐이고, 그 보수성이 곧 $\rho$ 와 노름 사이의 간격이다.

수렴 속도도 $\rho$ 가 정한다. 큰 $k$ 에서 오차가 반복당 대략 $\rho$ 배씩 줄므로, 자릿수 하나를 얻는 데 필요한 반복 수는

$$k \approx \frac{1}{-\log_{10}\rho(G)}$$

이다. $\rho = 0.9$ 면 22회, $\rho = 0.99$ 면 230회, $\rho = 0.999$ 면 2300회. 격자를 조일수록 $\rho \to 1$ 이라 반복 수가 폭발하는 것이 고전 반복법의 사형선고였다.

4.1. 야코비 · 가우스-자이델 · SOR[편집]

분할 $A = M - N$ 에 대해 반복행렬은 $G = M^{-1}N$ 이다. 알고리즘 자체는 반복법 문서에 있으니, 여기서는 $\rho$ 가 실제로 얼마인지만 본다. 단위 정사각형 위 포아송 방정식을 격자 간격 $h = 1/N$ 의 5점 차분으로 이산화한 표준 예제에서:

방법	스펙트럼 반지름	$h \to 0$ 점근	반복 수
야코비	$\cos \pi h$	$1 - \tfrac{1}{2}\pi^2h^2$	$O(h^{-2})$
가우스-자이델	$\cos^2 \pi h$	$1 - \pi^2h^2$	$O(h^{-2})$, 야코비의 절반
SOR(최적 $\omega$)	$\omega_{\text{opt}} - 1$	$1 - 2\pi h$	$O(h^{-1})$

“가우스-자이델이 야코비보다 두 배 빠르다”는 흔한 말의 정확한 의미가 이 표에 있다 — $\rho_{GS} = \rho_J^2$ 이므로 반복 하나가 야코비 두 번어치이지 수렴 차수가 개선된 게 아니다. 차수를 바꾸는 것은 SOR뿐이고, 그 대가는 최적 완화계수를 알아야 한다는 것이다.

영(D. M. Young)의 이론에 따르면 일관 순서화(consistently ordered)이고 성질 A를 갖는 행렬에서

$$\omega_{\text{opt}} = \frac{2}{1 + \sqrt{1 - \rho_J^2}}, \qquad \rho_{\text{SOR}}(\omega_{\text{opt}}) = \omega_{\text{opt}} - 1$$

이 성립한다. 위 예제면 $\rho_J = \cos\pi h$ 라 $\omega_{\text{opt}} = 2/(1 + \sin\pi h) \approx 2 - 2\pi h$ 이고, $\rho_{\text{SOR}} \approx 1 - 2\pi h$ 다. $h = 1/100$ 이면 가우스-자이델의 $\rho \approx 0.9990$ 이 SOR에서 $0.9391$ 로 떨어진다 — 반복 수 60배 차이.

문제는 이 공식이 $\rho_J$ 를 미리 알아야 쓸 수 있다는 것이고, 게다가 $\omega$ 에 대한 $\rho_{\text{SOR}}$ 곡선이 $\omega_{\text{opt}}$ 에서 왼쪽은 완만하고 오른쪽은 벼랑처럼 꺾인다. 틀릴 거면 크게 잡지 말고 작게 잡으라는 실무 격언이 여기서 나온다.¹ 이 민감성이 결국 SOR을 주역 자리에서 밀어냈고, 오늘날 같은 $O(h^{-1})$ 을 켤레기울기법이 파라미터 없이, 다중격자법이 아예 $O(1)$ 로 해낸다.

5. 비음수 행렬 — 페론-프로베니우스[편집]

$A \ge 0$ (성분별 비음수)이면 $\rho$ 에 대해 훨씬 강한 말을 할 수 있다. 페론-프로베니우스 정리는 기약(irreducible) 비음수 행렬에서 $\rho(A)$ 자체가 고유값이며, 단순하고, 대응 고유벡터를 성분이 전부 양수인 것으로 잡을 수 있음을 말한다. 게다가 행 합의 최솟값과 최댓값 사이에 갇힌다.

$$\min_i \sum_j a_{ij} \;\le\; \rho(A) \;\le\; \max_i \sum_j a_{ij}$$

확률행렬이면 행 합이 전부 1이므로 $\rho = 1$ 이고, 그 고유벡터가 정상분포다. 페이지랭크의 존재·유일성, 마르코프 연쇄의 수렴, 인구 모형의 성장률, 투입산출 모형의 생산 가능성이 전부 이 정리 위에 서 있다. 수치해석 쪽으로는 M-행렬 이론과 정칙 분할(regular splitting)의 수렴 판정이 여기서 나온다 — $A$ 가 M-행렬이면 야코비·가우스-자이델 반복행렬이 비음수가 되어 $\rho < 1$ 이 자동으로 보장된다. 자세한 것은 페론-프로베니우스 정리 문서에.

6. $\rho < 1$ 인데도 터질 때 — 과도 성장[편집]

여기서부터가 진짜다. $\rho(A) < 1$ 은 $\lVert A^k\rVert \to 0$ 을 보장한다. 단조 감소는 전혀 보장하지 않는다.

대각화 가능한 $A = V\Lambda V^{-1}$ 에 대해

$$\lVert A^k \rVert \le \kappa(V)\,\rho(A)^k$$

이고, 비정규 행렬에서는 고유벡터 행렬의 조건수 $\kappa(V)$ 가 $10^6$, $10^{12}$ 까지 치솟는다. 그 결과 $\lVert A^k\rVert$ 가 처음 수백 스텝 동안 수천 배로 부풀었다가 나중에 지수적으로 죽는 궤적이 가능하다. 이것이 과도 성장(transient growth)이다.

$$\rho(A) < 1 \;\text{인데}\; \lVert A \rVert \gg 1 \;\Longrightarrow\; \text{초기에는 커진다}$$

실제로 $\lVert A^k\rVert$ 의 초기 기울기를 정하는 것은 $\rho$ 가 아니라 $\lVert A\rVert$ 이고, 최대 증폭 크기는 의사스펙트럼이 단위원 밖으로 얼마나 삐져나오는지가 정한다. 크라이스 행렬 정리는 이 관계를 부등식으로 못박는다 — 크라이스 상수 $\mathcal{K}(A) = \sup_{|z|>1}(|z|-1)\lVert (zI-A)^{-1}\rVert$ 에 대해

$$\mathcal{K}(A) \;\le\; \sup_k \lVert A^k\rVert \;\le\; e\,n\,\mathcal{K}(A)$$

이다. 즉 거듭제곱의 최대 크기는 스펙트럼이 아니라 레졸벤트가 결정한다.

공학적으로 이게 문제가 되는 곳은 넘친다.

• 유동 안정성. 평면 푸아죄유·쿠에트 유동의 선형화 연산자는 모든 고유값이 안정한 레이놀즈수에서도 초기 교란을 $O(Re^2)$ 배 증폭한다. 이 증폭이 비선형항을 깨워 천이가 일어나는 것이 아우회 천이(bypass transition)이고, 모달 안정성 해석이 실험과 안 맞았던 오랜 미스터리의 정답이었다. 난류 천이 참고.
• 시간 전진 스킴. 폰 노이만 안정성 해석은 푸리에 모드를 쓰므로 본질적으로 정규 가정이다. 주기 경계가 아닌 순간 증폭행렬이 비정규가 되고, $\rho \le 1$ 은 랙스 의미의 안정성을 보장하지 못한다. 이것이 GKS 이론이 따로 필요한 이유다.
• 크리로프 부분공간법의 수렴. GMRES 잔차 상한을 고유값만으로 쓰면 $\kappa(V)$ 가 앞에 붙어 무의미해진다. 비정규 문제에서 “고유값이 뭉쳐 있으니 빨리 수렴할 것”이라는 예측은 자주 틀린다. GMRES 수렴은 스펙트럼이 아니라 의사스펙트럼·수치범위로 봐야 한다.

요약하면, $\rho$ 는 $k \to \infty$ 의 답이고 공학은 대개 유한 $k$ 를 쓴다. 정규 행렬이면 둘이 같지만, 현실의 이류 연산자·전단 유동·비대칭 감쇠 시스템은 대부분 정규가 아니다.

7. 실제로 계산하려면[편집]

• 작은 밀집 행렬: 슈어 분해를 계산해 대각을 읽는다. LAPACK dgeev/dgees. $O(n^3)$.
• 큰 희소 행렬: 최대 절댓값 고유값 하나만 필요하므로 거듭제곱법 또는 아놀디 알고리즘(ARPACK의 LM 모드). 다만 최대 고유값이 복소 켤레쌍이면 순수 거듭제곱법은 진동하고 수렴하지 않는다 — 이때 $\lVert A^kv\rVert^{1/k}$ 로 크기만 추정하거나 부분공간 반복으로 넘어간다.
• 상한만 필요하면: 게르슈고린 원판이나 $\rho \le \sqrt{\lVert A\rVert_1\lVert A\rVert_\infty}$ 로 두 번 훑어 끝낸다. 반복법 수렴 판정에는 이 정도로 충분한 경우가 많다.
• 겔판트 공식으로 재지 마라. $\lVert A^k\rVert^{1/k}$ 는 이론적으로는 옳지만 수렴이 느리고 오버·언더플로에 취약하다. 정의를 알고리즘으로 착각하는 전형적 사례.²

리아푸노프 쪽 판정도 유용하다. $\rho(A) < 1$ 은 어떤 $P \succ 0$ 에 대해 $A^\top P A - P \prec 0$ 인 것과 동치이고(리아푸노프 방정식의 이산 버전), 이 형태는 선형행렬부등식으로 바로 던질 수 있어 파라미터가 있는 시스템의 강건 안정성 검증에 쓰인다. 게다가 여기서 나오는 $P$ 는 노름 $\lVert x\rVert_P = \sqrt{x^\top Px}$ 를 정의하는데, 그 노름에서는 과도 성장이 아예 없다 — 비정규성은 좌표계의 문제이기도 하다는 관점이 여기서 나온다.³

8. 관련 문서[편집]

• 고유값 문제 · 유도 노름 · 조건수 · 슈어 분해
• 반복법 · 켤레기울기법 · 다중격자법 · 전처리기
• 비정규 행렬 · 의사스펙트럼 · 크리로프 부분공간법 · GMRES
• 페론-프로베니우스 정리 · 페이지랭크 · 거듭제곱법 · 아놀디 알고리즘
• 폰 노이만 안정성 해석 · 난류 천이 · 리아푸노프 방정식 · 랴푸노프 지수
• 행렬 곱셈 · 행렬함수 · 포아송 방정식

9. Footnotes[편집]

1. $\omega$ 를 $\omega_{\text{opt}}$ 보다 크게 잡으면 $\rho_{\text{SOR}} = \omega - 1$ 이 $\omega$ 에 대해 기울기 1로 직선 상승하고, 작게 잡으면 완만한 곡선을 탄다. 그래서 잘 모르면 조금 작게 잡는 게 안전한데, 실전에서는 그냥 $\omega$ 를 0.05 간격으로 열 개쯤 돌려 보고 제일 빠른 걸 고른다. 이론이 아무리 예뻐도 결국 노가다가 이긴다. ↩

2. 비슷한 부류로 “행렬식으로 특이성을 판정한다”, “정의대로 역행렬을 만들어 곱한다”, “고유다항식의 근을 구한다”가 있다. 셋 다 수학적으로는 옳고 수치적으로는 전부 사고다. 정의는 정의고 알고리즘은 알고리즘이다. ↩

3. 그렇다고 비정규성이 “가짜”인 것은 아니다. 물리적으로 의미 있는 노름(유동에서는 교란 운동에너지)이 미리 정해져 있고, 과도 성장은 그 노름에서 실제로 일어나는 현상이다. $P$-노름으로 갈아타면 성장이 사라지지만 그 노름은 물리적으로 재고 싶은 양이 아니다. 좌표를 바꿔 문제를 없애는 것과 문제를 안 보이게 만드는 것은 다르다. ↩