レイリー商反復法は、 レイリー商 を使用して より正確な 固有値推定値を取得することで、 逆反復法 の考え方を拡張する 固有値アルゴリズム です 。
レイリー商反復法は 反復法 です。つまり、限界内で真の解に 収束する 近似解のシーケンスを提供します。非常に迅速な収束が保証されており、妥当な近似値を得るために実際には数回の反復しか必要ありません。レイリー商反復アルゴリズムは、 解析対象の
行列 の 固有ベクトル に十分近い初期ベクトルが与えられれば、エルミート行列または対称行列に対して 3 次収束します。
アルゴリズム このアルゴリズムは逆反復法と非常に似ていますが、各反復の最後に推定された固有値をレイリー商に置き換えます。まず、 エルミート行列の初期固有値推定値として何らかの値を選択します 。初期ベクトル も初期固有ベクトル推定値として指定する必要があります。
μ
0
{\displaystyle \mu_{0}}
あ
{\displaystyle A}
b
0
{\displaystyle b_{0}}
固有ベクトルの次の近似値 を で
計算します。
ここで は単位行列です。そして、固有値の次の近似値を現在の反復のレイリー商に設定します。
b
私 + 1
{\displaystyle b_{i+1}}
b
私 + 1
=
（ あ −
μ
私
私
）
− 1
b
私
‖ （ あ −
μ
私
私
）
− 1
b
私
‖
、
{\displaystyle b_{i+1}={\frac {(A-\mu _{i}I)^{-1}b_{i}}{\|(A-\mu _{i}I)^{-1}b_{i}\|}},}
私
{\displaystyle I}
μ
私 + 1
=
b
私 + 1
∗
あ
b
私 + 1
b
私 + 1
∗
b
私 + 1
。
{\displaystyle \mu_{i+1}={\frac {b_{i+1}^{*}Ab_{i+1}}{b_{i+1}^{*}b_{i+1}}}.}
複数の固有値を計算するには、アルゴリズムをデフレーション手法と組み合わせることができます。
非常に小さな問題の場合、逆行列を 随伴行列 に 置き換えると効果的です 。随伴行列は、無関係なスケール (具体的には、行列式の逆行列) まで逆行列と等しいため、同じ反復処理が行われます。随伴行列は逆行列よりも明示的に計算する方が簡単です (ただし、問題が小さくない場合は逆行列をベクトルに適用する方が簡単です)。また、随伴行列は、固有値が収束しても適切に定義されているため、数値的にもより正確です。
例 マトリックスを考える
あ =
[
1
2
3
1
2
1
3
2
1
]
{\displaystyle A=\left[{\begin{matrix}1&2&3\\1&2&1\\3&2&1\\\end{matrix}}\right]}
の正確な固有値は 、 および であり、対応する固有ベクトルは
λ
1
= 3 +
5
{\displaystyle \lambda _{1}=3+{\sqrt {5}}}
λ
2
= 3 −
5
{\displaystyle \lambda _{2}=3-{\sqrt {5}}}
λ
3
= − 2
{\displaystyle \lambda _{3}=-2}
ヴ
1
=
[
1
φ − 1
1
]
{\displaystyle v_{1}=\left[{\begin{matrix}1\\\varphi -1\\1\\\end{matrix}}\right]}
、 そして 。
ヴ
2
=
[
1
− φ
1
]
{\displaystyle v_{2}=\left[{\begin{matrix}1\\-\varphi \\1\\\end{matrix}}\right]}
ヴ
3
=
[
1
0
1
]
{\displaystyle v_{3}=\left[{\begin{matrix}1\\0\\1\\\end{matrix}}\right]}
（ 黄金比はどこにあるか）。
φ =
1 +
5
2
{\displaystyle \textstyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}
最大の固有値はであり 、に比例する任意の固有ベクトルに対応する。
λ
1
≈ 5.2361
{\displaystyle \lambda _{1}\approx 5.2361}
ヴ
1
≈
[
1
0.6180
1
]
。
{\displaystyle v_{1}\approx \left[{\begin{matrix}1\\0.6180\\1\\\end{matrix}}\right].}
まず、初期固有値の推定値として
b
0
=
[
1
1
1
]
、
μ
0
= 200
{\displaystyle b_{0}=\left[{\begin{matrix}1\\1\\1\\end{matrix}}\right],~\mu _{0}=200}
。 そして、最初の反復では
b
1
≈
[
− 0.57927
− 0.57348
− 0.57927
]
、
μ
1
≈ 5.3355
{\displaystyle b_{1}\approx \left[{\begin{matrix}-0.57927\\-0.57348\\-0.57927\\\end{matrix}}\right],~\mu _{1}\approx 5.3355}
2回目の繰り返し
b
2
≈
[
0.64676
0.40422
0.64676
]
、
μ
2
≈ 5.2418
{\displaystyle b_{2}\approx \left[{\begin{matrix}0.64676\\0.40422\\0.64676\\\end{matrix}}\right],~\mu _{2}\approx 5.2418}
そして3番目は、
b
3
≈
[
− 0.64793
− 0.40045
− 0.64793
]
、
μ
3
≈ 5.2361
{\displaystyle b_{3}\approx \left[{\begin{matrix}-0.64793\\-0.40045\\-0.64793\\\end{matrix}}\right],~\mu _{3}\approx 5.2361}
そこから三次収束が明らかになります。
オクターブ実装 以下はOctave でのアルゴリズムの簡単な実装です 。
関数 x = rayleigh ( A, epsilon, mu, x ) x = x / norm ( x ); % Octave のバックスラッシュ演算子は線形システムを解きます y = ( A - mu * eye ( rows ( A ))) \ x ; lambda = y ' * x ; mu = mu + 1 / lambda err = norm ( y - lambda * x ) / norm ( y )
err > epsilon の 場合 x = y / norm ( y ); y = ( A - mu * eye ( rows ( A ))) \ x ; lambda = y ' * x ; mu = mu + 1 / lambda err = norm ( y - lambda * x ) / norm ( y ) 終了 終わり
参照
参考文献 Lloyd N. Trefethen と David Bau, III、 「数値線形代数」 、Society for Industrial and Applied Mathematics、1997 年 。ISBN 0-89871-361-7 。 Rainer Kress、「数値解析」、Springer、1991年 。ISBN 0-387-98408-9
![{\displaystyle A=\left[{\begin{matrix}1&2&3\\1&2&1\\3&2&1\\\end{matrix}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/100be72a4de1e00d34c2c6cec2fe30120645a778)
![{\displaystyle v_{1}=\left[{\begin{matrix}1\\\varphi -1\\1\\\end{matrix}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca2f0ca4cc5603861579ef138d645344d4b64cc4)
![{\displaystyle v_{2}=\left[{\begin{matrix}1\\-\varphi \\1\\\end{matrix}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f214dbe77c8e1a2e8115416b0933c3f26a92a12e)
![{\displaystyle v_{3}=\left[{\begin{matrix}1\\0\\1\\\end{matrix}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc3ee9506136cc3a5c0c1828eb695ed4a0a93d3a)
![{\displaystyle v_{1}\approx \left[{\begin{matrix}1\\0.6180\\1\\\end{matrix}}\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca7733c385d7bc4430a8ac01b7dd179021d7dcd9)
![{\displaystyle b_{0}=\left[{\begin{matrix}1\\1\\1\\end{matrix}}\right],~\mu _{0}=200}](https://wikimedia.org/api/rest_v1/media/math/render/svg/94e8b5982dd8f14b9671a20b7b1691f1efb7a04c)
![{\displaystyle b_{1}\approx \left[{\begin{matrix}-0.57927\\-0.57348\\-0.57927\\\end{matrix}}\right],~\mu _{1}\approx 5.3355}](https://wikimedia.org/api/rest_v1/media/math/render/svg/609ad6cfaa3365a2ae1800753d127496295559d2)
![{\displaystyle b_{2}\approx \left[{\begin{matrix}0.64676\\0.40422\\0.64676\\\end{matrix}}\right],~\mu _{2}\approx 5.2418}](https://wikimedia.org/api/rest_v1/media/math/render/svg/42a54a4af490f5ee35dee64c401f7f0a774e7da8)
![{\displaystyle b_{3}\approx \left[{\begin{matrix}-0.64793\\-0.40045\\-0.64793\\\end{matrix}}\right],~\mu _{3}\approx 5.2361}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec6d7cb6acb7ba1c06ae67090cd5fdc3706b859d)