5.逆反復法

何等かの方法(例えばQR法)で得られた各固有値に対応する固有ベクトルを求める手法です。

5.1.逆反復法の概要

行列\( A \)の固有値\( \lambda \)に対応する固有ベクトル\( x \)を求める方法について見ていきます。
\[ A \boldsymbol{ x } = \lambda \boldsymbol{ x } \tag{5.1-1} \] この計算法で用いる固有対(固有値と固有ベクトルの組)の性質は次の通りです。
  1. \( A \boldsymbol{ x } = \lambda \boldsymbol{ x } \Leftrightarrow A ^{-1} \boldsymbol{ x } = \displaystyle \frac{1}{\lambda} \boldsymbol{ x } \)
  2. \( ( A - \mu I ) \boldsymbol{ x } = ( \lambda - \mu ) \boldsymbol{ x } \qquad ( \because A \boldsymbol{ x } = \lambda \boldsymbol{ x } ) \)
    →\( \mu \)は近似固有値で、反復法による数値計算によって得られる値。 \( A \) と\( ( A - \mu I ) \)の固有ベクトル\( \boldsymbol{ x } \)は共通
  3. べき乗法(2章
    →Aの絶対値最大となる固有値と固有ベクトルを求める方法
(反復法を用いた)数値計算で得られる固有値、固有ベクトルは近似的です (この時点で近似固有値は既知とします)。 そこで、数値計算で得られた行列\( A \)の近似固有値を\( \mu \)で表すと、
\[ \mu \fallingdotseq \lambda \quad \rightarrow \quad \lambda - \mu \fallingdotseq 0 \] の関係があります。 つまり、≠0ということです。
この点を利用して、真の固有値と近似固有値の差を使って上記(2)の関係を作ります。
\[ ( A - \mu I ) \boldsymbol{ x } = ( \lambda - \mu ) \boldsymbol{ x } \tag{5.1-2} \] すると\( \boldsymbol{ x } \)は、\( ( A - \mu I ) \)の絶対値最小となる固有値\( ( \lambda - \mu ) \)に対応した固有ベクトルになります。 この関係に上記(1)を適用すると、
\[ ( A - \mu I )^{ -1 } \boldsymbol{ x } = \frac{ 1 }{ \lambda - \mu } \boldsymbol{ x } \tag{5.1-3} \] が得られ、\( 1 / ( \lambda - \mu ) \)は\( ( A - \mu I )^{ -1 } \ \)の絶対値最大の固有値となります。 絶対値最大の固有値に対応する固有ベクトル\( \boldsymbol{ x } \)は、上記(3)のべき乗法(2章)によって求めることができます。 べき乗法は反復計算によって固有ベクトル(固有値も)を求める方法です。 固有ベクトルの解初期値\( \boldsymbol{ x^{ (0) } } \)を適当(乱数)に設定し、次式を繰り返し計算していきます (理由は2章のべき乗法を確認ください)。
\[ ( A - \mu I )^{ -1 } \ \boldsymbol{ x^{ ( k - 1 ) } } = \boldsymbol{ x^{ ( k ) } } \tag{5.1-4} \] \( \boldsymbol{ x^{ (k-1) } } \fallingdotseq \boldsymbol{ x^{ (k) } } \)となったところで解は収束したものとして、\( \boldsymbol{ x^{ (k) } } \)を固有ベクトルの近似解とします。
実際の計算では、数値安定性の問題から逆行列計算は用いません。次式のように変形し、
\[ ( A - \mu I ) \boldsymbol{ x^{ ( k ) } } = \boldsymbol{ x^{ ( k - 1 ) } } \tag{5.1-5} \] \( \boldsymbol{ x^{ (k) } } \)の連立方程式として、\( A - \mu I \)をLU分解 (L:下三行列、U:上三角行列)して計算するのが一般的です。 逆反復法と呼ばれるのは逆行列をもとの行列に戻すところに由来がある、と言えます。
\[ ( A - \mu I ) = LU \quad \rightarrow \quad LU \boldsymbol{ x^{ (k) } } = \boldsymbol{ x^{ (k-1) } } \tag{5.1-6} \] と出来るので、まずは\( \boldsymbol{ y } = U \boldsymbol{ x^{(k)} } \)とおいて\( L \boldsymbol{ y } = \boldsymbol{ x^{(k-1)} } \ \)を連立方程式として解いて\( \boldsymbol{ y } \)を決めます。 \( \boldsymbol{ y } \)が決まれば今度は\( \boldsymbol{ y } = U \boldsymbol{ x^{ (k) } } \ \)を連立方程式として解いて近似固有ベクトルである\( \boldsymbol{ x^{(k)} } \)が決まります。
\( ( A - \mu I ) \)の固有ベクトルはそもそも\( A \)の\( \lambda \)に対応する固有ベクトル\( \boldsymbol{ x } \)であるため、\( \boldsymbol{ x } \fallingdotseq \boldsymbol{ x^{(k)} } \)として\( A \)の近似固有ベクトルが求まります。

ところで、数値計算上でも近似固有値が真の固有値と一致する場合が(多々)あります。 この場合\( \lambda - \mu = 0 \)となるため、本来の固有ベクトルとは似て非なる値が出てきます。 この対策として、\( \mu \)にわざと微小値(例えば単精度分1E-08)を足して計算してみると、解消されることがあります。
また、LU分解による連立方程式の解法ではなくQR分解を用いても固有ベクトルを計算できます (本サイトで公開している行列計算ツール(準備中)はQR分解を用いて固有ベクトルを計算しています)。

5.2.逆反復法の計算フロー

(1)LU分解を用いた逆反復法の計算フローは次の通りです。

逆反復法(LR分解)の計算フロー
図5.2-1 逆反復法(LR分解)の計算フロー


(2)QR分解を用いた逆反復法の計算フローは次の通りです。

逆反復法(QR分解)の計算フロー
図5.2-1 逆反復法(QR分解)の計算フロー

      

参考文献

固有値計算は、CAE、CFD、統計解析、機械学習など実用的にも重要な役割を担っています。