0
大学数学基礎解説
文献あり

クラフチック法の証明

188
0
$$$$

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

  1. 集合$S\subseteq\mathbb{R}$の直径$\sup\lbrace\lvert x-y\rvert\mid x,y\in S\rbrace$$\operatorname{diam}S$と書く.
  2. 集合$S\subseteq\mathbb{R}^n$の内部を$\operatorname{int}S$と書く.
  3. 写像$f$の始域に含まれる集合$A$について,像$\lbrace f(a)\mid a\in A\rbrace$$f\lbrack A\rbrack$と書く.

次の記法は独自のものなので,注意されたい.ベクトル値関数
$$ f(\boldsymbol{x}) = (\begin{matrix}f_1(\boldsymbol{x}) & f_2(\boldsymbol{x})& \cdots & f_n(\boldsymbol{x})\end{matrix})^{\mathsf{T}}\quad(\boldsymbol{x}=(\begin{matrix}x_1 & x_2& \cdots & x_n\end{matrix})^{\mathsf{T}}) $$
に対して,$\boldsymbol{I}_f(\boldsymbol{X})$
$$ \boldsymbol{I}_f(\boldsymbol{X}) = (\begin{matrix}(\nabla f_1)_{\boldsymbol{x}_1} & (\nabla f_2)_{\boldsymbol{x}_2} & \cdots & (\nabla f_n)_{\boldsymbol{x}_n}\end{matrix})^{\mathsf{T}}\quad(\boldsymbol{X}=(\begin{matrix}\boldsymbol{x}_1 & \boldsymbol{x}_2& \cdots & \boldsymbol{x}_n\end{matrix})) $$
で定義する.$\boldsymbol{x}_1=\boldsymbol{x}_2=\dotsb=\boldsymbol{x}_n=\boldsymbol{x}$のとき,$\boldsymbol{I}_f(\boldsymbol{X})$$f(\boldsymbol{x})$のヤコビ行列である.

平均値の定理

$I=\lbrack\boldsymbol{a},\boldsymbol{b}\rbrack\subseteq\mathbb{R}^n$を内部が空でない有界閉区間とする.また,関数$f\colon I\to\mathbb{R}^n$$I$で連続,$\operatorname{int}I$で偏微分可能とする.このとき,行列$\boldsymbol{C}\in\operatorname{int}( I)^n$が存在して
$$ f(\boldsymbol{b})-f(\boldsymbol{a}) = \boldsymbol{I}_f(\boldsymbol{C})(\boldsymbol{b}-\boldsymbol{a}) $$
を満たす.

ベクトル$f(\boldsymbol{x})$の第$i$成分を$f_i(\boldsymbol{x})$とおく.仮定から,関数$g_i(t)=f_i(\boldsymbol{a}+t(\boldsymbol{b}-\boldsymbol{a}))$は閉区間$\lbrack 0,1\rbrack$上で連続,開区間$(0,1)$上で微分可能である.よって,平均値の定理より$g_i(1)-g_i(0)=g_i'(\theta_i)$を満たす$\theta_i\in(0,1)$が存在する.$\boldsymbol{c}_i=\boldsymbol{a}+\theta_i(\boldsymbol{b}-\boldsymbol{a})$とおくと
$$ f_i(\boldsymbol{b})-f_i(\boldsymbol{a}) = (\nabla f_i)_{\boldsymbol{c}_i}^{\mathsf{T}}(\boldsymbol{b}-\boldsymbol{a}) $$
なので,$\boldsymbol{C}=(\begin{matrix}\boldsymbol{c}_1 & \boldsymbol{c}_2& \cdots & \boldsymbol{c}_n\end{matrix})$とおくと
$$ f(\boldsymbol{b})-f(\boldsymbol{a}) = \boldsymbol{I}_f(\boldsymbol{C})(\boldsymbol{b}-\boldsymbol{a}) $$
である.

クラフチック法

$I=I_1\times I_2\times\dotsb\times I_n\subseteq\mathbb{R}^n$を内部が空でない有界閉区間,$\boldsymbol{c}$をその中心とする.また,$\mathbb{R}^n$値関数$f$$I$を含むある開区間上で定義され,$C^1$級であるとする.仮に,ある$n$次正方行列$\boldsymbol{A}$が存在し,関数
$$ K(\boldsymbol{X},\boldsymbol{y}) = \boldsymbol{c}-\boldsymbol{A}f(\boldsymbol{c})+(\boldsymbol{I}-\boldsymbol{A}\boldsymbol{I}_f(\boldsymbol{X}))(\boldsymbol{y}-\boldsymbol{c})\quad(\text{$\boldsymbol{X}\in I^n$,$\boldsymbol{y}\in I$}) $$
が条件$K\lbrack I^n\times I\rbrack\subseteq\operatorname{int}I$を満たすのであれば,$I$上に$f$の零点がただ一つ存在する.

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

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

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

