§E20.11共役勾配法

最終更新

行列の分裂による定常反復法は、実対称正定値の係数行列をもつ一次方程式に対しても、次元が大きくなると遅くなることがある。二階差分の三重対角行列AnA_nでは、0<θ<10<\theta<1とするとき、任意の初期誤差についてAnA_n-ノルムの誤差をθ\theta倍以下にするのに必要な反復数は、Jacobi 法でも Gauss–Seidel 法でも、n→∞n\to\inftyのとき(n+1)2(n+1)^2に比例して増える下界をもつ。

係数行列AAが実対称正定値であれば、∥v∥A:=(vTAv)1/2\lVert v\rVert_A:=(v^{\mathsf T}Av)^{1/2}はRn\R^nのノルムであり、解xxとの誤差をこのノルムで測ることができる。共役勾配法は、初期値x0x_0と初期残差r0=b−Ax0r_0=b-Ax_0に対して、r0,Ar0,…,Ak−1r0r_0,Ar_0,\dots,A^{k-1}r_0の張る Krylov 部分空間Kk\mathcal K_kを用い、x0+Kkx_0+\mathcal K_kの上で∥x−y∥A\lVert x-y\rVert_Aを最小にするただ一つの点をkk段目の反復xkx_kとする方法である。この最小化点は、残差と探索方向を一段ずつ更新する漸化式によって計算することができ、厳密算術では、この算法は中断せず、nn段以内で残差が00になって解に達する。

共役勾配法の誤差は、AAの最大固有値と最小固有値の比κ\kappaを通して評価される。κ>1\kappa>1ならば、kk段目の誤差のAA-ノルムは初期誤差のAA-ノルムの2((κ−1)/(κ+1))k2\bigl((\sqrt\kappa-1)/(\sqrt\kappa+1)\bigr)^k倍以下である。この上界は、厳密算術での停止段より少ない段数で誤差を保証することがある。n=999n=999とし、11と100100を両端として等間隔に並ぶ相異なる999999個の数を対角成分とする対角行列をA′A'、成分がすべて00でないベクトルをbb、x0:=0x_0:=0とすると、A′A'の系の停止段は999999であるが、κ=100\kappa=100であるから上界は2(9/11)k2(9/11)^k倍であり、相対A′A'-ノルム誤差∥x−xk∥A′/∥x−x0∥A′\lVert x-x_k\rVert_{A'}/\lVert x-x_0\rVert_{A'}が10−610^{-6}以下であることを7373段で保証する。本記事では、共役勾配法を構成し、その基本的な性質と、厳密算術での誤差の評価および有限精度での残差と停止の判定について解説する。

1 エネルギー最小化と Krylov 部分空間

補題 1.1.n∈N≥1n\in\NNとし、A∈Rn×nA\in\R^{n\times n}を実対称正定値行列、b∈Rnb\in\R^n、x:=A−1bx:=A^{-1}bとする。u,v∈Rnu,v\in\R^nに対して⟨u,v⟩A:=uTAv\langle u,v\rangle_A:=u^{\mathsf T}Av、∥v∥A:=⟨v,v⟩A1/2\lVert v\rVert_A:=\langle v,v\rangle_A^{1/2}と置く。WWをRn\R^nの部分空間とし、x0∈Rnx_0\in\R^nとする。

  1. ⟨⋅,⋅⟩A\langle\cdot,\cdot\rangle_AはRn\R^nの内積であり、∥⋅∥A\lVert\cdot\rVert_AはRn\R^nのノルムである。
  2. x0+Wx_0+W上の関数y↦∥x−y∥Ay\mapsto\lVert x-y\rVert_Aの最小値を与える点y∘∈x0+Wy^\circ\in x_0+Wがただ一つ存在する。
  3. 任意のy∈x0+Wy\in x_0+Wについて∥x−y∥A2=∥x−y∘∥A2+∥y−y∘∥A2\lVert x-y\rVert_A^2=\lVert x-y^\circ\rVert_A^2+\lVert y-y^\circ\rVert_A^2が成り立つ。

y∈x0+Wy\in x_0+Wについて、次の三条件は同値である。

  1. y=y∘y=y^\circである。
  2. 任意のw∈Ww\in WについてwT(b−Ay)=0w^{\mathsf T}(b-Ay)=0である。
  3. 任意のw∈Ww\in WについてwTA(x−y)=0w^{\mathsf T}A(x-y)=0である。

証明.(1)を示す。⟨u,v⟩A\langle u,v\rangle_Aはuuとvvのそれぞれについて線形であり、AT=AA^{\mathsf T}=Aから⟨u,v⟩A=(uTAv)T=vTAu=⟨v,u⟩A\langle u,v\rangle_A=(u^{\mathsf T}Av)^{\mathsf T}=v^{\mathsf T}Au=\langle v,u\rangle_Aである。AAは正定値であるから、v≠0v\ne0ならば⟨v,v⟩A>0\langle v,v\rangle_A>0である。したがって⟨⋅,⋅⟩A\langle\cdot,\cdot\rangle_Aは内積である。∥⋅∥A\lVert\cdot\rVert_Aはこの内積から定まるノルムであるから、§D3.14 系 1.5により∥u+v∥A≤∥u∥A+∥v∥A\lVert u+v\rVert_A\le\lVert u\rVert_A+\lVert v\rVert_Aである。正定値性と斉次性は内積の性質から従う。

d:=dim⁡Wd:=\dim Wとし、WWの基底に内積⟨⋅,⋅⟩A\langle\cdot,\cdot\rangle_Aについて§D3.14 定理 2.1を適用して、⟨⋅,⋅⟩A\langle\cdot,\cdot\rangle_Aに関するWWの正規直交基底w1,…,wdw_1,\dots,w_dをとる（d=0d=0ならば空の族である）。

y∗:=x0+∑j=1d⟨x−x0,wj⟩Awjy^*:=x_0+\sum_{j=1}^d\langle x-x_0,w_j\rangle_Aw_j

と置く。y=x0+∑jcjwj∈x0+Wy=x_0+\sum_jc_jw_j\in x_0+Wについて⟨x−y,wi⟩A=⟨x−x0,wi⟩A−ci\langle x-y,w_i\rangle_A=\langle x-x_0,w_i\rangle_A-c_iであるから、yyが(3)を満たすことと、任意のiiについてci=⟨x−x0,wi⟩Ac_i=\langle x-x_0,w_i\rangle_Aであること、すなわちy=y∗y=y^*であることは同値である。y∈x0+Wy\in x_0+Wとするとy∗−y∈Wy^*-y\in Wであり、y∗y^*は(3)を満たすから⟨x−y∗,y∗−y⟩A=0\langle x-y^*,y^*-y\rangle_A=0である。x−y=(x−y∗)+(y∗−y)x-y=(x-y^*)+(y^*-y)から

∥x−y∥A2=∥x−y∗∥A2+∥y−y∗∥A2\lVert x-y\rVert_A^2=\lVert x-y^*\rVert_A^2+\lVert y-y^*\rVert_A^2

である。右辺は∥x−y∗∥A2\lVert x-y^*\rVert_A^2以上であり、等号は(1)によりy=y∗y=y^*のときに限る。したがってy∗y^*はx0+Wx_0+W上で最小値を与えるただ一つの点であり、(2)が成り立ってy∘=y∗y^\circ=y^*である。y∘=y∗y^\circ=y^*であるから、上の等式は(3)である。yyが(3)を満たすこととy=y∗y=y^*であることは同値であったから、(1)⇔\Leftrightarrow(3)が成り立つ。Ax=bAx=bからA(x−y)=b−AyA(x-y)=b-Ayであるから、(2)⇔\Leftrightarrow(3)が成り立つ。▨

補題 1.2.n∈N≥1n\in\NNとし、A∈Rn×nA\in\R^{n\times n}を実対称正定値行列、b∈Rnb\in\R^n、x:=A−1bx:=A^{-1}bとし、∥⋅∥A\lVert\cdot\rVert_Aを補題 1.1のとおりとする。y∈Rny\in\R^nに対してΦ(y):=12yTAy−bTy\Phi(y):=\tfrac12y^{\mathsf T}Ay-b^{\mathsf T}y（yyのエネルギー）と置く。

  1. 任意のy∈Rny\in\R^nについてΦ(y)−Φ(x)=12∥x−y∥A2\Phi(y)-\Phi(x)=\tfrac12\lVert x-y\rVert_A^2である。
  2. Φ\PhiはRn\R^n上で微分可能であり、任意のy∈Rny\in\R^nについて∇Φ(y)=Ay−b\nabla\Phi(y)=Ay-bである。すなわち∇Φ(y)\nabla\Phi(y)は残差b−Ayb-Ayの符号を変えたものである。
  3. WWをRn\R^nの部分空間、x0∈Rnx_0\in\R^nとし、y∘y^\circを補題 1.1 (2)の点とする。x0+Wx_0+W上でΦ\Phiの最小値を与える点はy∘y^\circただ一つである。すなわち、補題 1.1のx0+Wx_0+W上での∥x−y∥A\lVert x-y\rVert_Aの最小化は、x0+Wx_0+W上でのΦ\Phiの最小化である。

証明.(1)を示す。AT=AA^{\mathsf T}=AとAx=bAx=bからxTAy=(Ax)Ty=bTyx^{\mathsf T}Ay=(Ax)^{\mathsf T}y=b^{\mathsf T}y、xTAx=bTxx^{\mathsf T}Ax=b^{\mathsf T}xである。したがって

12∥x−y∥A2=12xTAx−xTAy+12yTAy=12yTAy−bTy+12bTx\tfrac12\lVert x-y\rVert_A^2=\tfrac12x^{\mathsf T}Ax-x^{\mathsf T}Ay+\tfrac12y^{\mathsf T}Ay=\tfrac12y^{\mathsf T}Ay-b^{\mathsf T}y+\tfrac12b^{\mathsf T}x

であり、Φ(x)=12bTx−bTx=−12bTx\Phi(x)=\tfrac12b^{\mathsf T}x-b^{\mathsf T}x=-\tfrac12b^{\mathsf T}xであるから、右辺はΦ(y)−Φ(x)\Phi(y)-\Phi(x)に等しい。

(2)を示す。y,h∈Rny,h\in\R^nとする。AT=AA^{\mathsf T}=AからhTAy=yTAhh^{\mathsf T}Ay=y^{\mathsf T}Ahであり、

Φ(y+h)−Φ(y)=yTAh+12hTAh−bTh=(Ay−b)Th+12hTAh\Phi(y+h)-\Phi(y)=y^{\mathsf T}Ah+\tfrac12h^{\mathsf T}Ah-b^{\mathsf T}h=(Ay-b)^{\mathsf T}h+\tfrac12h^{\mathsf T}Ah

である。A=(aij)A=(a_{ij})と置くと∣hTAh∣≤∑i,j∣aij∣∣hi∣∣hj∣≤(∑i,j∣aij∣)∥h∥22\lvert h^{\mathsf T}Ah\rvert\le\sum_{i,j}\lvert a_{ij}\rvert\lvert h_i\rvert\lvert h_j\rvert\le\bigl(\sum_{i,j}\lvert a_{ij}\rvert\bigr)\lVert h\rVert_2^2であるから、h→0h\to0のとき12hTAh/∥h∥2→0\tfrac12h^{\mathsf T}Ah/\lVert h\rVert_2\to0である。したがってΦ\Phiはyyで微分可能であり、∇Φ(y)=Ay−b=−(b−Ay)\nabla\Phi(y)=Ay-b=-(b-Ay)である。

(3)を示す。(1)により、y∈x0+Wy\in x_0+WについてΦ(y)=Φ(x)+12∥x−y∥A2\Phi(y)=\Phi(x)+\tfrac12\lVert x-y\rVert_A^2である。Φ(x)\Phi(x)はyyによらないから、y,y′∈x0+Wy,y'\in x_0+WについてΦ(y)≤Φ(y′)\Phi(y)\le\Phi(y')であることと∥x−y∥A≤∥x−y′∥A\lVert x-y\rVert_A\le\lVert x-y'\rVert_Aであることは同値である。したがってx0+Wx_0+W上でΦ\Phiの最小値を与える点はy↦∥x−y∥Ay\mapsto\lVert x-y\rVert_Aの最小値を与える点と一致し、補題 1.1 (2)によりそれはy∘y^\circただ一つである。▨

