슈어 분해

1. 개요[편집]

슈어 분해 Schur decomposition
형태	$A = Q T Q^H$ ($Q$ 유니터리, $T$ 상삼각)
존재성	모든 정사각 복소행렬에 대해 성립 (Schur, 1909)
계산	헤센베르크 축약 + 시프트 QR 알고리즘
비용	고유값만 $\approx 10n^3$, $T$·$Q$ 모두 $\approx 25n^3$ flops
LAPACK	LAPACK dgees / zgees (재정렬 dtrsen)

대각화는 못 할 수도 있다. 삼각화는 언제나 된다. 그것도 유니터리로.

슈어 분해(Schur decomposition)는 임의의 정사각 복소행렬 $A \in \mathbb{C}^{n \times n}$ 를

$$A = Q T Q^{H}, \qquad Q^{H}Q = I$$

꼴로 쓰는 분해다. $T$ 는 상삼각행렬이고, 유니터리 상사변환은 고유값을 보존하므로 $T$ 의 대각 원소가 곧 $A$ 의 고유값이다. 예외 조건이 붙지 않는다는 점이 핵심 — 대각화 가능이든 결함(defective)이든, 대칭이든 아니든, 모든 복소 정사각행렬에 대해 존재한다. 1909년 이사이 슈어가 증명했다.¹

증명은 귀납법 한 줄이다. 고유쌍 $(\lambda_1, v_1)$ 을 하나 잡아 $\|v_1\|_2 = 1$ 로 정규화하고, $v_1$ 을 첫 열로 하는 유니터리 $U$ 를 만들면 $U^H A U$ 의 첫 열이 $(\lambda_1, 0, \dots, 0)^T$ 가 된다. 남은 $(n-1) \times (n-1)$ 블록에 같은 짓을 반복하면 끝. 대수학의 기본정리 말고는 아무것도 쓰지 않았고, 그래서 실수 범위에서는 이 증명이 그대로 굴러가지 않는다(아래 실 슈어 형 참조).

2. 왜 유니터리가 그렇게 중요한가[편집]

$A = V \Lambda V^{-1}$ 로 대각화하는 쪽이 훨씬 예쁘다. 그런데 이 $V$ 는 두 가지 방식으로 배신한다. 첫째, 조르당 표준형이 필요한 결함 행렬에서는 아예 존재하지 않는다. 둘째, 존재하더라도 비정규 행렬에서는 $\kappa_2(V) = \|V\|\|V^{-1}\|$ 가 $10^{10}$ 을 넘겨 버릴 수 있고, 바우어-피케 정리가 말하듯 고유값의 섭동 민감도는 정확히 그 조건수에 비례한다.

유니터리 행렬은 $\kappa_2(Q) = 1$ 이다. 2-노름을 정확히 보존하므로 $\|QXQ^H\|_2 = \|X\|_2$, 반올림 오차가 변환을 거치며 증폭되지 않는다. 그 결과 슈어 분해는 후진 안정하다 — 부동소수점으로 계산한 $\hat{Q}, \hat{T}$ 는 $\|\Delta A\| = O(u)\|A\|$ 인 어떤 $A + \Delta A$ 의 정확한 슈어 분해가 된다.² “이론적으로 가장 좋은 표준형”은 조르당이지만 “실제로 계산할 수 있는 표준형”은 슈어라는 말이 여기서 나온다.

정규 행렬($AA^H = A^HA$)에서는 $T$ 가 아예 대각이 된다. 즉 정규성과 “슈어 형이 대각”은 동치이고, 에르미트 행렬의 스펙트럼 정리는 슈어 분해의 따름정리에 불과하다. 반대로 $T$ 의 비대각 성분 크기 $\|T - \mathrm{diag}(T)\|_F$ 는 비정규성의 정량적 척도(헨리치 척도)로 쓰이며, 의사스펙트럼 계산이 슈어 형 위에서 이루어지는 것도 같은 이유다.

3. 실 슈어 형[편집]

$A$ 가 실행렬이어도 고유값은 켤레복소수 쌍으로 나올 수 있으니, 실수 산술만으로 상삼각화하는 것은 불가능하다. 대신 직교행렬 $Q$ 로

$$A = Q T Q^{T}, \qquad T = \begin{bmatrix} T_{11} & \cdots & T_{1m} \\ & \ddots & \vdots \\ & & T_{mm}\end{bmatrix}$$

