固有値の反復解法 | 数値解析 I

1 べき乗法

定義 1.1. $n\in\NN$ とする。 $h,w\in\C^n$ に対して $h^*$ を $h$ の共役転置とし、 $h^*w=\sum_{i=1}^n\overline{h_i}w_i$ 、 $\lVert h\rVert_2:=(h^*h)^{1/2}$ と置く。 $A\in\C^{n\times n}$ とし、 $y_0\in\C^n$ を $\lVert y_0\rVert_2=1$ を満たすベクトルとする。 $k\ge0$ について $y_k$ が定まり $Ay_k\ne0$ であるとき

y_{k+1}:=\frac{Ay_k}{\lVert Ay_k\rVert_2}

と置く。こうして定まる列 $(y_k)$ を、 $A$ に対する $y_0$ からのべき乗法 (power iteration) という。 $A$ が正則ならば、すべての $k\ge0$ について $y_k$ が定まる。 $\lVert y\rVert_2=1$ を満たす $y\in\C^n$ に対して、複素数 $y^*Ay$ を $A$ の $y$ における Rayleigh 商 (Rayleigh quotient) といい、べき乗法について $\mu_k:=y_k^*Ay_k$ と置く。部分空間 $E\subset\C^n$ と $y\in\C^n$ に対して、 $\operatorname{dist}(y,E):=\inf_{e\in E}\lVert y-e\rVert_2$ と置き、これを $y$ の $E$ からの距離 (distance from a subspace) という。

補題 1.2. $n\in\NN$ 、 $A\in\C^{n\times n}$ とし、 $\lVert A\rVert_2$ を $\C^n$ の $\lVert\cdot\rVert_2$ に関する $A$ の作用素ノルム（§E20.5 定義 4.2）とする。 $\lambda\in\C$ と $\hat u\in\C^n$ が $A\hat u=\lambda\hat u$ 、 $\lVert\hat u\rVert_2=1$ を満たすとする。 $\lVert z\rVert_2=1$ を満たす任意の $z\in\C^n$ と $\lvert\theta\rvert=1$ を満たす任意の $\theta\in\C$ に対して

(\theta z)^*A(\theta z)=z^*Az,\qquad\lvert z^*Az-\lambda\rvert\le2\lVert A\rVert_2\lVert\theta z-\hat u\rVert_2

が成り立つ。

証明. 任意の $h\in\C^n$ に対して、Cauchy–Schwarz の不等式により $\lVert Ah\rVert_2^2=\sum_i\lvert\sum_ja_{ij}h_j\rvert^2\le\bigl(\sum_{i,j}\lvert a_{ij}\rvert^2\bigr)\lVert h\rVert_2^2$ であるから、 $\lVert A\rVert_2<\infty$ であり、 $\lVert Ah\rVert_2\le\lVert A\rVert_2\lVert h\rVert_2$ が成り立つ。 $w:=\theta z$ と置く。 $\overline\theta\theta=1$ であるから $w^*Aw=\overline\theta\theta z^*Az=z^*Az$ であり、 $\lVert w\rVert_2=1$ である。 $\hat u^*A\hat u=\lambda\hat u^*\hat u=\lambda$ であるから

z^*Az-\lambda=w^*Aw-\hat u^*A\hat u=(w-\hat u)^*Aw+\hat u^*A(w-\hat u)

である。Cauchy–Schwarz の不等式により $\lvert(w-\hat u)^*Aw\rvert\le\lVert w-\hat u\rVert_2\lVert A\rVert_2$ 、 $\lvert\hat u^*A(w-\hat u)\rvert\le\lVert A\rVert_2\lVert w-\hat u\rVert_2$ であり、二つを加えて主張の不等式を得る。▨

補題 1.3. $n\in\NN$ とし、 $a,b\in\C^n$ を $a\ne0$ 、 $b\ne0$ を満たすベクトルとする。このとき

\left\lVert\frac{a}{\lVert a\rVert_2}-\frac{b}{\lVert b\rVert_2}\right\rVert_2\le\frac{2\lVert a-b\rVert_2}{\lVert b\rVert_2}

が成り立つ。

証明. 演習とする（問題 8.1）。▨

定理 1.4. $n\in\NN$ とし、 $A\in\C^{n\times n}$ が $\C^n$ の基底 $v_1,\dots,v_n$ と複素数 $\lambda_1,\dots,\lambda_n$ について $Av_i=\lambda_iv_i$ （ $1\le i\le n$ ）を満たすとする。整数 $1\le d\le n$ と複素数 $\lambda\ne0$ について、 $i\le d$ ならば $\lambda_i=\lambda$ 、 $i>d$ ならば $\lvert\lambda_i\rvert<\lvert\lambda\rvert$ であるとする。 $d<n$ ならば $q:=\max_{i>d}\lvert\lambda_i\rvert/\lvert\lambda\rvert$ 、 $d=n$ ならば $q:=0$ と置き、 $q^0:=1$ とする。 $y_0\in\C^n$ を $\lVert y_0\rVert_2=1$ を満たすベクトルとし、 $y_0=\sum_{i=1}^nc_iv_i$ と表して、 $u:=\sum_{i\le d}c_iv_i\ne0$ を仮定する。 $(y_k)$ を $A$ に対する $y_0$ からのべき乗法、 $\mu_k:=y_k^*Ay_k$ とする。

すべての $k\ge0$ について $Ay_k\ne0$ であり、 $A^ky_0\ne0$ 、 $y_k=A^ky_0/\lVert A^ky_0\rVert_2$ である。
$\hat u:=u/\lVert u\rVert_2$ 、 $\theta_k:=\lvert\lambda\rvert^k/\lambda^k$ と置く。 $k$ によらない実数 $C\ge0$ が存在して、すべての $k\ge0$ について $\lVert\theta_ky_k-\hat u\rVert_2\le Cq^k$ が成り立つ。
(2)の $C$ について、すべての $k\ge0$ で $\lvert\mu_k-\lambda\rvert\le2C\lVert A\rVert_2q^k$ が成り立つ。

証明.(1)を示す。 $k\ge0$ について $w_k:=\sum_{i>d}c_i(\lambda_i/\lambda)^kv_i$ と置く（ $d=n$ ならば $w_k:=0$ ）。 $A^kv_i=\lambda_i^kv_i$ であるから

A^ky_0=\sum_{i=1}^nc_i\lambda_i^kv_i=\lambda^k(u+w_k)

である。 $u\ne0$ であるから $i\le d$ のある $i$ について $c_i\ne0$ であり、 $v_1,\dots,v_n$ は一次独立であるから $u+w_k\ne0$ 、したがって $A^ky_0\ne0$ である。 $y_k=A^ky_0/\lVert A^ky_0\rVert_2$ が成り立つとすると、 $Ay_k=A^{k+1}y_0/\lVert A^ky_0\rVert_2\ne0$ であり、 $y_{k+1}=A^{k+1}y_0/\lVert A^{k+1}y_0\rVert_2$ である。 $k=0$ では $\lVert y_0\rVert_2=1$ から等式が成り立つので、 $k$ に関する帰納法により(1)が従う。

(2)を示す。 $\theta_k\lambda^k=\lvert\lambda\rvert^k$ であるから、(1)により

