8.3 Krawczyk's Method (連立1次方程式に対する)

区間連立1次方程式 $\bm{A}\bm{x}=\bm{b}$ は、 行列 $C\in\mathbb{R}^{n\times n}$ をかけることで前処理できる。 ここで $C$ を、$\bm{A}$ の中点行列 (midpoint matrix) の逆行列と選ぶと、 $C\bm{A}$ はしばしば $H$-行列となる。 その場合は Gauss の消去法が使えるが、Krawczyk の方法を用いて、 包み込みを計算する方が速い。

区間ベクトル $\bm{x}^{(i)}$ が解集合を包み込む: $\square\Sigma\left( \bm{A},\bm{b}\right)\subset\bm{x}^(i)$ と仮定する。 このとき、任意の $\tilde A\in\bm{A}$, $\tilde b\in\bm{b}$ に対して

$${\tilde A}^{-1}\tilde b=C\tilde b+ (I-C\tilde A){\tilde A}^{-1}\tilde b \in C\bm{b}+\left(I-C\bm{A}\right)\bm{x}^{(i)}.$$

ゆえに

$$\square\Sigma\left(\bm{A},\bm{b}\right)\subset\bm{x}^(i) \quad\T... ...{b}\right)\subset C\bm{b}+\left(I-C\bm{A}\right)\bm{x}^{(i)} \cap\bm{x}^(i).$$

これは Krawczyk 反復

$$\bm{x}^{(i+1)}=C\bm{b}+\left(I-C\bm{A}\right)\bm{x}^{(i)}\cap\bm{x}^(i)$$

を与える。？？？

この反復を

証明. $\tilde A\tilde x=\tilde b$ であるから、 $C$ をかけて移項して $0=C\tilde b-C\tilde A\tilde x$. ゆえに $\tilde x=C\tilde b+(I-C\tilde A)\tilde x$. ゆえに (仮定 $\left\Vert I-C\tilde A\right\Vert=\beta$ から)

$$\left\Vert\tilde x\right\Vert \le\left\Vert C\tilde b\right\Vert... ...ght\Vert =\left\Vert C\tilde b\right\Vert+\beta\left\Vert\tilde x\right\Vert.$$

移項して $\beta<1$ に注意して、結論を得る。 $\qedsymbol$ $\qedsymbol$