30.28 QR 알고리즘의 원리와 전체 고유값 동시 계산

1. QR 알고리즘의 개요

**QR 알고리즘(QR algorithm)**은 n \times n 행렬의 모든 고유값을 동시에 계산하는 반복 알고리즘이다. 1961년 Francis와 Kublanovskaya에 의하여 독립적으로 제안되었으며, 현재 수치 선형대수학에서 고유값 계산의 표준 알고리즘으로 확립되어 있다. LAPACK, NumPy, MATLAB 등 주요 수치 계산 라이브러리의 고유값 계산 루틴은 QR 알고리즘에 기반한다.

멱승법이나 역멱승법이 하나의 고유값에 수렴하는 것과 달리, QR 알고리즘은 반복 과정에서 행렬을 유사 변환(similarity transformation)에 의하여 점진적으로 상삼각 행렬(또는 대각 행렬)로 수렴시킴으로써 모든 고유값을 동시에 드러낸다.

2. 기본 QR 알고리즘

알고리즘 (기본 QR 반복):

A_0 = A로 설정한다. k = 0, 1, 2, \ldots에 대하여:

단계 1. A_k의 QR 분해를 수행한다:

A_k = Q_k R_k

여기서 Q_k는 직교 행렬, R_k는 상삼각 행렬이다.

단계 2. Q_k와 R_k의 곱 순서를 뒤집어 새로운 행렬을 구성한다:

A_{k+1} = R_k Q_k

이 과정을 수렴할 때까지 반복한다.

3. QR 반복의 핵심 성질

3.1 유사 변환의 보존

A_{k+1} = R_k Q_k = Q_k^T A_k Q_k이다. 이를 확인하면:

A_k = Q_k R_k \implies Q_k^T A_k = R_k \implies R_k Q_k = Q_k^T A_k Q_k

따라서 A_{k+1}은 A_k와 직교 유사 변환으로 연결되며, 두 행렬은 동일한 고유값을 갖는다. 반복의 모든 단계에서 고유값이 보존된다.

3.2 누적 변환

P_k = Q_0 Q_1 \cdots Q_{k-1}으로 정의하면

A_k = P_k^T A_0 P_k

이다. P_k는 직교 행렬의 곱이므로 직교 행렬이다. A_k가 수렴하면 P_k의 열벡터가 A의 고유벡터에 수렴한다.

4. 수렴 원리

4.1 대칭 행렬의 경우

A가 대칭 행렬이고 고유값이 \lvert \lambda_1 \rvert > \lvert \lambda_2 \rvert > \cdots > \lvert \lambda_n \rvert > 0을 만족하면, A_k는 대각 행렬 \Lambda = \operatorname{diag}(\lambda_1, \lambda_2, \ldots, \lambda_n)에 수렴한다.

4.2 비대칭 행렬의 경우

A가 비대칭이면 A_k는 일반적으로 **실수 슈르 형태(real Schur form)**에 수렴한다:

A_k \to T = \begin{pmatrix} T_{11} & * & \cdots & * \\ 0 & T_{22} & \cdots & * \\ \vdots & \ddots & \ddots & \vdots \\ 0 & \cdots & 0 & T_{mm} \end{pmatrix}

여기서 각 대각 블록 T_{ii}는 1 \times 1 (실수 고유값) 또는 2 \times 2 (복소 켤레 고유값 쌍)이다.

4.3 수렴 속도

A_k의 하삼각 성분의 수렴 속도는 고유값의 비율에 의하여 결정된다. 구체적으로, (i, j) 위치의 성분(i > j)은

(A_k)_{ij} = O\left(\left\lvert \frac{\lambda_i}{\lambda_j} \right\rvert^k\right)

의 속도로 0에 수렴한다. 따라서 인접한 고유값의 비율 \lvert \lambda_{i+1} / \lambda_i \rvert이 1에 가까우면 수렴이 느려진다.

5. 멱승법과 QR 알고리즘의 관계

QR 알고리즘은 암묵적으로(implicitly) 모든 고유벡터 방향에 대하여 동시에 멱승법을 수행하는 것으로 해석할 수 있다.

A^k의 QR 분해를 A^k = \hat{Q}_k \hat{R}_k로 놓으면, \hat{Q}_k의 열벡터들은 A의 고유벡터에 수렴한다. QR 알고리즘의 누적 변환 P_k = Q_0 Q_1 \cdots Q_{k-1}은 이 \hat{Q}_k와 점근적으로 일치함이 알려져 있다. 즉, QR 알고리즘은 A의 거듭제곱에 대한 QR 분해를 암묵적으로 수행한다.

6. 시프트를 이용한 수렴 가속

기본 QR 알고리즘의 수렴은 인접 고유값의 비율에 의존하므로, 고유값이 근접할 경우 매우 느릴 수 있다. 이를 해결하기 위하여 **시프트(shift)**를 도입한다.

알고리즘 (시프트된 QR 반복):

A_k - \sigma_k I = Q_k R_k \quad \text{(시프트된 QR 분해)}

A_{k+1} = R_k Q_k + \sigma_k I