\theta_ky_k=\frac{\lvert\lambda\rvert^k(u+w_k)}{\lvert\lambda\rvert^k\lVert u+w_k\rVert_2}=\frac{u+w_k}{\lVert u+w_k\rVert_2}

である。 $M:=\sum_{i>d}\lvert c_i\rvert\lVert v_i\rVert_2$ と置くと、 $i>d$ について $\lvert\lambda_i/\lambda\rvert^k\le q^k$ であるから $\lVert w_k\rVert_2\le Mq^k$ である。補題 1.3を $a=u+w_k$ 、 $b=u$ に適用すると

\lVert\theta_ky_k-\hat u\rVert_2\le\frac{2\lVert w_k\rVert_2}{\lVert u\rVert_2}\le\frac{2M}{\lVert u\rVert_2}q^k

であり、 $C:=2M/\lVert u\rVert_2$ と置けばよい。

(3)を示す。 $u$ は $A$ の固有値 $\lambda$ の固有ベクトルの一次結合であるから $A\hat u=\lambda\hat u$ であり、 $\lvert\theta_k\rvert=1$ 、 $\lVert y_k\rVert_2=1$ である。補題 1.2を $z=y_k$ 、 $\theta=\theta_k$ に適用し、(2)を用いて $\lvert\mu_k-\lambda\rvert\le2\lVert A\rVert_2\lVert\theta_ky_k-\hat u\rVert_2\le2C\lVert A\rVert_2q^k$ を得る。▨

注意 1.5.

絶対値が最大の固有値が二つ以上あるとき、べき乗法の方向が収束するかどうかは初期ベクトルによる。 $A:=\operatorname{diag}(1,-1)$ の固有値 $1,-1$ の絶対値は等しく、固有空間は $\operatorname{span}\{e_1\}$ 、 $\operatorname{span}\{e_2\}$ である。 $y_0:=(1,1)^{\mathsf T}/\sqrt2$ ならば $Ay_k$ の第 $2$ 成分の符号が毎回反転するので $y_k=(1,(-1)^k)^{\mathsf T}/\sqrt2$ 、 $\mu_k=0$ であり、任意の $k$ と $\lvert\theta\rvert=1$ について $\operatorname{dist}(\theta y_k,\operatorname{span}\{e_1\})=\operatorname{dist}(\theta y_k,\operatorname{span}\{e_2\})=1/\sqrt2$ である。 $y_0:=e_1$ ならば、すべての $k$ について $y_k=e_1$ である。
定理 1.4の仮定の下で $(y_k)$ が収束するならば、 $\lambda$ は正の実数である。実際、 $y_k\to y$ とすると、 $\hat u$ の成分 $\hat u_j\ne0$ をとれば、定理 1.4 (2)により $\lvert y_{k,j}\rvert=\lvert\theta_ky_{k,j}\rvert\to\lvert\hat u_j\rvert$ であるから $\lvert y_j\rvert=\lvert\hat u_j\rvert>0$ であり、十分大きい $k$ について $y_{k,j}\ne0$ 、 $\theta_k=\theta_ky_{k,j}/y_{k,j}\to\hat u_j/y_j$ である。 $\lambda=\lvert\lambda\rvert e^{\mathrm i\varphi}$ と書くと $\theta_{k+1}/\theta_k=e^{-\mathrm i\varphi}$ であり、極限 $\hat u_j/y_j$ は $0$ でないから左辺は $1$ に収束し、 $e^{\mathrm i\varphi}=1$ である。 $A:=\operatorname{diag}(-2,1)$ 、 $y_0:=(1,1)^{\mathsf T}/\sqrt2$ では $\lambda=-2$ 、 $d=1$ 、 $u=e_1/\sqrt2$ 、 $\theta_k=(-1)^k$ であり、 $y_k=\frac{((-2)^k,1)^{\mathsf T}}{\sqrt{4^k+1}},\qquad\theta_ky_k=\frac{(2^k,(-1)^k)^{\mathsf T}}{\sqrt{4^k+1}}\to e_1,\qquad\mu_k=\frac{1-2\cdot4^k}{4^k+1}\to-2$ である。 $y_k$ の第 $1$ 成分は符号が交互に変わり、絶対値は $1$ に収束するので、 $(y_k)$ は収束しない。

2 正規直交な固有基底をもつ行列

補題 2.1. $n\in\NN$ 、 $A\in\C^{n\times n}$ とし、 $\C^n$ の基底 $v_1,\dots,v_n$ で $v_i^*v_j=\delta_{ij}$ を満たすものと実数 $\lambda_1,\dots,\lambda_n$ が $Av_i=\lambda_iv_i$ （ $1\le i\le n$ ）を満たすとする。 $y\in\C^n$ に対して $c_i:=v_i^*y$ と置く。

$y=\sum_ic_iv_i$ 、 $\lVert y\rVert_2^2=\sum_i\lvert c_i\rvert^2$ 、 $y^*Ay=\sum_i\lambda_i\lvert c_i\rvert^2$ であり、任意の $\mu\in\C$ に対して $\lVert Ay-\mu y\rVert_2^2=\sum_i\lvert\lambda_i-\mu\rvert^2\lvert c_i\rvert^2$ である。
$J\subset\{1,\dots,n\}$ とし、 $E_J:=\operatorname{span}\{v_i\mid i\in J\}$ と置く。 $\operatorname{dist}(y,E_J)^2=\sum_{i\notin J}\lvert c_i\rvert^2$ であり、 $\operatorname{dist}(y,E_J)=\lVert y-e\rVert_2$ を満たす $e\in E_J$ は $\sum_{i\in J}c_iv_i$ だけである。
$A\in\R^{n\times n}$ が $A^{\mathsf T}=A$ を満たすならば、 $\R^n$ の正規直交基底 $q_1,\dots,q_n$ と実数 $\lambda_1\le\dots\le\lambda_n$ で $Aq_i=\lambda_iq_i$ を満たすものが存在する。 $q_1,\dots,q_n$ は $\C^n$ の基底として $q_i^*q_j=\delta_{ij}$ を満たし、 $\det(tI-A)=\prod_i(t-\lambda_i)$ である。

証明.(1)を示す。 $y=\sum_ia_iv_i$ と表すと $v_j^*y=\sum_ia_iv_j^*v_i=a_j$ であるから $a_j=c_j$ である。 $w=\sum_ib_iv_i$ に対して $w^*w=\sum_{i,j}\overline{b_i}b_jv_i^*v_j=\sum_i\lvert b_i\rvert^2$ である。 $Ay=\sum_i\lambda_ic_iv_i$ であるから $y^*Ay=\sum_{i,j}\overline{c_i}\lambda_jc_jv_i^*v_j=\sum_i\lambda_i\lvert c_i\rvert^2$ であり、 $Ay-\mu y=\sum_i(\lambda_i-\mu)c_iv_i$ に $w^*w$ の式を適用して最後の等式を得る。