인 준상삼각(quasi-upper-triangular) 형을 만든다. 대각 블록 $T_{ii}$ 는 실고유값에 대응하는 $1 \times 1$ 이거나, 켤레쌍에 대응하는 $2 \times 2$ 다. 복소 산술을 쓰지 않으니 메모리와 연산이 대략 절반이고, 실무 코드가 다루는 것은 거의 항상 이쪽이다.

4. 계산 — 헤센베르크 축약 + 시프트 QR[편집]

슈어 형을 유한 단계로 구하는 알고리즘은 원리적으로 존재할 수 없다. 고유값 계산은 다항식 근 찾기와 동치이고 5차 이상은 근의 공식이 없기 때문이다.³ 그래서 표준 절차는 직접법 한 단계 + 반복법 한 단계의 조합이다.

1. 헤센베르크 축약. 하우스홀더 변환 $n-2$ 번으로 $A$ 를 상헤센베르크 형($h_{ij} = 0$ for $i > j+1$)으로 만든다. 유한 단계로 끝나며 $\frac{10}{3}n^3$ flops.
2. 시프트 QR 반복. 헤센베르크 $H$ 에 대해 $H - \mu I = QR$, $H \leftarrow RQ + \mu I$ 를 반복한다. 시프트가 없으면 수렴이 거듭제곱법 수준으로 느리지만, 시프트 $\mu$ 를 우하단 $2 \times 2$ 블록의 고유값 중 $h_{nn}$ 에 가까운 쪽(윌킨슨 시프트)으로 잡으면 부대각 성분이 일반적으로 2차 수렴으로 죽는다(대칭 삼중대각인 특수한 경우에는 3차). $h_{n,n-1}$ 이 충분히 작아지면 마지막 행을 떼어내고(디플레이션) 차수를 줄여 계속한다.

실행렬에서는 복소 시프트를 피하려고 프란시스 이중 시프트를 쓴다. 우하단 $2 \times 2$ 의 두 고유값을 켤레쌍째로 한꺼번에 적용하되, $H^2$ 를 만들지 않고 첫 열만 계산해 “부풀림-쫓아내기”(bulge chasing)로 헤센베르크 구조를 복원한다. 실제로 QR 분해를 명시적으로 하지 않으므로 암시적 QR이라 부르며, 각 sweep이 $O(n^2)$ 이다. 기븐스 회전이나 작은 하우스홀더 반사가 bulge를 밀어내는 도구다.

총 비용은 고유값만 구하면 $\approx 10n^3$, 슈어 벡터 $Q$ 까지 누적하면 $\approx 25n^3$ flops. 현대 LAPACK의 dhseqr 은 여기에 다중 시프트와 공격적 조기 디플레이션(Braman–Byers–Mathias, 2002)을 얹어 캐시 친화적인 블록 연산으로 돌린다.

5. 불변 부분공간과 순서화 슈어 분해[편집]

$Q$ 의 앞쪽 $k$ 열 $Q_k$ 를 떼어내면 $A Q_k = Q_k T_{11}$ 이 성립한다. 즉 $Q$ 의 선행 열들은 $T$ 의 좌상단 $k \times k$ 블록에 놓인 고유값들에 대응하는 불변 부분공간의 정규직교 기저다. 고유벡터와 달리 이 기저는 고유값이 겹치거나 붙어 있어도 잘 정의되고, 조건수도 개별 고유벡터가 아니라 두 스펙트럼 덩어리 사이의 분리도(sep)로 결정된다.

문제는 QR 반복이 고유값을 아무 순서로나 뱉는다는 것. 그래서 순서화 슈어 분해(ordered Schur form)가 필요하다. 인접한 두 대각 블록을 유니터리 상사변환으로 맞바꾸는 연산을 버블 정렬하듯 반복하면 원하는 고유값들을 좌상단으로 모을 수 있다(dtrsen). 예컨대 실부가 음수인 고유값을 전부 앞으로 보내면 그 자리에서 안정 불변 부분공간이 나온다.⁴

