Is There a More Efficient Version of Newton's Method Using Higher Derivatives?

[defunc]

Are there any variations of Newtons method, say where you use higher derivatives?

 

[HallsofIvy]

I don't know of any that are commonly used but it's not hard to extend the basic idea.

In "Newton' method", we approximate the function by its tangent line at a given point, and determine where that line crosses y= 0.

We could, as well, approximate the function by a parabola that (1) passes through the given point, (2) has the same slope their, and (3) has the same second derivative.

That is, to solve f(x)= 0, start with some given point [itex](x_0, f(x_0))[/itex], at which f(x) has derivative [itex]f'(x_0)[/itex] and second derivative [itex]f''(x_0)[/itex].

We can write a parabola through [itex](x_0, f(x_0))[/itex] as [itex]y= a(x- x_0)^2+ b(x- x_0)+ f(x_0)[/itex]. That has derivative, at [itex]x= x_0[/itex], [itex]y'= b[/itex] and second dervative [itex]y''= 2a[/itex] so that the "approximating parabola" is [itex]f''(x_0)(x- x_0)^2/2+ f'(x_0)(x- x_0)+ f(x_0)[/itex]. Set that equal to 0 and solve for x to get the next x at which to approximate.

But the fact is that there are just some "approximating" methods that are just so good, any improvement by a "better" approximation just isn't worth the additional work. Newton's method is one of those!

 

[Studiot]

As usually presented Newton's method is intended for a single unknown variable.
Hamming gives an improved method, sensitive to the difference between the current approximation and the last.

There is an equivalent method when you have a system of equations usng the Jacobian in place of the first derivative.

 

[Shaybay92]

We could, as well, approximate the function by a parabola that (1) passes through the given point, (2) has the same slope their, and (3) has the same second derivative.

Isnt this method the basic idea behind Taylor Polynomials?

 

[hotvette]

Are there any variations of Newtons method, say where you use higher derivatives?

Yep, Halley's method uses 2nd derivatives in addition to first derivatives. If Newton's method converges quickly, Halley's method is turbo charged.

http://en.wikipedia.org/wiki/Halley's_method

 

[Count Iblis]

The following method is often used when the evaluating the function is very time consuming. You first find a few starting values. E.g. if y(x) is your finction, you find two points x1 and x2 such that y changes siign and then you do, say, two bisection steps, ending up with four points. Then you do an interpolation using the four points, but not of y asa function of x, but instead of x as a function of y. In that interpolating polynoimial, x(y) you simply put y equal to zero and you obtain a very accurate estimate of the zero of y.

You then throw away the first point and construct a new interpolating polynomial using the last four points, insert y = 0 in there and then iterate this process.