October 2014 Archives

In recent posts we have concerned ourselves with numerically approximating inverses of functions, seeking a value x for which f(x) equals some desired value y.
We began with the bisection method which, whilst terrifically stable, was unfortunately rather slow, so we went on to discuss Newton's method which used the derivative of the function to make a potentially far more accurate estimate of the location of the inverse, albeit at the risk of making a catastrophically worse one; a risk we eliminated by switching back to bisection in the event that it did so.
Unfortunately, it's not always easy to calculate the derivative of a function, especially if we're numerically approximating it, so ideally we should seek an algorithm that is not quite so blind to the behaviour of the function as is the bisection method but that does not require the explicit caclulation of derivatives.

In the last post we implemented the bisection method for the numerical approximation of the inverse of a function. Now this is an extremely stable algorithm, but annoyingly not a particularly efficient one.
Fortunately, the great Isaac Newton is coming to our rescue with a significantly more efficient approach...

A common task in numerical computing is to approximate the inverse of a function. Specifically, given a function f such that

  y = f(x)

we shall often want to find a function f^-1 such that

  x = f^-1(y)