일반화 고유값 문제 $Ax = \lambda Bx$ 에도 같은 논리가 그대로 확장된다. 유니터리 $Q, Z$ 로 $Q^H A Z = T$, $Q^H B Z = S$ 를 동시에 상삼각화하는 일반화 슈어 분해(QZ 분해, 모울러-스튜어트 1973)이며, 고유값은 대각 원소의 비 $t_{ii}/s_{ii}$ 로 읽는다. $B$ 가 특이해도 $B^{-1}A$ 를 만들지 않으므로 무한 고유값($s_{ii}=0$)을 자연스럽게 표현할 수 있다는 것이 핵심 이점이다. 구조동역학의 $(K - \lambda M)x = 0$ 이나 유동 안정성의 일반화 문제에서 질량행렬이 특이한 경우(비압축 조건이 만드는 대수적 구속)가 정확히 이 상황이다.

6. 응용[편집]

• 리아푸노프 방정식과 실베스터 방정식. $AX + XB = C$ 를 그냥 풀면 $n^2 \times n^2$ 크라네커 계이지만, $A$ 와 $B$ 를 각각 슈어 형으로 바꾸면 삼각 구조 덕에 열 단위 후진대입으로 떨어진다. 이것이 1972년 바텔스-스튜어트 알고리즘이고 비용은 $O(n^3)$ 이다.
• 리카티 방정식. 대수 리카티 방정식의 안정화 해는 해밀토니안 행렬 $H$ 의 안정 불변 부분공간에서 나온다. 순서화 슈어 분해로 좌반평면 고유값을 모아 $\begin{bmatrix} Q_{11} \\ Q_{21}\end{bmatrix}$ 를 얻고 $X = Q_{21}Q_{11}^{-1}$ 로 끝내는 것이 라우브(1979)의 슈어 해법이며, 지금도 최적 제어 툴박스의 care/dare 가 이 경로다.
• 행렬함수. $f(A) = Q f(T) Q^H$ 이므로 삼각행렬의 함수만 구하면 된다. 대각은 $f(t_{ii})$, 비대각은 파레 점화식으로 채우는 것이 슈어-파레 방법. 가까운 고유값이 서로 다른 블록에 흩어지면 점화식이 폭발하므로, 데이비스-하이엄(2003)의 블록화가 가까운 고유값끼리 묶고 대각 블록은 테일러 급수로 처리한다.
• 크릴로프-슈어 방법. 아놀디 알고리즘의 암시적 재시작은 구현이 까다롭고 수치적으로 예민한데, 스튜어트(2001)는 아놀디 분해를 슈어 형으로 바꾼 뒤 원하지 않는 고유값을 뒤로 재정렬하고 잘라내는 방식으로 같은 일을 훨씬 안전하게 해냈다. 재시작이 곧 “순서화 후 절단”이 된다.

7. 관련 문서[편집]

• 고유값 문제 · 조르당 표준형 · 특이값 분해 · 조건수
• QR 분해 · 기븐스 회전 · 거듭제곱법 · 역반복법
• 아놀디 알고리즘 · 크릴로프-슈어 방법 · 야코비-데이비드슨 방법
• 비정규 행렬 · 의사스펙트럼 · 후진 오차 해석
• 리아푸노프 방정식 · 리카티 방정식 · LAPACK

8. Footnotes[편집]

1. 이사이 슈어(Issai Schur)는 프로베니우스의 제자로, 슈어 보조정리·슈어 여인자·슈어 곱 등 온갖 곳에 이름을 남겼다. 참고로 영역 분할법에 나오는 슈어 여인자는 이 분해와 이름만 같은 별개 개념이니 헷갈리지 말 것. ↩

2. 후진 안정성이 “정답이 나온다”는 뜻은 아니다. 원래 행렬이 고유값 조건수 $10^{12}$ 짜리면, 기계 정밀도만큼 흔들린 이웃 행렬의 정확한 답이 원래 답과 한참 다를 수 있다. 알고리즘은 무죄, 문제가 유죄. ↩

3. 아벨-루피니 정리. 그래서 “고유값을 구하는 직접법”이라는 말은 원리적으로 형용모순이다. QR 알고리즘은 어디까지나 반복법이고, 다만 시프트가 워낙 잘 들어서 실무에서는 행렬당 평균 부대각 성분 하나에 두세 번의 반복이면 끝나기 때문에 직접법처럼 보일 뿐이다. ↩

4. 대각 블록을 맞바꾸는 연산 자체는 국소적으로 실베스터 방정식 하나를 푸는 일이다. 두 블록의 고유값이 가까우면 그 실베스터 계가 나빠져 교환이 불안정해지는데, 애초에 그렇게 가까운 두 덩어리를 굳이 갈라놓는 것 자체가 잘못된 요구다. ↩