§E20.10定常反復法

最終更新

正則な係数行列AAをもつ連立一次方程式Ax=bAx=bについて、AAを正則行列MMと行列NNの差A=M−NA=M-Nに分け、この分け方を固定して、係数行列がMMの方程式Mxk+1=Nxk+bMx_{k+1}=Nx_k+bを解いて近似解xkx_kからxk+1x_{k+1}を定める計算を繰り返す方法を定常反復法という。AAの対角成分がすべて00でないとき、MMとしてAAの対角部分をとるものが Jacobi 法、下三角部分をとるものが Gauss–Seidel 法であり、各段の方程式は一つの成分の式から順に解くことができる。しかし、こうして定まる列は解x∗=A−1bx^*=A^{-1}bに収束するとは限らない。任意の初期値から解へ収束することは、反復行列M−1NM^{-1}Nのスペクトル半径が11未満であることと同値である。

収束するかどうかとその速さは、分け方とAAの性質によって決まる。対角成分が22、隣接成分が−1-1のnn次三重対角行列では、Jacobi 法の反復行列のスペクトル半径はcos⁡(π/(n+1))\cos(\pi/(n+1))、Gauss–Seidel 法の反復行列のスペクトル半径はその二乗であり、いずれもn→∞n\to\inftyのとき11に収束する。0<θ<10<\theta<1を固定すると、すべての誤差ベクトルのノルムをθ\theta倍以下に縮めるのに要する反復回数の下界は、nnが大きいときおよそ(n+1)2(n+1)^2に比例して増える。

本記事では、定常反復法の収束の条件と、代表的な行列に対する収束の速さについて解説する。

1 分裂と反復行列

定義 1.1.K∈{R,C}\mathbb K\in\{\R,\C\}、n∈N≥1n\in\NNとし、A=(aij)∈Kn×nA=(a_{ij})\in\mathbb K^{n\times n}、b∈Knb\in\mathbb K^nとする。

  1. AAが正則であり、M,N∈Kn×nM,N\in\mathbb K^{n\times n}がA=M−NA=M-Nを満たし、MMが正則であるとき、組(M,N)(M,N)をAAの 分裂 (splitting) といい、T:=M−1NT:=M^{-1}Nを分裂(M,N)(M,N)の 反復行列 (iteration matrix) という。x0∈Knx_0\in\mathbb K^nから始めてk≥0k\ge0についてxk+1:=Txk+M−1bx_{k+1}:=Tx_k+M^{-1}bと置き、列(xk)k≥0(x_k)_{k\ge0}を定める計算式を、分裂(M,N)(M,N)によるAx=bAx=bの 定常反復法 (stationary iterative method) という。xk+1x_{k+1}はMxk+1=Nxk+bMx_{k+1}=Nx_k+bのただ一つの解である。
  2. DDを対角成分がa11,…,anna_{11},\dots,a_{nn}の対角行列、EEをi>ji>jの(i,j)(i,j)成分が−aij-a_{ij}でその他の成分が00の行列、FFをi<ji<jの(i,j)(i,j)成分が−aij-a_{ij}でその他の成分が00の行列とし、A=D−E−FA=D-E-Fと書く。AAが正則で対角成分がすべて00でないとし、ω∈R∖{0}\omega\in\R\setminus\{0\}とする。分裂(D,E+F)(D,E+F)による定常反復法を Jacobi 法 (Jacobi method) といい、その反復行列をTJT_{\mathrm J}と書く。分裂(D−E,F)(D-E,F)による定常反復法を Gauss–Seidel 法 (Gauss–Seidel method) といい、その反復行列をTGST_{\mathrm{GS}}と書く。分裂(ω−1D−E, ω−1(1−ω)D+F)(\omega^{-1}D-E,\ \omega^{-1}(1-\omega)D+F)による定常反復法を緩和係数ω\omegaの SOR 法 (successive over-relaxation method) といい、その反復行列をTωT_\omegaと書く。三つの組の第一成分は対角成分が00でない三角行列であるから正則であり、三つの組はいずれも差がAAに等しいので、いずれもAAの分裂である。T1=TGST_1=T_{\mathrm{GS}}である。
  3. 任意のiiについて∣aii∣>∑j≠i∣aij∣\lvert a_{ii}\rvert>\sum_{j\ne i}\lvert a_{ij}\rvertが成り立つとき、AAは 狭義行対角優位 (strictly row diagonally dominant) であるという。

補題 1.2.K∈{R,C}\mathbb K\in\{\R,\C\}、n∈N≥1n\in\NNとし、A=(aij)∈Kn×nA=(a_{ij})\in\mathbb K^{n\times n}を正則行列、b∈Knb\in\mathbb K^nとする。列(xk)k≥0(x_k)_{k\ge0}のxkx_kの第ii成分をxk,ix_{k,i}と書く。

  1. (M,N)(M,N)をAAの分裂とすると、分裂(M,N)(M,N)による定常反復法の列は、任意のk≥0k\ge0についてxk+1=xk+M−1(b−Axk)x_{k+1}=x_k+M^{-1}(b-Ax_k)を満たす。
  2. AAの対角成分がすべて00でないとし、ω∈R∖{0}\omega\in\R\setminus\{0\}とする。緩和係数ω\omegaの SOR 法の列は、任意のk≥0k\ge0と1≤i≤n1\le i\le nについて xk+1,i=xk,i+ωaii(bi−∑j<iaijxk+1,j−∑j≥iaijxk,j)x_{k+1,i}=x_{k,i}+\frac{\omega}{a_{ii}}\Bigl(b_i-\sum_{j<i}a_{ij}x_{k+1,j}-\sum_{j\ge i}a_{ij}x_{k,j}\Bigr) を満たす。右辺はxk+1x_{k+1}の第11成分から第i−1i-1成分だけを含むので、この式をi=1,…,ni=1,\dots,nの順に用いるとxkx_kからxk+1x_{k+1}が定まる。ω=1\omega=1として、Gauss–Seidel 法の列も同じ式を満たす。
  3. AAの対角成分がすべて00でないとする。Jacobi 法の列は、任意のk≥0k\ge0と1≤i≤n1\le i\le nについて xk+1,i=xk,i+1aii(bi−∑j=1naijxk,j)x_{k+1,i}=x_{k,i}+\frac{1}{a_{ii}}\Bigl(b_i-\sum_{j=1}^na_{ij}x_{k,j}\Bigr) を満たす。

証明.(1)を示す。Mxk+1=Nxk+b=(M−A)xk+bMx_{k+1}=Nx_k+b=(M-A)x_k+bであるからM(xk+1−xk)=b−AxkM(x_{k+1}-x_k)=b-Ax_kであり、両辺に左からM−1M^{-1}を掛けて主張を得る。

(2)を示す。δ:=xk+1−xk\delta:=x_{k+1}-x_kと置く。(1)により(ω−1D−E)δ=b−Axk(\omega^{-1}D-E)\delta=b-Ax_kであり、この等式の第ii成分は

ω−1aiiδi+∑j<iaijδj=bi−∑j=1naijxk,j\omega^{-1}a_{ii}\delta_i+\sum_{j<i}a_{ij}\delta_j=b_i-\sum_{j=1}^na_{ij}x_{k,j}

である。δj=xk+1,j−xk,j\delta_j=x_{k+1,j}-x_{k,j}を左辺の和に代入して移項するとω−1aiiδi=bi−∑j<iaijxk+1,j−∑j≥iaijxk,j\omega^{-1}a_{ii}\delta_i=b_i-\sum_{j<i}a_{ij}x_{k+1,j}-\sum_{j\ge i}a_{ij}x_{k,j}であり、両辺にω/aii\omega/a_{ii}を掛けて主張の式を得る。