定義 1.3.n∈N≥1n\in\NNとし、A∈Rn×nA\in\R^{n\times n}、b∈Rnb\in\R^n、x0∈Rnx_0\in\R^nとし、r0:=b−Ax0r_0:=b-Ax_0と置く。

  1. AAが実対称正定値であるとき、補題 1.1のノルム∥v∥A=(vTAv)1/2\lVert v\rVert_A=(v^{\mathsf T}Av)^{1/2}を AA-ノルム (A-norm) という。
  2. k∈N≥1k\in\NNに対してKk:=span⁡{r0,Ar0,…,Ak−1r0}\mathcal K_k:=\operatorname{span}\{r_0,Ar_0,\dots,A^{k-1}r_0\}と置き、K0:={0}\mathcal K_0:=\{0\}と置く。Kk\mathcal K_kをAAとr0r_0のkk次の Krylov 部分空間 (Krylov subspace) という。任意のk∈N≥0k\in\NについてKk⊂Kk+1\mathcal K_k\subset\mathcal K_{k+1}かつAKk⊂Kk+1A\mathcal K_k\subset\mathcal K_{k+1}である。
  3. AAが実対称正定値であるとき、x:=A−1bx:=A^{-1}bとし、k∈N≥0k\in\Nに対して、x0+Kkx_0+\mathcal K_k上でy↦∥x−y∥Ay\mapsto\lVert x-y\rVert_Aの最小値を与えるただ一つの点（補題 1.1 (2)）をxkx_kと書く。k=0k=0のとき、この点は与えられたx0x_0である。列(xk)k∈N≥0(x_k)_{k\in\N}を、Ax=bAx=bに対する初期値x0x_0の 共役勾配法 (conjugate gradient method) の反復という。
  4. 次の計算式を共役勾配法の算法という。x~0:=x0\tilde x_0:=x_0、p0:=r0p_0:=r_0と置き、k=0,1,2,…k=0,1,2,\dotsの順に次を行う。rk=0r_k=0ならば停止し、m:=km:=kを停止段という。rk≠0r_k\ne0かつpkTApk=0p_k^{\mathsf T}Ap_k=0ならば、算法は段kkで中断する。rk≠0r_k\ne0かつpkTApk≠0p_k^{\mathsf T}Ap_k\ne0ならば αk:=rkTrkpkTApk,x~k+1:=x~k+αkpk,rk+1:=rk−αkApk,βk:=rk+1Trk+1rkTrk,pk+1:=rk+1+βkpk\alpha_k:=\frac{r_k^{\mathsf T}r_k}{p_k^{\mathsf T}Ap_k},\quad\tilde x_{k+1}:=\tilde x_k+\alpha_kp_k,\quad r_{k+1}:=r_k-\alpha_kAp_k,\quad\beta_k:=\frac{r_{k+1}^{\mathsf T}r_{k+1}}{r_k^{\mathsf T}r_k},\quad p_{k+1}:=r_{k+1}+\beta_kp_k と置き、これを段kkの実行という。

2 算法と最小化点の一致

定理 2.1.n∈N≥1n\in\NNとし、A∈Rn×nA\in\R^{n\times n}を実対称正定値行列、b,x0∈Rnb,x_0\in\R^n、x:=A−1bx:=A^{-1}bとする。Kk\mathcal K_k、xkx_kと、算法のx~k,rk,pk\tilde x_k,r_k,p_kを定義 1.3のとおりとする。

  1. 整数0≤m≤n0\le m\le nが存在して、k<mk<mならばrk≠0r_k\ne0かつpkTApk>0p_k^{\mathsf T}Ap_k>0であり、rm=0r_m=0である。すなわち、算法は中断せず、停止段mmで停止する。
  2. 0≤j<k≤m0\le j<k\le mならばrkTrj=0r_k^{\mathsf T}r_j=0かつpkTApj=0p_k^{\mathsf T}Ap_j=0である。
  3. 0≤k≤m0\le k\le mならばspan⁡{r0,…,rk−1}=span⁡{p0,…,pk−1}=Kk\operatorname{span}\{r_0,\dots,r_{k-1}\}=\operatorname{span}\{p_0,\dots,p_{k-1}\}=\mathcal K_kかつdim⁡Kk=k\dim\mathcal K_k=kである。
  4. 0≤k≤m0\le k\le mならばrk=b−Ax~kr_k=b-A\tilde x_kかつx~k=xk\tilde x_k=x_kである。k≥mk\ge mならばxk=xx_k=xである。

証明.

主張 2.1.1. 整数k≥0k\ge0について、算法が段0,…,k−10,\dots,k-1を実行してx~k,rk,pk\tilde x_k,r_k,p_kを定めたとする（k=0k=0では仮定はない）。このとき次が成り立つ。

  1. rk=b−Ax~kr_k=b-A\tilde x_kかつx~k∈x0+span⁡{p0,…,pk−1}\tilde x_k\in x_0+\operatorname{span}\{p_0,\dots,p_{k-1}\}である。
  2. 0≤i<j≤k0\le i<j\le kならばrjTri=0r_j^{\mathsf T}r_i=0かつpjTApi=0p_j^{\mathsf T}Ap_i=0である。
  3. 0≤j≤k0\le j\le kならばspan⁡{r0,…,rj}=span⁡{p0,…,pj}⊂Kj+1\operatorname{span}\{r_0,\dots,r_j\}=\operatorname{span}\{p_0,\dots,p_j\}\subset\mathcal K_{j+1}である。
  4. pkTrk=rkTrkp_k^{\mathsf T}r_k=r_k^{\mathsf T}r_kである。

証明.k=0k=0では、r0=b−Ax0=b−Ax~0r_0=b-Ax_0=b-A\tilde x_0、x~0=x0\tilde x_0=x_0、p0=r0∈K1p_0=r_0\in\mathcal K_1であり、四つの主張が成り立つ。k≥0k\ge0とし、算法が段0,…,k0,\dots,kを実行し、kkについて主張が成り立つとする。段0,…,k0,\dots,kでri≠0r_i\ne0であるから、0≤i≤k0\le i\le kについてαi≠0\alpha_i\ne0であり、Api=αi−1(ri−ri+1)Ap_i=\alpha_i^{-1}(r_i-r_{i+1})である。

rk+1=rk−αkApk=b−A(x~k+αkpk)=b−Ax~k+1r_{k+1}=r_k-\alpha_kAp_k=b-A(\tilde x_k+\alpha_kp_k)=b-A\tilde x_{k+1}であり、x~k+1=x~k+αkpk∈x0+span⁡{p0,…,pk}\tilde x_{k+1}=\tilde x_k+\alpha_kp_k\in x_0+\operatorname{span}\{p_0,\dots,p_k\}である。したがって主張 2.1.1 (1)はk+1k+1について成り立つ。

