Inverse quadratic interpolation is another root-finding algorithm besides bisection, Newton’s, and secant method. The way that inverse quadratic interpolation works is similar to secant method. However, instead of using two points as secant method, inverse quadratic interpolation use three points to get the next point.

Inverse quadratic interpolation works as following:

1)       Select three points, x0, x1, and x2 that x0 < x1 < x2. A root must be inside the interval of x0 and x2. Same as other methods, x0 and x2 must “close enough” to the root.

2)       Find f(x0), f(x1), and f(x2) as y0, y1, and y2.

3)       Here is the tricky part of this algorithm. For points (x0, y0), (x1, y1), and (x2, y2), we need to find an inverse quadratic function to satisfy all of them. That is in the form of x = ay² + by + c.

4)       For the next step, we find the intersection, (x’, y’), of the inverse quadratic function on x, which is simply is the constant c in the above inverse quadratic function.

5)       Finally, we need to set x0 = x1, x1 = x2 and x2 = x’ and go into next recursion.

The behavior of inverse quadratic interpolation is usually very good. According to Wikipedia, it converges to root faster than secant method but slightly slower than Newton’s method. However, pure inverse quadratic interpolation also has a weak point. If y0 = y1 or y1 = y2, an inverse quadratic function for these three points does not exist, so we have no way the find the next point. Therefore we need to initial points are close enough to the root.

One way of solving this problem is combining inverse quadratic interpolation with secant method. Test 1: or each recursion step, we test whether y0 = y1 or y1 = y2 is true. If y0 = y1 is true, we will use secant method with x1, x2. If y1 = y2 is true, we use x0, x1 for secant method. Test 2: for a new point we just got from inverse quadratic interpolation, if it is outside the interval, we use the middle point and an edge point that have different y values with second method to find the next point (x’, y’). After this, we replace the point we did use for secant method with x’ and come back to inverse quadratic interpolation.

http://en.wikipedia.org/wiki/Inverse_quadratic_interpolation