(3)を示す。(1)を分裂(D,E+F)(D,E+F)に適用するとD(xk+1−xk)=b−AxkD(x_{k+1}-x_k)=b-Ax_kであり、その第ii成分をaiia_{ii}で割って主張の式を得る。▨

注意 1.3.n∈N≥1n\in\NNとし、A∈Rn×nA\in\R^{n\times n}とG∈Rn×nG\in\R^{n\times n}を正則行列、b∈Rnb\in\R^nとする。(G−1,G−1−A)(G^{-1},G^{-1}-A)はAAの分裂であり、その反復行列はG(G−1−A)=I−GAG(G^{-1}-A)=I-GAである。補題 1.2 (1)により、この分裂による定常反復法の列はxk+1=xk+G(b−Axk)x_{k+1}=x_k+G(b-Ax_k)を満たし、§E20.5 命題 7.1 (1)の反復でM:=GM:=Gとしたものに一致する。

2 スペクトル半径と行列の冪

補題 2.1.n∈N≥1n\in\NN、T∈Cn×nT\in\C^{n\times n}とし、ρ(T)\rho(T)をTTのスペクトル半径とする。

  1. Cn\C^nの任意のノルム∥⋅∥\lVert\cdot\rVertについて、TTの作用素ノルム（§E20.5 定義 4.2）はρ(T)≤∥T∥\rho(T)\le\lVert T\rVertを満たす。
  2. 任意のε>0\varepsilon>0に対して正則行列S∈Cn×nS\in\C^{n\times n}が存在して、Cn\C^nのノルム∥h∥S:=max⁡1≤i≤n∣(Sh)i∣\lVert h\rVert_S:=\max_{1\le i\le n}\lvert(Sh)_i\rvertに関する作用素ノルムが∥T∥S≤ρ(T)+ε\lVert T\rVert_S\le\rho(T)+\varepsilonを満たす。

さらに、次の三条件は同値である。

  1. k→∞k\to\inftyのときTkT^kの各成分が00に収束する。
  2. 任意のx∈Cnx\in\C^nについて、k→∞k\to\inftyのときTkxT^kxの各成分が00に収束する。
  3. ρ(T)<1\rho(T)<1が成り立つ。

証明.(1)を示す。λ∈C\lambda\in\Cがdet⁡(λI−T)=0\det(\lambda I-T)=0を満たすとし、z∈Cn∖{0}z\in\C^n\setminus\{0\}をTz=λzTz=\lambda zを満たすベクトルとする。作用素ノルムの定義により∥T(z/∥z∥)∥≤∥T∥\lVert T(z/\lVert z\rVert)\rVert\le\lVert T\rVertであるから、∣λ∣=∥Tz∥/∥z∥≤∥T∥\lvert\lambda\rvert=\lVert Tz\rVert/\lVert z\rVert\le\lVert T\rVertである。λ\lambdaはTTの任意の固有値であるから、ρ(T)≤∥T∥\rho(T)\le\lVert T\rVertである。

(2)を示す。§E3.36 系 2.2により、ユニタリ行列QQと上三角行列R=(rij)R=(r_{ij})が存在してT=QRQ∗T=QRQ^*である。det⁡(λI−T)=det⁡(λI−R)=∏i(λ−rii)\det(\lambda I-T)=\det(\lambda I-R)=\prod_i(\lambda-r_{ii})であるから、ρ(T)=max⁡i∣rii∣\rho(T)=\max_i\lvert r_{ii}\rvertである。c:=max⁡i∑j>i∣rij∣c:=\max_i\sum_{j>i}\lvert r_{ij}\rvert、δ:=min⁡{1, ε/(c+1)}\delta:=\min\{1,\ \varepsilon/(c+1)\}、Δ:=diag⁡(1,δ,…,δn−1)\Delta:=\operatorname{diag}(1,\delta,\dots,\delta^{n-1})、S:=Δ−1Q∗S:=\Delta^{-1}Q^*と置く。SSは正則であるから、∥⋅∥S\lVert\cdot\rVert_SはCn\C^nのノルムである。R~:=Δ−1RΔ\widetilde R:=\Delta^{-1}R\Deltaの(i,j)(i,j)成分は、i≤ji\le jならばrijδj−ir_{ij}\delta^{j-i}、i>ji>jならば00である。0<δ≤10<\delta\le1であるから、各iiについて

∑j=1n∣r~ij∣≤∣rii∣+δ∑j>i∣rij∣≤ρ(T)+δc≤ρ(T)+ε\sum_{j=1}^n\lvert\widetilde r_{ij}\rvert\le\lvert r_{ii}\rvert+\delta\sum_{j>i}\lvert r_{ij}\rvert\le\rho(T)+\delta c\le\rho(T)+\varepsilon

である。h∈Cnh\in\C^nに対してg:=Shg:=Shと置くと、STh=Δ−1RQ∗h=R~gSTh=\Delta^{-1}RQ^*h=\widetilde Rgであるから

∥Th∥S=max⁡i∣∑jr~ijgj∣≤(max⁡i∑j∣r~ij∣)max⁡j∣gj∣≤(ρ(T)+ε)∥h∥S\lVert Th\rVert_S=\max_i\Bigl\lvert\sum_j\widetilde r_{ij}g_j\Bigr\rvert\le\Bigl(\max_i\sum_j\lvert\widetilde r_{ij}\rvert\Bigr)\max_j\lvert g_j\rvert\le(\rho(T)+\varepsilon)\lVert h\rVert_S

である。したがって∥T∥S≤ρ(T)+ε\lVert T\rVert_S\le\rho(T)+\varepsilonである。

