数値解析 第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)$
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.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 )$
(証明終)
$\require{color}$
注と例
Rem.15 $(\sharp)$ が成り立てばガウス・ザイデル法も収束する。
証明は下記のプリント pp.4-5 を見てください。
Rem.16 $(\sharp)$ はあくまで十分条件であって、
$(\sharp)$ が成り立たなくてヤコビ法やガウス・ザイデル法が収束することも少なくありません。