この記事は,
旧ブログ から移植された記事です. よって, その内容として,
旧ブログ に依存した文脈が含まれている可能性があります. 予めご了承下さい.
久しぶりにまたなにか d3.js で視覚化してみたくなったのだが,
このエントリがポストされる次の日はアイザック・ニュートン の誕生日らしいので, 今回はニュートン法 (Newton Raphson 法) を視覚化してみることにした.
早速であるが以下がその成果物である.
f ( x ) = 0 f(x)=0 f ( x ) = 0 f ( x ) f(x) f ( x ) f ′ ( x ) f'(x) f ′ ( x ) 2 \sqrt{2} 2
これで終わってしまうと何とも寂しいので, 一応簡単にニュートン法について書く.
ニュートン法はとても有名な方程式の近似解を求める方法の 1 つである.
連続的関数 f ( x ) f(x) f ( x ) f ( x ) = 0 f(x)=0 f ( x ) = 0 x x x x n x_{n} x n f ( x ) f(x) f ( x ) f ′ ( x n ) f'(x_{n}) f ′ ( x n ) x n + 1 x_{n+1} x n + 1 f ( x ) = 0 f(x)=0 f ( x ) = 0 f ′ ( x n ) f'(x_{n}) f ′ ( x n ) x n + 1 x_{n+1} x n + 1 ( x n , 0 ) , ( x n , f ( x n ) ) , ( x n + 1 , 0 ) (x_{n},0), (x_{n},f(x_{n})), (x_{n+1}, 0) ( x n , 0 ) , ( x n , f ( x n )) , ( x n + 1 , 0 ) f ′ ( x n ) = ( x n ) x n − x n + 1 f'(x_{n})=\frac{(x_{n})}{x_{n}-x_{n+1}} f ′ ( x n ) = x n − x n + 1 ( x n ) x n + 1 = x n − f ( x n ) f ′ ( x n ) x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{n})} x n + 1 = x n − f ′ ( x n ) f ( x n ) 2 \sqrt{2} 2 x 2 = 2 ⇔ x 2 − 2 = 0 x^2=2\Leftrightarrow x^2-2=0 x 2 = 2 ⇔ x 2 − 2 = 0 f ( x ) = x 2 − 2 , f ′ ( x ) = 2 x f(x)=x^2-2,f'(x)=2x f ( x ) = x 2 − 2 , f ′ ( x ) = 2 x x n − x n 2 − 2 2 x n x_{n}-\frac{x^2_{n}-2}{2x_{n}} x n − 2 x n x n 2 − 2 f ′ ( x n ) f'(x_{n}) f ′ ( x n ) 0 0 0
また, f ( x ) f(x) f ( x ) 2 \sqrt{2} 2 − 1 -1 − 1 − 2 -\sqrt{2} − 2 f ′ ( x 0 ) f'(x_0) f ′ ( x 0 )
なおニュートン法は 1 変数関数のみならず多変数関数に対しても同様にして解を求めることができる.
あまり厳密には書かないが, まずは簡単のために 2 変数の関数
f 1 ( x , y ) , f 2 ( x , y ) f_{1}(x,y),f_{2}(x,y) f 1 ( x , y ) , f 2 ( x , y ) f 1 ( x , y ) , f 2 ( x , y ) f_{1}(x,y),f_{2}(x,y) f 1 ( x , y ) , f 2 ( x , y ) 全微分 をすればよいので, 結局
( x n + 1 , y n + 1 ) = ( x n , y n ) T − ∂ f ( x n , y n ) − 1 ( f 1 ( x n , y n ) , f 2 ( x n , y n ) ) T
(x_{n+1},y_{n+1})=(x_{n},y_{n})^T-{\partial f(x_{n},y_{n})}^{-1}(f_{1}(x_{n}, y_{n}),f_{2}(x_{n},y_{n}))^T
( x n + 1 , y n + 1 ) = ( x n , y n ) T − ∂ f ( x n , y n ) − 1 ( f 1 ( x n , y n ) , f 2 ( x n , y n ) ) T
ここで
∂ f ( x , y ) : = ( ∂ f 1 ( x , y ) ∂ x ∂ f 1 ( x , y ) ∂ y ∂ f 2 ( x , y ) ∂ x ∂ f 2 ( x , y ) ∂ y )
\begin{aligned}\partial f(x,y):=
\left(\begin{array}{cc}
\frac{\partial f_{1}(x,y)}{\partial x} & \frac{\partial f_{1}(x,y)}{\partial y} \\
\frac{\partial f_{2}(x,y)}{\partial x} & \frac{\partial f_{2}(x,y)}{\partial y}
\end{array}\right)
\end{aligned}
∂ f ( x , y ) := ( ∂ x ∂ f 1 ( x , y ) ∂ x ∂ f 2 ( x , y ) ∂ y ∂ f 1 ( x , y ) ∂ y ∂ f 2 ( x , y ) )
なお ∂ f ( x , y ) \partial f(x,y) ∂ f ( x , y ) ∂ f ( x n , y n ) − 1 ( f 1 ( x n , y n ) , f 2 ( x n , y n ) ) T {\partial f(x_{n},y_{n})}^{-1}(f_{1}(x_{n}, y_{n}),f_{2}(x_{n},y_{n}))^T ∂ f ( x n , y n ) − 1 ( f 1 ( x n , y n ) , f 2 ( x n , y n ) ) T ∂ f ( x n , y n ) a = ( f 1 ( x n , y n ) , f 2 ( x n , y n ) ) T \partial f(x_{n},y_{n}){\boldsymbol a}=(f_{1}(x_{n}, y_{n}),f_{2}(x_{n},y_{n}))^T ∂ f ( x n , y n ) a = ( f 1 ( x n , y n ) , f 2 ( x n , y n ) ) T ( x n , y n ) T − a (x_n,y_n)^T-{\boldsymbol a} ( x n , y n ) T − a
因みに, 上記で描画される接線は, 単純に ラグランジュの補完公式より
y − y 1 = y 2 − y 1 x 2 − x 1 ( x − x 1 ) y-y_{1}=\frac{y_{2}-y_{1}}{x_{2}-x_{1}}(x-x_{1}) y − y 1 = x 2 − x 1 y 2 − y 1 ( x − x 1 ) g ( x ⋆ ) g(x^{\star}) g ( x ⋆ ) y 2 = 0 y_{2}=0 y 2 = 0 ( x , f ( x ) ) , ( x − f ( x ) f ′ ( x ) , 0 ) (x,f(x)),(x-\frac{f(x)}{f'(x)},0) ( x , f ( x )) , ( x − f ′ ( x ) f ( x ) , 0 )
g ( x ⋆ ) = f ( x ) f ( x ) f ′ ( x ) ( x ⋆ − x + f ( x ) f ′ ( x ) ) = f ′ ( x ) ( x ⋆ − x + f ( x ) f ′ ( x ) ) = f ′ ( x ) x ⋆ − f ′ ( x ) x + f ( x )
\begin{aligned}
g(x^{\star})&=&\frac{f(x)}{\frac{f(x)}{f'(x)}}(x^{\star}-x+\frac{f(x)}{f'(x)}) \\
&=&f'(x)(x^{\star}-x+\frac{f(x)}{f'(x)}) \\
&=&f'(x)x^{\star}-f'(x)x+f(x)
\end{aligned}
g ( x ⋆ ) = = = f ′ ( x ) f ( x ) f ( x ) ( x ⋆ − x + f ′ ( x ) f ( x ) ) f ′ ( x ) ( x ⋆ − x + f ′ ( x ) f ( x ) ) f ′ ( x ) x ⋆ − f ′ ( x ) x + f ( x )
と導ける.