(3)⇒\Rightarrow(1)を示す。ρ(T)<1\rho(T)<1とし、(2)をε:=(1−ρ(T))/2\varepsilon:=(1-\rho(T))/2に適用してSSをとる。q:=(1+ρ(T))/2q:=(1+\rho(T))/2と置くとq<1q<1かつ∥T∥S≤q\lVert T\rVert_S\le qであるから、kkに関する帰納法により、任意のh∈Cnh\in\C^nとk≥0k\ge0について∥Tkh∥S≤qk∥h∥S\lVert T^kh\rVert_S\le q^k\lVert h\rVert_Sである。S−1=(sij′)S^{-1}=(s'_{ij})、c′:=max⁡i∑j∣sij′∣c':=\max_i\sum_j\lvert s'_{ij}\rvertと置くと、h=S−1(Sh)h=S^{-1}(Sh)から、任意のhhとiiについて∣hi∣≤c′∥h∥S\lvert h_i\rvert\le c'\lVert h\rVert_Sである。eje_jを第jj基本ベクトルとすると、TkT^kの(i,j)(i,j)成分はTkejT^ke_jの第ii成分であり、その絶対値はc′qk∥ej∥Sc'q^k\lVert e_j\rVert_S以下であるから、k→∞k\to\inftyのとき00に収束する。

(1)⇒\Rightarrow(2)は、(Tkx)i=∑j(Tk)ijxj(T^kx)_i=\sum_j(T^k)_{ij}x_jから従う。

(2)⇒\Rightarrow(3)を示す。ρ(T)≥1\rho(T)\ge1とし、∣λ∣≥1\lvert\lambda\rvert\ge1を満たすTTの固有値λ\lambdaと、Tz=λzTz=\lambda zを満たすz∈Cn∖{0}z\in\C^n\setminus\{0\}をとる。zi≠0z_i\ne0を満たすiiについて∣(Tkz)i∣=∣λ∣k∣zi∣≥∣zi∣>0\lvert(T^kz)_i\rvert=\lvert\lambda\rvert^k\lvert z_i\rvert\ge\lvert z_i\rvert>0であるから、TkzT^kzの第ii成分は00に収束しない。したがってρ(T)≥1\rho(T)\ge1ならば(2)は成り立たない。▨

3 定常反復法の収束

定理 3.1.K∈{R,C}\mathbb K\in\{\R,\C\}、n∈N≥1n\in\NNとし、A∈Kn×nA\in\mathbb K^{n\times n}を正則行列、b∈Knb\in\mathbb K^n、x∗:=A−1bx^*:=A^{-1}bとする。(M,N)(M,N)をAAの分裂、T:=M−1NT:=M^{-1}Nをその反復行列とし、x0∈Knx_0\in\mathbb K^nから分裂(M,N)(M,N)による定常反復法で定まる列を(xk)k≥0(x_k)_{k\ge0}とする。

  1. 任意のk≥0k\ge0についてxk−x∗=Tk(x0−x∗)x_k-x^*=T^k(x_0-x^*)が成り立つ。
  2. 任意のε>0\varepsilon>0に対してCn\C^nのノルム∥⋅∥\lVert\cdot\rVertが存在して、任意のx0∈Knx_0\in\mathbb K^nとk≥0k\ge0について∥xk−x∗∥≤(ρ(T)+ε)k∥x0−x∗∥\lVert x_k-x^*\rVert\le(\rho(T)+\varepsilon)^k\lVert x_0-x^*\rVertが成り立つ。

さらに、Kn\mathbb K^nの列の収束を成分ごとの収束として、次の三条件は同値である。

  1. ρ(T)<1\rho(T)<1が成り立つ。
  2. 任意のx0∈Knx_0\in\mathbb K^nについて、k→∞k\to\inftyのときxk→x∗x_k\to x^*が成り立つ。
  3. 任意のx0∈Knx_0\in\mathbb K^nについて、列(xk)(x_k)がKn\mathbb K^nで収束する。

証明.(1)を示す。Mx∗−Nx∗=Ax∗=bMx^*-Nx^*=Ax^*=bであるからx∗=Tx∗+M−1bx^*=Tx^*+M^{-1}bである。xk+1=Txk+M−1bx_{k+1}=Tx_k+M^{-1}bからこの等式を引くとxk+1−x∗=T(xk−x∗)x_{k+1}-x^*=T(x_k-x^*)であり、kkに関する帰納法により主張が成り立つ。

(2)を示す。TTをCn×n\C^{n\times n}の元とみて補題 2.1 (2)を適用し、SSをとる。∥⋅∥:=∥⋅∥S\lVert\cdot\rVert:=\lVert\cdot\rVert_Sはx0x_0とkkによらず、任意のh∈Cnh\in\C^nについて∥Th∥≤(ρ(T)+ε)∥h∥\lVert Th\rVert\le(\rho(T)+\varepsilon)\lVert h\rVertを満たす。この不等式をkk回用いると∥Tkh∥≤(ρ(T)+ε)k∥h∥\lVert T^kh\rVert\le(\rho(T)+\varepsilon)^k\lVert h\rVertであり、h:=x0−x∗h:=x_0-x^*として(1)から主張を得る。

(1)⇒\Rightarrow(2)を示す。ρ(T)<1\rho(T)<1とし、x0∈Knx_0\in\mathbb K^nとする。補題 2.1 (3)⇒\Rightarrow(2)をx:=x0−x∗x:=x_0-x^*に適用すると、Tk(x0−x∗)T^k(x_0-x^*)の各成分は00に収束する。(1)によりxk→x∗x_k\to x^*である。

(2)⇒\Rightarrow(3)は、x∗x^*が列の極限であることから従う。

(3)⇒\Rightarrow(1)を示す。(3)を仮定する。x0∈Knx_0\in\mathbb K^nとし、(xk)(x_k)の極限をy∈Kny\in\mathbb K^nとする。Txk+M−1bTx_k+M^{-1}bの各成分はxkx_kの成分の一次式であるから、xk+1=Txk+M−1bx_{k+1}=Tx_k+M^{-1}bでk→∞k\to\inftyとするとy=Ty+M−1by=Ty+M^{-1}bである。両辺に左からMMを掛けるとMy=Ny+bMy=Ny+bであり、Ay=(M−N)y=bAy=(M-N)y=bである。AAは正則であるからy=x∗y=x^*である。e∈Kne\in\mathbb K^nとし、x0:=x∗+ex_0:=x^*+eとすると、(1)とxk→x∗x_k\to x^*によりTkeT^keの各成分は00に収束する。K=C\mathbb K=\Cならば、これは補題 2.1 (2)である。K=R\mathbb K=\Rならば、M−1M^{-1}とNNは実行列であるからTTは実行列であり、w∈Cnw\in\C^nをw=u+ivw=u+iv（u,v∈Rnu,v\in\R^n）と書くとTkw=Tku+iTkvT^kw=T^ku+iT^kvの各成分は00に収束するので、補題 2.1 (2)が成り立つ。いずれの場合も、補題 2.1 (2)⇒\Rightarrow(3)によりρ(T)<1\rho(T)<1である。▨

注意 3.2.ρ(T)≥1\rho(T)\ge1であっても、特定のx0x_0からの列はx∗x^*に収束することがある。実際、TTの固有値λ\lambdaが∣λ∣<1\lvert\lambda\rvert<1を満たし、x0−x∗x_0-x^*がλ\lambdaに対する固有ベクトルならば、定理 3.1 (1)によりxk−x∗=λk(x0−x∗)x_k-x^*=\lambda^k(x_0-x^*)であり、xk→x∗x_k\to x^*である。例としてA:=diag⁡(1/2,−1)∈R2×2A:=\operatorname{diag}(1/2,-1)\in\R^{2\times2}、M:=IM:=I、N:=I−A=diag⁡(1/2,2)N:=I-A=\operatorname{diag}(1/2,2)とすると、(M,N)(M,N)はAAの分裂であり、T=diag⁡(1/2,2)T=\operatorname{diag}(1/2,2)、ρ(T)=2\rho(T)=2である。任意のb∈R2b\in\R^2とx0∈R2x_0\in\R^2についてx0−x∗=(s,t)Tx_0-x^*=(s,t)^{\mathsf T}と書くと、定理 3.1 (1)によりxk−x∗=(2−ks, 2kt)Tx_k-x^*=(2^{-k}s,\ 2^kt)^{\mathsf T}である。t=0t=0ならばxk→x∗x_k\to x^*であり、t≠0t\ne0ならばxkx_kの第22成分は有界でなく、(xk)(x_k)は収束しない。

例 3.3.A:=(1/2−201/2)∈R2×2A:=\begin{pmatrix}1/2&-2\\0&1/2\end{pmatrix}\in\R^{2\times2}、M:=IM:=I、N:=I−A=(1/2201/2)N:=I-A=\begin{pmatrix}1/2&2\\0&1/2\end{pmatrix}とする。det⁡A=1/4≠0\det A=1/4\ne0であるからAAは正則であり、MMは正則でM−N=AM-N=Aであるから、(M,N)(M,N)はAAの分裂である。その反復行列はT=NT=Nであり、det⁡(λI−T)=(λ−1/2)2\det(\lambda I-T)=(\lambda-1/2)^2であるからρ(T)=1/2\rho(T)=1/2である。kkに関する帰納法により、任意のk≥0k\ge0について

Tk=(2−k4k 2−k02−k)T^k=\begin{pmatrix}2^{-k}&4k\,2^{-k}\\0&2^{-k}\end{pmatrix}

である。実際、k=0k=0では両辺がIIであり、Tk+1=TkTT^{k+1}=T^kTの(1,2)(1,2)成分は2−k⋅2+4k 2−k⋅2−1=4(k+1)2−(k+1)2^{-k}\cdot2+4k\,2^{-k}\cdot2^{-1}=4(k+1)2^{-(k+1)}、その他の成分は2−(k+1)2^{-(k+1)}または00である。b∈R2b\in\R^2、x∗:=A−1bx^*:=A^{-1}b、e2:=(0,1)Te_2:=(0,1)^{\mathsf T}とし、x0:=x∗+e2x_0:=x^*+e_2から分裂(M,N)(M,N)による定常反復法で列(xk)k≥0(x_k)_{k\ge0}を定める。定理 3.1 (1)によりxk−x∗=Tke2=(4k 2−k, 2−k)Tx_k-x^*=T^ke_2=(4k\,2^{-k},\ 2^{-k})^{\mathsf T}である。h∈C2h\in\C^2について∥h∥∞:=max⁡{∣h1∣,∣h2∣}\lVert h\rVert_\infty:=\max\{\lvert h_1\rvert,\lvert h_2\rvert\}、∥h∥2:=(∣h1∣2+∣h2∣2)1/2\lVert h\rVert_2:=(\lvert h_1\rvert^2+\lvert h_2\rvert^2)^{1/2}と置くと、∥xk−x∗∥∞\lVert x_k-x^*\rVert_\inftyはk=0,1,2,3,4k=0,1,2,3,4で1, 2, 2, 3/2, 11,\ 2,\ 2,\ 3/2,\ 1であり、k=1,2,3k=1,2,3で∥x0−x∗∥∞=1\lVert x_0-x^*\rVert_\infty=1より大きい。また∥x0−x∗∥2=1\lVert x_0-x^*\rVert_2=1、∥x1−x∗∥2=17/2>2\lVert x_1-x^*\rVert_2=\sqrt{17}/2>2である。0<ε<3/20<\varepsilon<3/2とする。∥⋅∥\lVert\cdot\rVertが∥⋅∥∞\lVert\cdot\rVert_\inftyと∥⋅∥2\lVert\cdot\rVert_2のいずれであっても、上のx0x_0について∥x1−x∗∥≥2>ρ(T)+ε=(ρ(T)+ε)∥x0−x∗∥\lVert x_1-x^*\rVert\ge2>\rho(T)+\varepsilon=(\rho(T)+\varepsilon)\lVert x_0-x^*\rVertであるから、定理 3.1 (2)の不等式はk=1k=1で成り立たない。したがって∥⋅∥∞\lVert\cdot\rVert_\inftyと∥⋅∥2\lVert\cdot\rVert_2は、このε\varepsilonに対して定理 3.1 (2)が存在を主張するノルムではない。一方、ρ(T)<1\rho(T)<1であるから、定理 3.1 (1)⇒\Rightarrow(2)により、任意のx0∈R2x_0\in\R^2についてxk→x∗x_k\to x^*である。

4 収束の判定条件

補題 4.1.n∈N≥1n\in\NNとし、A∈Rn×nA\in\R^{n\times n}を実対称かつ正定値な行列、(M,N)(M,N)をM,N∈Rn×nM,N\in\R^{n\times n}によるAAの分裂とする。実対称行列M+MT−AM+M^{\mathsf T}-Aが正定値ならば、ρ(M−1N)<1\rho(M^{-1}N)<1である。

証明. 実対称かつ正定値なB∈Rn×nB\in\R^{n\times n}とz=u+iv∈Cn∖{0}z=u+iv\in\C^n\setminus\{0\}（u,v∈Rnu,v\in\R^n）について、uTBv=vTBuu^{\mathsf T}Bv=v^{\mathsf T}Buであるからz∗Bz=uTBu+vTBv>0z^*Bz=u^{\mathsf T}Bu+v^{\mathsf T}Bv>0である。T:=M−1NT:=M^{-1}Nの固有値λ\lambdaと、Tz=λzTz=\lambda zを満たすz∈Cn∖{0}z\in\C^n\setminus\{0\}をとり、w:=M−1Azw:=M^{-1}Azと置く。T=M−1(M−A)=I−M−1AT=M^{-1}(M-A)=I-M^{-1}AであるからTz=z−wTz=z-wであり、w=(1−λ)zw=(1-\lambda)zである。AAは正定値であるから正則であり、Az≠0Az\ne0からw≠0w\ne0である。Az=MwAz=Mwからw∗Az=w∗Mww^*Az=w^*Mwである。AAは実対称であるからz∗Aw=w∗Az‾=w∗Mw‾=w∗MTwz^*Aw=\overline{w^*Az}=\overline{w^*Mw}=w^*M^{\mathsf T}wである。よって

z∗Az−(z−w)∗A(z−w)=w∗Az+z∗Aw−w∗Aw=w∗(M+MT−A)w>0z^*Az-(z-w)^*A(z-w)=w^*Az+z^*Aw-w^*Aw=w^*(M+M^{\mathsf T}-A)w>0

である。z−w=λzz-w=\lambda zであるから左辺は(1−∣λ∣2)z∗Az(1-\lvert\lambda\rvert^2)z^*Azであり、z∗Az>0z^*Az>0から∣λ∣<1\lvert\lambda\rvert<1である。λ\lambdaはTTの任意の固有値であるから、ρ(T)<1\rho(T)<1である。▨

命題 4.2.n∈N≥1n\in\NN、A=(aij)∈Cn×nA=(a_{ij})\in\C^{n\times n}とし、A=D−E−FA=D-E-Fを定義 1.1 (2)の分解とする。

  1. AAが狭義行対角優位ならば、AAは正則で対角成分はすべて00でなく、 ρ(TJ)≤max⁡1≤i≤n1∣aii∣∑j≠i∣aij∣<1,ρ(TGS)<1\rho(T_{\mathrm J})\le\max_{1\le i\le n}\frac{1}{\lvert a_{ii}\rvert}\sum_{j\ne i}\lvert a_{ij}\rvert<1,\qquad\rho(T_{\mathrm{GS}})<1 が成り立つ。
  2. A∈Rn×nA\in\R^{n\times n}が実対称かつ正定値であり、0<ω<20<\omega<2ならば、AAは正則で対角成分はすべて正であり、ρ(Tω)<1\rho(T_\omega)<1である。特にρ(TGS)<1\rho(T_{\mathrm{GS}})<1である。
  3. AAが正則で対角成分がすべて00でなく、ω∈R∖{0}\omega\in\R\setminus\{0\}ならば、det⁡Tω=(1−ω)n\det T_\omega=(1-\omega)^nかつρ(Tω)≥∣1−ω∣\rho(T_\omega)\ge\lvert1-\omega\rvertである。したがってρ(Tω)<1\rho(T_\omega)<1ならば0<ω<20<\omega<2である。
  4. AAが正則で対角成分がすべて00でなく、∣i−j∣≥2\lvert i-j\rvert\ge2ならばaij=0a_{ij}=0であるとする。任意のμ∈C\mu\in\Cについて det⁡(μ2I−TGS)=μndet⁡(μI−TJ)\det(\mu^2I-T_{\mathrm{GS}})=\mu^n\det(\mu I-T_{\mathrm J}) が成り立ち、ρ(TGS)=ρ(TJ)2\rho(T_{\mathrm{GS}})=\rho(T_{\mathrm J})^2である。

証明.(1)を示す。AAが狭義行対角優位であるとする。∣aii∣>∑j≠i∣aij∣≥0\lvert a_{ii}\rvert>\sum_{j\ne i}\lvert a_{ij}\rvert\ge0からaii≠0a_{ii}\ne0である。q:=max⁡i∣aii∣−1∑j≠i∣aij∣q:=\max_i\lvert a_{ii}\rvert^{-1}\sum_{j\ne i}\lvert a_{ij}\rvertと置くとq<1q<1である。J:=D−1(E+F)J:=D^{-1}(E+F)の(i,j)(i,j)成分は、i≠ji\ne jならば−aij/aii-a_{ij}/a_{ii}、i=ji=jならば00である。Cn\C^nのノルム∥h∥∞:=max⁡i∣hi∣\lVert h\rVert_\infty:=\max_i\lvert h_i\rvertについて∣(Jh)i∣≤∣aii∣−1∑j≠i∣aij∣∣hj∣≤q∥h∥∞\lvert(Jh)_i\rvert\le\lvert a_{ii}\rvert^{-1}\sum_{j\ne i}\lvert a_{ij}\rvert\lvert h_j\rvert\le q\lVert h\rVert_\inftyであるから、JJの作用素ノルムはqq以下であり、補題 2.1 (1)によりρ(J)≤q<1\rho(J)\le q<1である。特に11はJJの固有値でなく、I−JI-Jは正則であるから、A=D(I−J)A=D(I-J)は正則である。したがって(D,E+F)(D,E+F)はAAの分裂であり、TJ=JT_{\mathrm J}=Jである。λ\lambdaをTGST_{\mathrm{GS}}の固有値とし、∣λ∣≥1\lvert\lambda\rvert\ge1と仮定する。TGSz=λzT_{\mathrm{GS}}z=\lambda zを満たすz∈Cn∖{0}z\in\C^n\setminus\{0\}をとるとFz=λ(D−E)zFz=\lambda(D-E)zであり、その第ii成分は

λaiizi=−λ∑j<iaijzj−∑j>iaijzj\lambda a_{ii}z_i=-\lambda\sum_{j<i}a_{ij}z_j-\sum_{j>i}a_{ij}z_j

である。∣zi∣=max⁡j∣zj∣>0\lvert z_i\rvert=\max_j\lvert z_j\rvert>0を満たすiiをとると、∣λ∣≥1\lvert\lambda\rvert\ge1から

∣λ∣∣aii∣∣zi∣≤∣λ∣∑j<i∣aij∣∣zi∣+∑j>i∣aij∣∣zi∣≤∣λ∣∑j≠i∣aij∣∣zi∣\lvert\lambda\rvert\lvert a_{ii}\rvert\lvert z_i\rvert\le\lvert\lambda\rvert\sum_{j<i}\lvert a_{ij}\rvert\lvert z_i\rvert+\sum_{j>i}\lvert a_{ij}\rvert\lvert z_i\rvert\le\lvert\lambda\rvert\sum_{j\ne i}\lvert a_{ij}\rvert\lvert z_i\rvert

であり、∣aii∣≤∑j≠i∣aij∣\lvert a_{ii}\rvert\le\sum_{j\ne i}\lvert a_{ij}\rvertを得る。これは∣aii∣>∑j≠i∣aij∣\lvert a_{ii}\rvert>\sum_{j\ne i}\lvert a_{ij}\rvertと両立しない。したがってTGST_{\mathrm{GS}}の固有値の絶対値はすべて11未満であり、ρ(TGS)<1\rho(T_{\mathrm{GS}})<1である。

(2)を示す。AAは正定値であるから正則であり、aii=eiTAei>0a_{ii}=e_i^{\mathsf T}Ae_i>0である。AT=AA^{\mathsf T}=AからF=ETF=E^{\mathsf T}である。M:=ω−1D−EM:=\omega^{-1}D-Eと置くと

M+MT−A=2ω−1D−E−ET−(D−E−ET)=(2ω−1−1)DM+M^{\mathsf T}-A=2\omega^{-1}D-E-E^{\mathsf T}-(D-E-E^{\mathsf T})=(2\omega^{-1}-1)D

である。0<ω<20<\omega<2から2ω−1−1>02\omega^{-1}-1>0であり、(2ω−1−1)D(2\omega^{-1}-1)Dは対角成分が正の対角行列であるから正定値である。補題 4.1によりρ(Tω)<1\rho(T_\omega)<1である。ω=1\omega=1としてρ(TGS)<1\rho(T_{\mathrm{GS}})<1である。

(3)を示す。ω−1D−E\omega^{-1}D-Eは対角成分がω−1aii\omega^{-1}a_{ii}の下三角行列、ω−1(1−ω)D+F\omega^{-1}(1-\omega)D+Fは対角成分がω−1(1−ω)aii\omega^{-1}(1-\omega)a_{ii}の上三角行列であるから、

det⁡Tω=det⁡(ω−1(1−ω)D+F)det⁡(ω−1D−E)=ω−n(1−ω)n∏iaiiω−n∏iaii=(1−ω)n\det T_\omega=\frac{\det(\omega^{-1}(1-\omega)D+F)}{\det(\omega^{-1}D-E)}=\frac{\omega^{-n}(1-\omega)^n\prod_ia_{ii}}{\omega^{-n}\prod_ia_{ii}}=(1-\omega)^n

である。TωT_\omegaの固有値を重複度を込めてλ1,…,λn\lambda_1,\dots,\lambda_nとするとdet⁡Tω=∏iλi\det T_\omega=\prod_i\lambda_iであるから、∣1−ω∣n≤ρ(Tω)n\lvert1-\omega\rvert^n\le\rho(T_\omega)^nであり、ρ(Tω)≥∣1−ω∣\rho(T_\omega)\ge\lvert1-\omega\rvertである。ρ(Tω)<1\rho(T_\omega)<1ならば∣1−ω∣<1\lvert1-\omega\rvert<1であり、ω\omegaは実数であるから0<ω<20<\omega<2である。

(4)を示す。L:=D−1EL:=D^{-1}E、U:=D−1FU:=D^{-1}Fと置くと、TJ=L+UT_{\mathrm J}=L+U、TGS=(D−E)−1F=(I−L)−1UT_{\mathrm{GS}}=(D-E)^{-1}F=(I-L)^{-1}Uである。I−LI-Lは対角成分が11の下三角行列でありdet⁡(I−L)=1\det(I-L)=1であるから、任意のλ∈C\lambda\in\Cについて

det⁡(λI−TGS)=det⁡(I−L)det⁡(λI−(I−L)−1U)=det⁡(λI−λL−U)\det(\lambda I-T_{\mathrm{GS}})=\det(I-L)\det\bigl(\lambda I-(I-L)^{-1}U\bigr)=\det(\lambda I-\lambda L-U)

である。AAの仮定により、LLの00でない成分は(i,i−1)(i,i-1)成分だけであり、UUの00でない成分は(i,i+1)(i,i+1)成分だけである。α∈C∖{0}\alpha\in\C\setminus\{0\}に対してSα:=diag⁡(α,α2,…,αn)S_\alpha:=\operatorname{diag}(\alpha,\alpha^2,\dots,\alpha^n)と置くと、SαLSα−1S_\alpha LS_\alpha^{-1}の(i,i−1)(i,i-1)成分はαiα−(i−1)li,i−1=αli,i−1\alpha^i\alpha^{-(i-1)}l_{i,i-1}=\alpha l_{i,i-1}であるからSαLSα−1=αLS_\alpha LS_\alpha^{-1}=\alpha Lであり、同様にSαUSα−1=α−1US_\alpha US_\alpha^{-1}=\alpha^{-1}Uである。μ≠0\mu\ne0とし、λ:=μ2\lambda:=\mu^2、α:=μ−1\alpha:=\mu^{-1}とすると

det⁡(μ2I−μ2L−U)=det⁡(Sα(μ2I−μ2L−U)Sα−1)=det⁡(μ2I−μL−μU)=μndet⁡(μI−TJ)\det(\mu^2I-\mu^2L-U)=\det\bigl(S_\alpha(\mu^2I-\mu^2L-U)S_\alpha^{-1}\bigr)=\det(\mu^2I-\mu L-\mu U)=\mu^n\det(\mu I-T_{\mathrm J})

であり、主張の等式が成り立つ。μ=0\mu=0では、左辺はdet⁡(−U)\det(-U)であり、UUは対角成分が00の上三角行列であるから00に等しく、右辺も00である。λ≠0\lambda\ne0をTGST_{\mathrm{GS}}の固有値とし、μ2=λ\mu^2=\lambdaを満たすμ∈C\mu\in\Cをとると、主張の等式によりdet⁡(μI−TJ)=0\det(\mu I-T_{\mathrm J})=0であり、∣λ∣=∣μ∣2≤ρ(TJ)2\lvert\lambda\rvert=\lvert\mu\rvert^2\le\rho(T_{\mathrm J})^2である。固有値00もこの不等式を満たすから、ρ(TGS)≤ρ(TJ)2\rho(T_{\mathrm{GS}})\le\rho(T_{\mathrm J})^2である。逆にμ\muを∣μ∣=ρ(TJ)\lvert\mu\rvert=\rho(T_{\mathrm J})を満たすTJT_{\mathrm J}の固有値とすると、主張の等式によりμ2\mu^2はTGST_{\mathrm{GS}}の固有値であり、ρ(TGS)≥ρ(TJ)2\rho(T_{\mathrm{GS}})\ge\rho(T_{\mathrm J})^2である。▨

例 4.3.

A:=(13/43/43/413/43/43/41)A:=\begin{pmatrix}1&3/4&3/4\\3/4&1&3/4\\3/4&3/4&1\end{pmatrix}

とする。v∈R3v\in\R^3についてvTAv=14∑ivi2+34(∑ivi)2v^{\mathsf T}Av=\frac14\sum_iv_i^2+\frac34\bigl(\sum_iv_i\bigr)^2であるから、AAは実対称かつ正定値である。D=ID=Iであり、TJ=I−AT_{\mathrm J}=I-AはTJ(1,1,1)T=−32(1,1,1)TT_{\mathrm J}(1,1,1)^{\mathsf T}=-\frac32(1,1,1)^{\mathsf T}を満たすから、ρ(TJ)≥3/2\rho(T_{\mathrm J})\ge3/2である。det⁡(μI−TJ)=μ3−2716μ+2732=(μ+32)(μ−34)2\det(\mu I-T_{\mathrm J})=\mu^3-\frac{27}{16}\mu+\frac{27}{32}=(\mu+\frac32)(\mu-\frac34)^2であり、ρ(TJ)=3/2\rho(T_{\mathrm J})=3/2である。x0−x∗=(1,1,1)Tx_0-x^*=(1,1,1)^{\mathsf T}ならば、定理 3.1 (1)によりxk−x∗=(−3/2)k(1,1,1)Tx_k-x^*=(-3/2)^k(1,1,1)^{\mathsf T}であり、Jacobi 法の列は収束しない。Jacobi 法の分裂(I,I−A)(I,I-A)ではM+MT−A=2I−AM+M^{\mathsf T}-A=2I-Aであり、(1,1,1)(2I−A)(1,1,1)T=3(2−52)=−32<0(1,1,1)(2I-A)(1,1,1)^{\mathsf T}=3(2-\frac52)=-\frac32<0であるから、補題 4.1の仮定は成り立たない。同じAAの Gauss–Seidel 法では

TGS=(0−3/4−3/409/16−3/1609/6445/64),det⁡(λI−TGS)=λ(λ2−8164λ+2764)T_{\mathrm{GS}}=\begin{pmatrix}0&-3/4&-3/4\\0&9/16&-3/16\\0&9/64&45/64\end{pmatrix},\qquad\det(\lambda I-T_{\mathrm{GS}})=\lambda\Bigl(\lambda^2-\frac{81}{64}\lambda+\frac{27}{64}\Bigr)

である。二次式の判別式は(81/64)2−4⋅27/64=−351/4096<0(81/64)^2-4\cdot27/64=-351/4096<0であるから、二次式の二根は互いに共役であり、その絶対値の二乗は二根の積27/6427/64に等しい。したがってρ(TGS)=33/8≈0.650\rho(T_{\mathrm{GS}})=3\sqrt3/8\approx0.650である。

例 4.4.

A:=(410141014),b:=(565)A:=\begin{pmatrix}4&1&0\\1&4&1\\0&1&4\end{pmatrix},\qquad b:=\begin{pmatrix}5\\6\\5\end{pmatrix}

とするとx∗=A−1b=(1,1,1)Tx^*=A^{-1}b=(1,1,1)^{\mathsf T}である。AAは狭義行対角優位な三重対角行列であり、vTAv=3v12+2v22+3v32+(v1+v2)2+(v2+v3)2v^{\mathsf T}Av=3v_1^2+2v_2^2+3v_3^2+(v_1+v_2)^2+(v_2+v_3)^2であるから実対称かつ正定値でもある。TJ=−14(010101010)T_{\mathrm J}=-\frac14\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}であり、det⁡(μI−TJ)=μ3−μ/8\det(\mu I-T_{\mathrm J})=\mu^3-\mu/8であるから、TJT_{\mathrm J}の固有値は0, ±2/40,\ \pm\sqrt2/4、ρ(TJ)=1/(22)≈0.354\rho(T_{\mathrm J})=1/(2\sqrt2)\approx0.354である。命題 4.2 (1)の上界はmax⁡{1/4, 2/4, 1/4}=1/2\max\{1/4,\ 2/4,\ 1/4\}=1/2である。命題 4.2 (4)によりdet⁡(μ2I−TGS)=μ3(μ3−μ/8)\det(\mu^2I-T_{\mathrm{GS}})=\mu^3(\mu^3-\mu/8)であるから、det⁡(λI−TGS)=λ2(λ−1/8)\det(\lambda I-T_{\mathrm{GS}})=\lambda^2(\lambda-1/8)であり、ρ(TGS)=1/8=ρ(TJ)2\rho(T_{\mathrm{GS}})=1/8=\rho(T_{\mathrm J})^2である。x0:=0x_0:=0とし、ek:=xk−x∗e_k:=x_k-x^*と置く。Jacobi 法では

