Finding Roots Using Binary or Interpolation Search

A binary search algorithm is often used to search for a certain element in a sorted sequence. It can also be used to find a point where a function is zero (if the function is monotonic over the interval, there is one such point).
Instead of dividing the interval, an interpolating search (the secant method) uses linear interpolation to guess where the root might be. This method usually converges faster than a binary search (see Details), but each step is computationally more demanding. This Demonstration provides an interactive graphical comparison of the two methods on a set of example functions.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

In general the secant method (interpolation search) converges faster than the binary search. However there are exceptions to this rule, as shown in the cubic example; the binary search converges neatly, whereas the multiple root causes a derivative to be zero, sending the interpolation far away. Such conditions can be very unfortunate for the secant method, but they can be avoided: multiple roots can be eliminated using algebraic methods, like dividing the polynomial by its derivative.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.