(2)を示す。 $e\in E_J$ を $e=\sum_{i\in J}b_iv_i$ と表すと、 $y-e=\sum_{i\in J}(c_i-b_i)v_i+\sum_{i\notin J}c_iv_i$ であるから、(1)の式により $\lVert y-e\rVert_2^2=\sum_{i\in J}\lvert c_i-b_i\rvert^2+\sum_{i\notin J}\lvert c_i\rvert^2$ である。右辺は $b_i=c_i$ （ $i\in J$ ）のときだけ最小値 $\sum_{i\notin J}\lvert c_i\rvert^2$ をとる。

(3)を示す。§D3.15 定理 3.1により、直交行列 $P$ と対角行列 $D$ が $P^{\mathsf T}AP=D$ を満たす。 $P$ の列を $D$ の対角成分が非減少になる順に並べ替えても直交行列であり、並べ替えた列を $q_1,\dots,q_n$ 、対角成分を $\lambda_1\le\dots\le\lambda_n$ とすると $Aq_i=\lambda_iq_i$ である。 $q_i$ は実ベクトルであるから $q_i^*q_j=q_i^{\mathsf T}q_j=\delta_{ij}$ であり、 $\det(tI-A)=\det(tI-D)=\prod_i(t-\lambda_i)$ である。▨

命題 2.2. $n\in\NN$ 、 $A\in\C^{n\times n}$ とし、 $v_1,\dots,v_n$ と実数 $\lambda_1,\dots,\lambda_n$ は補題 2.1の仮定を満たすとする。整数 $1\le d\le n$ と実数 $\lambda$ について、 $i\le d$ ならば $\lambda_i=\lambda$ 、 $i>d$ ならば $\lambda_i\ne\lambda$ であるとし、 $E:=\operatorname{span}\{v_1,\dots,v_d\}$ 、 $\delta:=\max_i\lvert\lambda_i-\lambda\rvert$ と置く。

$\lVert y\rVert_2=1$ を満たす任意の $y\in\C^n$ に対して $\lvert y^*Ay-\lambda\rvert\le\delta\operatorname{dist}(y,E)^2$ が成り立つ。さらに、 $\hat u\in E$ が $\lVert\hat u\rVert_2=1$ を満たし、 $\theta\in\C$ が $\lvert\theta\rvert=1$ を満たすならば、 $\operatorname{dist}(y,E)\le\lVert\theta y-\hat u\rVert_2$ である。
$\lambda\ne0$ であり、 $i>d$ ならば $\lvert\lambda_i\rvert<\lvert\lambda\rvert$ であるとし、 $y_0$ は定理 1.4の仮定を満たすとする。同定理の $q$ 、 $(\mu_k)$ と定理 1.4 (2)の $C$ について、すべての $k\ge0$ で $\lvert\mu_k-\lambda\rvert\le\delta C^2q^{2k}$ が成り立つ。
$y_0\in\C^n$ が $\lVert y_0\rVert_2=1$ と $v_i^*y_0=0$ （ $i\le d$ ）を満たすならば、 $A$ に対する $y_0$ からのべき乗法の $y_k$ が定まる任意の $k$ について、 $v_i^*y_k=0$ （ $i\le d$ ）であり、 $\operatorname{dist}(y_k,E)=1$ である。

証明.(1)を示す。 $c_i:=v_i^*y$ と置く。補題 2.1 (1)により $\sum_i\lvert c_i\rvert^2=1$ であり、 $i\le d$ で $\lambda_i=\lambda$ であるから

y^*Ay-\lambda=\sum_i(\lambda_i-\lambda)\lvert c_i\rvert^2=\sum_{i>d}(\lambda_i-\lambda)\lvert c_i\rvert^2

である。したがって $\lvert y^*Ay-\lambda\rvert\le\delta\sum_{i>d}\lvert c_i\rvert^2$ であり、補題 2.1 (2)を $J=\{1,\dots,d\}$ に適用すると右辺は $\delta\operatorname{dist}(y,E)^2$ である。後半について、 $\overline\theta\hat u\in E$ であり $\lVert y-\overline\theta\hat u\rVert_2=\lVert\theta y-\hat u\rVert_2$ であるから、 $\operatorname{dist}(y,E)\le\lVert\theta y-\hat u\rVert_2$ である。

(2)を示す。定理 1.4 (2)の $\hat u=u/\lVert u\rVert_2$ は $E$ の単位ベクトルである。(1)と定理 1.4 (2)により $\lvert\mu_k-\lambda\rvert\le\delta\operatorname{dist}(y_k,E)^2\le\delta\lVert\theta_ky_k-\hat u\rVert_2^2\le\delta C^2q^{2k}$ である。

(3)を示す。 $F:=\operatorname{span}\{v_{d+1},\dots,v_n\}$ と置くと $AF\subset F$ であり、補題 2.1 (1)により $w\in\C^n$ が $F$ に属することと $v_i^*w=0$ （ $i\le d$ ）であることは同値である。 $y_0\in F$ であり、 $y_k\in F$ かつ $Ay_k\ne0$ ならば $y_{k+1}=Ay_k/\lVert Ay_k\rVert_2\in F$ であるから、 $y_k$ が定まる限り $y_k\in F$ である。補題 2.1 (2)により $\operatorname{dist}(y_k,E)^2=\sum_{i>d}\lvert v_i^*y_k\rvert^2=\lVert y_k\rVert_2^2=1$ である。▨

例 2.3. $A:=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ とする。 $v_1:=(1,1)^{\mathsf T}/\sqrt2$ 、 $v_2:=(1,-1)^{\mathsf T}/\sqrt2$ は $v_i^*v_j=\delta_{ij}$ と $Av_1=3v_1$ 、 $Av_2=v_2$ を満たし、命題 2.2は $d=1$ 、 $\lambda=3$ 、 $E=\operatorname{span}\{v_1\}$ 、 $\delta=2$ で適用することができる。

$y_0:=(1,0)^{\mathsf T}=(v_1+v_2)/\sqrt2$ とする。 $A^ky_0=(3^kv_1+v_2)/\sqrt2=\frac12(3^k+1,3^k-1)^{\mathsf T}$ であり、 $\lVert A^ky_0\rVert_2^2=(9^k+1)/2$ であるから、定理 1.4 (1)により $y_k=(3^kv_1+v_2)/\sqrt{9^k+1}$ である。 $y_k$ の $v_2$ 成分と $v_1$ 成分の比は $3^{-k}$ であり、 $y_1=(2,1)^{\mathsf T}/\sqrt5$ 、 $\mu_1=14/5$ である。補題 2.1 (1)と補題 2.1 (2)により $\operatorname{dist}(y_k,E)^2=\frac1{9^k+1},\qquad\mu_k=\frac{3\cdot9^k+1}{9^k+1},\qquad3-\mu_k=\frac2{9^k+1}$ であり、命題 2.2 (1)の不等式 $\lvert\mu_k-3\rvert\le2\operatorname{dist}(y_k,E)^2$ は等号で成り立つ。 $k=1,2,5$ では $3-\mu_k=1/5,\ 1/41,\ 1/29525$ である。
$y_0:=v_2$ ならば、命題 2.2 (3)により厳密算術では $y_k=v_2$ 、 $\mu_k=1$ 、 $\operatorname{dist}(y_k,E)=1$ がすべての $k$ で成り立つ。
binary64 の最近接丸めで $s:=\operatorname{fl}(1/\operatorname{fl}(\sqrt2))=\texttt{0x1.6a09e667f3bccp-1}$ を計算し、 $y_0:=(s,-s)^{\mathsf T}$ から、 $Ay_k$ 、 $\lVert Ay_k\rVert_2$ 、その商、 $\mu_k$ を binary64 の四則演算と平方根で計算した。 $1\le k\le60$ で、計算した $y_k$ の成分は $\pm0.7071067811865476$ であり、二つの成分の和は $0$ 、すなわち $v_1$ 成分は $0$ であった。計算した $\mu_0$ は $1-2^{-52}$ 、 $\mu_k$ （ $1\le k\le60$ ）は $1+2^{-52}$ であった。この入力では、 $y_k=(a,-a)^{\mathsf T}$ から $Ay_k$ を計算する演算 $2a-a$ 、 $a-2a$ の厳密な結果 $\pm a$ が binary64 の元であり、最近接丸めは符号について対称であるから、計算した $y_{k+1}$ も $(a',-a')^{\mathsf T}$ の形をもつ。