e0=(−1−1−1),e1=(1/41/21/4),e2=(−1/8−1/8−1/8)=18e0e_0=\begin{pmatrix}-1\\-1\\-1\end{pmatrix},\quad e_1=\begin{pmatrix}1/4\\1/2\\1/4\end{pmatrix},\quad e_2=\begin{pmatrix}-1/8\\-1/8\\-1/8\end{pmatrix}=\frac18e_0

であるから、ek+2=TJke2=ek/8=ρ(TJ)2eke_{k+2}=T_{\mathrm J}^ke_2=e_k/8=\rho(T_{\mathrm J})^2e_kである。∥ek∥∞\lVert e_k\rVert_\inftyはk=0,…,5k=0,\dots,5で1, 1/2, 1/8, 1/16, 1/64, 1/1281,\ 1/2,\ 1/8,\ 1/16,\ 1/64,\ 1/128である。 Gauss–Seidel 法では

e1=(1/43/16−3/64),e2=(−3/643/128−3/512),e3=(−3/5123/1024−3/4096)=18e2e_1=\begin{pmatrix}1/4\\3/16\\-3/64\end{pmatrix},\quad e_2=\begin{pmatrix}-3/64\\3/128\\-3/512\end{pmatrix},\quad e_3=\begin{pmatrix}-3/512\\3/1024\\-3/4096\end{pmatrix}=\frac18e_2

