目次
はじめに 記法のリスト クラフチック法 参考文献
はじめに
この記事では，非線形方程式の解を精度保証つき数値計算で求めるのによく使われる，クラフチック法 (Krawczyk method) を証明する．
記法のリスト
集合S ⊆ R S\subseteq\mathbb{R} S ⊆ R sup { ∣ x − y ∣ ∣ x , y ∈ S } \sup\lbrace\lvert x-y\rvert\mid x,y\in S\rbrace sup {∣ x − y ∣ ∣ x , y ∈ S } diam S \operatorname{diam}S diam S
集合S ⊆ R n S\subseteq\mathbb{R}^{n} S ⊆ R n int S \operatorname{int}S int S
写像f f f A A A { f ( a ) ∣ a ∈ A } \lbrace f(a)\mid a\in A\rbrace { f ( a ) ∣ a ∈ A } f ( A ) f(A) f ( A )
次の記法は独自のものなので，注意されたい．ベクトル値関数
f ( x ) = ( f 1 ( x ) f 2 ( x ) ⋮ f n ( x ) ) ( x = ( x 1 x 2 ⋯ x n ) T ) f(\bm{x}) = \mathopen{}\mathclose{\left(\begin{matrix}f_{1}(\bm{x})\\ f_{2}(\bm{x})\\ \vdots\\ f_{n}(\bm{x})\end{matrix}\right)}\quad(\bm{x}=(\begin{matrix}x_{1} & x_{2} & \cdots & x_{n}\end{matrix})^{\mathsf{T}}) f ( x ) = f 1 ( x ) f 2 ( x ) ⋮ f n ( x ) ( x = ( x 1 x 2 ⋯ x n ) T ) に対して，I f ( X ) \bm{I_{\mathnormal{f}}}(\bm{X}) I f ( X )
I f ( X ) = ( ( ∇ f 1 ( x 1 ) ) T ( ∇ f 2 ( x 2 ) ) T ⋮ ( ∇ f n ( x n ) ) T ) ( X = ( x 1 x 2 ⋯ x n ) ) \bm{I_{\mathnormal{f}}}(\bm{X})
= \mathopen{}\mathclose{\left(\begin{matrix}(\nabla f_{1}(\bm{x_{\mathrm{1}}}))^{\mathsf{T}}\\ (\nabla f_{2}(\bm{x_{\mathrm{2}}}))^{\mathsf{T}}\\ \vdots\\ (\nabla f_{n}(\bm{x_{\mathnormal{n}}}))^{\mathsf{T}}\end{matrix}\right)}\quad(\bm{X}=(\begin{matrix}\bm{x_{\mathrm{1}}} & \bm{x_{\mathrm{2}}}& \cdots & \bm{x_{\mathnormal{n}}}\end{matrix})) I f ( X ) = ( ∇ f 1 ( x 1 ) ) T ( ∇ f 2 ( x 2 ) ) T ⋮ ( ∇ f n ( x n ) ) T ( X = ( x 1 x 2 ⋯ x n )) で定義する．x 1 = x 2 = ⋯ = x n = x \bm{x_{\mathrm{1}}}=\bm{x_{\mathrm{2}}}=\dotsb=\bm{x_{\mathnormal{n}}}=\bm{x} x 1 = x 2 = ⋯ = x n = x I f ( X ) \bm{I_{\mathnormal{f}}}(\bm{X}) I f ( X ) f ( x ) f(\bm{x}) f ( x )
クラフチック法
クラフチック法を示す前に，補題を一つ証明する．
I = [ a , b ] ⊆ R n I=\lbrack\bm{a},\bm{b}\rbrack\subseteq\mathbb{R}^{n} I = [ a , b ] ⊆ R n f : I → R n f\colon I\to\mathbb{R}^{n} f : I → R n I I I int I \operatorname{int}I int I C ∈ int ( I ) n \bm{C}\in\operatorname{int}(
I)^{n} C ∈ int ( I ) n
f ( b ) − f ( a ) = I f ( C ) ( b − a ) f(\bm{b})-f(\bm{a}) = \bm{I_{\mathnormal{f}}}(\bm{C})(\bm{b}-\bm{a}) f ( b ) − f ( a ) = I f ( C ) ( b − a ) を満たす．
ベクトルf ( x ) f(\bm{x}) f ( x ) i i i f i ( x ) f_{i}(\bm{x}) f i ( x ) g i ( t ) = f i ( a + t ( b − a ) ) g_{i}(t)=f_{i}(\bm{a}+t(\bm{b}-\bm{a})) g i ( t ) = f i ( a + t ( b − a )) [ 0 , 1 ] \lbrack 0,1\rbrack [ 0 , 1 ] ( 0 , 1 ) (0,1) ( 0 , 1 ) g i ( 1 ) − g i ( 0 ) = g i ′ ( θ i ) g_{i}(1)-g_{i}(0)=g_{i}'(\theta_i) g i ( 1 ) − g i ( 0 ) = g i ′ ( θ i ) θ i ∈ ( 0 , 1 ) \theta_{i}\in(0,1) θ i ∈ ( 0 , 1 ) c i = a + θ i ( b − a ) \bm{c_{\mathnormal{i}}}=\bm{a}+\theta_{i}(\bm{b}-\bm{a}) c i = a + θ i ( b − a )
f i ( b ) − f i ( a ) = ( ∇ f i ( x ) ) T ∣ x = c i ( b − a ) f_{i}(\bm{b})-f_{i}(\bm{a}) = (\nabla f_{i}(\bm{x}))^{\mathsf{T}}\rvert_{\bm{x}=\bm{c_{\mathnormal{i}}}}(\bm{b}-\bm{a}) f i ( b ) − f i ( a ) = ( ∇ f i ( x ) ) T ∣ x = c i ( b − a ) なので，C = ( c 1 c 2 ⋯ c n ) \bm{C}=(\begin{matrix}\bm{c_{\mathrm{1}}} & \bm{c_{\mathrm{2}}} & \cdots & \bm{c_{\mathnormal{n}}}\end{matrix}) C = ( c 1 c 2 ⋯ c n )
f ( b ) − f ( a ) = I f ( C ) ( b − a ) f(\bm{b})-f(\bm{a}) = \bm{I_{\mathnormal{f}}}(\bm{C})(\bm{b}-\bm{a}) f ( b ) − f ( a ) = I f ( C ) ( b − a ) である．
I = I 1 × I 2 × ⋯ × I n ⊆ R n I=I_{1}\times I_{2}\times\dotsb\times I_{n}\subseteq\mathbb{R}^{n} I = I 1 × I 2 × ⋯ × I n ⊆ R n c \bm{c} c R n \mathbb{R}^{n} R n f f f I I I C 1 C^{1} C 1 n n n A \bm{A} A
K ( X , y ) = c − A f ( c ) + ( I − A I f ( X ) ) ( y − c ) K(\bm{X},\bm{y}) = \bm{c}-\bm{A}f(\bm{c})+(\bm{I}-\bm{A}\bm{I_{\mathnormal{f}}}(\bm{X}))(\bm{y}-\bm{c}) K ( X , y ) = c − A f ( c ) + ( I − A I f ( X )) ( y − c ) が条件K ( I n × I ) ⊆ int I K(I^{n}\times I)\subseteq\operatorname{int}I K ( I n × I ) ⊆ int I I I I f f f
仮定が成り立つとき，関数g ( x ) = x − A f ( x ) g(\bm{x})=\bm{x}-\bm{A}f(\bm{x}) g ( x ) = x − A f ( x ) x ∈ I \bm{x}\in I x ∈ I A \bm{A} A x ∗ − A f ( x ∗ ) = x ∗ \bm{x^{\mathnormal{\ast}}}-\bm{A}f(\bm{x^{\mathnormal{\ast}}})=\bm{x^{\mathnormal{\ast}}} x ∗ − A f ( x ∗ ) = x ∗ x ∗ ∈ I \bm{x^{\mathnormal{\ast}}}\in I x ∗ ∈ I
まずg ( I ) ⊆ I g(I)\subseteq I g ( I ) ⊆ I x ∈ I \bm{x}\in I x ∈ I f ( x ) − f ( c ) = I f ( C ) ( x − c ) f(\bm{x})-f(\bm{c})=\bm{I_{\mathnormal{f}}}(\bm{C})(\bm{x}-\bm{c}) f ( x ) − f ( c ) = I f ( C ) ( x − c ) C ∈ I n \bm{C}\in I^{n} C ∈ I n
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 ) \begin{aligned}
g(\bm{x}) &= \bm{x}-\bm{A}(f(\bm{x})-f(\bm{c}))-\bm{A}f(\bm{c})\\
&= \bm{x}-\bm{A}\bm{I_{\mathnormal{f}}}(\bm{C})(\bm{x}-\bm{c})-\bm{A}f(\bm{c})\\
&= \bm{c}-\bm{A}f(\bm{c})+(\bm{I}-\bm{A}\bm{I_{\mathnormal{f}}}(\bm{C}))(\bm{x}-\bm{c})
\end{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 ) なのでg ( x ) = K ( C , x ) ∈ int I g(\bm{x})=K(\bm{C},\bm{x})\in\operatorname{int}I g ( x ) = K ( C , x ) ∈ int I g ( I ) ⊆ I g(I)\subseteq I g ( I ) ⊆ I
次に，g g g x , y ∈ I \bm{x},\bm{y}\in I x , y ∈ I g ( x ) − g ( y ) = I g ( C ) ( x − y ) g(\bm{x})-g(\bm{y})=\bm{I_{\mathnormal{g}}}(\bm{C})(\bm{x}-\bm{y}) g ( x ) − g ( y ) = I g ( C ) ( x − y ) C ∈ I n \bm{C}\in I^{n} C ∈ I n
∥ g ( x ) − g ( y ) ∥ ≤ ∥ I g ( C ) ∥ o p ∥ x − y ∥ ≤ sup X ∈ I n ∥ I g ( X ) ∥ o p ∥ x − y ∥ \begin{aligned}
\lVert g(\bm{x})-g(\bm{y})\rVert &\leq \lVert\bm{I_{\mathnormal{g}}}(\bm{C})\rVert_{\mathrm{op}}\lVert\bm{x}-\bm{y}\rVert\\
&\leq \sup_{\bm{X}\in I^{n}}\lVert\bm{I_{\mathnormal{g}}}(\bm{X})\rVert_{\mathrm{op}}\lVert\bm{x}-\bm{y}\rVert
\end{aligned} ∥ g ( x ) − g ( y )∥ ≤ ∥ I g ( C ) ∥ op ∥ x − y ∥ ≤ X ∈ I n sup ∥ I g ( X ) ∥ op ∥ x − y ∥ である（∥ ⋅ ∥ o p \lVert\mathord{\,\cdot\,}\rVert_{\mathrm{op}} ∥ ⋅ ∥ op f f f C 1 C^1 C 1 X \bm{X} X ∥ I g ( X ) ∥ o p \lVert\bm{I_{\mathnormal{g}}}(\bm{X})\rVert_{\mathrm{op}} ∥ I g ( X ) ∥ op I n ⊆ R n × n I^{n}\subseteq\mathbb{R}^{n\times n} I n ⊆ R n × n ∥ I g ( X ) ∥ o p < 1 \lVert\bm{I_{\mathnormal{g}}}(\bm{X})\rVert_{\mathrm{op}}\lt 1 ∥ I g ( X ) ∥ op < 1 X ∈ I n \bm{X}\in I^{n} X ∈ I n g g g
X ∈ I n \bm{X}\in I^{n} X ∈ I n ∥ ⋅ ∥ I \lVert\mathord{\,\cdot\,}\rVert_I ∥ ⋅ ∥ I
∥ ( x 1 x 2 ⋯ x n ) T ∥ I = max 1 ≤ k ≤ n ∣ x k ∣ ϕ k ( ϕ k = diam I k ) \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}) ∥( x 1 x 2 ⋯ x n ) T ∥ I = 1 ≤ k ≤ n max ϕ k ∣ x k ∣ ( ϕ k = diam I k ) で定義し，ベクトルK ( X , y ) K(\bm{X},\bm{y}) K ( X , y ) i i i K i ( y ) K_i(\bm{y}) 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 \begin{gathered}
\bm{I_{\mathnormal{g}}}(\bm{X}) = \bm{I}-\bm{A}\bm{I_{\mathnormal{f}}}(\bm{X}),\\
K(\bm{X},\bm{y}) = \bm{I_{\mathnormal{g}}}(\bm{X})\bm{y} +\bm{c}-\bm{A}f(\bm{c})-\bm{I_{\mathnormal{g}}}(\bm{X})\bm{c}
\end{gathered} 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 ) \bm{I_{\mathnormal{g}}}(\bm{X}) I g ( X ) i i i g i T \bm{g_{\mathnormal{i}}^{\mathsf{T}}} g i T
diam K i ( I ) = diam { g i T y ∣ y ∈ I } = sup { ∣ g i T ( y 1 − y 2 ) ∣ ∣ y 1 , y 2 ∈ I } = sup { ∣ g i T ( δ 1 δ 2 ⋯ δ n ) T ∣ ∣ ∣ δ k ∣ ≤ ϕ k } = sup { ∣ g i T δ ∣ ∣ ∥ δ ∥ I ≤ 1 } \begin{aligned}
\operatorname{diam}K_{i}(I) &= \operatorname{diam}\lbrace\bm{g_{\mathnormal{i}}^{\mathsf{T}}}\bm{y}\mid\bm{y}\in I\rbrace\\
&= \sup\lbrace\lvert\bm{g_{\mathnormal{i}}^{\mathsf{T}}}(\bm{y_{\mathrm{1}}}-\bm{y_{\mathrm{2}}})\rvert\mid\bm{y_{\mathrm{1}}},\bm{y_{\mathrm{2}}}\in I\rbrace\\
&= \sup\lbrace\lvert\bm{g_{\mathnormal{i}}^{\mathsf{T}}}(\begin{matrix}\delta_{1} & \delta_{2} & \cdots & \delta_{n}\end{matrix})^{\mathsf{T}}\rvert\mid\lvert\delta_{k}\rvert\leq\phi_{k}\rbrace\\
&= \sup\lbrace\lvert\bm{g_{\mathnormal{i}}^{\mathsf{T}}}\bm{\delta}\rvert\mid\lVert\bm{\delta}\rVert_{I}\leq 1\rbrace
\end{aligned} diam K i ( I ) = diam { g i T y ∣ y ∈ I } = sup {∣ g i T ( y 1 − y 2 )∣ ∣ y 1 , y 2 ∈ I } = sup {∣ g i T ( δ 1 δ 2 ⋯ δ n ) T ∣ ∣ ∣ δ k ∣ ≤ ϕ k } = sup {∣ g i T δ ∣ ∣ ∥ δ ∥ I ≤ 1 } だからdiam K i ( I ) = max { ∣ g i T e ∣ ∣ ∥ e ∥ I ≤ 1 } \operatorname{diam}K_{i}(I)=\max\lbrace\lvert\bm{g_{\mathnormal{i}}^{\mathsf{T}}}\bm{e}\rvert\mid\lVert\bm{e}\rVert_{I}\leq 1\rbrace diam K i ( I ) = max {∣ g i T e ∣ ∣ ∥ e ∥ I ≤ 1 }
max 1 ≤ i ≤ n diam K i ( I ) ϕ i = max 1 ≤ i ≤ n ( 1 ϕ i max ∥ e ∥ I ≤ 1 ∣ g i T e ∣ ) = max ∥ e ∥ I ≤ 1 max 1 ≤ i ≤ n ∣ g i T e ∣ ϕ i = max ∥ e ∥ I ≤ 1 ∥ I g ( X ) e ∥ I = ∥ I g ( X ) ∥ o p \begin{aligned}
\max_{1\leq i\leq n}\frac{\operatorname{diam}K_{i}(I)}{\phi_{i}} &= \max_{1\leq i\leq n}\biggl(\frac{1}{\phi_{i}}\max_{\lVert\bm{e}\rVert_{I}\leq 1}\lvert\bm{g_{\mathnormal{i}}^{\mathsf{T}}}\bm{e}\rvert\biggr)\\
&= \max_{\lVert\bm{e}\rVert_{I}\leq 1}\max_{1\leq i\leq n}\frac{\lvert\bm{g_{\mathnormal{i}}^{\mathsf{T}}}\bm{e}\rvert}{\phi_{i}}\\
&= \max_{\lVert\bm{e}\rVert_{I}\leq 1}\lVert\bm{I_{\mathnormal{g}}}(\bm{X})\bm{e}\rVert_{I}\\
&= \lVert\bm{I_{\mathnormal{g}}}(\bm{X})\rVert_{\mathrm{op}}
\end{aligned} 1 ≤ i ≤ n max ϕ i diam K i ( I ) = 1 ≤ i ≤ n max ( ϕ i 1 ∥ e ∥ I ≤ 1 max ∣ g i T e ∣ ) = ∥ e ∥ I ≤ 1 max 1 ≤ i ≤ n max ϕ i ∣ g i T e ∣ = ∥ e ∥ I ≤ 1 max ∥ I g ( X ) e ∥ I = ∥ I g ( X ) ∥ op である．
一方，n n n K i ( y ) K_{i}(\bm{y}) K i ( y ) I I I I I I K ( I n × I ) ⊆ int I K(I^{n}\times I)\subseteq\operatorname{int}I K ( I n × I ) ⊆ int I
diam K i ( I ) < diam I i = ϕ i , diam K i ( I ) ϕ i < 1 \operatorname{diam}K_{i}(I) \lt \operatorname{diam}I_{i}
= \phi_{i},
\quad\frac{\operatorname{diam}K_{i}(I)}{\phi_{i}} \lt 1 diam K i ( I ) < diam I i = ϕ i , ϕ i diam K i ( I ) < 1 である．よって∥ I g ( X ) ∥ o p < 1 \lVert\bm{I_{\mathnormal{g}}}(\bm{X})\rVert_{\mathrm{op}}\lt 1 ∥ I g ( X ) ∥ op < 1 g g g
最後に，A \bm{A} A A \bm{A} A A I f ( X ) \bm{A}\bm{I_{\mathnormal{f}}}(\bm{X}) A I f ( X ) A I f ( X ) v = 0 \bm{A}\bm{I_{\mathnormal{f}}}(\bm{X})\bm{v}=\bm{0} A I f ( X ) v = 0 v ≠ 0 \bm{v}\neq\bm{0} v = 0 I g ( X ) v = v \bm{I_{\mathnormal{g}}}(\bm{X})\bm{v}=\bm{v} I g ( X ) v = v ∥ I g ( X ) ∥ o p < 1 \lVert\bm{I_{\mathnormal{g}}}(\bm{X})\rVert_{\mathrm{op}}\lt 1 ∥ I g ( X ) ∥ op < 1
参考文献
Krawczyk, Robert. Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken: Newton-algorithms for evaluation of roots with error bounds. Computing . 1969, vol. 4, p. 187-201.
大石進一ほか. 精度保証付き数値計算の基礎. コロナ社, 2018, 311p.
