ニュートン法の問題がどうしてもわからないので教えてください。

質問

非線形方程式の解を求めるアルゴリズムのひとつに、ニュートン法と呼ばれる方式がある。この方法ではf(x)=0の解の近似値を次の漸化式から求める。
x_(i+1) =x_i - f(x_i)/f'(x_i)

なぜこのアルゴリズムで解を得られるのかをf(x)=x^2 - e^x -2 =0
を例に説明せよ。

という問題です。
どなたかわかる方がいたらお願いします。

回答No.5

stomachman

ニュートン法のキモチとしては、出発値をx、解をsとして、
ε=s-x
とおく。
f(s)=f(x+ε)=f(x)+f'(x)ε+R
とテイラー展開できる場合に、(Rはεの2次以上の項）
x-f(x)/f'(x)=s+R/f'(x)
なので、もし|R/f'(x)|がうんと小さければx-f(x)/f'(x)はxより解sに近くなる。それどころか、ひとたび解のごく近くまで行くと、あとは「繰り返しごとに有効数字の桁数が倍になる（2次収束）」という、もの凄い勢いで収束する。
　でも、解から遠いところから出発した場合には旨く行くとは限らない。実は、例に挙がっている f(x)=x^2 - e^x -2 ）の場合には、（xが実数の場合に限ると）どんな初期値から出発しても解に行き着けることが証明できる。しかし、これは「たまたま」に過ぎないのであり、ANo.2にある通り、「どんな初期値から出発しても解に行き着ける、というわけには行かない方程式」はいくらでもあります。
　例えば、折れ線グラフになってる関数を考えると、ニュートン法が旨く行かない例は簡単に作れるでしょう。また、至る所何回でも微分可能な関数であっても、たとえば、
f(x)=x^5-45x^3
なんて簡単な例ですら、
x_i=5
から出発すると
x_(i+1)=-5, x_(i+2)=5,....となって収束しない。
　あるいは、
f(x)=x e^(-x^2)
だと、x_iが解(0)に近いときは収束するが、さもないと発散しちゃうのは明らかでしょう。

　なので、「なぜこのアルゴリズムで解を得られるのかを説明せよ」って言われたって、そりゃあ無理ナンダイ。

回答No.4

alice_38

解に近づくはず…
その根拠は？

回答No.3

Ishiwara

要するに、ニュートン法の原理を直観的に理解したいわけですよね。
ｆ(x)＝０を「解く」ということは、f(x)がｘ軸と交わる場所を知りたいということです。
まず、曲線上に適当な点を１つとります。これが「第１の点」です。その点で曲線f(x)に接線を引き、その接線とｘ軸の交点を求めます。この交点から真上または真下に線を伸ばし、曲線と交わったところを「第２の点」とします。こうして、次々に第３、第４…と求めていけば、限りなく「解」に近づくはずです。
この「図形操作」と「漸化式」が「同質」のものあることを理解してください。

回答No.2

alice_38

ニュートン法は、
任意の方程式で、勝手な初期値から出発して
収束するという保証は無い。
ただし、収束するならば、漸化式よりただちに
x_∞ = x_∞ - f(x_∞) / f'(x_∞) だから、
f(x_∞) = 0 と分かる。

ニュートン法で、期待する解が得られるような
初期値を探す問題は、一般には非常に難しく、
それは、複雑系の生い立ちの一つでもある。

回答No.1

spring135

url参照。

　要は適当な点から出発して曲線とx軸の交点を求める方法です。
点（x0,f(x0))における接線は
y-f(x0)=f'(x0)(x-x0)
接線とx軸の交点ではｙ＝0、この時
x=x0-f(x0)/f'(x0)
これをurlの図のように繰り返す時
点（xn,f(xn))における接線とx軸の交点xn+1は
xn+1=xn-f(xn)/f'(xn)

例題は大して難しいものではありません。
f(x)=x^2 - e^x -2
とすればよろしい。

参考URL：

http://ja.wikipedia.org/wiki/%E3%83%8B%E3%83%A5%E3%83%BC%E3%83%88%E3%83%B3%E6%B3%95