3 逆反復

定義 3.1. $n\in\NN$ 、 $A\in\C^{n\times n}$ とし、 $\sigma\in\C$ は $\det(A-\sigma I)\ne0$ を満たすとする。 $y_0\in\C^n$ を $\lVert y_0\rVert_2=1$ を満たすベクトルとする。 $k\ge0$ について、 $z_k\in\C^n$ を一次方程式 $(A-\sigma I)z_k=y_k$ のただ一つの解とし、 $y_{k+1}:=z_k/\lVert z_k\rVert_2$ と置く。こうして定まる列 $(y_k)$ を、 $A$ に対するシフト (shift) $\sigma$ 、初期ベクトル $y_0$ の逆反復 (inverse iteration) という。 $y_k\ne0$ であるから $z_k\ne0$ であり、すべての $k\ge0$ について $y_k$ が定まる。 $y_k$ は $(A-\sigma I)^{-1}$ に対する $y_0$ からのべき乗法の第 $k$ 項に等しい。

注意 3.2. $A\in\R^{n\times n}$ 、 $\sigma\in\R$ 、 $y_0\in\R^n$ とし、 $\det(A-\sigma I)\ne0$ とする。§E20.5 定理 2.5 (1)により $A-\sigma I$ のピボット付き LU 分解 $(P,L,U)$ が部分ピボット付き消去で得られ、§E20.5 定理 2.5 (2)により、各 $k$ の $z_k$ は $Lw=Py_k$ の前進代入と $Uz_k=w$ の後退代入を厳密算術で実行して得られる。§E20.5 定理 2.5 (3)により、分解は $2n^3/3-n^2/2-n/6$ 回の四則演算を一度だけ行い、各反復の二つの代入は $2n^2-n$ 回の四則演算を行う。

系 3.3. $n\in\NN$ とし、 $A\in\C^{n\times n}$ が $\C^n$ の基底 $v_1,\dots,v_n$ と複素数 $\lambda_1,\dots,\lambda_n$ について $Av_i=\lambda_iv_i$ を満たすとする。 $\sigma\in\C$ は $\sigma\ne\lambda_i$ （ $1\le i\le n$ ）を満たすとする。整数 $1\le d\le n$ と $\lambda\in\C$ について、 $i\le d$ ならば $\lambda_i=\lambda$ 、 $i>d$ ならば $\lvert\lambda_i-\sigma\rvert>\lvert\lambda-\sigma\rvert$ であるとする。 $d<n$ ならば $q:=\max_{i>d}\lvert\lambda-\sigma\rvert/\lvert\lambda_i-\sigma\rvert$ 、 $d=n$ ならば $q:=0$ と置き、 $q^0:=1$ とする。 $y_0\in\C^n$ を $\lVert y_0\rVert_2=1$ を満たすベクトルとし、 $y_0=\sum_ic_iv_i$ 、 $u:=\sum_{i\le d}c_iv_i\ne0$ 、 $\hat u:=u/\lVert u\rVert_2$ とする。 $(y_k)$ をシフト $\sigma$ 、初期ベクトル $y_0$ の逆反復とし、 $\theta_k:=\bigl((\lambda-\sigma)/\lvert\lambda-\sigma\rvert\bigr)^k$ と置く。このとき $k$ によらない実数 $C\ge0$ が存在して、すべての $k\ge0$ について

\lVert\theta_ky_k-\hat u\rVert_2\le Cq^k,\qquad\lvert y_k^*Ay_k-\lambda\rvert\le2C\lVert A\rVert_2q^k

が成り立つ。

証明. $\sigma$ は $A$ の固有値でないから $B:=(A-\sigma I)^{-1}$ が存在し、 $Bv_i=(\lambda_i-\sigma)^{-1}v_i$ である。 $\beta:=(\lambda-\sigma)^{-1}\ne0$ と置くと、 $i\le d$ ならば $B$ の $v_i$ に対する固有値は $\beta$ である。各 $i>d$ について $\lvert(\lambda_i-\sigma)^{-1}\rvert/\lvert\beta\rvert=\lvert\lambda-\sigma\rvert/\lvert\lambda_i-\sigma\rvert<1$ であるから、 $B$ 、 $\beta$ は定理 1.4の仮定を満たし、同定理の $q$ は、 $d<n$ ならば $\max_{i>d}\lvert\lambda-\sigma\rvert/\lvert\lambda_i-\sigma\rvert$ 、 $d=n$ ならば $0$ であって、本系の $q$ に一致する。また $\lvert\beta\rvert^k/\beta^k=\theta_k$ である。定義 3.1により $(y_k)$ は $B$ に対する $y_0$ からのべき乗法であるから、定理 1.4 (2)を $B$ に適用して第一の不等式を得る。 $A\hat u=\lambda\hat u$ であるから、補題 1.2を $A$ 、 $z=y_k$ 、 $\theta=\theta_k$ に適用して第二の不等式を得る。▨

例 3.4. 固有値が $1$ 、 $0.99$ 、 $0.5$ である対角化可能な $3$ 次の行列 $A$ を考える。べき乗法について定理 1.4の $q$ は $0.99$ であり、評価の因子 $q^k$ が $10^{-8}$ 以下になる最小の $k$ は $1833$ である。シフト $\sigma:=1.001$ の逆反復について系 3.3の $q$ は $0.001/\min\{0.011,0.501\}=1/11$ であり、 $q^k\le10^{-8}$ となる最小の $k$ は $8$ である。

4 実対称行列の固有値の最小最大表示

補題 4.1. $n\in\NN$ とし、 $A\in\R^{n\times n}$ は $A^{\mathsf T}=A$ を満たすとする。 $S\subset\R^n$ を $S\ne\{0\}$ を満たす部分空間とすると、集合 $\{x^{\mathsf T}Ax\mid x\in S,\ \lVert x\rVert_2=1\}$ は最大値と最小値をもつ。