k≥1k\ge1ならば、rk=pk−βk−1pk−1r_k=p_k-\beta_{k-1}p_{k-1}と主張 2.1.1 (2)からpkTArk=pkTApkp_k^{\mathsf T}Ar_k=p_k^{\mathsf T}Ap_kであり、k=0k=0でもr0=p0r_0=p_0からこの等式が成り立つ。0≤i≤k0\le i\le kとする。AT=AA^{\mathsf T}=Aから

rk+1Tri=rkTri−αkpkTArir_{k+1}^{\mathsf T}r_i=r_k^{\mathsf T}r_i-\alpha_kp_k^{\mathsf T}Ar_i

である。i<ki<kならば、主張 2.1.1 (2)によりrkTri=0r_k^{\mathsf T}r_i=0であり、主張 2.1.1 (3)によりri∈span⁡{p0,…,pi}r_i\in\operatorname{span}\{p_0,\dots,p_i\}であるから、主張 2.1.1 (2)によりpkTAri=0p_k^{\mathsf T}Ar_i=0である。i=ki=kならば、右辺はrkTrk−αkpkTApk=0r_k^{\mathsf T}r_k-\alpha_kp_k^{\mathsf T}Ap_k=0である。したがってrk+1Tri=0r_{k+1}^{\mathsf T}r_i=0（0≤i≤k0\le i\le k）である。次に

pk+1TApi=αi−1(rk+1Tri−rk+1Tri+1)+βkpkTApip_{k+1}^{\mathsf T}Ap_i=\alpha_i^{-1}\bigl(r_{k+1}^{\mathsf T}r_i-r_{k+1}^{\mathsf T}r_{i+1}\bigr)+\beta_kp_k^{\mathsf T}Ap_i

である。i<ki<kならば、i+1≤ki+1\le kであるから右辺の三項はいずれも00である。i=ki=kならば、右辺は−αk−1rk+1Trk+1+βkpkTApk=rk+1Trk+1(−pkTApk+pkTApk)/rkTrk=0-\alpha_k^{-1}r_{k+1}^{\mathsf T}r_{k+1}+\beta_kp_k^{\mathsf T}Ap_k=r_{k+1}^{\mathsf T}r_{k+1}\bigl(-p_k^{\mathsf T}Ap_k+p_k^{\mathsf T}Ap_k\bigr)/r_k^{\mathsf T}r_k=0である。したがって主張 2.1.1 (2)はk+1k+1について成り立つ。

pk+1−rk+1=βkpkp_{k+1}-r_{k+1}=\beta_kp_kと主張 2.1.1 (3)からspan⁡{r0,…,rk+1}=span⁡{p0,…,pk+1}\operatorname{span}\{r_0,\dots,r_{k+1}\}=\operatorname{span}\{p_0,\dots,p_{k+1}\}である。rk,pk∈Kk+1r_k,p_k\in\mathcal K_{k+1}であり、AKk+1⊂Kk+2A\mathcal K_{k+1}\subset\mathcal K_{k+2}であるから、rk+1=rk−αkApk∈Kk+2r_{k+1}=r_k-\alpha_kAp_k\in\mathcal K_{k+2}である。したがって主張 2.1.1 (3)はk+1k+1について成り立つ。

pk∈span⁡{r0,…,rk}p_k\in\operatorname{span}\{r_0,\dots,r_k\}であり、rk+1r_{k+1}はr0,…,rkr_0,\dots,r_kに直交するから、pk+1Trk+1=rk+1Trk+1+βkpkTrk+1=rk+1Trk+1p_{k+1}^{\mathsf T}r_{k+1}=r_{k+1}^{\mathsf T}r_{k+1}+\beta_kp_k^{\mathsf T}r_{k+1}=r_{k+1}^{\mathsf T}r_{k+1}である。したがって主張 2.1.1 (4)はk+1k+1について成り立つ。kkに関する帰納法により、主張は任意のk≥0k\ge0について成り立つ。▨

(1)を示す。算法が段0,…,k−10,\dots,k-1を実行し、r0,…,rkr_0,\dots,r_kがいずれも00でないとする。主張 2.1.1 (4)によりpkTrk=rkTrk>0p_k^{\mathsf T}r_k=r_k^{\mathsf T}r_k>0であるからpk≠0p_k\ne0であり、AAは正定値であるからpkTApk>0p_k^{\mathsf T}Ap_k>0である。したがって算法は段kkを実行する。主張 2.1.1 (2)によりr0,…,rkr_0,\dots,r_kは00でない互いに直交するベクトルであり、一次独立であるからk+1≤nk+1\le nである。k=0,1,2,…k=0,1,2,\dotsの順にこの議論を適用すると、rk≠0r_k\ne0である限り段kkが実行されてk+1≤nk+1\le nであるから、rm=0r_m=0を満たすm≤nm\le nが存在し、k<mk<mならばrk≠0r_k\ne0かつpkTApk>0p_k^{\mathsf T}Ap_k>0である。

(2)は、(1)により算法が段0,…,m−10,\dots,m-1を実行するので、主張 2.1.1 (2)をk=mk=mに適用したものである。

(3)を示す。k=0k=0ではすべて{0}\{0\}である。1≤k≤m1\le k\le mとする。主張 2.1.1 (3)によりspan⁡{r0,…,rk−1}=span⁡{p0,…,pk−1}⊂Kk\operatorname{span}\{r_0,\dots,r_{k-1}\}=\operatorname{span}\{p_0,\dots,p_{k-1}\}\subset\mathcal K_kである。r0,…,rk−1r_0,\dots,r_{k-1}は00でない互いに直交するベクトルであるから左辺の次元はkkであり、Kk\mathcal K_kはkk個のベクトルで張られるからdim⁡Kk≤k\dim\mathcal K_k\le kである。したがって三つの空間は一致し、dim⁡Kk=k\dim\mathcal K_k=kである。

(4)を示す。0≤k≤m0\le k\le mとする。主張 2.1.1 (1)と(3)によりrk=b−Ax~kr_k=b-A\tilde x_kかつx~k∈x0+Kk\tilde x_k\in x_0+\mathcal K_kであり、(2)と(3)によりrkr_kはKk\mathcal K_kのすべての元に直交する。補題 1.1をW=KkW=\mathcal K_kに適用すると、x~k\tilde x_kは補題 1.1 (2)を満たすので、補題 1.1 (1)⇔\Leftrightarrow(2)によりx~k=xk\tilde x_k=x_kである。k≥mk\ge mとする。b−Ax~m=rm=0b-A\tilde x_m=r_m=0からxm=x~m=xx_m=\tilde x_m=xであり、x∈x0+Km⊂x0+Kkx\in x_0+\mathcal K_m\subset x_0+\mathcal K_kである。∥x−x∥A=0\lVert x-x\rVert_A=0はx0+Kkx_0+\mathcal K_k上の最小値であるから、補題 1.1 (2)の一意性によりxk=xx_k=xである。▨

例 2.2.A:=diag⁡(1,−1)A:=\operatorname{diag}(1,-1)、b:=(1,1)Tb:=(1,1)^{\mathsf T}、x0:=0x_0:=0とする。AAは実対称で正則であるが正定値でない。r0=p0=(1,1)Tr_0=p_0=(1,1)^{\mathsf T}であり、p0TAp0=1−1=0p_0^{\mathsf T}Ap_0=1-1=0であるから、算法は段00で中断する。vTAv=v12−v22v^{\mathsf T}Av=v_1^2-v_2^2はv=(0,1)Tv=(0,1)^{\mathsf T}で−1-1であり、(vTAv)1/2(v^{\mathsf T}Av)^{1/2}はR2\R^2のノルムを定めない。

A:=(11−11),b:=(10),x0:=0A:=\begin{pmatrix}1&1\\-1&1\end{pmatrix},\qquad b:=\begin{pmatrix}1\\0\end{pmatrix},\qquad x_0:=0

とする。AAは対称でなく、任意のv∈R2v\in\R^2でvTAv=v12+v22v^{\mathsf T}Av=v_1^2+v_2^2である。x=A−1b=(1/2,1/2)Tx=A^{-1}b=(1/2,1/2)^{\mathsf T}である。算法の値は次のとおりである。

r0=p0=(1,0)T, Ap0=(1,−1)T, α0=1, x~1=(1,0)T, r1=(0,1)T, β0=1, p1=(1,1)T,Ap1=(2,0)T, α1=12, x~2=(32,12)T, r2=(−1,1)T.\begin{aligned} &r_0=p_0=(1,0)^{\mathsf T},\ Ap_0=(1,-1)^{\mathsf T},\ \alpha_0=1,\ \tilde x_1=(1,0)^{\mathsf T},\ r_1=(0,1)^{\mathsf T},\ \beta_0=1,\ p_1=(1,1)^{\mathsf T},\\ &Ap_1=(2,0)^{\mathsf T},\ \alpha_1=\tfrac12,\ \tilde x_2=\bigl(\tfrac32,\tfrac12\bigr)^{\mathsf T},\ r_2=(-1,1)^{\mathsf T}. \end{aligned}

算法は中断しない。K2=span⁡{(1,0)T,(1,−1)T}=R2\mathcal K_2=\operatorname{span}\{(1,0)^{\mathsf T},(1,-1)^{\mathsf T}\}=\R^2であるから、y↦(x−y)TA(x−y)=∥x−y∥22y\mapsto(x-y)^{\mathsf T}A(x-y)=\lVert x-y\rVert_2^2のx0+K2x_0+\mathcal K_2上の最小値を与える点はxxであるが、x~2≠x\tilde x_2\ne xである。またr2Tr1=1≠0r_2^{\mathsf T}r_1=1\ne0である。

