逆べき乗法（inverse iteration, inverse power method）は、行列の絶対値最小固有値および対応する固有ベクトルを反復計算によって近似的に求めるアルゴリズムです。
名前が示しているように、前回扱ったべき乗法と深い関係があります。
$A$ を可逆な $n$ 次正方行列とすると、$0$ でないスカラー $\lambda$ と $n$ 次元ベクトル $x$ に対して
$$ Ax=\lambda x \iff x=A^{-1}(\lambda x) \iff A^{-1}x=\frac{1}{\lambda}x $$が成り立ちます。すなわち、$\lambda$ と $x$ が $A$ の固有値および対応する固有ベクトルであることと、$\frac{1}{\lambda}$ と $x$ が $A^{-1}$ の固有値および対応する固有ベクトルであることは、同値です。
このことから、$A$ の絶対値最小固有値は $A^{-1}$ の絶対値最大固有値の逆数であり、$A^{-1}$ に対してべき乗法を適用して得られる固有値の逆数と固有ベクトルが$A$ の絶対値最小固有値および対応する固有ベクトルになることが分かります。
前回扱ったべき乗法のアルゴリズムを参考にして逆べき乗法のアルゴリズムを実現するコードを書き、
$$ A= \begin{pmatrix} 2 & -1 & 0 & 0 & 0\\ -1 & 2 & -1 & 0 & 0\\ 0 & -1 & 2 & -1 & 0\\ 0 & 0 & -1 & 2 & -1\\ 0 & 0 & 0 & -1 & 2 \end{pmatrix} $$の絶対値最小固有値および対応する固有ベクトルの近似値を求めてください。ただし、
$$ x^{(0)}= \begin{pmatrix} 1\\ 0\\ 0\\ 0\\ 0 \end{pmatrix} ,\quad EPS=10^{-2},\quad K=100 $$とします。逆行列 $A^{-1}$ の計算には、関数invを使用すること。
%演習1のコード
%前回の演習1のコードを修正する
%変数Aを定めた後に、Aの逆行列を格納する変数を「inv_A = inv(A)」のように用意して使うと良い
%最後に固有値の逆数を取る必要があることに注意
上では逆行列を実際に計算していますが、一般に数値計算の分野では計算量や誤差の観点から逆行列の計算をなるべく避けることが通常です。
逆べき乗法では、初期値ベクトル $x^{(0)}$ から
$$ \lambda^{(k)}=x^{(k)}{}^T A^{-1}x^{(k)},\quad x^{(k+1)}=\frac{A^{-1}x^{(k)}}{\left\|A^{-1}x^{(k)}\right\|} $$によって数列 $\left\{\lambda^{(k)}\right\}_{k=0}^{\infty}$ とベクトル列 $\left\{x^{(k)}\right\}_{k=0}^{\infty}$ を定め、反復の終了条件
$$ \left\| A^{-1}x^{(k)}-\lambda^{(k)}x^{(k)}\right\| < EPS \quad \text{or} \quad k>K $$を満たすまで反復計算を行った後の $\lambda^{(k)}$ の逆数と $x^{(k)}$ を、行列 $A$ の絶対値最小固有値および対応する固有ベクトルの近似値として得ます。
ここで、
$$ y^{(k)}=A^{-1}x^{(k)} $$とおけば、上の定義式は
$$ \lambda^{(k)}=x^{(k)}{}^T y^{(k)},\quad x^{(k+1)}=\frac{y^{(k)}}{\left\|y^{(k)}\right\|}, $$反復の終了条件は
$$ \left\| y^{(k)}-\lambda^{(k)}x^{(k)}\right\| < EPS \quad \text{or} \quad k>K $$となります。
このとき、逆行列 $A^{-1}$ を用いずに $y^{(k)}$ を計算することを考えると、連立一次方程式
$$ Ay^{(k)}=x^{(k)} $$を解けばよいということが分かります。
特に、一つの行列 $A$ と複数のベクトル $x^{(0)},x^{(1)},x^{(2)},\ldots$ に対して連立一次方程式を解くことになるため、ガウスの消去法の前進消去によるLU分解と前進代入・後退代入を用いた解法（第7回の授業内容）が有効です。
ガウスの消去法の前進消去によるLU分解と前進代入・後退代入を利用した逆べき乗法によって、演習1と同じく
$$ A= \begin{pmatrix} 2 & -1 & 0 & 0 & 0\\ -1 & 2 & -1 & 0 & 0\\ 0 & -1 & 2 & -1 & 0\\ 0 & 0 & -1 & 2 & -1\\ 0 & 0 & 0 & -1 & 2 \end{pmatrix} $$の絶対値最小固有値および対応する固有ベクトルの近似値を求めてください。ただし、
$$ x^{(0)}= \begin{pmatrix} 1\\ 0\\ 0\\ 0\\ 0 \end{pmatrix} ,\quad EPS=10^{-2},\quad K=100 $$とします。
%演習2のコード
与えられた行列に対して、べき乗法を使えば絶対値最大固有値、逆べき乗法を使えば絶対値最小固有値を計算できると分かりましたが、逆べき乗法は他の固有値の計算にも利用することができます。
$n$ 次正方行列 $A$ に対して、指定された値 $\mu$ に最も近い固有値および対応する固有ベクトルを求めることを考えます。
$I_n$ を $n$ 次単位行列とするとき、
$$ Ax=\lambda x \iff \left(A-\mu I_n\right)x=(\lambda-\mu)x $$であるから、$\lambda$ と $x$ が $A$ の固有値および対応する固有ベクトルであることと、$\lambda-\mu$ と $x$ が $A-\mu I_n$ の固有値および対応する固有ベクトルであることは、同値です。
ここで、$A$ の固有値を $\lambda_1,\ldots,\lambda_n$ とすれば、$A-\mu I_n$ の固有値を $\tilde{\lambda}_1=\lambda_1-\mu,\ldots,\tilde{\lambda}_n=\lambda_n-\mu$ とおくことができます。
もし $\tilde{\lambda}_i$ が $A-\mu I_n$ の絶対値最小固有値であれば、
$$ \left|\tilde{\lambda}_i\right|=\min_{j=1,\ldots,n}\left|\tilde{\lambda}_j\right| $$より
$$ \left|\lambda_i-\mu\right|=\min_{j=1,\ldots,n}\left|\lambda_j-\mu\right| $$が成り立つため、$\lambda_i=\tilde{\lambda}_i+\mu$ が $A$ の $\mu$ に最も近い固有値となります。
したがって、行列 $A-\mu I_n$ に対して逆べき乗法を適用することによって、$A$ の $\mu$ に最も近い固有値および対応する固有ベクトルを求めることができると分かります。
逆べき乗法を利用して、
$$ A= \begin{pmatrix} 2 & -1 & 0 & 0 & 0\\ -1 & 2 & -1 & 0 & 0\\ 0 & -1 & 2 & -1 & 0\\ 0 & 0 & -1 & 2 & -1\\ 0 & 0 & 0 & -1 & 2 \end{pmatrix} $$の $\mu=2.3$ に最も近い固有値および対応する固有ベクトルの近似値を求めてください。ただし、
$$ x^{(0)}= \begin{pmatrix} 1\\ 0\\ 0\\ 0\\ 0 \end{pmatrix} ,\quad EPS=10^{-2},\quad K=100 $$とします。関数invを使用して逆行列の計算を行ってもよいです。
%演習3のコード
演習1～演習3に取り組んでください。