である。Cayley–Hamilton の定理によりTGS2(TGS−I/8)=0T_{\mathrm{GS}}^2(T_{\mathrm{GS}}-I/8)=0であるから、任意のx0x_0とk≥2k\ge2についてek+1−ek/8=TGSk−2(TGS−I/8)TGS2e0=0e_{k+1}-e_k/8=T_{\mathrm{GS}}^{k-2}(T_{\mathrm{GS}}-I/8)T_{\mathrm{GS}}^2e_0=0であり、e2e_2は固有値1/81/8の固有ベクトルである。∥ek∥∞\lVert e_k\rVert_\inftyはk=0,…,4k=0,\dots,4で1, 1/4, 3/64, 3/512, 3/40961,\ 1/4,\ 3/64,\ 3/512,\ 3/4096である。

5 二階差分の三重対角行列

命題 5.1.n∈N≥1n\in\NNとし、An∈Rn×nA_n\in\R^{n\times n}を、対角成分が22、(i,i+1)(i,i+1)成分と(i+1,i)(i+1,i)成分（1≤i≤n−11\le i\le n-1）が−1-1、その他の成分が00の行列とする。

  1. v∈Rnv\in\R^nに対してv0:=vn+1:=0v_0:=v_{n+1}:=0と置くと、vTAnv=∑j=0n(vj+1−vj)2v^{\mathsf T}A_nv=\sum_{j=0}^n(v_{j+1}-v_j)^2が成り立つ。AnA_nは実対称かつ正定値である。
  2. 1≤k≤n1\le k\le nについてs(k):=(sin⁡(jkπ/(n+1)))j=1n∈Rns^{(k)}:=\bigl(\sin(jk\pi/(n+1))\bigr)_{j=1}^n\in\R^nと置くと、s(k)≠0s^{(k)}\ne0であり Ans(k)=λks(k),λk:=2−2cos⁡kπn+1=4sin⁡2kπ2(n+1)A_ns^{(k)}=\lambda_ks^{(k)},\qquad\lambda_k:=2-2\cos\frac{k\pi}{n+1}=4\sin^2\frac{k\pi}{2(n+1)} が成り立つ。0<λ1<λ2<⋯<λn<40<\lambda_1<\lambda_2<\dots<\lambda_n<4であり、λ1,…,λn\lambda_1,\dots,\lambda_nはAnA_nの固有値のすべてである。

