Arnoldi法(Arnoldi method)とは、正方行列 $A$ と単位ベクトル $v_1$ から Krylov 部分空間の正規直交基底を Gram–Schmidt の直交化で作り、$A$ をそこへ圧縮した上 Hessenberg 行列 $H_k$ の固有値(Ritz 値)で $A$ の固有値を近似する方法である。Hermite 性を仮定せず、行列とベクトルの積だけで大きな疎行列の少数の固有値を求められる。Ritz 対の残差は $H_k$ の固有ベクトルの最後の成分から分かり、分解は初期ベクトルだけで決まる(暗黙の $Q$ の定理)。段数を固定して $H_k$ の上でシフト付き QR を行う暗黙の再出発は、初期ベクトルに多項式を掛けてやり直すことと同じである。
前提知識: Krylov部分空間法, Gram–Schmidtの直交化, 固有値, QR分解, Schurの三角化定理
Arnoldi法(Arnoldi method)とは、正方行列 $A$ と単位ベクトル $v_1$ から、Krylov 部分空間 $\mathcal K_k(A,v_1)=\operatorname{span}\{v_1,Av_1,\dots,A^{k-1}v_1\}$ の正規直交基底 $v_1,\dots,v_k$ を Gram–Schmidt の直交化で 1 本ずつ作り、$A$ をこの部分空間へ圧縮した上 Hessenberg 行列 $H_k$ の固有値で $A$ の固有値を近似する方法である。基底を並べた行列 $V_k$ について $AV_k=V_kH_k+h_{k+1,k}v_{k+1}e_k^{\mathsf T}$ が成り立つ。
Markov 連鎖の推移行列、流体の線形安定性の解析、回路のモデルなどから出る大きな疎行列は、一般に Hermite 行列ではない。必要なのは、絶対値の大きい固有値や、実部が最も大きい固有値(安定性を決めるもの)など、少数の固有値である。Hermite 行列なら Lanczos法 の 3 項の漸化式が使えるが、一般の行列ではそれが基底の直交性を保たない。そこで、新しいベクトルをそれまでのすべての基底に対して直交化する。これが Arnoldi の手順である。
手順の定義と、関係式 $AV_k=V_{k+1}\overline H_k$ が成り立つことの証明は Krylov部分空間法 にあり、そこでは連立 1 次方程式の解法(GMRES)に使った。この記事は同じ手順を 固有値の計算 に使う側を扱う。Ritz 対の残差の公式、分解が初期ベクトルだけで決まること(暗黙の $Q$ の定理)、そして記憶を一定に保つための 暗黙の再出発 が、初期ベクトルに多項式を掛けることと同じであることを証明する。
以下、$\mathbb K$ は $\mathbb R$ または $\mathbb C$、$\langle x,y\rangle:=y^*x$、$\|x\|:=\langle x,x\rangle^{1/2}$、$A\in M_n(\mathbb K)$ とし、$d=d(A,v_1)$ を $v_1$ の $A$ に関する次数とする(Krylov部分空間法 の定義「Krylov 部分空間と次数」)。$e_j$ は標準基底のベクトルで、長さは文脈で決める。
$\|v_1\|=1$ とする。$j=1,2,\dots$ について、$w\leftarrow Av_j$ とし、$i=1,\dots,j$ の順に
$$
h_{ij}:=\langle w,v_i\rangle,\qquad w\leftarrow w-h_{ij}v_i
$$
と更新する。$h_{j+1,j}:=\|w\|$ とし、$0$ なら止まる。そうでなければ $v_{j+1}:=w/h_{j+1,j}$ とする。$k$ 段までの $V_k:=(v_1,\dots,v_k)$、$h_{ij}$ を並べた $k$ 次の上 Hessenberg 行列 $H_k$($i>j+1$ の成分は $0$)を作る。
$i$ 番目の内積を取る時点の $w$ は、$Av_j$ から $v_1,\dots,v_{i-1}$ の方向を除いたものなので、丸めのない計算では $h_{ij}=\langle Av_j,v_i\rangle$ であり、Krylov部分空間法 の定義「Arnoldi の手順」と同じ値を与える。同記事の定理「Arnoldi の関係式」により、手順はちょうど $j=d$ で止まり、$1\le k\le d$ で $v_1,\dots,v_k$ は $\mathcal K_k(A,v_1)$ の正規直交基底で、$k< d$ で
$$
AV_k=V_kH_k+h_{k+1,k}v_{k+1}e_k^{\mathsf T},\qquad V_k^*AV_k=H_k
$$
である。この形を抽象化しておく。
$k\ge1$ とする。列が正規直交な $V\in\mathbb K^{n\times k}$、$k$ 次の上 Hessenberg 行列 $H$、$V^*f=0$ を満たす $f\in\mathbb K^n$ の組で
$$
AV=VH+fe_k^{\mathsf T}
$$
を満たすものを、長さ $k$ の Arnoldi 分解 という。$H$ の副対角成分 $h_{j+1,j}$($1\le j< k$)がすべて $0$ でないとき、$H$ は 非簡約 であるという。
左から $V^*$ を掛けると $H=V^*AV$ である。Arnoldi の手順の $k< d$ 段目までの出力は、$f=h_{k+1,k}v_{k+1}$ とした長さ $k$ の Arnoldi 分解で、$H_k$ の副対角成分は正である。
Arnoldi 分解 $AV=VH+fe_k^{\mathsf T}$ について、$Hs=\theta s$、$\|s\|=1$ のとき、$\theta$ を Ritz 値、$y:=Vs$ を Ritz ベクトル という。
使える条件。
$AV=VH+fe_k^{\mathsf T}$ を長さ $k$ の Arnoldi 分解、$(\theta,s)$ を $H$ の固有対($\|s\|=1$)、$y=Vs$ とする。
| 公式 | 使える条件 | 根拠 |
|---|---|---|
| $AV_k=V_kH_k+h_{k+1,k}v_{k+1}e_k^{\mathsf T}$、$V_k^*AV_k=H_k$ | 手順の出力、$k< d$ | Krylov部分空間法 |
| $Ay-\theta y=(e_k^{\mathsf T}s)f$、$\Vert Ay-\theta y\Vert=\lvert e_k^{\mathsf T}s\rvert\,\Vert f\Vert$ | なし | prop-arn-ritz |
| $\theta=\langle Ay,y\rangle$ は $A$ の数域に入る | なし | prop-arn-ritz |
| $\theta$ は $A$ の固有値の凸包に入り、$\min_i\lvert\lambda_i-\theta\rvert\le\Vert Ay-\theta y\Vert$ | $A$ が正規行列 | prop-arn-ritz |
| $f=0$ なら $H$ の固有値はすべて $A$ の固有値 | なし | prop-arn-ritz |
| $Ve_1=V'e_1$ なら $V'=VD$、$H'=D^*HD$($D$ は対角ユニタリ) | $H$ が非簡約 | thm-arn-unique |
| 再出発後の分解の先頭の列 $\propto\psi(A)v_1$、$\psi(t)=\prod_{j=1}^p(t-\mu_j)$ | $H_m$ が非簡約、$p< m$ | thm-arn-restart |
$AV=VH+fe_k^{\mathsf T}$ を長さ $k$ の Arnoldi 分解、$Hs=\theta s$、$\|s\|=1$、$y=Vs$ とする。
1:$V$ の列は正規直交なので $\|y\|=1$、$\langle Ay,y\rangle=s^*V^*AVs=s^*Hs=\theta$ である($V^*f=0$ を使った)。分解に右から $s$ を掛けると $Ay=VHs+(e_k^{\mathsf T}s)f=\theta y+(e_k^{\mathsf T}s)f$ である。
2:$A=U\Lambda U^*$($U$ ユニタリ、$\Lambda=\operatorname{diag}(\lambda_1,\dots,\lambda_n)$)と書き、$c:=U^*y$ とおくと $\sum_i\lvert c_i\rvert^2=1$ である。$\theta=\langle Ay,y\rangle=\sum_i\lambda_i\lvert c_i\rvert^2$ は固有値の凸結合である。また $\|Ay-\theta y\|^2=\sum_i\lvert\lambda_i-\theta\rvert^2\lvert c_i\rvert^2\ge\min_i\lvert\lambda_i-\theta\rvert^2$ である。
3:$f=0$ なら $AV=VH$ で列の張る空間 $\mathcal V$ は不変である。逆に $\mathcal V$ が不変なら $f=AVe_k-VHe_k\in\mathcal V$ で、$V^*f=0$ から $f=0$ である。$f=0$ で $Hs=\theta s$ なら $Ay=\theta y$、$y\ne0$ である。$\square$
(1 は Saa11 Proposition 6.8(pp. 130–131)、3 は同書 Proposition 6.7(pp. 129–130)、正規行列の数域が固有値の凸包であることは同書 Theorem 1.6(p. 22)。)1 により、Ritz ベクトルを作らずに $s$ の最後の成分だけで残差が分かる。手順の出力では $\|f\|=h_{k+1,k}$ である。
一般の行列では Ritz 値は $A$ の 数域 $\{\langle Ax,x\rangle\mid\|x\|=1\}$ に入るだけで、固有値の凸包の外に出ることがあり、残差が小さくても固有値が遠いことがある(反例の表)。
$AV=VH+fe_k^{\mathsf T}$ と $AV'=V'H'+f'e_k^{\mathsf T}$ を長さ $k$ の Arnoldi 分解とし、$Ve_1=V'e_1$、$H$ は非簡約とする。
$V=(v_1,\dots,v_k)$、$V'=(v_1',\dots,v_k')$ と書く。$j< k$ で $e_k^{\mathsf T}e_j=0$ なので、分解の第 $j$ 列は
$$
Av_j=\sum_{i=1}^{j+1}h_{ij}v_i,\qquad Av_j'=\sum_{i=1}^{j+1}h_{ij}'v_i'\qquad(1\le j< k)
$$
である。$V'$ の列は正規直交なので $h'_{ij}=\langle Av'_j,v'_i\rangle$($i\le j+1$)である。
1:$j$ についての帰納法で、$\lvert\delta_i\rvert=1$ の数があって $v'_i=\delta_iv_i$($i\le j$)となることを示す。$j=1$ は $\delta_1=1$ でよい。$j< k$ で成り立つとする。$i\le j$ について $h'_{ij}=\langle\delta_jAv_j,\delta_iv_i\rangle=\overline{\delta_i}\delta_jh_{ij}$ なので
$$
h'_{j+1,j}v'_{j+1}=Av'_j-\sum_{i=1}^jh'_{ij}v'_i=\delta_j\Bigl(Av_j-\sum_{i=1}^jh_{ij}v_i\Bigr)=\delta_jh_{j+1,j}v_{j+1}
$$
である。$H$ は非簡約なので右辺は $0$ でなく、$h'_{j+1,j}\ne0$ で $v'_{j+1}=\delta_{j+1}v_{j+1}$、$\delta_{j+1}:=\delta_jh_{j+1,j}/h'_{j+1,j}$ である。両辺が単位ベクトルなので $\lvert\delta_{j+1}\rvert=1$ である。これで $V'=VD$ が言えた。$V'^*f'=0$ から $H'=V'^*AV'=D^*V^*AVD=D^*HD$ である。$f'e_k^{\mathsf T}=AV'-V'H'=(AV-VH)D=fe_k^{\mathsf T}D=\delta_kfe_k^{\mathsf T}$ から $f'=\delta_kf$ である。$h'_{j+1,j}=\overline{\delta_{j+1}}\delta_jh_{j+1,j}\ne0$ なので $H'$ も非簡約である。
2:$h'_{j+1,j}=\overline{\delta_{j+1}}\delta_jh_{j+1,j}$ と $h_{j+1,j},h'_{j+1,j}>0$ から $\delta_{j+1}=\delta_j$ で、$\delta_1=1$ からすべて $1$ である。
3:$\mathcal V_j:=\operatorname{span}\{v_1,\dots,v_j\}$ とおく。$\mathcal V_j=\mathcal K_j(A,v_1)$ を $j$ についての帰納法で示す。$j=1$ は明らかである。$\mathcal V_j=\mathcal K_j$($j< k$)なら、上の第 $j$ 列の式と $h_{j+1,j}\ne0$ から $v_{j+1}\in\mathcal V_j+A\mathcal V_j\subset\mathcal K_{j+1}$ なので $\mathcal V_{j+1}\subset\mathcal K_{j+1}$ であり、$\dim\mathcal V_{j+1}=j+1\ge\dim\mathcal K_{j+1}$ から等しい。$\dim\mathcal K_k=k$ なので Krylov部分空間法 の命題「Krylov 部分空間の基本性質」の 2 により $k\le d$ である。副対角成分が正なら、$k< d$ のとき手順の出力(長さ $k$ の Arnoldi 分解で副対角成分が正)と 2 により一致する。$k=d$ のときも、手順の $d$ 段目までの出力は $f=0$ の Arnoldi 分解($AV_d=V_dH_d$)なので、同じく一致する。$\square$
$n\times n$ の場合($k=n$、$f=0$)が、固有値の計算で 暗黙の $Q$ の定理 と呼ばれるものである。
$Q,Q'$ をユニタリ行列、$H:=Q^*AQ$ と $H':=Q'^*AQ'$ を上 Hessenberg 行列とし、$H$ は非簡約、$Qe_1=Q'e_1$ とする。このとき対角ユニタリ行列 $D$ があって $Q'=QD$、$H'=D^*HD$ である。
$AQ=QH$、$AQ'=Q'H'$ は $f=f'=0$ の長さ $n$ の Arnoldi 分解である。thm-arn-unique の 1 を当てる。$\square$
(Saa11 p. 168 はこの定理を Hessenberg 行列の QR 法の実装に使うことを述べ、詳細を他書に譲っている。上の証明は列ごとの帰納法で書き下ろしたものである。)QR法(固有値) では、この系により、1 段のシフト付き QR を先頭の列だけ決めて回転を追いかける形で実行できる。
段数 $m$ を大きくすると記憶と手間が増えるので、$m$ を固定して分解を短く切り、初期ベクトルを取り替えてやり直す。望まない固有値の方向を初期ベクトルから弱めたいので、新しい初期ベクトルとして $\psi(A)v_1$($\psi$ は望まない固有値の近くで小さい多項式)を使うのが自然である。これを、$A$ を新たに掛けずに、$H_m$ の上の QR の反復だけで実行するのが暗黙の再出発である。
$m$ 次の上 Hessenberg 行列 $H$ と数 $\mu$ について、Givens 回転によるシフト付き QR の 1 段 とは、$H-\mu I$ に左から第 $(i,i+1)$ 行の Givens回転 $G_i$ を $i=1,\dots,m-1$ の順に掛けて上三角行列 $R=G_{m-1}\cdots G_1(H-\mu I)$ にし、$Q:=G_1^*\cdots G_{m-1}^*$、$H':=RQ+\mu I=Q^*HQ$ とおく操作である。$G_i^*$ は第 $i,i+1$ 列だけに働くので、$Q$ は上 Hessenberg 行列であり、$H'$ も上 Hessenberg 行列である(QR分解 の注意「QR 法」)。
$AV_m=V_mH_m+f_me_m^{\mathsf T}$ を長さ $m$ の Arnoldi 分解で $H_m$ が非簡約なものとし、$1\le p< m$、$\mu_1,\dots,\mu_p\in\mathbb K$ とする。$H^{(0)}:=H_m$ とし、$j=1,\dots,p$ について $H^{(j-1)}$ にシフト $\mu_j$ の Givens 回転による QR の 1 段を施して $H^{(j-1)}-\mu_jI=Q_jR_j$、$H^{(j)}:=Q_j^*H^{(j-1)}Q_j$ とする。$Q:=Q_1\cdots Q_p$、$H^+:=H^{(p)}=Q^*H_mQ$、$V^+:=V_mQ$、$k:=m-p$ とし、$V_k^+$ を $V^+$ の最初の $k$ 列、$H_k^+$ を $H^+$ の左上の $k$ 次の主小行列、$q_{mk}$ を $Q$ の第 $(m,k)$ 成分とする。
帯の幅。 行列 $M$ の第 $(i,l)$ 成分が $i>l+b$ で $0$ になるとき、$M$ の下の帯の幅は $b$ 以下であるという。上 Hessenberg 行列は幅 $1$ 以下で、幅 $b$ 以下と幅 $c$ 以下の行列の積は幅 $b+c$ 以下である($(MN)_{il}=\sum_rM_{ir}N_{rl}$ で、$i>r+b$ か $r>l+c$ の項は消え、$i>l+b+c$ ならどの $r$ でもどちらかが成り立つ)。よって $Q_1\cdots Q_j$ の幅は $j$ 以下である。
1:分解に右から $Q$ を掛けると $AV^+=V^+H^++f_me_m^{\mathsf T}Q$ である。$Q$ の幅は $p$ 以下なので、$l< m-p=k$ で $e_m^{\mathsf T}Qe_l=0$ であり、最初の $k$ 列では $e_m^{\mathsf T}Q$ は $q_{mk}e_k^{\mathsf T}$ になる。$H^+$ は上 Hessenberg 行列なので、その最初の $k$ 列は $H_k^+$ の下に第 $k+1$ 行 $h^+_{k+1,k}e_k^{\mathsf T}$ を足し、残りを $0$ にしたものである。したがって最初の $k$ 列を取ると
$$
AV_k^+=V_k^+H_k^++h^+_{k+1,k}V^+e_{k+1}e_k^{\mathsf T}+q_{mk}f_me_k^{\mathsf T}=V_k^+H_k^++f_k^+e_k^{\mathsf T}
$$
である。$Q$ はユニタリ行列なので $V^+$ の列は正規直交である。$V^+e_{k+1}$ は $V_k^+$ の列に直交し、$f_m$ は $V_m$ の列の張る空間に直交してそこに $V_k^+$ の列が入るので、$(V_k^+)^*f_k^+=0$ である。$H_k^+$ は上 Hessenberg 行列である。
2:$V^{(j)}:=V_mQ_1\cdots Q_j$($V^{(0)}=V_m$)とおくと、1 と同じ計算で $AV^{(j-1)}=V^{(j-1)}H^{(j-1)}+f_me_m^{\mathsf T}Q_1\cdots Q_{j-1}$ である。$\mu_jV^{(j-1)}$ を引き、$H^{(j-1)}-\mu_jI=Q_jR_j$ を使うと
$$
(A-\mu_jI)V^{(j-1)}=V^{(j)}R_j+f_me_m^{\mathsf T}Q_1\cdots Q_{j-1}
$$
である。右から $e_1$ を掛ける。$R_j$ は上三角なので $R_je_1=(R_j)_{11}e_1$ であり、$Q_1\cdots Q_{j-1}$ の幅は $j-1$ 以下で $m>j$ なので $e_m^{\mathsf T}Q_1\cdots Q_{j-1}e_1=0$ である。よって $(A-\mu_jI)V^{(j-1)}e_1=(R_j)_{11}V^{(j)}e_1$ であり、$j=1,\dots,p$ を順に合わせると $\psi(A)v_1=\tau V^+e_1$ である($A-\mu_jI$ どうしは可換)。$H_m$ は非簡約なので thm-arn-unique の 3 により $m\le d(A,v_1)$ であり、$\deg\psi=p< d$ だから $\psi(A)v_1\ne0$ である。$\|V^+e_1\|=1$ から残りが従う。
3:1 の分解の先頭の列は 2 により $\psi(A)v_1/\tau$ である。thm-arn-unique の 3 により列の張る空間は $\mathcal K_k(A,\psi(A)v_1)$ であり、同定理の 1 を、$\psi(A)v_1/\|\psi(A)v_1\|$ から始めた手順の出力の分解(先頭の列が $\tau/\lvert\tau\rvert$ 倍だけ違う。その分を $V_k^+$ に掛けて合わせる)と比べればよい。$\square$
(暗黙の再出発は Sorensen による(Sor92)。Saa11 §7.3(pp. 166–169)は $p=2$ の場合の計算と手順(Algorithm 7.3)を述べている。上の証明はその計算を一般の $p$ に広げ、帯の幅の議論で書き下ろしたものである。)
1 の分解から $p$ 段だけ Arnoldi の手順を続ければ($v_{k+1}:=f_k^+/\|f_k^+\|$ から)、再び長さ $m$ の分解になる。必要な行列とベクトルの積は $p$ 回だけで、$\psi(A)v_1$ から $m$ 段をやり直す場合($m$ 回)より少ない。$\mu_j$ に $H_m$ の望まない Ritz 値を選ぶ(厳密なシフト)と、$\psi$ はそれらの Ritz 値で $0$ になるので、対応する方向が初期ベクトルから弱まる。
暗黙の再出発つき Arnoldi 法の手順を書く。入力は $x\mapsto Ax$ を計算する手続き、初期ベクトル $v_1$(特別な情報がなければ乱数のベクトル)、求める固有値の個数 $k$ と選び方(絶対値の大きい順、実部の大きい順など)、段数 $m$($k$ の 2〜3 倍が目安)、許容誤差 $\varepsilon$ である。$p:=m-k$ とする。
手間。 1 回の再出発あたり、行列とベクトルの積が $p$ 回、直交化が $O(nm^2)$、$H_m$ の上の計算が $O(m^3)$ である。覚えるベクトルは $m+1$ 本で、再出発の回数によらない。
$A=\begin{pmatrix}1&1&1\\0&1&1\\0&0&1\end{pmatrix}$、$v_1=e_3$ に Arnoldi の手順を 2 段当て、Ritz 値と残差を求める。
使う公式:def-arn-procedure、prop-arn-ritz。
答え:$v_2=\frac1{\sqrt2}(1,1,0)^{\mathsf T}$、$H_2=\begin{pmatrix}1&0\\\sqrt2&\frac32\end{pmatrix}$、$h_{32}=\frac12$ である。Ritz 値は $1$ と $\frac32$ で、残差はそれぞれ $\frac{\sqrt2}3\approx0.471405$ と $\frac12$ である。$A$ の固有値は $1$ だけなので、$\theta=\frac32$ は固有値の凸包 $\{1\}$ の外にある。$\frac32=\langle Av_2,v_2\rangle$ は数域の点である。
$Av_1=(1,1,1)^{\mathsf T}$、$h_{11}=1$、$w=(1,1,0)^{\mathsf T}$、$h_{21}=\sqrt2$。$Av_2=\frac1{\sqrt2}(2,1,0)^{\mathsf T}$、$h_{12}=0$、$h_{22}=\frac32$、$w=\frac1{2\sqrt2}(1,-1,0)^{\mathsf T}$、$h_{32}=\frac12$。$H_2$ は下三角なので固有値は対角成分である。$\theta=\frac32$ の固有ベクトルは $s=e_2$ で残差は $h_{32}\cdot1$。$\theta=1$ では $\sqrt2s_1+\frac32s_2=s_2$ から $s=\frac13(1,-2\sqrt2)^{\mathsf T}$ で、残差は $\frac12\cdot\frac{2\sqrt2}3$ である。3 段目で $f=0$ になり($d=3$)、$H_3$ の固有値は $1,1,1$ である。
$n=100$、$A=\operatorname{diag}(1,2,\dots,100)+N$($N$ は $(i,i+1)$ 成分だけが $1$)とする。$A$ は正規行列ではなく、固有値は $1,\dots,100$ である。$v_1=\frac1{10}(1,\dots,1)^{\mathsf T}$ から再直交化つきで $m$ 段行い、実部が最大の Ritz 値 $\theta$ を見る。
使う公式:prop-arn-ritz の 1。
答え:
| $m$ | $10$ | $20$ | $30$ | $40$ | $50$ |
|---|---|---|---|---|---|
| $100-\theta$ | $4.523\times10^{-1}$ | $9.806\times10^{-3}$ | $1.602\times10^{-4}$ | $5.681\times10^{-7}$ | $1.785\times10^{-10}$ |
| 残差 $h_{m+1,m}\lvert e_m^{\mathsf T}s\rvert$ | $1.807$ | $1.128\times10^{-1}$ | $3.203\times10^{-3}$ | $5.107\times10^{-5}$ | $2.727\times10^{-7}$ |
残差の公式の値は $\|Ay-\theta y\|$ の直接の計算と一致する。正規行列でないので残差は誤差の上界を与えないが、この例では誤差と同じ速さで減る。
ex-arn-bidiag の $A$ と $v_1$ で、最大の 3 個の固有値 $100,99,98$ を、3 個の Ritz 対の残差がすべて $10^{-8}$ 以下になるまで求める。
使う公式:thm-arn-restart、節「計算の手順」。
答え:
| 方法 | $H_m$ を作った回数 | 行列とベクトルの積 | 覚えるベクトル |
|---|---|---|---|
| 再出発 $(m,k)=(10,3)$ | $35$ | $10+34\cdot7=248$ | $11$ |
| 再出発 $(m,k)=(20,3)$ | $12$ | $20+11\cdot17=207$ | $21$ |
| 再出発しない | $m=71$ で達する | $71$ | $72$ |
再出発すると積の回数は増えるが、記憶は $m+1$ 本で済み、直交化の手間 $O(nm^2)$ も小さい。どの場合も $100,99,98$ が得られる(図 1)。同じ計算で、thm-arn-restart の 2 の $\psi(A)v_1=\tau V^+e_1$ と、$Q$ の下の帯の幅が $p$ 以下であることも数値で確かめられる。
暗黙の再出発つき Arnoldi 法で、望む 3 個の Ritz 対の残差の最大値を再出発の回数に対して片対数で描いたもの
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $H$ が非簡約 | $A=I_3$、$V=I_3$、$V'=(e_1,e_3,e_2)$、$H=H'=I_3$、$f=f'=0$ | $Ve_1=V'e_1$ だが $V'\ne VD$。thm-arn-unique の一意性が成り立たない |
| $A$ が正規行列(凸包) | ex-arn-3x3 | Ritz 値 $\frac32$ が固有値の凸包 $\{1\}$ の外にある(prop-arn-ritz の 2) |
| $A$ が正規行列(距離) | $A=\begin{pmatrix}0&1\\\varepsilon&0\end{pmatrix}$、$\varepsilon=10^{-4}$、$v_1=e_1$、$k=1$ | $\theta=0$、残差 $10^{-4}$ だが、固有値 $\pm10^{-2}$ までの距離は残差の $100$ 倍(prop-arn-ritz の 2) |
非簡約:$V'$ の列は正規直交で、$AV'=V'=V'I_3$ なので $f'=0$ の長さ $3$ の Arnoldi 分解である。$H=I_3$ の副対角成分は $0$ で非簡約でない。$V'e_2=e_3$ は $Ve_2=e_2$ の定数倍でない。
距離:$\theta=\langle Ae_1,e_1\rangle=0$、$f=Ae_1-0\cdot e_1=(0,\varepsilon)^{\mathsf T}$ で残差は $\varepsilon$ である。固有多項式は $t^2-\varepsilon$ で固有値は $\pm\sqrt\varepsilon=\pm10^{-2}$ である。
| 誤り | 正しくは | なぜ |
|---|---|---|
| Ritz 値は固有値の凸包に入る | 一般の行列では数域に入るだけ | ex-arn-3x3 |
| 残差が小さければ Ritz 値は固有値に近い | 正規行列でなければ保証されない | 反例の表 |
| 再出発は新しい初期ベクトルでやり直すのと同じ手間 | 続きの積は $p$ 回で済み、$\psi(A)v_1$ から $m$ 段やり直す $m$ 回より少ない | thm-arn-restart |
| 望む Ritz 値もシフトにしてよい | $\psi$ がその値で $0$ になり、望む方向が初期ベクトルから弱まる | thm-arn-restart の 2 |
連立 1 次方程式との関係。 同じ分解の $\overline H_k$ を使って残差を最小にするのが GMRES である(Krylov部分空間法)。固有値問題と連立 1 次方程式は 1 つの手順を共有する。
シフトと逆変換。 $\sigma$ に近い固有値が欲しいときは、$(A-\sigma I)^{-1}$ に手順を当てる。その固有値は $1/(\lambda-\sigma)$ で、$\sigma$ に近い $\lambda$ ほど絶対値が大きくなる。1 段ごとに $A-\sigma I$ を係数とする連立 1 次方程式を解く(LU 分解を 1 度作っておく)。
歴史と実装。 手順は Arnoldi による(Arn51)。暗黙の再出発は 1990 年代初めに Sorensen が導入し(Sor92)、それに基づく ARPACK が Krylov 部分空間法による固有値計算の事実上の標準になっている(Saa11 p. 162、p. 191)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する