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.
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.
Full text...