クラフチック法の証明

ベクトル$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}) $$
である．

仮定が成り立つとき，関数$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$に反する．