証明.(1)を示す。vTAnv=2∑j=1nvj2−2∑j=1n−1vjvj+1v^{\mathsf T}A_nv=2\sum_{j=1}^nv_j^2-2\sum_{j=1}^{n-1}v_jv_{j+1}である。一方、v0=vn+1=0v_0=v_{n+1}=0から

∑j=0n(vj+1−vj)2=∑j=0nvj+12+∑j=0nvj2−2∑j=0nvjvj+1=2∑j=1nvj2−2∑j=1n−1vjvj+1\sum_{j=0}^n(v_{j+1}-v_j)^2=\sum_{j=0}^nv_{j+1}^2+\sum_{j=0}^nv_j^2-2\sum_{j=0}^nv_jv_{j+1}=2\sum_{j=1}^nv_j^2-2\sum_{j=1}^{n-1}v_jv_{j+1}

であり、等式が成り立つ。右辺が00ならばvj+1=vjv_{j+1}=v_j（0≤j≤n0\le j\le n）であり、v0=0v_0=0からv=0v=0である。したがってAnA_nは正定値である。

(2)を示す。θ:=kπ/(n+1)\theta:=k\pi/(n+1)、sj:=sin⁡(jθ)s_j:=\sin(j\theta)（0≤j≤n+10\le j\le n+1）と置くと、s0=0s_0=0、sn+1=sin⁡(kπ)=0s_{n+1}=\sin(k\pi)=0であるから、1≤j≤n1\le j\le nについて(Ans(k))j=−sj−1+2sj−sj+1(A_ns^{(k)})_j=-s_{j-1}+2s_j-s_{j+1}である。加法定理によりsj−1+sj+1=2sjcos⁡θs_{j-1}+s_{j+1}=2s_j\cos\thetaであるから、(Ans(k))j=(2−2cos⁡θ)sj(A_ns^{(k)})_j=(2-2\cos\theta)s_jであり、2−2cos⁡θ=4sin⁡2(θ/2)2-2\cos\theta=4\sin^2(\theta/2)である。0<θ<π0<\theta<\piからs1=sin⁡θ>0s_1=\sin\theta>0であり、s(k)≠0s^{(k)}\ne0である。θ\thetaはkkについて狭義増加で(0,π)(0,\pi)に属し、cos⁡\cosは(0,π)(0,\pi)で狭義減少であるから、λk\lambda_kはkkについて狭義増加で(0,4)(0,4)に属する。AnA_nは相異なるnn個の固有値λ1,…,λn\lambda_1,\dots,\lambda_nをもつから、これらがAnA_nの固有値のすべてである。▨

