Newton's method

[hobz]

I find the following confusing.

 

I compared the two Wikipedia articles with each other:

http://en.wikipedia.org/wiki/Newton%27s_method and http://en.wikipedia.org/wiki/Newton%27s_method_in_optimization

 

The first one tells us that with

[math]f'(x_{n}) = \frac{ \mathrm{rise} }{ \mathrm{run} } = \frac{ \mathrm{\Delta y} }{ \mathrm{\Delta x} } = \frac{ f( x_{n} ) - 0 }{ x_{n} - x_{n+1} } = \frac{0 - f(x_{n})}{(x_{n+1} - x_{n})}\,\![/math]

then

[math]

x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\,\!

[/math]

No restrictions what so ever as to the choice of [math]x_0[/math] (the initial value).

 

However, the second one, uses the Taylor expansion of [math]f(x)[/math]

[math]

\displaystyle f(x+\Delta x)=f(x)+f'(x)\Delta x+\frac 1 2 f'' (x) \Delta x^2

[/math]

and then restricts [math]x_0[/math] to be chosen sufficiently close to [math]x^*[/math] to ensure convergence.

 

Why this difference?

[timo]

The main difference comes from the two articles being written by different people . Further differences come from that you possibly didn't read the two articles carefully enough. Simply from skimming (hm, perhaps I shouldn't claim that others hadn't read the articles ... ), I see two things that are different/contrary to your post:

1) Article 2 doesn't claim that x0 sufficiently close to x* was necessary for convergence, but that (together with f being twice-differentiable) it was sufficient for convergence to x*.

2) Article 1 explicitly gives examples where the x_n do not converge (bottom of the article), so "no restrictions what so ever as to the choice of x_0 (the initial value)" is true in so far as that no restrictions are explicitly mentioned, but not in the sense that the article claimed there were none.

[hobz]

Thanks for your reply!

I too sometimes claim that skimming is reading on wikipedia.

So what article 1 states is that, the algorithm always will converge to a root (except in some pathological cases), however, it will only converge to the specific root x* if x_0 is close enough to that root, otherwise it WILL (again no pathology) converge towards another root? This fact could, in my opinion, had been illustrated better, if the illustration of wikipedia had two (or more) roots.

[D H]

Thanks for your reply!

So what article 1 states is that, the algorithm always will converge to a root ...

Newton's method does not always converge to a root. The first article explicitly points out that "if the starting point is not close to a root then convergence may fail to occur." Newton's method always works for a quadratic. YMMV for any equation more complex that a quadratic. Even something as innocuous as [math]x^3-1=0[/math] can be problematic; see the related wiki article on the "Newton fractal" (link here).

[hobz]

I agree, but those fall under what I called pathological examples.

Anyways, I think I got it now. The second article uses a second order Taylor expansion, to get curvature information as well, where as the first article only uses first order information.

Thanks to all who replied. I appreciate it.

[Dr. Jekyll]

Generally for convergence, the iteration function [math]\Phi(x)[/math] must fulfill [math]|\Phi'(x)|<1[/math] in a vicinity of the solution.

 

For Newton's method we have [math]\Phi(x)=x-\frac{f(x)}{f'(x)} \Rightarrow \Phi'(x)=1-(\frac{f'(x)}{f'(x)}-\frac{f(x)}{(f'(x))^2}f''(x))=\frac{f(x)f''(x)}{(f'(x))^2}[/math]

 

If now [math]f'(x_*)=0[/math] at a solution [math]f(x_*)=0[/math], problems with convergence might arise since we have [math](f'(x))^2[/math] in the denominator of [math]\Phi'(x)[/math].

[DeanK2]

The above is sufficient, yet also the root itself must be differentiable.