30.27 역멱승법(Inverse Power Method)과 특정 고유값 추적

1. 역멱승법의 기본 원리

**역멱승법(inverse power method, inverse iteration)**은 멱승법의 변형으로서, 행렬 A의 역행렬 A^{-1}에 멱승법을 적용하는 알고리즘이다. 멱승법이 절댓값이 가장 큰 고유값(지배 고유값)에 수렴하는 것과 대조적으로, 역멱승법은 절댓값이 가장 작은 고유값에 수렴한다.

핵심 관찰은 다음과 같다. A의 고유값이 \lambda_1, \lambda_2, \ldots, \lambda_n (\lambda_i \neq 0)이면, A^{-1}의 고유값은 1/\lambda_1, 1/\lambda_2, \ldots, 1/\lambda_n이다. \lvert \lambda_j \rvert이 가장 작으면 \lvert 1/\lambda_j \rvert이 가장 크므로, A^{-1}에 멱승법을 적용하면 1/\lambda_j, 즉 A의 최소 절대 고유값 \lambda_j에 수렴한다.

2. 역멱승법 알고리즘

알고리즘 (역멱승법):

임의의 초기 벡터 q_0 (\lVert q_0 \rVert = 1)을 선택한다. k = 0, 1, 2, \ldots에 대하여:

A z_{k+1} = q_k \quad \text{(연립방정식 풀기)}

q_{k+1} = \frac{z_{k+1}}{\lVert z_{k+1} \rVert}

\mu_{k+1} = q_{k+1}^T A q_{k+1}

수렴 시 q_k는 A의 최소 절대 고유값에 대응하는 고유벡터에 수렴하고, \mu_k는 해당 고유값에 수렴한다.

핵심적으로, A^{-1}을 명시적으로 계산하지 않고 연립방정식 Az = q_k를 풀어 z = A^{-1} q_k를 구한다. 이는 A^{-1}의 계산(O(n^3))을 매 반복마다 수행하는 대신, LU 분해를 한 번 수행하고(O(n^3)) 이후 반복에서는 전방·후방 대입(O(n^2))만 수행하여 효율을 확보하는 방식이다.

3. 시프트된 역멱승법(Shifted Inverse Power Method)

역멱승법의 진정한 위력은 시프트(shift) \sigma를 도입할 때 발현된다. 시프트된 역멱승법은 A의 고유값 중 \sigma에 가장 가까운 고유값을 추적한다.

3.1 이론적 기초

A의 고유값이 \lambda_i이면, 시프트된 행렬 (A - \sigma I)의 고유값은 \lambda_i - \sigma이다. (A - \sigma I)^{-1}의 고유값은 1/(\lambda_i - \sigma)이다. \lambda_j가 \sigma에 가장 가까운 고유값이면 \lvert \lambda_j - \sigma \rvert이 가장 작고, 따라서 \lvert 1/(\lambda_j - \sigma) \rvert이 가장 크다. 그러므로 (A - \sigma I)^{-1}에 멱승법을 적용하면 \lambda_j에 수렴한다.

3.2 알고리즘

알고리즘 (시프트된 역멱승법):

시프트 \sigma와 초기 벡터 q_0 (\lVert q_0 \rVert = 1)을 선택한다. k = 0, 1, 2, \ldots에 대하여:

(A - \sigma I) z_{k+1} = q_k

q_{k+1} = \frac{z_{k+1}}{\lVert z_{k+1} \rVert}

\mu_{k+1} = q_{k+1}^T A q_{k+1}

수렴 시 \mu_k \to \lambda_j (\sigma에 가장 가까운 고유값)이다.

3.3 수렴 속도

수렴 비율은

r = \frac{\lvert \lambda_j - \sigma \rvert}{\lvert \lambda_{\text{next}} - \sigma \rvert}

이다. 여기서 \lambda_{\text{next}}는 \sigma에 두 번째로 가까운 고유값이다. \sigma가 \lambda_j에 가까울수록 r이 작아지고 수렴이 빨라진다. 극단적으로, \sigma가 \lambda_j에 매우 근접하면 수렴은 사실상 한두 번의 반복으로 달성된다.