3 Chebyshev 多項式

定義 3.1. 実係数多項式の列(Tk)k∈N≥0(T_k)_{k\in\N}を

T0(t):=1,T1(t):=t,Tk+1(t):=2tTk(t)−Tk−1(t)(k≥1)T_0(t):=1,\qquad T_1(t):=t,\qquad T_{k+1}(t):=2tT_k(t)-T_{k-1}(t)\quad(k\ge1)

で定め、TkT_kをkk次の Chebyshev 多項式 (Chebyshev polynomial) という。

補題 3.2.k∈N≥0k\in\Nとする。

  1. TkT_kは実係数で次数kk以下の多項式である。
  2. 任意のθ∈R\theta\in\Rに対してTk(cos⁡θ)=cos⁡kθT_k(\cos\theta)=\cos k\thetaである。
  3. t∈[−1,1]t\in[-1,1]ならば∣Tk(t)∣≤1\lvert T_k(t)\rvert\le1である。
  4. t∈Rt\in\Rが∣t∣≥1\lvert t\rvert\ge1を満たすならば Tk(t)=12((t+t2−1)k+(t−t2−1)k)T_k(t)=\frac12\Bigl(\bigl(t+\sqrt{t^2-1}\bigr)^k+\bigl(t-\sqrt{t^2-1}\bigr)^k\Bigr) である。

証明.(1)を示す。T0T_0とT1T_1の次数はそれぞれ00と11である。k≥1k\ge1についてTk−1T_{k-1}とTkT_kの次数がそれぞれk−1k-1以下とkk以下ならば、2tTk−Tk−12tT_k-T_{k-1}の次数はk+1k+1以下である。kkに関する帰納法により主張が成り立つ。

(2)を示す。k=0,1k=0,1では定義から成り立つ。加法定理によりcos⁡(k+1)θ+cos⁡(k−1)θ=2cos⁡θcos⁡kθ\cos(k+1)\theta+\cos(k-1)\theta=2\cos\theta\cos k\thetaであるから、k−1k-1とkkで主張が成り立てばTk+1(cos⁡θ)=2cos⁡θcos⁡kθ−cos⁡(k−1)θ=cos⁡(k+1)θT_{k+1}(\cos\theta)=2\cos\theta\cos k\theta-\cos(k-1)\theta=\cos(k+1)\thetaである。kkに関する帰納法により主張が成り立つ。

(3)を示す。t∈[−1,1]t\in[-1,1]ならばθ:=arccos⁡t\theta:=\arccos tはcos⁡θ=t\cos\theta=tを満たし、(2)により∣Tk(t)∣=∣cos⁡kθ∣≤1\lvert T_k(t)\rvert=\lvert\cos k\theta\rvert\le1である。

(4)を示す。∣t∣≥1\lvert t\rvert\ge1ならばs±:=t±t2−1s_\pm:=t\pm\sqrt{t^2-1}は実数であり、二次方程式s2−2ts+1=0s^2-2ts+1=0の根である。Sk:=(s+k+s−k)/2S_k:=(s_+^k+s_-^k)/2と置くと、S0=1S_0=1、S1=tS_1=tであり、s±k+1=2ts±k−s±k−1s_\pm^{k+1}=2ts_\pm^k-s_\pm^{k-1}からSk+1=2tSk−Sk−1S_{k+1}=2tS_k-S_{k-1}（k≥1k\ge1）である。(Sk)(S_k)と(Tk(t))(T_k(t))は同じ初期値と同じ漸化式を満たすから、kkに関する帰納法によりSk=Tk(t)S_k=T_k(t)である。▨

4 誤差の多項式表示と条件数による上界

補題 4.1. 実数0<λ−<λ+0<\lambda_-<\lambda_+とk∈N≥0k\in\Nに対して、z:=(λ+−λ−)/(λ++λ−)z:=(\sqrt{\lambda_+}-\sqrt{\lambda_-})/(\sqrt{\lambda_+}+\sqrt{\lambda_-})と置く。次数kk以下の実係数多項式qqであって、q(0)=1q(0)=1を満たし、任意のt∈[λ−,λ+]t\in[\lambda_-,\lambda_+]について∣q(t)∣≤2zk\lvert q(t)\rvert\le2z^kを満たすものが存在する。

証明.σ:=(λ++λ−)/(λ+−λ−)\sigma:=(\lambda_++\lambda_-)/(\lambda_+-\lambda_-)と置くとσ>1\sigma>1であり、σ2−1=4λ+λ−/(λ+−λ−)2\sigma^2-1=4\lambda_+\lambda_-/(\lambda_+-\lambda_-)^2から

σ+σ2−1=(λ++λ−)2λ+−λ−=z−1,σ−σ2−1=(λ+−λ−)2λ+−λ−=z\sigma+\sqrt{\sigma^2-1}=\frac{(\sqrt{\lambda_+}+\sqrt{\lambda_-})^2}{\lambda_+-\lambda_-}=z^{-1},\qquad\sigma-\sqrt{\sigma^2-1}=\frac{(\sqrt{\lambda_+}-\sqrt{\lambda_-})^2}{\lambda_+-\lambda_-}=z

である。補題 3.2 (4)によりTk(σ)=(z−k+zk)/2≥z−k/2>0T_k(\sigma)=(z^{-k}+z^k)/2\ge z^{-k}/2>0である。

q(t):=1Tk(σ)Tk(λ++λ−−2tλ+−λ−)q(t):=\frac{1}{T_k(\sigma)}T_k\Bigl(\frac{\lambda_++\lambda_--2t}{\lambda_+-\lambda_-}\Bigr)

と置く。補題 3.2 (1)によりqqは次数kk以下の実係数多項式であり、q(0)=Tk(σ)/Tk(σ)=1q(0)=T_k(\sigma)/T_k(\sigma)=1である。t∈[λ−,λ+]t\in[\lambda_-,\lambda_+]ならば(λ++λ−−2t)/(λ+−λ−)∈[−1,1](\lambda_++\lambda_--2t)/(\lambda_+-\lambda_-)\in[-1,1]であるから、補題 3.2 (3)により∣q(t)∣≤1/Tk(σ)≤2zk\lvert q(t)\rvert\le1/T_k(\sigma)\le2z^kである。▨

定理 4.2.n∈N≥1n\in\NNとし、A∈Rn×nA\in\R^{n\times n}を実対称正定値行列、b,x0∈Rnb,x_0\in\R^n、x:=A−1bx:=A^{-1}b、e0:=x−x0e_0:=x-x_0とし、(xk)k∈N≥0(x_k)_{k\in\N}を共役勾配法の反復とする。Λ\LambdaをAAの固有値の集合とし、λmin⁡:=min⁡Λ\lambda_{\min}:=\min\Lambda、λmax⁡:=max⁡Λ\lambda_{\max}:=\max\Lambda、κ:=λmax⁡/λmin⁡\kappa:=\lambda_{\max}/\lambda_{\min}と置く（λmin⁡>0\lambda_{\min}>0である）。k∈N≥0k\in\Nに対して、次数kk以下でq(0)=1q(0)=1を満たす実係数多項式qqの全体をPk\mathcal P_kと書く。

  1. 任意のk∈N≥0k\in\Nについて、{∥q(A)e0∥A∣q∈Pk}\{\lVert q(A)e_0\rVert_A\mid q\in\mathcal P_k\}は最小値をもち、∥x−xk∥A=min⁡q∈Pk∥q(A)e0∥A\lVert x-x_k\rVert_A=\min_{q\in\mathcal P_k}\lVert q(A)e_0\rVert_Aである。
  2. 任意の実係数多項式qqについて∥q(A)e0∥A≤max⁡λ∈Λ∣q(λ)∣ ∥e0∥A\lVert q(A)e_0\rVert_A\le\max_{\lambda\in\Lambda}\lvert q(\lambda)\rvert\,\lVert e_0\rVert_Aである。
  3. κ>1\kappa>1ならば、任意のk∈N≥0k\in\Nについて ∥x−xk∥A≤2(κ−1κ+1)k∥x−x0∥A\lVert x-x_k\rVert_A\le2\Bigl(\frac{\sqrt\kappa-1}{\sqrt\kappa+1}\Bigr)^k\lVert x-x_0\rVert_A である。
  4. κ=1\kappa=1ならば、任意のk≥1k\ge1についてxk=xx_k=xである。

証明.(1)を示す。r0=b−Ax0=Ae0r_0=b-Ax_0=Ae_0である。Kk\mathcal K_kの定義により、y∈x0+Kky\in x_0+\mathcal K_kであることと、次数k−1k-1以下の実係数多項式pp（k=0k=0ではp=0p=0）が存在してy=x0+p(A)r0y=x_0+p(A)r_0であることは同値である。このときx−y=e0−p(A)Ae0=q(A)e0x-y=e_0-p(A)Ae_0=q(A)e_0、q(t):=1−tp(t)∈Pkq(t):=1-tp(t)\in\mathcal P_kである。逆にq∈Pkq\in\mathcal P_kならばq−1q-1は定数項が00であるから、次数k−1k-1以下の実係数多項式ppが存在してq(t)=1−tp(t)q(t)=1-tp(t)である。したがって{x−y∣y∈x0+Kk}={q(A)e0∣q∈Pk}\{x-y\mid y\in x_0+\mathcal K_k\}=\{q(A)e_0\mid q\in\mathcal P_k\}であり、xkx_kの定義により主張が成り立つ。

