べき乗法

繰り返しの掛け算で支配的な方向を見つける

$1000\times1000$ の行列で特性多項式を解くのは現実的ではなく、しばしば最大の固有対だけ（たとえば第1主成分）が必要です。べき乗法は行列とベクトルの積だけでそれを求めます。任意のベクトル $\mathbf x_0$ から始め、 $\mathbf x_{k+1}=A\mathbf x_k/\lVert A\mathbf x_k\rVert$ を繰り返します。掛けるたびに支配的な固有ベクトル方向の成分が他より大きく伸びるので、十分な回数の後にはベクトルがその方向を向きます。

\mathbf x_{k+1}=\frac{A\mathbf x_k}{\lVert A\mathbf x_k\rVert},\qquad \lambda\approx\frac{\mathbf x_k^{T}A\mathbf x_k}{\mathbf x_k^{T}\mathbf x_k},\qquad e_k\propto\Big|\frac{\lambda_2}{\lambda_1}\Big|^{k}

(1)

$\mathbf x_0=c_1\mathbf v_1+c_2\mathbf v_2+\cdots$ と固有ベクトルで展開します。 $k$ 回後には係数が $\lambda_i^k$ 倍されるので、2番目と1番目の比は $(\lambda_2/\lambda_1)^k$ です。 $|\lambda_1|>|\lambda_2|$ で、初期ベクトルが $\mathbf v_1$ 方向の成分を持てば収束し、速さは $|\lambda_2/\lambda_1|$ で決まります。固有値が近いと収束は遅くなります。正規化はオーバーフローを防ぐだけで、重要なのは方向です。固有値の推定にはレイリー商を使います。次の固有対は、対称行列 $A$ から $\lambda_1\mathbf v_1\mathbf v_1^{T}$ を引いて繰り返し、これを収縮（デフレーション）と呼びます。

手計算で数ステップ

A=\begin{pmatrix}2&1\\1&2\end{pmatrix}

（固有値3と1、支配的な固有ベクトルは

(1,1)

）を考えます。

\mathbf x_0=(1,0)

から始めると

A\mathbf x_0=(2,1)

で、

(2,1)

のレイリー商は

\frac{(2,1)\cdot(5,4)}{5}=\frac{14}{5}=2.8

とすでに3に近い値です。次の積は

A(2,1)=(5,4)

で、ほぼ

(1,1)

の方向です。誤差は1回ごとに

|\lambda_2/\lambda_1|=1/3

倍になるので、

10^{-6}

まで縮めるには

3^k\ge10^6

となる

k=13

が必要です。

更新： $A$ を掛けてノルムで割ることを繰り返す。1回あたり行列ベクトル積1回のコスト。
速さ：誤差は $|\lambda_2/\lambda_1|^k$ で減る。上位の固有値が近いと収束は遅い。
条件： $|\lambda_1|>|\lambda_2|$ という差と、 $\mathbf v_1$ に直交しない初期ベクトル。

同じ発想がウェブページの順位付けに使われるべき乗法はPageRankの背後にある手法で、共分散行列が巨大であったり明示的に作られず積

A\mathbf x

しか使えなかったりする場合に、何千もの資産の第1主成分を安く計算する方法でもあります。完全な分解を行うライブラリのルーチンは約

n^3

回の演算ですが、べき乗法の1ステップは密行列でも

n^2

です。

ラボ：採点される内容

何に収束するか15点
レイリー商20点
収束比10点
反復回数15点
アルゴリズムの順序15点
遅い・失敗する場合15点
なぜ正規化するか10点

繰り返しの掛け算で支配的な方向を見つける

\mathbf x_{k+1}=\frac{A\mathbf x_k}{\lVert A\mathbf x_k\rVert},\qquad \lambda\approx\frac{\mathbf x_k^{T}A\mathbf x_k}{\mathbf x_k^{T}\mathbf x_k},\qquad e_k\propto\Big|\frac{\lambda_2}{\lambda_1}\Big|^{k}

(1)

手計算で数ステップ

A=\begin{pmatrix}2&1\\1&2\end{pmatrix}

（固有値3と1、支配的な固有ベクトルは

(1,1)

）を考えます。

\mathbf x_0=(1,0)

から始めると

A\mathbf x_0=(2,1)

で、

(2,1)

のレイリー商は

\frac{(2,1)\cdot(5,4)}{5}=\frac{14}{5}=2.8

とすでに3に近い値です。次の積は

A(2,1)=(5,4)

で、ほぼ

(1,1)

の方向です。誤差は1回ごとに

|\lambda_2/\lambda_1|=1/3

倍になるので、

10^{-6}

まで縮めるには

3^k\ge10^6

となる

k=13

が必要です。

更新： $A$ を掛けてノルムで割ることを繰り返す。1回あたり行列ベクトル積1回のコスト。
速さ：誤差は $|\lambda_2/\lambda_1|^k$ で減る。上位の固有値が近いと収束は遅い。
条件： $|\lambda_1|>|\lambda_2|$ という差と、 $\mathbf v_1$ に直交しない初期ベクトル。

同じ発想がウェブページの順位付けに使われるべき乗法はPageRankの背後にある手法で、共分散行列が巨大であったり明示的に作られず積

A\mathbf x

しか使えなかったりする場合に、何千もの資産の第1主成分を安く計算する方法でもあります。完全な分解を行うライブラリのルーチンは約

n^3

回の演算ですが、べき乗法の1ステップは密行列でも

n^2

です。

ラボ：採点される内容

何に収束するか15点
レイリー商20点
収束比10点
反復回数15点
アルゴリズムの順序15点
遅い・失敗する場合15点
なぜ正規化するか10点

繰り返しの掛け算で支配的な方向を見つける

ラボ：採点される内容

コードを実行するにはログインしてください。

べき乗法

繰り返しの掛け算で支配的な方向を見つける

ラボ：採点される内容

コードを実行するにはログインしてください。