証明. $k:=\dim S$ とし、 $S$ の正規直交基底 $w_1,\dots,w_k$ を Gram–Schmidt の直交化でとり、 $W:=(w_1\ \cdots\ w_k)\in\R^{n\times k}$ と置く。 $W^{\mathsf T}W=I_k$ であるから、 $z\in\R^k$ について $\lVert Wz\rVert_2=\lVert z\rVert_2$ であり、 $\{x\in S\mid\lVert x\rVert_2=1\}=\{Wz\mid z\in\R^k,\ \lVert z\rVert_2=1\}$ である。 $B:=W^{\mathsf T}AW$ は $B^{\mathsf T}=B$ を満たし、 $(Wz)^{\mathsf T}A(Wz)=z^{\mathsf T}Bz$ である。補題 2.1 (3)を $B$ に適用して正規直交基底 $b_1,\dots,b_k$ と実数 $\beta_1\le\dots\le\beta_k$ をとると、補題 2.1 (1)により $\lVert z\rVert_2=1$ のとき $z^{\mathsf T}Bz=\sum_j\beta_j(b_j^{\mathsf T}z)^2\in[\beta_1,\beta_k]$ であり、 $z=b_1$ 、 $z=b_k$ でそれぞれ $\beta_1$ 、 $\beta_k$ に等しい。▨

定理 4.2 (Courant–Fischer の定理). $n\in\NN$ とし、 $A\in\R^{n\times n}$ は $A^{\mathsf T}=A$ を満たすとする。 $\lambda_1\le\dots\le\lambda_n$ を $\det(tI-A)=\prod_i(t-\lambda_i)$ を満たす実数とする（補題 2.1 (3)により存在する）。任意の整数 $1\le k\le n$ に対して

\lambda_k=\min_{\substack{S\subset\R^n\\\dim S=k}}\ \max_{\substack{x\in S\\\lVert x\rVert_2=1}}x^{\mathsf T}Ax=\max_{\substack{S\subset\R^n\\\dim S=n-k+1}}\ \min_{\substack{x\in S\\\lVert x\rVert_2=1}}x^{\mathsf T}Ax

が成り立つ。ここで $S$ は部分空間を動き、内側の最大値・最小値は補題 4.1により存在し、外側の最小値・最大値の存在も主張に含む。

証明.補題 2.1 (3)により、 $\R^n$ の正規直交基底 $q_1,\dots,q_n$ で $Aq_i=\lambda_iq_i$ を満たすものがとれる。 $\det(tI-A)$ の根を重複度を込めて非減少に並べた列は一つに定まるので、ここでの $\lambda_i$ は主張の $\lambda_i$ に一致する。 $x\in\R^n$ について $x^{\mathsf T}Ax=\sum_i\lambda_i(q_i^{\mathsf T}x)^2$ である（補題 2.1 (1)）。

$S$ を $\dim S=k$ を満たす部分空間とし、 $T:=\operatorname{span}\{q_k,\dots,q_n\}$ と置く。 $\dim(S\cap T)=\dim S+\dim T-\dim(S+T)\ge k+(n-k+1)-n=1$ であるから、 $\lVert x\rVert_2=1$ を満たす $x\in S\cap T$ がある。 $i<k$ について $q_i^{\mathsf T}x=0$ であるから $x^{\mathsf T}Ax=\sum_{i\ge k}\lambda_i(q_i^{\mathsf T}x)^2\ge\lambda_k\sum_{i\ge k}(q_i^{\mathsf T}x)^2=\lambda_k$ であり、 $S$ 上の最大値は $\lambda_k$ 以上である。 $S_0:=\operatorname{span}\{q_1,\dots,q_k\}$ の単位ベクトル $x$ については $x^{\mathsf T}Ax=\sum_{i\le k}\lambda_i(q_i^{\mathsf T}x)^2\le\lambda_k$ であり、 $x=q_k$ で等号が成り立つので、 $S_0$ 上の最大値は $\lambda_k$ である。したがって最小最大表示の外側の最小値は存在して $\lambda_k$ に等しい。

$-A$ は対称であり、 $\det(tI+A)=\prod_i(t+\lambda_i)$ であるから、 $-A$ について非減少に並べた列の第 $j$ 項は $-\lambda_{n+1-j}$ である。最小最大表示を $-A$ と $j:=n-k+1$ に適用すると

-\lambda_k=\min_{\dim S=n-k+1}\ \max_{x\in S,\ \lVert x\rVert_2=1}\bigl(-x^{\mathsf T}Ax\bigr)=-\max_{\dim S=n-k+1}\ \min_{x\in S,\ \lVert x\rVert_2=1}x^{\mathsf T}Ax

であり、最大最小表示を得る。▨

5 残差と固有値間隔

命題 5.1. $n\in\NN$ 、 $A\in\C^{n\times n}$ とし、 $v_1,\dots,v_n$ と実数 $\lambda_1,\dots,\lambda_n$ は補題 2.1の仮定を満たすとする。 $y\in\C^n$ を $\lVert y\rVert_2=1$ を満たすベクトル、 $\mu\in\C$ とし、 $r:=Ay-\mu y$ と置く。

$\min_i\lvert\lambda_i-\mu\rvert\le\lVert r\rVert_2$ が成り立つ。
$\lambda\in\{\lambda_1,\dots,\lambda_n\}$ とし、 $E:=\operatorname{span}\{v_i\mid\lambda_i=\lambda\}$ と置く。 $\lambda_i\ne\lambda$ を満たす $i$ が存在し、 $\gamma:=\min\{\lvert\lambda_i-\mu\rvert\mid\lambda_i\ne\lambda\}$ が $\gamma>0$ を満たすならば、 $\operatorname{dist}(y,E)\le\lVert r\rVert_2/\gamma$ が成り立つ。
(2)の仮定に加えて $\mu=y^*Ay$ であるとし、 $\delta:=\max_i\lvert\lambda_i-\lambda\rvert$ と置くと、 $\lvert\mu-\lambda\rvert\le\delta\lVert r\rVert_2^2/\gamma^2$ が成り立つ。

証明. $c_i:=v_i^*y$ と置く。補題 2.1 (1)により $\sum_i\lvert c_i\rvert^2=1$ 、 $\lVert r\rVert_2^2=\sum_i\lvert\lambda_i-\mu\rvert^2\lvert c_i\rvert^2$ である。

(1)を示す。 $m:=\min_i\lvert\lambda_i-\mu\rvert$ と置くと $\lVert r\rVert_2^2\ge m^2\sum_i\lvert c_i\rvert^2=m^2$ である。

(2)を示す。 $\lVert r\rVert_2^2\ge\sum_{\lambda_i\ne\lambda}\lvert\lambda_i-\mu\rvert^2\lvert c_i\rvert^2\ge\gamma^2\sum_{\lambda_i\ne\lambda}\lvert c_i\rvert^2$ であり、補題 2.1 (2)を $J=\{i\mid\lambda_i=\lambda\}$ に適用すると右辺は $\gamma^2\operatorname{dist}(y,E)^2$ である。

(3)を示す。番号を付け替えて命題 2.2 (1)を適用すると $\lvert\mu-\lambda\rvert\le\delta\operatorname{dist}(y,E)^2$ であり、(2)により $\operatorname{dist}(y,E)^2\le\lVert r\rVert_2^2/\gamma^2$ である。▨