A_{k+1} = Q_k^T A_k Q_k이므로 유사 변환 관계는 유지된다. 시프트 \sigma_k를 적절히 선택하면, A_k의 마지막 행의 비대각 성분이 빠르게 0에 수렴하여 고유값이 “디플레이트(deflate)“된다.

6.1 시프트 전략

단일 시프트 (Rayleigh quotient shift). \sigma_k = (A_k)_{nn}, 즉 A_k의 (n, n) 성분을 시프트로 사용한다. 이 전략은 대칭 행렬에서 3차 수렴을 제공한다.

Wilkinson 시프트. A_k의 우하단 2 \times 2 블록

\begin{pmatrix} a & b \\ c & d \end{pmatrix}

의 두 고유값 중 d에 더 가까운 것을 시프트로 선택한다. Wilkinson 시프트는 대칭 행렬에서 전역 수렴(global convergence)이 보장되며, 수렴 속도는 최소 2차이다.

이중 시프트 (Francis double shift). 비대칭 실수 행렬에서 복소 켤레 고유값 쌍에 대응하기 위하여, 한 번에 두 개의 시프트를 동시에 적용한다. 이는 실수 산술만을 사용하면서도 복소 고유값에 대한 수렴을 보장한다.

7. 전처리: 하이젠베르크 환원

QR 알고리즘을 직접 적용하면 매 반복의 QR 분해에 O(n^3)이 소요된다. 이를 개선하기 위하여, 사전에 행렬을 **상부 하이젠베르크 형태(upper Hessenberg form)**로 환원한다.

정의. 행렬 H가 상부 하이젠베르크 형태라 함은 주대각선 바로 아래의 부대각선(subdiagonal) 이하의 모든 성분이 0인 것이다:

h_{ij} = 0 \quad \text{for } i > j + 1

환원 절차. 임의의 행렬 A를 하우스홀더 변환(Householder transformation)을 이용하여 O(\frac{2}{3}n^3) 연산으로 상부 하이젠베르크 형태로 환원할 수 있다:

Q_0^T A Q_0 = H

A가 대칭이면 H도 대칭이므로 하이젠베르크 형태는 **삼대각 행렬(tridiagonal matrix)**로 환원된다.

QR 반복의 효율화. 상부 하이젠베르크 행렬의 QR 분해는 기븐스 회전(Givens rotation)을 이용하여 O(n^2)에 수행할 수 있다. 따라서 하이젠베르크 환원 후의 QR 반복은 반복당 O(n^2)의 비용만 소요된다.

8. QR 알고리즘의 전체 절차

완전한 QR 알고리즘은 다음의 단계로 구성된다:

단계 1. 하이젠베르크 환원. 하우스홀더 변환으로 A를 상부 하이젠베르크 형태 H로 변환한다. 대칭 행렬이면 삼대각 행렬로 변환한다. 비용: O(n^3).

단계 2. QR 반복 (시프트 포함). H에 대하여 시프트된 QR 반복을 수행한다. 매 반복에서 마지막 부대각 성분이 충분히 작아지면 마지막 고유값(또는 2 \times 2 블록)을 디플레이트하고, 크기가 줄어든 행렬에 대하여 반복을 계속한다. 반복당 비용: O(n^2). 적절한 시프트 전략 하에서 총 반복 횟수는 O(n)이다.

단계 3. (선택) 고유벡터 계산. 고유값이 모두 구해지면, 역멱승법으로 각 고유값에 대응하는 고유벡터를 계산한다.

전체 계산 복잡도: O(n^3).

9. 수치 예시

A = \begin{pmatrix} 2 & 1 & 0 \\ 1 & 3 & 1 \\ 0 & 1 & 4 \end{pmatrix}

A는 대칭 삼대각 행렬이므로 하이젠베르크 환원이 불필요하다.

반복 1: A_0 = A의 QR 분해를 수행하고 A_1 = R_0 Q_0을 구한다. 비대각 성분이 감소한다.

반복 2~5: Wilkinson 시프트를 적용하면 비대각 성분이 급속히 감소한다.

수 회의 반복 후 A_k가 대각 행렬에 수렴하며, 대각 성분은 A의 고유값 \lambda_1 \approx 4.414, \lambda_2 \approx 3.000, \lambda_3 \approx 1.586에 수렴한다.

10. QR 알고리즘의 수렴성 보장

정리. A가 실수 대칭 행렬이고 Wilkinson 시프트를 사용하면, QR 알고리즘은 전역적으로 수렴한다 (임의의 초기 행렬에 대하여 수렴).

비대칭 행렬에서의 전역 수렴은 일반적으로 보장되지 않으나, Francis의 이중 시프트 QR 알고리즘은 실용적으로 거의 항상 수렴하며, 수렴 실패 사례는 극히 드물다.

11. QR 알고리즘과 다른 고유값 알고리즘의 비교

QR 알고리즘은 밀집 행렬에 대하여 모든 고유값을 동시에 계산하는 가장 효율적이고 안정적인 방법으로서, 수치 선형대수학의 “일꾼(workhorse)“이라 불린다.