(2)を示す。§D3.15 定理 3.1により、直交行列PPとD=diag⁡(λ1,…,λn)D=\operatorname{diag}(\lambda_1,\dots,\lambda_n)が存在してA=PDPTA=PDP^{\mathsf T}である。λi∈Λ\lambda_i\in\Lambdaであり、PPの第ii列viv_iについてλi=viTAvi>0\lambda_i=v_i^{\mathsf T}Av_i>0である。c:=PTe0c:=P^{\mathsf T}e_0と置くとq(A)=Pq(D)PTq(A)=Pq(D)P^{\mathsf T}であり、

∥q(A)e0∥A2=cTq(D)Dq(D)c=∑i=1nλiq(λi)2ci2≤max⁡λ∈Λq(λ)2∑i=1nλici2=max⁡λ∈Λq(λ)2 ∥e0∥A2\lVert q(A)e_0\rVert_A^2=c^{\mathsf T}q(D)Dq(D)c=\sum_{i=1}^n\lambda_iq(\lambda_i)^2c_i^2\le\max_{\lambda\in\Lambda}q(\lambda)^2\sum_{i=1}^n\lambda_ic_i^2=\max_{\lambda\in\Lambda}q(\lambda)^2\,\lVert e_0\rVert_A^2

である。

(3)を示す。κ>1\kappa>1ならば0<λmin⁡<λmax⁡0<\lambda_{\min}<\lambda_{\max}であり、(λmax⁡−λmin⁡)/(λmax⁡+λmin⁡)=(κ−1)/(κ+1)(\sqrt{\lambda_{\max}}-\sqrt{\lambda_{\min}})/(\sqrt{\lambda_{\max}}+\sqrt{\lambda_{\min}})=(\sqrt\kappa-1)/(\sqrt\kappa+1)である。補題 4.1をλ−=λmin⁡\lambda_-=\lambda_{\min}、λ+=λmax⁡\lambda_+=\lambda_{\max}に適用して得るq∈Pkq\in\mathcal P_kはΛ⊂[λmin⁡,λmax⁡]\Lambda\subset[\lambda_{\min},\lambda_{\max}]上で∣q∣≤2((κ−1)/(κ+1))k\lvert q\rvert\le2((\sqrt\kappa-1)/(\sqrt\kappa+1))^kを満たす。(1)と(2)により主張が成り立つ。

(4)を示す。κ=1\kappa=1ならばΛ={λmin⁡}\Lambda=\{\lambda_{\min}\}である。q(t):=1−t/λmin⁡q(t):=1-t/\lambda_{\min}はP1⊂Pk\mathcal P_1\subset\mathcal P_kに属し、Λ\Lambda上で00である。(2)によりq(A)e0=0q(A)e_0=0であり、(1)により∥x−xk∥A=0\lVert x-x_k\rVert_A=0、すなわちxk=xx_k=xである。▨

系 4.3.n∈N≥1n\in\NNとし、A∈Rn×nA\in\R^{n\times n}を実対称正定値行列、b,x0∈Rnb,x_0\in\R^n、x:=A−1bx:=A^{-1}b、r0:=b−Ax0r_0:=b-Ax_0とし、(xk)k∈N≥0(x_k)_{k\in\N}を共役勾配法の反復、mmを算法の停止段（定理 2.1 (1)）とする。ℓ\ellをAAの相異なる固有値の個数とする。

  1. r0=0r_0=0ならば、m=0m=0であり、任意のk∈N≥0k\in\Nについてxk=xx_k=xである。
  2. r0≠0r_0\ne0とし、ccをAAとr0r_0について§E3.18 命題 3.3が与えるモニック多項式（c(A)r0=0c(A)r_0=0を満たす00でない多項式のうち次数が最小のモニックなもの）とし、ddをその次数とする。このとき1≤d≤ℓ1\le d\le\ellかつm=dm=dであり、k∈N≥0k\in\Nについてxk=xx_k=xであるための必要十分条件はk≥dk\ge dである。
  3. xℓ=xx_\ell=xかつm≤ℓm\le\ellである。

証明.(1)を示す。r0=0r_0=0ならば算法は段00で停止し、m=0m=0である。x0=xx_0=xであるからx∈x0+Kkx\in x_0+\mathcal K_kであり、補題 1.1 (2)の一意性によりxk=xx_k=xである。

(2)を示す。r0≠0r_0\ne0であるからd≥1d\ge1である。Λ\LambdaをAAの固有値の集合とし、π(t):=∏μ∈Λ(t−μ)\pi(t):=\prod_{\mu\in\Lambda}(t-\mu)と置く。§D3.15 定理 3.1により直交行列PPと対角成分がΛ\Lambdaに属する対角行列DDが存在してA=PDPTA=PDP^{\mathsf T}であり、π(A)=Pπ(D)PT=0\pi(A)=P\pi(D)P^{\mathsf T}=0である。§E3.22 命題 1.2によりAAの最小多項式mAm_Aはπ\piを割り、§E3.22 命題 3.1によりccはmAm_Aを割る。したがってc∣πc\mid\piであり、d≤ℓd\le\ellである。Λ\Lambdaの元は正であるからπ(0)≠0\pi(0)\ne0であり、c(0)≠0c(0)\ne0である。q:=c/c(0)q:=c/c(0)と置くとq∈Pdq\in\mathcal P_dであり、e0:=x−x0=A−1r0e_0:=x-x_0=A^{-1}r_0についてq(A)e0=c(0)−1A−1c(A)r0=0q(A)e_0=c(0)^{-1}A^{-1}c(A)r_0=0である。k≥dk\ge dならばq∈Pkq\in\mathcal P_kであるから、定理 4.2 (1)により∥x−xk∥A=0\lVert x-x_k\rVert_A=0、すなわちxk=xx_k=xである。逆にxk=xx_k=xならば、定理 4.2 (1)によりq′∈Pkq'\in\mathcal P_kが存在してq′(A)e0=0q'(A)e_0=0であり、q′(A)r0=Aq′(A)e0=0q'(A)r_0=Aq'(A)e_0=0である。§E3.18 命題 3.3によりc∣q′c\mid q'であり、q′(0)=1q'(0)=1からq′≠0q'\ne0であるので、d≤deg⁡q′≤kd\le\deg q'\le kである。定理 2.1 (4)により、k≤mk\le mならばb−Axk=rkb-Ax_k=r_kである。k<mk<mならばrk≠0r_k\ne0からxk≠xx_k\ne xであり、rm=0r_m=0からxm=xx_m=xである。したがってmmはxk=xx_k=xを満たす最小のkkであり、m=dm=dである。

(3)は、r0=0r_0=0ならば(1)から、r0≠0r_0\ne0ならば(2)とd≤ℓd\le\ellから従う。▨

例 4.4.n≥3n\ge3とし、b∈Rnb\in\R^nを成分がすべて00でないベクトル、x0:=0x_0:=0とする。A:=diag⁡(1,100,…,100)A:=\operatorname{diag}(1,100,\dots,100)、A′:=diag⁡(μ1,…,μn)A':=\operatorname{diag}(\mu_1,\dots,\mu_n)、μi:=1+99(i−1)/(n−1)\mu_i:=1+99(i-1)/(n-1)と置く。二つの行列はどちらも実対称正定値で、最小固有値11と最大固有値100100をもち、定理 4.2 (3)の右辺はどちらの系でも2(9/11)k∥x−x0∥A2(9/11)^k\lVert x-x_0\rVert_A（∥⋅∥A\lVert\cdot\rVert_Aはそれぞれの行列のAA-ノルム）である。

  1. AAの相異なる固有値は11と100100の二つであるから、系 4.3 (3)により、AAの系の停止段は22以下であり、x2=xx_2=xである。k=2k=2での上界の係数は2(9/11)2=162/121>12(9/11)^2=162/121>1である。
  2. D=diag⁡(δ1,…,δn)D=\operatorname{diag}(\delta_1,\dots,\delta_n)が相異なる正の対角成分をもち、r0r_0の成分がすべて00でないならば、DDとr0r_0について系 4.3 (2)の次数ddはnnであり、停止段はnnである。実際、次数n−1n-1以下の実係数多項式ppがp(D)r0=0p(D)r_0=0を満たすならば、各iiでp(δi)(r0)i=0p(\delta_i)(r_0)_i=0からp(δi)=0p(\delta_i)=0であり、ppは相異なるnn点で00になるのでp=0p=0である。したがってd≥nd\ge nであり、d≤ℓ=nd\le\ell=nと合わせてd=nd=nである。A′A'とr0=br_0=bはこの仮定を満たすので、A′A'の系の停止段はnnであり、k<nk<nではxk≠xx_k\ne xである。n=999n=999ならばA′A'の系の停止段は999999であるが、2(9/11)72>10−6>2(9/11)732(9/11)^{72}>10^{-6}>2(9/11)^{73}であるから、相対A′A'-ノルム誤差∥x−xk∥A′/∥x−x0∥A′\lVert x-x_k\rVert_{A'}/\lVert x-x_0\rVert_{A'}を10−610^{-6}以下にすることを定理 4.2 (3)が保証する最小のkkは7373である。