$\boldsymbol{X}\in I^n$を任意にとる.新たにノルム$\lVert\mathord{\,\cdot\,}\rVert_I$
$$ \lVert(\begin{matrix}x_1 & x_2 & \cdots & x_n\end{matrix})^{\mathsf{T}}\rVert_I = \max_{1\leq k\leq n}\frac{\lvert x_k\rvert}{\phi_k}\quad(\phi_k=\operatorname{diam}I_k) $$
で定義し,ベクトル$K(\boldsymbol{X},\boldsymbol{y})$の第$i$成分を$K_i(\boldsymbol{y})$とおく.
$$ \boldsymbol{I}_g(\boldsymbol{X}) = \boldsymbol{I}-\boldsymbol{A}\boldsymbol{I}_f(\boldsymbol{X}), \quad K(\boldsymbol{X},\boldsymbol{y}) = \boldsymbol{I}_g(\boldsymbol{X})\boldsymbol{y} +\boldsymbol{c}-\boldsymbol{A}f(\boldsymbol{c})-\boldsymbol{I}_g(\boldsymbol{X})\boldsymbol{c} $$
より,$\boldsymbol{I}_g(\boldsymbol{X})$の第$i$行ベクトルを$\boldsymbol{g}_i^{\mathsf{T}}$とおくと
$$ \begin{aligned} \operatorname{diam}K_i\lbrack I\rbrack &= \operatorname{diam}\lbrace\boldsymbol{g}_i^{\mathsf{T}}\boldsymbol{y}\mid\boldsymbol{y}\in I\rbrace \\ &= \sup\lbrace\lvert\boldsymbol{g}_i^{\mathsf{T}}(\boldsymbol{y}_1-\boldsymbol{y}_2)\rvert\mid\boldsymbol{y}_1,\boldsymbol{y}_2\in I\rbrace \\ &= \sup\lbrace\lvert\boldsymbol{g}_i^{\mathsf{T}}(\begin{matrix}\delta_1 & \delta_2 & \cdots & \delta_k & \cdots & \delta_n\end{matrix})^{\mathsf{T}}\rvert\mid\lvert\delta_k\rvert\leq\phi_k\rbrace \\ &= \sup\lbrace\lvert\boldsymbol{g}_i^{\mathsf{T}}\boldsymbol{\delta}\rvert\mid\lVert\boldsymbol{\delta}\rVert_I\leq 1\rbrace \end{aligned} $$
だから$\operatorname{diam}K_i\lbrack I\rbrack=\max\lbrace\lvert\boldsymbol{g}_i^{\mathsf{T}}\boldsymbol{e}\rvert\mid\lVert\boldsymbol{e}\rVert_I\leq 1\rbrace$である.よって
$$ \begin{aligned} \max_{1\leq i\leq n}\frac{\operatorname{diam}K_i\lbrack I\rbrack}{\phi_i} &= \max_{1\leq i\leq n}\Biggl(\frac{1}{\phi_i}\max_{\lVert\boldsymbol{e}\rVert_I\leq 1}\lvert\boldsymbol{g}_i^{\mathsf{T}}\boldsymbol{e}\rvert\Biggr) = \max_{\lVert\boldsymbol{e}\rVert_I\leq 1}\max_{1\leq i\leq n}\frac{\lvert\boldsymbol{g}_i^{\mathsf{T}}\boldsymbol{e}\rvert}{\phi_i} \\ &= \max_{\lVert\boldsymbol{e}\rVert_I\leq 1}\lVert\boldsymbol{I}_g(\boldsymbol{X})\boldsymbol{e}\rVert_I = \lVert\boldsymbol{I}_g(\boldsymbol{X})\rVert_{\mathrm{op}} \end{aligned} $$
である.

一方,$n$変数関数$K_i(\boldsymbol{y})$は有界閉区間$I$上の連続関数なので,$I$上で最大値と最小値に達する.そのため,仮定$K\lbrack I^n\times I\rbrack\subseteq\operatorname{int}I$から
$$ \operatorname{diam}K_i\lbrack I\rbrack < \operatorname{diam}I_i = \phi_i, \quad\frac{\operatorname{diam}K_i\lbrack I\rbrack}{\phi_i} < 1 $$
である.よって$\lVert\boldsymbol{I}_g(\boldsymbol{X})\rVert_{\mathrm{op}}<1$である.これで$g$が縮小写像であることが示せた.

最後に,$\boldsymbol{A}$が正則であることを示す.$\boldsymbol{A}$が正則でないと仮定する.このとき$\boldsymbol{A}\boldsymbol{I}_f(\boldsymbol{X})$も正則でないから,連立1次方程式$\boldsymbol{A}\boldsymbol{I}_f(\boldsymbol{X})\boldsymbol{v}=\boldsymbol{0}$は非自明な解$\boldsymbol{v}\neq\boldsymbol{0}$を持つ.すると$\boldsymbol{I}_g(\boldsymbol{X})\boldsymbol{v}=\boldsymbol{v}$であるが,これは$\lVert\boldsymbol{I}_g(\boldsymbol{X})\rVert_{\mathrm{op}}<1$に反する.

参考文献

投稿日:2023524
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

数学、特に応用数学が好きです。Mathlogでは主に、数学とプログラミングを絡めたようなことを書けたらいいなと思っています。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中