4. 레일리 몫 반복(Rayleigh Quotient Iteration)

시프트된 역멱승법에서 시프트 \sigma를 매 반복마다 갱신하면 수렴 속도를 극적으로 향상시킬 수 있다. 이것이 **레일리 몫 반복(Rayleigh quotient iteration, RQI)**이다.

알고리즘 (레일리 몫 반복):

초기 벡터 q_0 (\lVert q_0 \rVert = 1), 초기 시프트 \sigma_0 = q_0^T A q_0을 설정한다. k = 0, 1, 2, \ldots에 대하여:

(A - \sigma_k I) z_{k+1} = q_k

q_{k+1} = \frac{z_{k+1}}{\lVert z_{k+1} \rVert}

\sigma_{k+1} = q_{k+1}^T A q_{k+1}

4.1 수렴 속도의 가속

레일리 몫 반복의 수렴 속도는 행렬의 유형에 따라 다르다:

• 대칭 행렬: 3차(cubic) 수렴. 즉, \lvert \sigma_{k+1} - \lambda \rvert = O(\lvert \sigma_k - \lambda \rvert^3)이다.
• 비대칭 행렬: 2차(quadratic) 수렴. 즉, \lvert \sigma_{k+1} - \lambda \rvert = O(\lvert \sigma_k - \lambda \rvert^2)이다.

대칭 행렬에서의 3차 수렴은 뉴턴법의 2차 수렴보다도 빠르며, 실용적으로 3~5회의 반복이면 기계 정밀도 수준의 수렴이 달성된다.

그러나 레일리 몫 반복은 매 반복마다 행렬 (A - \sigma_k I)이 변하므로 LU 분해를 재수행하여야 한다. 이는 반복당 O(n^3)의 비용을 초래한다. 시프트가 고정된 역멱승법에서는 LU 분해를 한 번만 수행하고 O(n^2)의 반복을 계속하므로, 총 비용의 관점에서는 반드시 레일리 몫 반복이 유리한 것은 아니다.

5. 실용적 구현 시의 고려 사항

5.1 LU 분해의 활용

시프트가 고정된 역멱승법에서는 (A - \sigma I)의 LU 분해를 사전에 한 번 수행한다:

A - \sigma I = LU

이후 각 반복에서는 LU z_{k+1} = q_k를 전방·후방 대입으로 O(n^2)에 풀 수 있다. 이는 역멱승법의 효율성의 핵심이다.

5.2 시프트가 고유값에 너무 가까운 경우

\sigma \approx \lambda_j이면 (A - \sigma I)가 거의 특이(nearly singular)하다. 이 경우 z_{k+1} = (A - \sigma I)^{-1} q_k의 크기가 매우 커지나, 정규화 단계에서 방향만 추출하므로 알고리즘의 정확성에는 영향이 없다. 오히려 (A - \sigma I)가 특이에 가까울수록 z_{k+1}이 \lambda_j의 고유벡터 방향에 더 가까워지므로 수렴이 빨라진다. 이는 직관적이지 않으나 이론적으로 확립된 사실이다.

유한 정밀도 산술에서의 안정성도 보장된다. (A - \sigma I)의 조건수가 클 때 z_{k+1}의 성분에 큰 반올림 오차가 발생하지만, 이 오차는 고유벡터 방향의 성분에 집중되므로 정규화 후의 방향은 정확하다.

5.3 초기 시프트의 선택

시프트 \sigma의 선택은 수렴 속도와 어느 고유값에 수렴할지를 결정한다. 초기 시프트의 선택 전략으로는:

• 거슈고린 추정: 거슈고린 원 정리를 이용하여 목표 고유값의 대략적 위치를 추정하고 시프트로 사용한다.
• 물리적 사전 지식: 문제의 물리적 맥락에서 고유값의 대략적 크기가 알려진 경우 이를 활용한다.
• 다른 알고리즘의 중간 결과: QR 알고리즘의 중간 단계에서 얻어진 근사 고유값을 시프트로 사용한다.

6. 수치 예시

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

