Quadratic approximation
- Author:
- Ryan Hirst
Improving the root-hunting method.
Assume there are two, distinct points where the first derivative is zero, and consider a root which lies on an outside arm of the cubic...
Desirable properties:
Convergence is very fast (almost a decimal of accuracy per iteration).
We may choose ε arbitrarily, and the initial guess is very good.
Each step switches from over- to under- estimate: the roots is approached from both sides.
It is a proper sequence: the result of one step can be used directly in the next (without control flow/ checking intermediate values).
Using what we know about the cubic, this method can be reduced to a single, continued fraction... {link}
____________
Establishing the properties:
There are probably easier ways, but I chose this one:
Compare the curvature of the cubic at B, and the parabola with vertex B, passing through f(b+ε), ε>0. Invariably, the curvature of the parabola is greater at the vertex. That is, the radius of curvature of the parabola vertex is smaller. Provided you and I agree that there is exactly one intersection of the two curves to the right of B, this is sufficient to establish that the parabola lies to the left of the cubic in b<x< c, and to the right for x > c.
So if f(c) > 0, the parabola crosses the x-axis before it intersects the curve: the zero crossing is an underestimate of the root. And if f(c) < 0, the parabola crosses the curve before intersecting the x-axis: the zero crossing is an overestimate of the root. Formally,
The change of sign is the desired magic. From there it remains to prove/verify that each estimate is closer to the curve than the previous. (For example, lie on the same side of the root. Is it possible, under the given assumptions, for |x2-x1| > |x0-x1| ?