情報系(ニュートン法)

サイトのTOP→理系インデックス
情報系のTOP→情報系インデックス





参考 ( ニュートン法は数値解析の入口 )

よく知られているように、数学の世界は、代数・解析・幾何の3つに分類される。

とくに、代数は 『 離散の世界 』 であり、解析は 『 連続の世界 』 である。

離散はコンピュータとの相性がよい。

例えば、行列はそのままコンピュータに応用される。

しかし、連続性をそのままコンピュータで扱うことはできない。

よって、何らかの離散的なアルゴリズムによって連続性にアプローチする必要がある。

その代表的な例が 『 ニュートン法 』 である。

ニュートン法は数値解析の入口である。

ちなみに、数値解析のテーマとして 『 差分方程式 』 がある。

よく知られているように、常微分方程式は工学で有用である。

しかし、常微分方程式のような連続的な概念をそのままコンピュータで扱うことはできない。

そこで、常微分方程式の離散化である差分方程式も有用である。

P1 ( ニュートン法 )

f:[a、b]→ を関数とする。

f は [a、b] 上で f’’(x)>0 であるとする。

f(a)<0、f(b)>0 とする。

(xn∈ を、x=b、xn+1=x−f(x)/f’(x) によって定める。(★0)

このとき、ある η∈[a、b] が一意に存在して、limn→∞=η かつ f(η)=0 となる。

補足

仮定が f(a)>0、f(b)<0 である場合は、x=a として漸化式(★0)を実行する。

仮定が f’’(x)<0、f(a)<0、f(b)>0 である場合は、f(x) を −f(x) として漸化式(★0)を実行する。

証明

いま、f(a)<0、f(b)>0 である。

よって、ある x∈[a、b] が存在して、f(x)=0 となる。(※中間値の定理)

そのような x 全体の最小数を η と表す。

いま、ある c∈(a、η) が存在して、−f(a)/(η−a)=f’(c)>0 となる。(※平均値の定理)

よって、f は [c、b] 上で狭義単調増加である。(※定理の仮定)(★1)

よって、[a、b] 上で f(x)=0 の解は η のみである。(★2)

−−−−−−−−−−−−−−−−−−−−

x=x における y=f(x) の接線は y−f(x)=f’(x)(x−x) である。

接線と x 軸の交点を xn+1 と表す。

いま、(★0)と(★1)より、f’(x)>0 である。

よって、xn+1=x−f(x)/f’(x) である。(★3)

−−−−−−−−−−−−−−−−−−−−

以下、任意の n∈ に対して f(x)≧0 となることを示す。

ある n∈ が存在して、f(x)>0>f(xn+1) となるとする。(背理法)

いま、(★3)より、x>xn+1 である。

また、f(η)=0 より、x>η>xn+1 である。

g(x)=f’(x)(x−x)+f(x) とおく。

いま、y=g(x) は点 (x、f(x)) における y=f(x) の接線である。

また、f は下に凸である。

よって、g(η)<f(η) である。

一方、y=g(x) は (xn+1、0) と (x、f(x)) を結ぶ直線である。

よって、区間(x、xn+1) において g(x)>0 である。

よって、f(η)>g(η)>0 である。

これは矛盾である。

以上により、任意の n∈ に対して f(x)≧0 である。(★4)

−−−−−−−−−−−−−−−−−−−−

(★4)より、任意の n∈ に対して x≧η である。

また、(★3)より、x≧xn+1 である。

つまり、(x) は下に有界な減少列である。

よって、(x) は収束する。(※実数の連続性)

そこで、limn→∞=λ とおく。

(★3)より、λ=λ−f(λ)/f’(λ) である。

いま、f(λ)>0 である。

よって、f(λ)=0 である。

よって、(★2)より、λ=η である。

P2 ( ニュートン法の誤差評価 )

f:[a、b]→ を関数とする。

f は [a、b] 上で f’’(x)>0 であるとする。

f(a)<0、f(b)>0 とする。

(xn∈ を、x=b、xn+1=x−f(x)/f’(x) によって定める。

M を、f’’(x)/f’(x) の最大値とする。

ηを、(x) の極限とする。( つまり、f(η)=0 である )

ε=x−η とおく。( つまり、ε はニュートン法による n 回目の誤差である )

このとき、εn+1<Mε である。

証明

いま、[η、x] 上で f と f’ は狭義単調増加である。(※P1の証明)

よって、ある c、c∈(η、x) が存在して、次を満たす。(※平均値の定理)

(*1) f(x)=f(η)+εf’(c)=εf’(c

(*2) f’(x)=f’(η)+εf’’(c

また、ε=x−η>0、f’(x)>0、f’(η)−f’(c)<0 である。

よって、