文献あり

クラフチック法の証明

188

本稿では，非線形方程式の解を精度保証つき数値計算で求めるのによく使われる，クラフチック法（Krawczyk method）を証明する．なお，本稿では以下の記法を用いる．

集合 $S \subseteq R$ の直径 $sup {| x - y | ∣ x, y \in S}$ を $diam S$ と書く．
集合 $S \subseteq R^{n}$ の内部を $int S$ と書く．
写像 $f$ の始域に含まれる集合 $A$ について，像 ${f (a) ∣ a \in A}$ を $f [A]$ と書く．

次の記法は独自のものなので，注意されたい．ベクトル値関数
$f (x) = (\begin{matrix} f_{1} (x) & f_{2} (x) & \dots & f_{n} (x) \end{matrix})^{T} (x = (\begin{matrix} x_{1} & x_{2} & \dots & x_{n} \end{matrix})^{T})$
に対して， $I_{f} (X)$ を
$I_{f} (X) = (\begin{matrix} (\nabla f_{1})_{x_{1}} & (\nabla f_{2})_{x_{2}} & \dots & (\nabla f_{n})_{x_{n}} \end{matrix})^{T} (X = (\begin{matrix} x_{1} & x_{2} & \dots & x_{n} \end{matrix}))$
で定義する． $x_{1} = x_{2} = \dots = x_{n} = x$ のとき， $I_{f} (X)$ は $f (x)$ のヤコビ行列である．

平均値の定理

$I = [a, b] \subseteq R^{n}$ を内部が空でない有界閉区間とする．また，関数 $f : I \to R^{n}$ は $I$ で連続， $int I$ で偏微分可能とする．このとき，行列 $C \in int (I)^{n}$ が存在して
$f (b) - f (a) = I_{f} (C) (b - a)$
を満たす．