例 4.5.n≥2n\ge2とし、AnA_nを§E20.10 命題 5.1の行列とする。φ:=π/(2(n+1))\varphi:=\pi/(2(n+1))と置く。

  1. κ2(An)=cot⁡2φ\kappa_2(A_n)=\cot^2\varphiであり、(κ2(An)−1)/(κ2(An)+1)=tan⁡(π/4−φ)(\sqrt{\kappa_2(A_n)}-1)/(\sqrt{\kappa_2(A_n)}+1)=\tan(\pi/4-\varphi)である。
  2. 0<θ<10<\theta<1とする。整数k≥(n+1)log⁡(2/θ)/πk\ge(n+1)\log(2/\theta)/\piならば、任意のb,x0∈Rnb,x_0\in\R^nについて、Anx=bA_nx=bの共役勾配法の反復は∥x−xk∥An≤θ∥x−x0∥An\lVert x-x_k\rVert_{A_n}\le\theta\lVert x-x_0\rVert_{A_n}を満たす。
  3. 0<θ<10<\theta<1とし、TTをAnA_nの Jacobi 法または Gauss–Seidel 法の反復行列とする。整数k≥0k\ge0が任意の初期誤差e∈Rne\in\R^nについて∥Tke∥An≤θ∥e∥An\lVert T^ke\rVert_{A_n}\le\theta\lVert e\rVert_{A_n}を満たすならば、k≥log⁡θ/log⁡ρ(T)k\ge\log\theta/\log\rho(T)である。n→∞n\to\inftyのとき、log⁡θ/log⁡ρ(T)\log\theta/\log\rho(T)を(n+1)2(n+1)^2で割った値は、Jacobi 法では2log⁡(1/θ)/π22\log(1/\theta)/\pi^2に、Gauss–Seidel 法ではlog⁡(1/θ)/π2\log(1/\theta)/\pi^2に収束する。

(1)を示す。§E20.10 命題 5.1 (2)によりAnA_nの最小固有値はλ1=4sin⁡2φ\lambda_1=4\sin^2\varphi、最大固有値はλn=4sin⁡2(nπ/(2(n+1)))=4cos⁡2φ\lambda_n=4\sin^2(n\pi/(2(n+1)))=4\cos^2\varphiであり、§E20.5 命題 4.4 (5)によりκ2(An)=cot⁡2φ\kappa_2(A_n)=\cot^2\varphiである。κ2(An)=cot⁡φ\sqrt{\kappa_2(A_n)}=\cot\varphiであるから、y:=tan⁡φy:=\tan\varphiと置くと(cot⁡φ−1)/(cot⁡φ+1)=(1−y)/(1+y)=tan⁡(π/4−φ)(\cot\varphi-1)/(\cot\varphi+1)=(1-y)/(1+y)=\tan(\pi/4-\varphi)である。

(2)を示す。n≥2n\ge2から0<φ≤π/60<\varphi\le\pi/6であり、0<y<10<y<1である。g(s):=log⁡(1+s)−log⁡(1−s)−2sg(s):=\log(1+s)-\log(1-s)-2sはg(0)=0g(0)=0、g′(s)=2s2/(1−s2)≥0g'(s)=2s^2/(1-s^2)\ge0（0≤s<10\le s<1）を満たすからg(y)≥0g(y)\ge0であり、tan⁡φ≥φ\tan\varphi\ge\varphiと合わせて

−log⁡tan⁡(π/4−φ)=log⁡1+y1−y≥2y≥2φ=πn+1-\log\tan(\pi/4-\varphi)=\log\frac{1+y}{1-y}\ge2y\ge2\varphi=\frac{\pi}{n+1}

である。k≥(n+1)log⁡(2/θ)/πk\ge(n+1)\log(2/\theta)/\piならば2tan⁡(π/4−φ)k≤2e−kπ/(n+1)≤θ2\tan(\pi/4-\varphi)^k\le2e^{-k\pi/(n+1)}\le\thetaであり、κ2(An)>1\kappa_2(A_n)>1であるから定理 4.2 (3)により主張が成り立つ。

(3)を示す。補題 1.1 (1)により∥⋅∥An\lVert\cdot\rVert_{A_n}はRn\R^nのノルムであるから、前半は§E20.10 命題 5.2 (3)をこのノルムに適用したものである。§E20.10 定理 3.1 (1)により、この二法のkk段後の誤差は初期誤差eeに対してTkeT^keである。後半は§E20.10 命題 5.2 (2)から従う。

θ=10−6\theta=10^{-6}とする。下表は、2tan⁡(π/4−φ)k≤θ2\tan(\pi/4-\varphi)^k\le\thetaを満たす最小の整数kkと、Jacobi 法と Gauss–Seidel 法のlog⁡θ/log⁡ρ(T)\log\theta/\log\rho(T)以上の最小の整数を、倍精度の浮動小数点計算で求めた値である（ρ(T)\rho(T)は§E20.10 命題 5.2 (1)の値を用いた）。

nn κ2(An)\kappa_2(A_n) 共役勾配法（十分なkk） Jacobi 法（必要なkk） Gauss–Seidel 法（必要なkk）
99 3.986×1013.986\times10^{1} 4646 276276 138138
9999 4.052×1034.052\times10^{3} 462462 2799227992 1399613996
999999 4.053×1054.053\times10^{5} 46194619 27996042799604 13998021399802

第三列は、すべてのb,x0b,x_0に対してAnA_n-ノルムの誤差をθ\theta倍以下にすることを保証する反復数の上界であり、第四列と第五列は、すべての初期誤差に対して同じ保証を与える反復数の下界である。

注意 4.6.

  1. 系 4.3 (2)は厳密算術での主張である。n=24n=24、λi:=110+i−123(100−110)(45)24−i\lambda_i:=\frac1{10}+\frac{i-1}{23}\bigl(100-\frac1{10}\bigr)\bigl(\frac45\bigr)^{24-i}（1≤i≤241\le i\le24）、A:=diag⁡(λ1,…,λ24)A:=\operatorname{diag}(\lambda_1,\dots,\lambda_{24})、b:=(1,…,1)Tb:=(1,\dots,1)^{\mathsf T}、x0:=0x_0:=0とする。λ1=1/10<λ2<⋯<λ24=100\lambda_1=1/10<\lambda_2<\dots<\lambda_{24}=100であるから、例 4.4 (2)により停止段は2424であり、算法を有理数で実行するとrk≠0r_k\ne0（k<24k<24）かつr24=0r_{24}=0である。

    λi\lambda_iを binary64 へ最近接偶数丸めで丸めた値を対角成分とする行列について、算法の各演算を binary64 で実行した（内積は成分の番号順の逐次和である）。

    計算した近似解x^k\hat x_kの相対AA-ノルム誤差∥x−x^k∥A/∥x−x0∥A\lVert x-\hat x_k\rVert_A/\lVert x-x_0\rVert_Aを、元のAAとx=A−1bx=A^{-1}bについて有理数で計算すると、k=24k=24で1.96×10−21.96\times10^{-2}であり、10−1010^{-10}を下回る最小のkkは3737である（k=36k=36で5.34×10−105.34\times10^{-10}、k=37k=37で3.33×10−113.33\times10^{-11}）。

  2. A∈Rn×nA\in\R^{n\times n}を実対称正定値行列、b,x0∈Rnb,x_0\in\R^n、x:=A−1bx:=A^{-1}bとする。C∈Rn×nC\in\R^{n\times n}を実対称正定値行列、LLをC=LLTC=LL^{\mathsf T}を満たす正則行列とし、B:=L−1AL−TB:=L^{-1}AL^{-\mathsf T}、c:=L−1bc:=L^{-1}b、z0:=LTx0z_0:=L^{\mathsf T}x_0と置く（CCによる前処理）。BBは実対称正定値であり、Bz=cBz=cの解はz=LTxz=L^{\mathsf T}xである。任意のv∈Rnv\in\R^nについて∥LTv∥B2=vTLL−1AL−TLTv=∥v∥A2\lVert L^{\mathsf T}v\rVert_B^2=v^{\mathsf T}LL^{-1}AL^{-\mathsf T}L^{\mathsf T}v=\lVert v\rVert_A^2である。したがって、Bz=cBz=cの初期値z0z_0の共役勾配法の反復zkz_kからyk:=L−Tzky_k:=L^{-\mathsf T}z_kと置くと∥x−yk∥A=∥z−zk∥B\lVert x-y_k\rVert_A=\lVert z-z_k\rVert_Bであり、定理 4.2 (3)をBBに適用して、κC>1\kappa_C>1ならば∥x−yk∥A≤2((κC−1)/(κC+1))k∥x−x0∥A\lVert x-y_k\rVert_A\le2((\sqrt{\kappa_C}-1)/(\sqrt{\kappa_C}+1))^k\lVert x-x_0\rVert_Aを得る。ここでκC\kappa_CはBBの最大固有値と最小固有値の比である。C−1A=L−TBLTC^{-1}A=L^{-\mathsf T}BL^{\mathsf T}はBBと相似であるから、κC\kappa_CはC−1AC^{-1}Aの最大固有値と最小固有値の比に等しい。

5 有限精度での残差と停止条件

命題 5.1.n∈N≥1n\in\NNとし、A=(aij)∈Rn×nA=(a_{ij})\in\R^{n\times n}、b∈Rnb\in\R^nとする。K∈N≥1K\in\NNとし、x^k,r^k,p^k∈Rn\hat x_k,\hat r_k,\hat p_k\in\R^n（0≤k≤K0\le k\le K）とα^k∈R\hat\alpha_k\in\R（0≤k<K0\le k<K）を任意にとる。0≤k<K0\le k<Kについて

fk:=x^k+1−x^k−α^kp^k,gk:=r^k+1−r^k+α^kAp^kf_k:=\hat x_{k+1}-\hat x_k-\hat\alpha_k\hat p_k,\qquad g_k:=\hat r_{k+1}-\hat r_k+\hat\alpha_kA\hat p_k

