数値解析（塩田）2022年度

数値解析第12回 (6)　ヤコビ法の収束性

反復行列

Def.12　

$A$ の対角部分を

$\dps{ D=\mat{cc}{ \begin{array}{cc} a_{11} & \\ & a_{22} \\ \end{array} & \Huge{0} \\[-0.5em] \Huge{0} & \begin{array}[b]{cc} \ddots & \\ & a_{nn} \\ \end{array} } }$ とし、

$\dps{H=(h_{ij})=-D^{-1}(A-D)}$ とおく。

$H$ をヤコビ法の「反復行列」と呼ぶ。

ちょっと見、複雑そうですが、

$\dps{ h_{ij}= \left\{ \begin{array}{cl} \dps{-\left(\frac{a_{ij}}{a_{ii}}\right)} & \quad \mbox{if }\ i \neq j \\ 0 & \quad \mbox{otherwise} \\ \end{array} \right. }$ です。なぜ反復行列と呼ぶかと言うと、

Th.13　ヤコビ法の

$k$ ステップ目の誤差ベクトルを

$\dps{\eee^{(k)}=\xxx^{(k)} - }$ ( 真の

$\xxx$ ) と置くと

$\eee^{(k+1)} = H \eee^{(k)}$ . 従って

$\eee^{(k)} = H^k \eee^{(0)}$ .

証明　ヤコビ法のアイデアは、

$D$ を用いて

$D\xxx^{(k+1)} = \bbb - (A-D)\xxx^{(k)}$ と書くことができます。真の解

$\xxx$ は

$D\xxx = \bbb - (A-D)\xxx$ を満たすので、辺々引くと

$D(\xxx^{(k+1)}-\xxx) = - (A-D)(\xxx^{(k)}-\xxx)$

$\therefore\quad D\eee^{(k+1)} = - (A-D)\eee^{(k)}$

$\therefore\quad \eee^{(k+1)} = - D^{-1}(A-D)\eee^{(k)} = H\eee^{(k)}$ . (証明終)

ヤコビ法が収束する十分条件

Th.14　

$A=(a_{ij})$ が次の条件を満たせばヤコビ法は必ず収束する：

$\forall\, i$ について

$\dps{ \sum_{j \neq i} |\,a_{ij}\,| \lt |\,a_{ii}\,|}$

$\cdots\cdots$

$(\sharp)$

　予想 5 のとおり、対角成分

$a_{ii}$ の絶対値が「同じ行の他の成分の絶対値の和」より大きければヤコビ法は収束する、という定理です。

Ex.　

$A=\mat{rrr}{5 & 1 & 2 \\ 2 & 7 & -3 \\ 1 & -1 & 4 }$ のとき

$i=1$ : $|\,1\,|+|\,2\,| = 3 \lt |\,5\,|$
$i=2$ : $|\,2\,|+|\,-3\,| = 5 \lt |\,7\,|$
$i=3$ : $|\,1\,|+|\,-1\,| = 2 \lt |\,4\,|$

となって

$(\sharp)$ が成り立ちますのでヤコビ法は収束します。

証明　

$\require{color}$

$\dps{ ||\,H\,||_{\infty} \mathop{=}^{\textcolor{red}{\mbox{Th.9}}} \max_{1 \leqq i \leqq n} \left( \sum_{j=1}^n |\,h_{ij}\,| \right) \mathop{=}^{\textcolor{red}{\mbox{Def.12}}} \max_{1 \leqq i \leqq n} \left( \frac{1}{|\,a_{ii}\,|} \sum_{j \neq i} |\,a_{ij}\,| \right) \ \mathop{\lt}^{\textcolor{red}{\Large{(\sharp)}}}\ 1. }$ すると Th.10 (2), Th.13 より

$\dps{ \left|\,\eee^{(k)}\,\right|_{\infty} = \left|\,H^k \eee^{(0)}\,\right|_{\infty} \leqq \left(||\,H\,||_{\infty} \right)^k \left|\,\eee^{(0)}\,\right| \longrightarrow 0 \qquad ( k \rightarrow \infty ) }$ よって Cor.11 より

$\eee^{(k)} \longrightarrow \ooo \qquad ( k \rightarrow \infty )$

$\therefore$

$\xxx^{(k)} \longrightarrow \xxx \qquad ( k \rightarrow \infty )$ (証明終)

　誤差ベクトル

$\eee^{(k)}$ がある意味 "公比

$H$ の等比数列" であり、条件

$(\sharp)$ より

$H$ のノルムが 1 未満なので、 Th.10 (2), Cor.11 より誤差ベクトルはゼロベクトルに収束する、という仕組みです。

$\require{color}$

注と例

Rem.15　

$(\sharp)$ が成り立てばガウス・ザイデル法も収束する。

証明は下記のプリント pp.4-5 を見てください。

Rem.16　

$(\sharp)$ はあくまで十分条件であって、

$(\sharp)$ が成り立たなくてヤコビ法やガウス・ザイデル法が収束することも少なくありません。

前へ / 戻る / 次へ