命題 5.2.n∈N≥1n\in\NNとし、AnA_nを命題 5.1の行列、TJT_{\mathrm J}とTGST_{\mathrm{GS}}をAnA_nの Jacobi 法と Gauss–Seidel 法の反復行列とする。

  1. ρ(TJ)=cos⁡(π/(n+1))\rho(T_{\mathrm J})=\cos(\pi/(n+1))、ρ(TGS)=cos⁡2(π/(n+1))\rho(T_{\mathrm{GS}})=\cos^2(\pi/(n+1))である。
  2. 1−ρ(TJ)≤π2/(2(n+1)2)1-\rho(T_{\mathrm J})\le\pi^2/(2(n+1)^2)、1−ρ(TGS)≤π2/(n+1)21-\rho(T_{\mathrm{GS}})\le\pi^2/(n+1)^2であり、n→∞n\to\inftyのとき (n+1)2(−log⁡ρ(TJ))→π22,(n+1)2(−log⁡ρ(TGS))→π2(n+1)^2\bigl(-\log\rho(T_{\mathrm J})\bigr)\to\frac{\pi^2}{2},\qquad(n+1)^2\bigl(-\log\rho(T_{\mathrm{GS}})\bigr)\to\pi^2 である（左辺はn≥2n\ge2で定まる）。
  3. n≥2n\ge2、0<θ<10<\theta<1とし、T∈{TJ,TGS}T\in\{T_{\mathrm J},T_{\mathrm{GS}}\}とする。0<ρ(T)<10<\rho(T)<1であり、次が成り立つ。Rn\R^nの任意のノルム∥⋅∥\lVert\cdot\rVertについて、整数k≥0k\ge0が任意のe∈Rne\in\R^nに対して∥Tke∥≤θ∥e∥\lVert T^ke\rVert\le\theta\lVert e\rVertを満たすならば、k≥log⁡θ/log⁡ρ(T)k\ge\log\theta/\log\rho(T)である。ρ(T)+ε<1\rho(T)+\varepsilon<1を満たす任意のε>0\varepsilon>0に対してCn\C^nのノルム∥⋅∥\lVert\cdot\rVertが存在して、k≥log⁡θ/log⁡(ρ(T)+ε)k\ge\log\theta/\log(\rho(T)+\varepsilon)を満たす任意の整数kkと任意のe∈Cne\in\C^nについて∥Tke∥≤θ∥e∥\lVert T^ke\rVert\le\theta\lVert e\rVertである。さらにlog⁡ρ(TGS)=2log⁡ρ(TJ)\log\rho(T_{\mathrm{GS}})=2\log\rho(T_{\mathrm J})である。