と置き、0≤k≤K0\le k\le Kについてsk:=b−Ax^ks_k:=b-A\hat x_kと置く。ベクトルと行列の絶対値∣⋅∣\lvert\cdot\rvertと不等号は成分ごとにとる。

  1. 0≤k≤K0\le k\le Kについてsk−r^k=s0−r^0−∑j=0k−1(Afj+gj)s_k-\hat r_k=s_0-\hat r_0-\sum_{j=0}^{k-1}(Af_j+g_j)が成り立つ。
  2. FFを浮動小数点数系、uuをその単位丸め誤差、fl⁡\operatorname{fl}をFFの最近接丸めとし、(n+2)u<1(n+2)u<1とし、j∈{2,n,n+2}j\in\{2,n,n+2\}についてγj:=ju/(1−ju)\gamma_j:=ju/(1-ju)と置く。0≤k<K0\le k<Kとし、A∈Fn×nA\in F^{n\times n}、x^k,r^k,p^k∈Fn\hat x_k,\hat r_k,\hat p_k\in F^n、α^k∈F\hat\alpha_k\in Fとする。1≤i≤n1\le i\le nについて、wiw_iを積fl⁡(ai1p^k,1),…,fl⁡(ainp^k,n)\operatorname{fl}(a_{i1}\hat p_{k,1}),\dots,\operatorname{fl}(a_{in}\hat p_{k,n})の逐次和とし、 x^k+1,i:=fl⁡(x^k,i+fl⁡(α^kp^k,i)),r^k+1,i:=fl⁡(r^k,i−fl⁡(α^kwi))\hat x_{k+1,i}:=\operatorname{fl}\bigl(\hat x_{k,i}+\operatorname{fl}(\hat\alpha_k\hat p_{k,i})\bigr),\qquad\hat r_{k+1,i}:=\operatorname{fl}\bigl(\hat r_{k,i}-\operatorname{fl}(\hat\alpha_kw_i)\bigr) とする。この計算式の浮動小数点算術での実行が範囲条件（§E20.5 定義 1.1）を満たすならば、∣fk∣≤u∣x^k∣+γ2∣α^k∣∣p^k∣\lvert f_k\rvert\le u\lvert\hat x_k\rvert+\gamma_2\lvert\hat\alpha_k\rvert\lvert\hat p_k\rvertかつ∣gk∣≤u∣r^k∣+γn+2∣α^k∣∣A∣∣p^k∣\lvert g_k\rvert\le u\lvert\hat r_k\rvert+\gamma_{n+2}\lvert\hat\alpha_k\rvert\lvert A\rvert\lvert\hat p_k\rvertである。
  3. 1≤k≤K1\le k\le Kとし、0≤j<k0\le j<kのすべてのjjについて(2)の仮定が成り立つならば、 ∣sk−r^k∣≤∣s0−r^0∣+∑j=0k−1(u∣A∣∣x^j∣+u∣r^j∣+(γ2+γn+2)∣α^j∣∣A∣∣p^j∣)\lvert s_k-\hat r_k\rvert\le\lvert s_0-\hat r_0\rvert+\sum_{j=0}^{k-1}\Bigl(u\lvert A\rvert\lvert\hat x_j\rvert+u\lvert\hat r_j\rvert+(\gamma_2+\gamma_{n+2})\lvert\hat\alpha_j\rvert\lvert A\rvert\lvert\hat p_j\rvert\Bigr) である。

証明.(1)を示す。0≤j<k0\le j<kについてsj+1=b−A(x^j+α^jp^j+fj)=sj−α^jAp^j−Afjs_{j+1}=b-A(\hat x_j+\hat\alpha_j\hat p_j+f_j)=s_j-\hat\alpha_jA\hat p_j-Af_jであり、r^j+1=r^j−α^jAp^j+gj\hat r_{j+1}=\hat r_j-\hat\alpha_jA\hat p_j+g_jであるから、sj+1−r^j+1=sj−r^j−Afj−gjs_{j+1}-\hat r_{j+1}=s_j-\hat r_j-Af_j-g_jである。j=0,…,k−1j=0,\dots,k-1について和をとる。

(2)を示す。iiを固定する。範囲条件により積α^kp^k,i\hat\alpha_k\hat p_{k,i}の厳密な結果は00であるか正規範囲にあるので、§E20.1 系 3.2 (1)または§E20.1 系 3.2 (2)により∣δ1∣≤u\lvert\delta_1\rvert\le uを満たすδ1\delta_1が存在してfl⁡(α^kp^k,i)=α^kp^k,i(1+δ1)\operatorname{fl}(\hat\alpha_k\hat p_{k,i})=\hat\alpha_k\hat p_{k,i}(1+\delta_1)である。範囲条件により加算の厳密な結果の絶対値はNmax⁡N_{\max}以下であるから、§E20.1 系 3.3により∣δ2∣≤u\lvert\delta_2\rvert\le uを満たすδ2\delta_2が存在してx^k+1,i=(x^k,i+α^kp^k,i(1+δ1))(1+δ2)\hat x_{k+1,i}=(\hat x_{k,i}+\hat\alpha_k\hat p_{k,i}(1+\delta_1))(1+\delta_2)である。したがって

fk,i=x^k,iδ2+α^kp^k,i((1+δ1)(1+δ2)−1)f_{k,i}=\hat x_{k,i}\delta_2+\hat\alpha_k\hat p_{k,i}\bigl((1+\delta_1)(1+\delta_2)-1\bigr)

であり、2u<12u<1から§E20.1 補題 4.1により∣(1+δ1)(1+δ2)−1∣≤γ2\lvert(1+\delta_1)(1+\delta_2)-1\rvert\le\gamma_2であるので、fkf_kの評価が成り立つ。nu<1nu<1であるから、§E20.3 命題 5.1を加算木RnR_nとd=n−1d=n-1に適用して、∣θj∣≤γn\lvert\theta_j\rvert\le\gamma_nを満たすθ1,…,θn\theta_1,\dots,\theta_nが存在してwi=∑jaijp^k,j(1+θj)w_i=\sum_ja_{ij}\hat p_{k,j}(1+\theta_j)である。fkf_kと同じく§E20.1 系 3.2 (1)、§E20.1 系 3.2 (2)、§E20.1 系 3.3（減算は−fl⁡(α^kwi)∈F-\operatorname{fl}(\hat\alpha_kw_i)\in Fとの加算として適用する）により、∣δ3∣,∣δ4∣≤u\lvert\delta_3\rvert,\lvert\delta_4\rvert\le uを満たすδ3,δ4\delta_3,\delta_4が存在してr^k+1,i=(r^k,i−α^kwi(1+δ3))(1+δ4)\hat r_{k+1,i}=(\hat r_{k,i}-\hat\alpha_kw_i(1+\delta_3))(1+\delta_4)である。1+η:=(1+δ3)(1+δ4)1+\eta:=(1+\delta_3)(1+\delta_4)と置くと、§E20.1 補題 4.1により∣η∣≤γ2\lvert\eta\rvert\le\gamma_2であり、

gk,i=r^k,iδ4−α^k∑j=1naijp^k,j((1+θj)(1+η)−1)g_{k,i}=\hat r_{k,i}\delta_4-\hat\alpha_k\sum_{j=1}^na_{ij}\hat p_{k,j}\bigl((1+\theta_j)(1+\eta)-1\bigr)

である。(1−nu)(1−2u)=1−(n+2)u+2nu2≥1−(n+2)u>0(1-nu)(1-2u)=1-(n+2)u+2nu^2\ge1-(n+2)u>0であるから

∣(1+θj)(1+η)−1∣≤(1+γn)(1+γ2)−1=1(1−nu)(1−2u)−1≤11−(n+2)u−1=γn+2\bigl\lvert(1+\theta_j)(1+\eta)-1\bigr\rvert\le(1+\gamma_n)(1+\gamma_2)-1=\frac{1}{(1-nu)(1-2u)}-1\le\frac{1}{1-(n+2)u}-1=\gamma_{n+2}

であり、gkg_kの評価が成り立つ。

(3)を示す。(1)と三角不等式により∣sk−r^k∣≤∣s0−r^0∣+∑j<k(∣A∣∣fj∣+∣gj∣)\lvert s_k-\hat r_k\rvert\le\lvert s_0-\hat r_0\rvert+\sum_{j<k}(\lvert A\rvert\lvert f_j\rvert+\lvert g_j\rvert)であり、(2)の二つの評価を代入する。▨

例 5.2.注意 4.6 (1)の binary64 での計算を考え、丸めた対角成分をもつ行列をA^∈F24×24\hat A\in F^{24\times24}とし、binary64 で計算したx~k,rk,pk,αk\tilde x_k,r_k,p_k,\alpha_kをx^k,r^k,p^k,α^k\hat x_k,\hat r_k,\hat p_k,\hat\alpha_kと書く。x^k+1\hat x_{k+1}とr^k+1\hat r_{k+1}の更新は命題 5.1 (2)の計算式であり、A^\hat Aは対角行列であるから、wiw_iはfl⁡(a^iip^k,i)\operatorname{fl}(\hat a_{ii}\hat p_{k,i})に等しい。漸化式で更新した残差r^k\hat r_kと、計算した近似解x^k\hat x_kに対するA^\hat Aの真の残差b−A^x^kb-\hat A\hat x_k（有理数で計算した）の22-ノルムは、k=24k=24ではともに2.854×10−12.854\times10^{-1}、k=40k=40ではともに1.529×10−111.529\times10^{-11}である。k=46k=46では∥r^46∥2=2.96×10−16\lVert\hat r_{46}\rVert_2=2.96\times10^{-16}、∥b−A^x^46∥2=2.67×10−15\lVert b-\hat A\hat x_{46}\rVert_2=2.67\times10^{-15}であり、k=80k=80では∥r^80∥2=6.55×10−30\lVert\hat r_{80}\rVert_2=6.55\times10^{-30}、∥b−A^x^80∥2=2.51×10−15\lVert b-\hat A\hat x_{80}\rVert_2=2.51\times10^{-15}である。40≤k≤20040\le k\le200の範囲で真の残差の22-ノルムは2.47×10−152.47\times10^{-15}以上である。停止判定∥r^k∥2≤10−15\lVert\hat r_k\rVert_2\le10^{-15}はk=46k=46で初めて成り立つが、そのとき真の残差は10−1510^{-15}を超えている。