注意 5.2.命題 5.1の記号で $\Delta A:=-ry^*$ と置くと、 $(A+\Delta A)y=Ay-r=\mu y$ であり、 $\mu$ と $y$ は $A+\Delta A$ の固有値と固有ベクトルである。任意の $h\in\C^n$ に対して $\lVert ry^*h\rVert_2=\lvert y^*h\rvert\lVert r\rVert_2\le\lVert r\rVert_2\lVert h\rVert_2$ であり、 $h=y$ で等号が成り立つので $\lVert\Delta A\rVert_2=\lVert r\rVert_2$ である。命題 5.1の仮定の下で反復を $\lVert r\rVert_2\le\tau$ で止めるならば、命題 5.1 (1)により $\mu$ から距離 $\tau$ 以内に $A$ の固有値があり、命題 5.1 (2)により $\operatorname{dist}(y,E)\le\tau/\gamma$ である。

例 5.3. $M>0$ とし、

A:=\begin{pmatrix}0&0&0\\0&1&M\\0&0&2\end{pmatrix},\qquad y:=\frac{(1,M,-1)^{\mathsf T}}{\sqrt{M^2+2}},\qquad\mu:=0

と置く。 $A$ の固有値は $0,1,2$ であり、固有空間はそれぞれ $\operatorname{span}\{e_1\}$ 、 $\operatorname{span}\{e_2\}$ 、 $\operatorname{span}\{(0,M,1)^{\mathsf T}\}$ である。 $A$ は対角化可能であるが、各固有空間は一次元であり $e_2^*(0,M,1)^{\mathsf T}=M\ne0$ であるから、固有ベクトルからなる正規直交基底は存在せず、命題 5.1の仮定を満たさない。 $A(1,M,-1)^{\mathsf T}=(0,0,-2)^{\mathsf T}$ であるから $r=Ay-\mu y$ は $\lVert r\rVert_2=2/\sqrt{M^2+2}$ を満たす。 $\lambda:=0$ 、 $E:=\operatorname{span}\{e_1\}$ について、 $\mu$ と他の固有値との間隔は $\gamma=\min\{1,2\}=1$ であり、

\operatorname{dist}(y,E)=\sqrt{\frac{M^2+1}{M^2+2}},\qquad\frac{\lVert r\rVert_2}{\gamma}=\frac2{\sqrt{M^2+2}}

である。 $M>\sqrt3$ ならば $\sqrt{M^2+1}>2$ であるから $\operatorname{dist}(y,E)>\lVert r\rVert_2/\gamma$ である。 $M=100$ では $\lVert r\rVert_2=0.019998\ldots$ 、 $\operatorname{dist}(y,E)=0.99995\ldots$ である。固有値 $1$ の固有空間については $\operatorname{dist}(y,\operatorname{span}\{e_2\})=\sqrt2/\sqrt{M^2+2}$ であり、 $M=100$ では $0.014140\ldots$ である。

6 Rayleigh 商反復

定義 6.1. $n\in\NN$ とし、 $A\in\R^{n\times n}$ は $A^{\mathsf T}=A$ を満たすとする。 $y_0\in\R^n$ を $\lVert y_0\rVert_2=1$ を満たすベクトルとする。 $k\ge0$ について $y_k$ が定まっているとき、 $\mu_k:=y_k^{\mathsf T}Ay_k$ 、 $r_k:=Ay_k-\mu_ky_k$ と置く。 $\det(A-\mu_kI)\ne0$ ならば、 $z_k\in\R^n$ を $(A-\mu_kI)z_k=y_k$ のただ一つの解とし、 $y_{k+1}:=z_k/\lVert z_k\rVert_2$ と置く。 $\det(A-\mu_kI)=0$ ならば $y_{k+1}$ を定めず、反復は第 $k$ 段で停止 (termination) するという。こうして定まる $(y_k)$ と $(\mu_k)$ を、 $y_0$ からの Rayleigh 商反復 (Rayleigh quotient iteration) という。

注意 6.2.定義 6.1の反復が第 $k$ 段で停止するとき、 $\mu_k$ は $A$ の固有値である。 $y_k$ が $A$ の固有ベクトルであることと $r_k=0$ であることは同値である。実際、 $Ay_k=\lambda'y_k$ ならば $\mu_k=\lambda'y_k^{\mathsf T}y_k=\lambda'$ であり、 $r_k=0$ ならば $Ay_k=\mu_ky_k$ である。停止しても $r_k=0$ とは限らない。 $A:=\operatorname{diag}(0,-1,1)$ 、 $y_0:=(2,1,1)^{\mathsf T}/\sqrt6$ では $\mu_0=(-1+1)/6=0$ であり、 $A$ は正則でないので反復は第 $0$ 段で停止するが、 $r_0=(0,-1,1)^{\mathsf T}/\sqrt6\ne0$ である。

