4.5.2.0.1.2 ステップ2

($A_k$ の挙動) $A$ は固有値がすべて相異なるから対角化が可能である。 すなわち $\exists M\in GL(n;\C)$ s.t.

$$M^{-1} A M=\Lambda,\quad\Lambda={\rm diag}(\lambda_1,\cdots,\lambda_n).$$

$M$ を $M=QR$ と QR 分解、$M^{-1}$ を $M^{-1}=LU$ (ただし $L$ の対角成 分はすべて $1$) と LU 分解して、

$$A^{k+1}=M\Lambda^{k+1}M^{-1} =(Q R)\Lambda^{k+1} (L U) =Q R (\Lambda^{k+1}L\Lambda^{-(k+1)}) \Lambda^{k+1}U.$$ (4.11)

ここで $\Lambda^{k+1}L\Lambda^{-(k+1)}$ は下三角行列で、対角成分はすべて $1$ に等しく、$i>j$ のとき $(i,j)$ 成分は

$$\ell_{ij}\left(\frac{\lambda_i}{\lambda_j}\right)^{k+1}$$

に等しい (ただし $\ell_{ij}$ は $L$ の $(i,j)$ 成分)。そこで

$$\Lambda^{k+1}L\Lambda^{-(k+1)}=I+E_k$$

とおくと、 $\dsp\lim_{k\to\infty}E_k=O$. 上式を (4.11) 代入して、

$$A^{k+1} = Q R(\Lambda^{k+1}L\Lambda^{-(k+1)})\Lambda^{l+1} U$$ (4.12)

$$= Q R(I+E_k) (R^{-1}R) (\Lambda^{l+1} U) =Q R(I+E_k) R^{-1}(R \Lambda^{l+1} U)$$

$$= Q (I+R E_k R^{-1})(R \Lambda^{l+1} U)$$

この $I+R E_k R^{-1}$ を QR 分解する:

$$I+R E_k R^{-1}=S_k T_k.$$ (4.13)

$I+R E_k R^{-1}\to I$ ($k\to\infty$) で、QR 分解の連続性は明らかだから、

$$\dsp\lim_{k\to\infty}S_k=I, \quad \dsp\lim_{k\to\infty}T_k=I.$$

(4.13) を (4.12) に代入して、

$$A^{k+1}=Q(S_k T_k)(R\Lambda^{k+1}U) =(Q S_k) (T_k R\Lambda^{k+1}U).$$ (4.14)

この右辺は unitary 行列と、上三角行列の積の形になっている。