# 固有値の計算 I：冪乗法・逆反復・Rayleigh 商反復と同時反復
> 冪乗法が固有値の比 |λ₂/λ₁| の速さで収束すること、Rayleigh 商の 2 次の精度、シフトつき逆反復の収束率、Rayleigh 商反復の局所 3 次収束、同時反復による不変部分空間の収束を証明し、数値例で確かめる。
> https://rikai.mugen-giken.com/mathematics/numerical-linear-algebra/power-and-inverse-iteration
## 0. この記事の要点
行列の固有値は、行列が「ベクトルをどれだけ伸ばす向きがあるか」を表す数です。小さな行列なら方程式を解いて求められますが、大きな行列では、適当なベクトルに行列を何度も掛けるだけで、いちばん強く伸びる向きが浮かび上がってきます。この記事では、この単純な繰り返しがなぜ固有値と固有ベクトルに行き着くのか、どれくらいの速さで近づくのか、そして掛ける前に行列を少しずらす工夫でどれだけ速くなるのかを、数値例とともに確かめます。
- **冪乗法**は $\boldsymbol{x}_{k+1} = A\boldsymbol{x}_k/\|A\boldsymbol{x}_k\|$ を繰り返すだけの算法です。[対角化可能](/mathematics/linear-algebra/diagonalization-and-jordan-form#def-diagonalizable)で $|\lambda_1| > |\lambda_2|$ なら、$\boldsymbol{x}_k$ と[固有ベクトル](/mathematics/linear-algebra/eigenvalues#def-eigen) $\boldsymbol{v}_1$ のなす角は $O(|\lambda_2/\lambda_1|^k)$ で $0$ に近づきます。
- Hermite 行列では、Rayleigh 商の誤差は角の正弦の **2 乗**に比例します（$R_A(\boldsymbol{x}) - \lambda = \sin^2\theta\,(R_A(\boldsymbol{w}) - \lambda)$）。このため固有値は $|\lambda_2/\lambda_1|^{2k}$ の速さで求まります。
- **シフトつき逆反復**は $(A - \mu I)^{-1}$ に対する冪乗法で、収束率は $|\lambda_J - \mu|/|\lambda_K - \mu|$（$\lambda_J$ は $\mu$ に最も近い固有値、$\lambda_K$ は 2 番目に近い固有値）です。シフトを固有値に近づけるほど速くなります。
- シフトを毎回 Rayleigh 商に取り替える **Rayleigh 商反復**は、Hermite 行列では角の正接が $\tan\theta_{k+1} \le (2\Delta/\delta)\tan^3\theta_k$ を満たし、局所 3 次収束（誤差が 1 回ごとにおよそ 3 乗になる速さの収束）します。
- $p$ 本のベクトルを同時に掛けて直交化する**同時反復**は、優勢な $p$ 次元の不変部分空間（行列を掛けても外へ出ない部分空間）に $O(|\lambda_{p+1}/\lambda_p|^k)$ で近づきます。これが次の章の [QR 法](/mathematics/numerical-linear-algebra/qr-algorithm#def-qr-iteration)の収束の理論の土台になります。
- 計算した近似固有対は、残差 $\boldsymbol{r} = A\boldsymbol{x} - R_A(\boldsymbol{x})\boldsymbol{x}$ を使って事後に評価できます（残差による評価・Temple の不等式・Bauer–Fike の定理。いずれも、残差の大きさから固有値の誤差を押さえる不等式です）。
## 1. 動機
研究で使う固有値の計算のほとんどは、`numpy.linalg.eigh` や `scipy.sparse.linalg.eigsh` を呼ぶだけで済みます。それでも「何回反復すれば何桁合うのか」「固有値が近いと何が起きるのか」「求めた固有値はどこまで信用できるのか」を答えるには、中で動いている反復の理論が要ります。
固有値問題は多項式の根を求める問題を含むので、5 次以上では有限回の四則と冪根で解く公式がありません。したがって固有値の算法は必ず**反復法**です。その最も単純な形が冪乗法で、QR 法・Lanczos 法・Arnoldi 法といった実用の算法は、どれも冪乗法を賢く組み合わせたものとして理解できます。
本章では、固有ベクトルを含む方向へベクトルを寄せていく反復を、次の 4 段で扱います。
1. 冪乗法：$A^k\boldsymbol{x}_0$ の方向は、絶対値最大の固有値の固有ベクトルへ向かう。
2. 逆反復：$(A - \mu I)^{-1}$ に冪乗法を使えば、$\mu$ に最も近い固有値が「最大」になる。
3. Rayleigh 商反復：シフト $\mu$ を毎回いまの近似固有値に更新すると、収束は 3 次になる。
4. 同時反復：1 本のベクトルではなく部分空間を反復すると、上位 $p$ 個の固有値に対応する不変部分空間が求まる。
証明はどれも「固有ベクトルの基底で展開し、各成分が固有値の冪で伸び縮みする様子を見る」という同じ考え方です。
## 2. 準備：角・Rayleigh 商・2 ノルム
この章では $\mathbb{C}^n$ の標準内積 $\boldsymbol{y}^{*}\boldsymbol{x}$ とそのノルム $\|\boldsymbol{x}\| = (\boldsymbol{x}^{*}\boldsymbol{x})^{1/2}$ だけを使います。行列 $B \in \mathbb{C}^{m\times n}$ のノルムは、このノルムから誘導される作用素ノルム
$$
\|B\| = \sup_{\boldsymbol{x}\ne\boldsymbol{0}} \frac{\|B\boldsymbol{x}\|}{\|\boldsymbol{x}\|}
$$
です。$B$ の第 $i$ 行を $\boldsymbol{b}_i^{*}$ とすると、Cauchy–Schwarz の不等式（
$A \in \mathbb{C}^{n\times n}$ は対角化可能で、固有値を重複を込めて $|\lambda_1| > |\lambda_2| \ge |\lambda_3| \ge \cdots \ge |\lambda_n|$ と並べられるとする。対応する固有ベクトル $\boldsymbol{v}_1, \ldots, \boldsymbol{v}_n$（$\|\boldsymbol{v}_i\| = 1$）は基底をなすとし、$\boldsymbol{x}_0 = \sum_{i=1}^{n} c_i\boldsymbol{v}_i$ で $c_1 \ne 0$ とする。このとき冪乗法はすべての $k$ で定義され、
$$
r = \left|\frac{\lambda_2}{\lambda_1}\right|,\qquad S = \sum_{i=2}^{n}\frac{|c_i|}{|c_1|}
$$
とおくと、$Sr^k < 1$ を満たす $k$ について
$$
\sin\angle(\boldsymbol{x}_k, \boldsymbol{v}_1) \le \frac{S r^k}{1 - S r^k}
$$
が成り立つ。とくに $\sin\angle(\boldsymbol{x}_k, \boldsymbol{v}_1) = O(r^k)$ である。
対角化可能なので固有ベクトルの基底がとれます（