## 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.

I have used these methods quite a lot in my work. Good methods are IMO bisection and secant (only if close to the root). Regula Falsi is not so good as bisection, as it is in general not faster and is not so robust as bisection. Try Regula Falsi on the function called dirty and you have to wait a long time (with this code it fails, as too many iterations are taken). The root finding functions return the solution and the number of function evaluations used. Combining the bisection and secant methods it is possible to make a method, that works fast for all functions, that do not underflow.