証明.(1)を示す。命題 5.1 (1)によりAnA_nは正則であり、対角成分は22であるから、TJT_{\mathrm J}とTGST_{\mathrm{GS}}は定まる。D=2ID=2I、E+F=2I−AnE+F=2I-A_nであるからTJ=I−An/2T_{\mathrm J}=I-A_n/2であり、命題 5.1 (2)によりTJT_{\mathrm J}の固有値は1−λk/2=cos⁡(kπ/(n+1))1-\lambda_k/2=\cos(k\pi/(n+1))（1≤k≤n1\le k\le n）のすべてである。1≤k≤n1\le k\le nならばπ/(n+1)≤kπ/(n+1)≤π−π/(n+1)\pi/(n+1)\le k\pi/(n+1)\le\pi-\pi/(n+1)であるから∣cos⁡(kπ/(n+1))∣≤cos⁡(π/(n+1))\lvert\cos(k\pi/(n+1))\rvert\le\cos(\pi/(n+1))であり、k=1k=1で等号が成り立つ。したがってρ(TJ)=cos⁡(π/(n+1))\rho(T_{\mathrm J})=\cos(\pi/(n+1))である。AnA_nは三重対角であるから、命題 4.2 (4)によりρ(TGS)=cos⁡2(π/(n+1))\rho(T_{\mathrm{GS}})=\cos^2(\pi/(n+1))である。

(2)の証明は演習とする（問題 6.1）。

(3)を示す。n≥2n\ge2から0<π/(n+1)<π/20<\pi/(n+1)<\pi/2であり、(1)により0<ρ(T)<10<\rho(T)<1である。T=TJT=T_{\mathrm J}ならば、s(1)s^{(1)}はTJs(1)=ρ(TJ)s(1)T_{\mathrm J}s^{(1)}=\rho(T_{\mathrm J})s^{(1)}を満たす。T=TGST=T_{\mathrm{GS}}ならば、μ:=ρ(TJ)\mu:=\rho(T_{\mathrm J})はTJT_{\mathrm J}の固有値であるから、命題 4.2 (4)の等式によりdet⁡(ρ(TGS)I−TGS)=0\det(\rho(T_{\mathrm{GS}})I-T_{\mathrm{GS}})=0であり、実行列ρ(TGS)I−TGS\rho(T_{\mathrm{GS}})I-T_{\mathrm{GS}}の核はRn\R^nの00でない元を含む。いずれの場合も、e∈Rn∖{0}e\in\R^n\setminus\{0\}が存在してTke=ρ(T)keT^ke=\rho(T)^ke（k≥0k\ge0）である。∥Tke∥≤θ∥e∥\lVert T^ke\rVert\le\theta\lVert e\rVertならばρ(T)k≤θ\rho(T)^k\le\thetaであり、log⁡ρ(T)<0\log\rho(T)<0からk≥log⁡θ/log⁡ρ(T)k\ge\log\theta/\log\rho(T)である。ε>0\varepsilon>0がρ(T)+ε<1\rho(T)+\varepsilon<1を満たすとし、補題 2.1 (2)によりSSをとると、∥Tke∥S≤(ρ(T)+ε)k∥e∥S\lVert T^ke\rVert_S\le(\rho(T)+\varepsilon)^k\lVert e\rVert_Sである。k≥log⁡θ/log⁡(ρ(T)+ε)k\ge\log\theta/\log(\rho(T)+\varepsilon)ならば(ρ(T)+ε)k≤θ(\rho(T)+\varepsilon)^k\le\thetaである。最後の等式は(1)による。▨

例 5.3.命題 5.2 (3)でθ=10−6\theta=10^{-6}とする。下表は、1−ρ(T)1-\rho(T)と、反復数の下界log⁡θ/log⁡ρ(T)\log\theta/\log\rho(T)以上の最小の整数を、倍精度の浮動小数点計算で求めた値である（1−ρ1-\rhoは有効数字44桁に丸めた）。

nn 1−ρ(TJ)1-\rho(T_{\mathrm J}) 1−ρ(TGS)1-\rho(T_{\mathrm{GS}}) Jacobi 法の下界 Gauss–Seidel 法の下界
99 4.894×10−24.894\times10^{-2} 9.549×10−29.549\times10^{-2} 276276 138138
9999 4.934×10−44.934\times10^{-4} 9.866×10−49.866\times10^{-4} 2799227992 1399613996
999999 4.935×10−64.935\times10^{-6} 9.870×10−69.870\times10^{-6} 27996042799604 13998021399802

n+1n+1を1010倍にすると、1−ρ1-\rhoはおよそ1/1001/100倍になり、下界はおよそ100100倍になる。表の各nnで、Gauss–Seidel 法の下界は Jacobi 法の下界の半分である。π2/2≈4.935\pi^2/2\approx4.935であり、(n+1)2(1−ρ(TJ))(n+1)^2(1-\rho(T_{\mathrm J}))はn=9,99,999n=9,99,999で4.894, 4.934, 4.9354.894,\ 4.934,\ 4.935である。

6 演習

問題 6.1.命題 5.2 (2)の証明を完成させよ。

解答.

h:=π/(n+1)h:=\pi/(n+1)と置くと、命題 5.2 (1)により1−ρ(TJ)=1−cos⁡h1-\rho(T_{\mathrm J})=1-\cos h、1−ρ(TGS)=1−cos⁡2h=sin⁡2h1-\rho(T_{\mathrm{GS}})=1-\cos^2h=\sin^2hである。t≥0t\ge0についてsin⁡t=∫0tcos⁡s ds≤t\sin t=\int_0^t\cos s\,ds\le tであるから、1−cos⁡h=∫0hsin⁡t dt≤h2/21-\cos h=\int_0^h\sin t\,dt\le h^2/2であり、sin⁡2h≤h2\sin^2h\le h^2である。これで二つの不等式が成り立つ。1−cos⁡h=2sin⁡2(h/2)1-\cos h=2\sin^2(h/2)であるから

(n+1)2(1−cos⁡h)=π22(sin⁡(h/2)h/2)2,(n+1)2sin⁡2h=π2(sin⁡hh)2(n+1)^2(1-\cos h)=\frac{\pi^2}{2}\Bigl(\frac{\sin(h/2)}{h/2}\Bigr)^2,\qquad(n+1)^2\sin^2h=\pi^2\Bigl(\frac{\sin h}{h}\Bigr)^2

であり、n→∞n\to\inftyのときh→+0h\to+0、sin⁡t/t→1\sin t/t\to1（t→+0t\to+0）であるから、二つの量はそれぞれπ2/2\pi^2/2とπ2\pi^2に収束する。n≥2n\ge2では0<ρ(TJ)<10<\rho(T_{\mathrm J})<1であり、x:=1−ρ(TJ)∈(0,1)x:=1-\rho(T_{\mathrm J})\in(0,1)と置くと

(n+1)2(−log⁡ρ(TJ))=−log⁡(1−x)x⋅(n+1)2x(n+1)^2\bigl(-\log\rho(T_{\mathrm J})\bigr)=\frac{-\log(1-x)}{x}\cdot(n+1)^2x

である。n→∞n\to\inftyのときx→+0x\to+0であり、log⁡\logの11における微分係数が11であることから−log⁡(1−x)/x→1-\log(1-x)/x\to1である。したがって左辺はπ2/2\pi^2/2に収束する。命題 5.2 (1)により−log⁡ρ(TGS)=−2log⁡ρ(TJ)-\log\rho(T_{\mathrm{GS}})=-2\log\rho(T_{\mathrm J})であるから、(n+1)2(−log⁡ρ(TGS))→π2(n+1)^2(-\log\rho(T_{\mathrm{GS}}))\to\pi^2である。▨

前提記事