定理 6.3. $n\ge2$ とし、 $A\in\R^{n\times n}$ は $A^{\mathsf T}=A$ を満たすとする。 $\lambda$ を $\det(tI-A)$ の単根である $A$ の固有値、 $v\in\R^n$ を $Av=\lambda v$ 、 $\lVert v\rVert_2=1$ を満たすベクトルとする。 $\Lambda$ を $A$ の固有値の集合とし、 $g:=\min\{\lvert\lambda'-\lambda\rvert\mid\lambda'\in\Lambda,\ \lambda'\ne\lambda\}$ 、 $\delta:=\max\{\lvert\lambda'-\lambda\rvert\mid\lambda'\in\Lambda\}$ と置く。 $\lVert y\rVert_2=1$ かつ $v^{\mathsf T}y\ne0$ を満たす $y\in\R^n$ に対して

t(y):=\frac{\operatorname{dist}(y,\operatorname{span}\{v\})}{\lvert v^{\mathsf T}y\rvert}

と置く。 $y_0\in\R^n$ は $\lVert y_0\rVert_2=1$ 、 $v^{\mathsf T}y_0\ne0$ 、 $\delta t(y_0)^2\le g/2$ を満たすとし、 $(y_k)$ 、 $(\mu_k)$ を $y_0$ からの Rayleigh 商反復とする。 $y_k$ が定まる任意の $k\ge0$ について次が成り立つ。

$v^{\mathsf T}y_k\ne0$ 、 $\delta t(y_k)^2\le g/2$ であり、 $\lvert\mu_k-\lambda\rvert\le\delta\operatorname{dist}(y_k,\operatorname{span}\{v\})^2$ である。
反復が第 $k$ 段で停止するならば、 $\mu_k=\lambda$ である。
反復が第 $k$ 段で停止しないならば、 $v^{\mathsf T}y_{k+1}\ne0$ であり $t(y_{k+1})\le\frac{\delta\,t(y_k)^3}{g-\delta t(y_k)^2}\le\frac{2\delta}{g}t(y_k)^3$ が成り立つ。
反復が第 $k$ 段で停止しないならば、 $\operatorname{dist}(y_{k+1},\operatorname{span}\{v\})\le(4\sqrt2\,\delta/g)\operatorname{dist}(y_k,\operatorname{span}\{v\})^3$ が成り立つ。
$e_k:=(2\delta/g)t(y_k)^2$ と置くと $e_k\le e_0^{3^k}$ である。とくに $\delta t(y_0)^2<g/2$ であり、反復がどの段でも停止しないならば、 $t(y_k)\to0$ 、 $\mu_k\to\lambda$ である。

証明.補題 2.1 (3)により $\R^n$ の正規直交基底 $q_1,\dots,q_n$ と実数 $\lambda_1,\dots,\lambda_n$ で $Aq_i=\lambda_iq_i$ 、 $\det(tI-A)=\prod_i(t-\lambda_i)$ を満たすものをとる。 $\lambda$ は単根であるから $\lambda_i=\lambda$ を満たす $i$ はただ一つであり、番号を付け替えてそれを $i=1$ とする。補題 2.1 (1)により $\ker(A-\lambda I)=\operatorname{span}\{q_1\}$ であるから $q_1=\pm v$ であり、 $q_1$ を $v$ に置き換える。 $i\ge2$ について $\lambda_i\ne\lambda$ であり、 $g\le\lvert\lambda_i-\lambda\rvert\le\delta$ である。 $\lVert y\rVert_2=1$ を満たす $y\in\R^n$ について $c_i(y):=q_i^{\mathsf T}y$ と置く。補題 2.1 (2)を $J=\{1\}$ に適用すると $s(y):=\operatorname{dist}(y,\operatorname{span}\{v\})$ は $s(y)^2=\sum_{i\ge2}c_i(y)^2=1-c_1(y)^2$ を満たし、 $c_1(y)\ne0$ ならば $t(y)^2=\sum_{i\ge2}c_i(y)^2/c_1(y)^2$ 、 $s(y)\le t(y)$ である。 $z\in\R^n$ が $q_1^{\mathsf T}z\ne0$ を満たすならば、 $t(z/\lVert z\rVert_2)^2=\sum_{i\ge2}(q_i^{\mathsf T}z)^2/(q_1^{\mathsf T}z)^2$ である。

$y_k$ が定まり $v^{\mathsf T}y_k\ne0$ かつ $\delta t(y_k)^2\le g/2$ であるという条件を $(\mathrm H_k)$ と書く。 $(\mathrm H_0)$ は仮定である。 $(\mathrm H_k)$ を仮定し、 $c_i:=c_i(y_k)$ 、 $s_k:=s(y_k)$ 、 $t_k:=t(y_k)$ と置く。

命題 2.2 (1)を $d=1$ 、 $E=\operatorname{span}\{v\}$ に適用すると $\lvert\mu_k-\lambda\rvert\le\delta s_k^2\le\delta t_k^2\le g/2$ であり、(1)が成り立つ。 $i\ge2$ について

\lvert\lambda_i-\mu_k\rvert\ge\lvert\lambda_i-\lambda\rvert-\lvert\lambda-\mu_k\rvert\ge g-\delta t_k^2\ge g/2>0

である。反復が第 $k$ 段で停止するならば $\mu_k$ は $\lambda_1,\dots,\lambda_n$ のいずれかに等しく、上の不等式により $i\ge2$ の $\lambda_i$ には等しくないので、 $\mu_k=\lambda_1=\lambda$ であり、(2)が成り立つ。

反復が第 $k$ 段で停止しないとする。 $\mu_k\ne\lambda_i$ （ $1\le i\le n$ ）であり、 $(A-\mu_kI)^{-1}q_i=(\lambda_i-\mu_k)^{-1}q_i$ であるから $z_k=\sum_ic_i(\lambda_i-\mu_k)^{-1}q_i$ である。 $q_1^{\mathsf T}z_k=c_1/(\lambda-\mu_k)\ne0$ であるから $v^{\mathsf T}y_{k+1}\ne0$ であり、

t_{k+1}^2=\frac{\sum_{i\ge2}c_i^2(\lambda_i-\mu_k)^{-2}}{c_1^2(\lambda-\mu_k)^{-2}}\le\frac{(\lambda-\mu_k)^2}{(g-\delta t_k^2)^2}\cdot\frac{\sum_{i\ge2}c_i^2}{c_1^2}=\frac{(\lambda-\mu_k)^2}{(g-\delta t_k^2)^2}t_k^2

である。 $\lvert\lambda-\mu_k\rvert\le\delta t_k^2$ と $g-\delta t_k^2\ge g/2$ により(3)が成り立つ。 $(2\delta/g)t_k^2\le1$ であるから $t_{k+1}\le t_k$ であり、 $\delta t_{k+1}^2\le g/2$ であるから $(\mathrm H_{k+1})$ が成り立つ。 $\delta\ge g$ であるから $t_k^2\le g/(2\delta)\le1/2$ であり、 $s_k^2=t_k^2/(1+t_k^2)$ から $t_k^2=s_k^2/(1-s_k^2)\le2s_k^2$ である。 $s_{k+1}\le t_{k+1}\le(2\delta/g)t_k^3\le(2\delta/g)2\sqrt2\,s_k^3$ であり、(4)が成り立つ。 $k$ に関する帰納法により、 $y_k$ が定まる任意の $k$ について $(\mathrm H_k)$ と(1)から(4)が成り立つ。

(5)を示す。(3)により $e_{k+1}=(2\delta/g)t_{k+1}^2\le(2\delta/g)^3t_k^6=e_k^3$ であり、 $k$ に関する帰納法で $e_k\le e_0^{3^k}$ である。 $\delta t_0^2<g/2$ ならば $0\le e_0<1$ であるから $e_k\to0$ 、 $t_k\to0$ であり、(1)と $s_k\le t_k$ により $\lvert\mu_k-\lambda\rvert\le\delta t_k^2\to0$ である。▨

7 正の確率行列への適用

例 7.1. $n\in\NN$ とし、 $Q=(q_{ij})\in\R^{n\times n}$ を確率行列（成分が非負で、各列の成分の和が $1$ である行列）、 $0<\varepsilon\le1$ 、 $\mathbf 1:=(1,\dots,1)^{\mathsf T}\in\R^n$ とし、 $P:=(1-\varepsilon)Q+(\varepsilon/n)\mathbf 1\mathbf 1^{\mathsf T}$ と置く。 $\Delta:=\{x\in\R^n\mid x\ge0,\ \sum_ix_i=1\}$ とする。 $P$ の各成分は $(1-\varepsilon)q_{ij}+\varepsilon/n\ge\varepsilon/n>0$ であり、第 $j$ 列の和は $(1-\varepsilon)+\varepsilon=1$ であるから、 $P$ は成分がすべて正の確率行列である。§D3.19 定理 3.2により $P$ の定常分布 $\pi\in\Delta$ がただ一つ存在する。 $\delta_P:=\min_{i,j}(P)_{ij}\ge\varepsilon/n$ であるから $1-n\delta_P\le1-\varepsilon$ であり、§D3.19 定理 4.2により、任意の $p\in\Delta$ と $k\ge0$ について

\lVert P^kp-\pi\rVert_1\le(1-\varepsilon)^k\lVert p-\pi\rVert_1\le2(1-\varepsilon)^k

である。 $x\in\Delta$ ならば $Px\ge0$ 、 $\sum_i(Px)_i=\sum_jx_j=1$ であるから $P^kp\in\Delta$ 、 $P^kp\ne0$ である。 $P$ に対する $y_0:=p/\lVert p\rVert_2$ からのべき乗法について、 $y_k=P^kp/\lVert P^kp\rVert_2$ ならば $Py_k=P^{k+1}p/\lVert P^kp\rVert_2\ne0$ 、 $y_{k+1}=P^{k+1}p/\lVert P^{k+1}p\rVert_2$ であるから、すべての $k$ について $y_k=P^kp/\lVert P^kp\rVert_2$ である。補題 1.3と $\lVert\pi\rVert_2\ge\lVert\pi\rVert_1/\sqrt n=1/\sqrt n$ 、 $\lVert\cdot\rVert_2\le\lVert\cdot\rVert_1$ により

\left\lVert y_k-\frac{\pi}{\lVert\pi\rVert_2}\right\rVert_2\le\frac{2\lVert P^kp-\pi\rVert_2}{\lVert\pi\rVert_2}\le4\sqrt n\,(1-\varepsilon)^k

である。 $P$ は対角化可能とは限らず、そのとき定理 1.4の仮定は満たされない。 $n=3$ 、 $Q:=\begin{pmatrix}0&0&0\\1&0&0\\0&1&1\end{pmatrix}$ 、 $0<\varepsilon<1$ 、 $w:=e_1-e_2$ とすると、 $\mathbf 1^{\mathsf T}w=0$ 、 $\mathbf 1^{\mathsf T}(e_2-e_3)=0$ から $Pw=(1-\varepsilon)(e_2-e_3)\ne0$ 、 $P^2w=(1-\varepsilon)^2(e_3-e_3)=0$ である。 $P=VDV^{-1}$ （ $D$ は対角行列）ならば、 $P^2x=0$ から $D^2V^{-1}x=0$ 、 $DV^{-1}x=0$ 、 $Px=0$ が従うので、 $P$ は対角化可能でない。

8 演習

問題 8.1.補題 1.3の証明を完成させよ。

解答.

$\left\lVert\frac{a}{\lVert a\rVert_2}-\frac{b}{\lVert b\rVert_2}\right\rVert_2\le\left\lVert\frac{a}{\lVert a\rVert_2}-\frac{a}{\lVert b\rVert_2}\right\rVert_2+\left\lVert\frac{a}{\lVert b\rVert_2}-\frac{b}{\lVert b\rVert_2}\right\rVert_2$ である。右辺の第一項は $\lVert a\rVert_2\bigl\lvert\lVert a\rVert_2^{-1}-\lVert b\rVert_2^{-1}\bigr\rvert=\bigl\lvert\lVert b\rVert_2-\lVert a\rVert_2\bigr\rvert/\lVert b\rVert_2$ に等しく、三角不等式により $\bigl\lvert\lVert b\rVert_2-\lVert a\rVert_2\bigr\rvert\le\lVert a-b\rVert_2$ であるから $\lVert a-b\rVert_2/\lVert b\rVert_2$ 以下である。第二項は $\lVert a-b\rVert_2/\lVert b\rVert_2$ に等しい。二つを加えて主張の不等式を得る。▨

問題 8.2. $A:=\operatorname{diag}(0,1)\in\R^{2\times2}$ 、 $t>0$ 、 $y_0:=(1,t)^{\mathsf T}/\sqrt{1+t^2}$ とし、 $(y_k)$ 、 $(\mu_k)$ を $y_0$ からの Rayleigh 商反復（定義 6.1）とする。反復が第 $0$ 段で停止せず $y_1=(-1,t^3)^{\mathsf T}/\sqrt{1+t^6}$ であること、したがって第 $2$ 成分と第 $1$ 成分の比が $t$ から $-t^3$ に移ることを示せ。さらに $\operatorname{dist}(y_1,\operatorname{span}\{e_1\})\le2\operatorname{dist}(y_0,\operatorname{span}\{e_1\})^3$ と $\lVert y_1-e_1\rVert_2>\sqrt2>\lVert y_0-e_1\rVert_2$ を示せ。

解答.

$\mu_0=y_0^{\mathsf T}Ay_0=t^2/(1+t^2)$ であり、 $A-\mu_0I=\operatorname{diag}\bigl(-t^2/(1+t^2),\,1/(1+t^2)\bigr)$ の対角成分は $t>0$ によりどちらも $0$ でないから、 $\det(A-\mu_0I)\ne0$ であり、反復は第 $0$ 段で停止しない。 $(A-\mu_0I)z_0=y_0$ の解は

z_0=\left(-\frac{1+t^2}{t^2}\cdot\frac1{\sqrt{1+t^2}},\ (1+t^2)\cdot\frac t{\sqrt{1+t^2}}\right)^{\mathsf T}=\frac{\sqrt{1+t^2}}{t^2}\,(-1,t^3)^{\mathsf T}

であり、 $\sqrt{1+t^2}/t^2>0$ であるから $y_1=z_0/\lVert z_0\rVert_2=(-1,t^3)^{\mathsf T}/\sqrt{1+t^6}$ である。 $y_0$ の成分の比は $t$ 、 $y_1$ の成分の比は $t^3/(-1)=-t^3$ である。 $e_1,e_2$ は $A$ の固有ベクトルからなる正規直交基底であるから、補題 2.1 (2)を $J=\{1\}$ に適用すると、 $\lVert y\rVert_2=1$ を満たす $y\in\R^2$ について $\operatorname{dist}(y,\operatorname{span}\{e_1\})=\lvert e_2^{\mathsf T}y\rvert$ である。よって $\operatorname{dist}(y_0,\operatorname{span}\{e_1\})=t/\sqrt{1+t^2}$ 、 $\operatorname{dist}(y_1,\operatorname{span}\{e_1\})=t^3/\sqrt{1+t^6}$ であり、

\frac{\operatorname{dist}(y_1,\operatorname{span}\{e_1\})^2}{\operatorname{dist}(y_0,\operatorname{span}\{e_1\})^6}=\frac{(1+t^2)^3}{1+t^6}

である。 $x:=t^2$ と置くと $4(1+x^3)-(1+x)^3=3(1-x)^2(1+x)\ge0$ であるから右辺は $4$ 以下であり、 $\operatorname{dist}(y_1,\operatorname{span}\{e_1\})\le2\operatorname{dist}(y_0,\operatorname{span}\{e_1\})^3$ を得る。 $\lVert y\rVert_2=1$ を満たす $y$ について $\lVert y-e_1\rVert_2^2=2-2e_1^{\mathsf T}y$ であるから、 $\lVert y_1-e_1\rVert_2^2=2+2/\sqrt{1+t^6}>2$ 、 $\lVert y_0-e_1\rVert_2^2=2-2/\sqrt{1+t^2}<2$ であり、 $\lVert y_1-e_1\rVert_2>\sqrt2>\lVert y_0-e_1\rVert_2$ である。定理 6.3の記号では $\lambda=0$ 、 $v=e_1$ 、 $g=\delta=1$ 、 $t(y_0)=t$ であり、仮定 $\delta t(y_0)^2\le g/2$ は $t\le1/\sqrt2$ と同値である。▨

§E20.7固有値の反復解法

1 べき乗法

2 正規直交な固有基底をもつ行列

3 逆反復

4 実対称行列の固有値の最小最大表示

5 残差と固有値間隔

6 Rayleigh 商反復

7 正の確率行列への適用

8 演習

前提記事