A의 고유값은 \lambda_1 \approx 4.732, \lambda_2 \approx 3.000, \lambda_3 \approx 1.268이다.

6.1 시프트 없는 역멱승법 (\sigma = 0)

\sigma = 0이면 최소 절대 고유값 \lambda_3 \approx 1.268에 수렴한다.

q_0 = \frac{1}{\sqrt{3}}(1, 1, 1)^T로 시작한다.

반복 1: Az_1 = q_0을 풀어 z_1을 구하고 정규화한다. \mu_1 = q_1^T A q_1을 계산하면 \mu_1 \approx 1.33이다.

수 회의 반복 후 \mu_k \to 1.268에 수렴한다. 수렴 비율은 r = \lvert \lambda_3 \rvert / \lvert \lambda_2 \rvert = 1.268 / 3.000 \approx 0.423이다.

6.2 시프트된 역멱승법 (\sigma = 3.0)

\sigma = 3.0으로 설정하면 \lambda_2 = 3.000에 가장 가까운 고유값에 수렴한다.

(A - 3I)의 고유값은 1.732, 0.000, -1.732이므로, 0에 가장 가까운 고유값에 대응하는 \lambda_2 = 3에 수렴한다. \sigma = 3이 정확히 \lambda_2이므로 (A - 3I)가 특이이지만, 수치적으로는 \sigma = 2.99 등으로 약간 벗어난 값을 사용하면 한두 번의 반복으로 \lambda_2 \approx 3에 수렴한다.

7. 멱승법과 역멱승법의 비교

8. 역멱승법의 응용

8.1 특정 고유값의 정밀 계산

다른 알고리즘(QR 알고리즘, 이분법 등)으로 고유값의 대략적 위치 \sigma를 알고 있을 때, 시프트된 역멱승법으로 해당 고유값을 기계 정밀도까지 정밀하게 계산할 수 있다. 이는 QR 알고리즘의 시프트 전략에서 핵심적으로 활용된다.

8.2 고유벡터의 계산

고유값이 이미 알려진 경우, 대응하는 고유벡터를 구하기 위하여 시프트된 역멱승법을 1~2회 반복하는 것이 효율적이다. \sigma를 알려진 고유값으로 설정하면, (A - \sigma I)가 거의 특이이므로 해 z가 고유벡터 방향을 강하게 가리킨다.

8.3 최소 고유값에 의한 안정성 판별

역멱승법은 행렬의 최소 고유값을 계산하므로, 양의 정부호성의 판별에 활용할 수 있다. 대칭 행렬의 최소 고유값이 양수이면 양의 정부호이고, 음수이면 양의 정부호가 아니다.

8.4 조건수의 추정

행렬의 조건수 \kappa(A) = \lVert A \rVert_2 \lVert A^{-1} \rVert_2 = \lvert \lambda_{\max} \rvert / \lvert \lambda_{\min} \rvert (대칭 행렬의 경우)를 계산하기 위하여, 멱승법으로 \lvert \lambda_{\max} \rvert를, 역멱승법으로 \lvert \lambda_{\min} \rvert를 각각 추정할 수 있다.

9. 역멱승법의 수렴 실패 조건

역멱승법이 수렴하지 않거나 예상과 다른 고유값에 수렴하는 경우는 다음과 같다:

\sigma에 등거리인 두 고유값. \lvert \lambda_j - \sigma \rvert = \lvert \lambda_k - \sigma \rvert (j \neq k)이면 수렴이 보장되지 않는다. 시프트를 약간 조정하여 해결한다.

초기 벡터가 목표 고유벡터에 직교. 이론적으로 발생 가능하나, 유한 정밀도 산술에서는 실용적으로 문제가 되지 않는다.

A - \sigma I가 정확히 특이. \sigma가 정확한 고유값이면 (A - \sigma I)가 특이이다. 이 경우 연립방정식에 해가 존재하지 않을 수 있으나, 수치적으로는 반올림 오차에 의하여 거의 특이 행렬이 되며, 앞서 설명한 바와 같이 알고리즘은 정상적으로 수렴한다.