命題 5.3.n∈N≥1n\in\NNとし、A∈Rn×nA\in\R^{n\times n}を実対称正定値行列、λmin⁡\lambda_{\min}とλmax⁡\lambda_{\max}をAAの最小と最大の固有値、b∈Rnb\in\R^n、x:=A−1bx:=A^{-1}bとする。任意のx~∈Rn\tilde x\in\R^nについてr:=b−Ax~r:=b-A\tilde xと置く。

  1. ∥x−x~∥A≤λmin⁡−1/2∥r∥2\lVert x-\tilde x\rVert_A\le\lambda_{\min}^{-1/2}\lVert r\rVert_2かつ∥x−x~∥2≤λmin⁡−1∥r∥2\lVert x-\tilde x\rVert_2\le\lambda_{\min}^{-1}\lVert r\rVert_2である。
  2. b≠0b\ne0ならば∥x−x~∥2/∥x∥2≤(λmax⁡/λmin⁡)∥r∥2/∥b∥2\lVert x-\tilde x\rVert_2/\lVert x\rVert_2\le(\lambda_{\max}/\lambda_{\min})\lVert r\rVert_2/\lVert b\rVert_2である。

証明.(1)を示す。x−x~=A−1rx-\tilde x=A^{-1}rである。§D3.15 定理 3.1により直交行列PPとD=diag⁡(λ1,…,λn)D=\operatorname{diag}(\lambda_1,\dots,\lambda_n)が存在してA=PDPTA=PDP^{\mathsf T}であり、各λi\lambda_iはλi≥λmin⁡>0\lambda_i\ge\lambda_{\min}>0を満たす。s:=PTrs:=P^{\mathsf T}rと置くと∥s∥2=∥r∥2\lVert s\rVert_2=\lVert r\rVert_2であり、

∥x−x~∥A2=rTA−1r=∑i=1nsi2λi≤∥r∥22λmin⁡,∥x−x~∥22=∑i=1nsi2λi2≤∥r∥22λmin⁡2\lVert x-\tilde x\rVert_A^2=r^{\mathsf T}A^{-1}r=\sum_{i=1}^n\frac{s_i^2}{\lambda_i}\le\frac{\lVert r\rVert_2^2}{\lambda_{\min}},\qquad\lVert x-\tilde x\rVert_2^2=\sum_{i=1}^n\frac{s_i^2}{\lambda_i^2}\le\frac{\lVert r\rVert_2^2}{\lambda_{\min}^2}

である。

(2)は、§E20.5 命題 4.5をRn\R^nのノルム∥⋅∥2\lVert\cdot\rVert_2に適用し、§E20.5 命題 4.4 (5)によりκ2(A)=λmax⁡/λmin⁡\kappa_2(A)=\lambda_{\max}/\lambda_{\min}としたものである。▨

命題 5.4.FFを浮動小数点数系、uuをその単位丸め誤差、fl⁡\operatorname{fl}をFFの最近接丸めとし、n∈N≥1n\in\NNが(n+1)u<1(n+1)u<1を満たすとし、γn+1:=(n+1)u/(1−(n+1)u)\gamma_{n+1}:=(n+1)u/(1-(n+1)u)と置く。A∈Fn×nA\in F^{n\times n}を実対称正定値行列、b∈Fnb\in F^n、x:=A−1bx:=A^{-1}b、x~∈Fn\tilde x\in F^nとし、r~∈Fn\tilde r\in F^nを§E20.5 系 7.3の計算式でb−Ax~b-A\tilde xを計算した値とし、その計算の各積の厳密な結果が00であるか正規範囲にあり、各加算の厳密な結果の絶対値がNmax⁡N_{\max}以下であるとする。実数λ\lambdaが0<λ≤λmin⁡0<\lambda\le\lambda_{\min}（λmin⁡\lambda_{\min}はAAの最小固有値）を満たすとし、

η:=∥r~∥2+γn+1∥∣b∣+∣A∣∣x~∣∥2\eta:=\lVert\tilde r\rVert_2+\gamma_{n+1}\bigl\lVert\lvert b\rvert+\lvert A\rvert\lvert\tilde x\rvert\bigr\rVert_2

と置く（絶対値は成分ごとにとる）。このとき∥b−Ax~∥2≤η\lVert b-A\tilde x\rVert_2\le\eta、∥x−x~∥A≤λ−1/2η\lVert x-\tilde x\rVert_A\le\lambda^{-1/2}\eta、∥x−x~∥2≤λ−1η\lVert x-\tilde x\rVert_2\le\lambda^{-1}\etaである。特に、τ>0\tau>0についてη≤λ1/2τ\eta\le\lambda^{1/2}\tauならば∥x−x~∥A≤τ\lVert x-\tilde x\rVert_A\le\tauである。

証明.r:=b−Ax~r:=b-A\tilde xと置く。§E20.5 系 7.3により、各iiで∣r~i−ri∣≤γn+1(∣b∣+∣A∣∣x~∣)i\lvert\tilde r_i-r_i\rvert\le\gamma_{n+1}(\lvert b\rvert+\lvert A\rvert\lvert\tilde x\rvert)_iである。v,w∈Rnv,w\in\R^nが成分ごとに∣v∣≤∣w∣\lvert v\rvert\le\lvert w\rvertを満たすならば∥v∥2≤∥w∥2\lVert v\rVert_2\le\lVert w\rVert_2であるから∥r~−r∥2≤γn+1∥∣b∣+∣A∣∣x~∣∥2\lVert\tilde r-r\rVert_2\le\gamma_{n+1}\lVert\lvert b\rvert+\lvert A\rvert\lvert\tilde x\rvert\rVert_2であり、三角不等式により∥r∥2≤η\lVert r\rVert_2\le\etaである。命題 5.3 (1)とλmin⁡−1≤λ−1\lambda_{\min}^{-1}\le\lambda^{-1}により残りの評価が成り立つ。▨

6 演習

問題 6.1.n∈N≥1n\in\NNとし、A∈Rn×nA\in\R^{n\times n}を実対称正定値行列、b,x0∈Rnb,x_0\in\R^n、x:=A−1bx:=A^{-1}bとし、(xk)k∈N≥0(x_k)_{k\in\N}を共役勾配法の反復とする。実数0<λ−<λ+≤μ0<\lambda_-<\lambda_+\le\muがあって、AAの固有値の集合が[λ−,λ+]∪{μ}[\lambda_-,\lambda_+]\cup\{\mu\}に含まれるとする。任意のk∈N≥0k\in\Nについて

∥x−xk+1∥A≤2(λ+−λ−λ++λ−)k∥x−x0∥A\lVert x-x_{k+1}\rVert_A\le2\Bigl(\frac{\sqrt{\lambda_+}-\sqrt{\lambda_-}}{\sqrt{\lambda_+}+\sqrt{\lambda_-}}\Bigr)^k\lVert x-x_0\rVert_A

が成り立つことを示せ。

解答.

補題 4.1をλ−<λ+\lambda_-<\lambda_+とkkに適用して、次数kk以下でq(0)=1q(0)=1を満たし[λ−,λ+][\lambda_-,\lambda_+]上で∣q∣≤2zk\lvert q\rvert\le2z^k（z:=(λ+−λ−)/(λ++λ−)z:=(\sqrt{\lambda_+}-\sqrt{\lambda_-})/(\sqrt{\lambda_+}+\sqrt{\lambda_-})）を満たす実係数多項式qqをとる。Q(t):=(1−t/μ)q(t)Q(t):=(1-t/\mu)q(t)と置くと、QQは次数k+1k+1以下の実係数多項式でQ(0)=1Q(0)=1を満たし、Q(μ)=0Q(\mu)=0である。t∈[λ−,λ+]t\in[\lambda_-,\lambda_+]ならば0<t≤μ0<t\le\muから0≤1−t/μ<10\le1-t/\mu<1であり、∣Q(t)∣≤∣q(t)∣≤2zk\lvert Q(t)\rvert\le\lvert q(t)\rvert\le2z^kである。AAの固有値の集合Λ\Lambdaは[λ−,λ+]∪{μ}[\lambda_-,\lambda_+]\cup\{\mu\}に含まれるからmax⁡λ∈Λ∣Q(λ)∣≤2zk\max_{\lambda\in\Lambda}\lvert Q(\lambda)\rvert\le2z^kであり、定理 4.2 (1)と定理 4.2 (2)により∥x−xk+1∥A≤∥Q(A)(x−x0)∥A≤2zk∥x−x0∥A\lVert x-x_{k+1}\rVert_A\le\lVert Q(A)(x-x_0)\rVert_A\le2z^k\lVert x-x_0\rVert_Aである。▨

前提記事