Root Finding
March 14, 2014
Finding the roots of an equation is an important operation in mathematics, and there are many algorithms for finding roots numerically. We will study two of those algorithms in today’s exercise, and perhaps we will look at other algorithms in future exercises.
Let’s begin with the rules of the game. We are given a univariate function f(x) and want to find one or more values of x such that f(x) = 0. The function could be a polynomial, or could use trigonometric or exponential functions, or integrals, or any other mathematical operation.
The bisection algorithm starts with two points lo and hi that bound the root; thus, one of f(lo) and f(hi) is positive and the other is negative. The algorithm is iterative; at each step, the midpoint mid = (lo + hi) / 2 is found, the function f(mid) is evaluated at the midpoint, and then it replaces either lo or hi, whichever has the same sign. Iteration stops if f(mid) = 0 or if the difference between lo and hi is sufficiently small.
The regula falsi method is similar, but instead of calculating the center midpoint it calculates the midpoint at the point where a line connecting the current lo and hi crosses the axis. The method dates to the ancient Egyptians and Babylonians.
Both methods work only when the function f is continuous, with no discontinuities between lo and hi.
Your task is to write functions that find roots by the bisection and regula falsi methods. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 