ベクトル $f (x)$ の第 $i$ 成分を $f_{i} (x)$ とおく．仮定から，関数 $g_{i} (t) = f_{i} (a + t (b - a))$ は閉区間 $[0, 1]$ 上で連続，開区間 $(0, 1)$ 上で微分可能である．よって，平均値の定理より $g_{i} (1) - g_{i} (0) = g_{i}^{'} (θ_{i})$ を満たす $θ_{i} \in (0, 1)$ が存在する． $c_{i} = a + θ_{i} (b - a)$ とおくと
$f_{i} (b) - f_{i} (a) = (\nabla f_{i})_{c_{i}}^{T} (b - a)$
なので， $C = (\begin{matrix} c_{1} & c_{2} & \dots & c_{n} \end{matrix})$ とおくと
$f (b) - f (a) = I_{f} (C) (b - a)$
である．

クラフチック法

$I = I_{1} \times I_{2} \times \dots \times I_{n} \subseteq R^{n}$ を内部が空でない有界閉区間， $c$ をその中心とする．また， $R^{n}$ 値関数 $f$ は $I$ を含むある開区間上で定義され， $C^{1}$ 級であるとする．仮に，ある $n$ 次正方行列 $A$ が存在し，関数
$K (X, y) = c - A f (c) + (I - A I_{f} (X)) (y - c) (X \in I^{n} ， y \in I)$
が条件 $K [I^{n} \times I] \subseteq int I$ を満たすのであれば， $I$ 上に $f$ の零点がただ一つ存在する．

仮定が成り立つとき，関数 $g (x) = x - A f (x)$ （ $x \in I$ ）は縮小写像かつ， $A$ は正則であることを示す．これが示せれば，バナッハの不動点定理から $x^{*} - A f (x^{*}) = x^{*}$ を満たす $x^{*} \in I$ がただ一つ存在するので，定理が示せたことになる．

まず $g [I] \subseteq I$ を示す．任意に $x \in I$ をとる．平均値の定理より， $f (x) - f (c) = I_{f} (C) (x - c)$ を満たす $C \in I^{n}$ が存在する．
$\begin{aligned} g (x) & = x - A (f (x) - f (c)) - A f (c) \\ = x - A I_{f} (C) (x - c) - A f (c) \\ = c - A f (c) + (I - A I_{f} (C)) (x - c) \end{aligned}$
なので $g (x) = K (C, x) \in int I$ である．これで $g [I] \subseteq I$ が示せた．

次に， $g$ が縮小写像であることを示す．任意に $x, y \in I$ をとる． $g (x) - g (y) = I_{g} (C) (x - y)$ を満たす $C \in I^{n}$ が存在するから
$‖ g (x) - g (y) ‖ \leq ‖ I_{g} (C) ‖_{op} ‖ x - y ‖ \leq sup_{X \in I^{n}} ‖ I_{g} (X) ‖_{op} ‖ x - y ‖$
である（ $‖ \cdot ‖_{op}$ は作用素ノルム）． $f$ が $C^{1}$ 級なので， $X$ の関数 $‖ I_{g} (X) ‖_{op}$ は有界閉集合 $I^{n} \subseteq R^{n \times n}$ 上で最大値をとる．よって， $‖ I_{g} (X) ‖_{op} < 1$ （ $X \in I^{n}$ ）を証明できれば， $g$ が縮小写像といえる．

$X \in I^{n}$ を任意にとる．新たにノルム $‖ \cdot ‖_{I}$ を
$‖ (\begin{matrix} x_{1} & x_{2} & \dots & x_{n} \end{matrix})^{T} ‖_{I} = max_{1 \leq k \leq n} \frac{| x_{k} |}{ϕ_{k}} (ϕ_{k} = diam I_{k})$
で定義し，ベクトル $K (X, y)$ の第 $i$ 成分を $K_{i} (y)$ とおく．
$I_{g} (X) = I - A I_{f} (X), K (X, y) = I_{g} (X) y + c - A f (c) - I_{g} (X) c$
より， $I_{g} (X)$ の第 $i$ 行ベクトルを $g_{i}^{T}$ とおくと
$\begin{aligned} diam K_{i} [I] & = diam {g_{i}^{T} y ∣ y \in I} \\ = sup {| g_{i}^{T} (y_{1} - y_{2}) | ∣ y_{1}, y_{2} \in I} \\ = sup {| g_{i}^{T} (\begin{array}{c} δ_{1} & δ_{2} & \dots & δ_{k} & \dots & δ_{n} \end{array})^{T} | ∣ | δ_{k} | \leq ϕ_{k}} \\ = sup {| g_{i}^{T} δ | ∣ ‖ δ ‖_{I} \leq 1} \end{aligned}$
だから $diam K_{i} [I] = max {| g_{i}^{T} e | ∣ ‖ e ‖_{I} \leq 1}$ である．よって
$\begin{aligned} max_{1 \leq i \leq n} \frac{diam K_{i} [I]}{ϕ_{i}} & = max_{1 \leq i \leq n} (\frac{1}{ϕ_{i}} max_{‖ e ‖_{I} \leq 1} | g_{i}^{T} e |) = max_{‖ e ‖_{I} \leq 1} max_{1 \leq i \leq n} \frac{| g_{i}^{T} e |}{ϕ_{i}} \\ = max_{‖ e ‖_{I} \leq 1} ‖ I_{g} (X) e ‖_{I} = ‖ I_{g} (X) ‖_{op} \end{aligned}$
である．

一方， $n$ 変数関数 $K_{i} (y)$ は有界閉区間 $I$ 上の連続関数なので， $I$ 上で最大値と最小値に達する．そのため，仮定 $K [I^{n} \times I] \subseteq int I$ から
$diam K_{i} [I] < diam I_{i} = ϕ_{i}, \frac{diam K_{i} [I]}{ϕ_{i}} < 1$
である．よって $‖ I_{g} (X) ‖_{op} < 1$ である．これで $g$ が縮小写像であることが示せた．

最後に， $A$ が正則であることを示す． $A$ が正則でないと仮定する．このとき $A I_{f} (X)$ も正則でないから，連立1次方程式 $A I_{f} (X) v = 0$ は非自明な解 $v \neq 0$ を持つ．すると $I_{g} (X) v = v$ であるが，これは $‖ I_{g} (X) ‖_{op} < 1$ に反する．