## Root Finding

### March 14, 2014

We begin with the bisection method; the midpoint is just the average of *lo* and *hi*, and iteration stops when the difference between *lo* and *hi* is less than *epsilon*:

`(define (bisection f lo hi epsilon)`

(let loop ((lo lo) (f-lo (f lo)) (hi hi) (f-hi (f hi)))

(let* ((mid (/ (+ lo hi) 2)) (f-mid (f mid)))

(cond ((or (zero? f-mid) (< (abs (- hi lo)) epsilon)) mid)

((= (signum f-lo) (signum f-mid))

(loop mid f-mid hi f-hi))

(else (loop lo f-lo mid f-mid))))))

There are two changes for the *regula falsi* method. First, the midpoint is linear interpolation between *lo* and *hi*, instead of just their simple average. Second, since one of the endpoints never moves during *regula falsi*, the stopping criterion occurs when the difference between the new midpoint and one of the old endpoints is less than *epsilon*:

`(define (regula-falsi f lo hi epsilon)`

(let loop ((lo lo) (f-lo (f lo)) (hi hi) (f-hi (f hi)))

(let* ((mid (/ (- (* f-lo hi) (* f-hi lo)) (- f-lo f-hi))) (f-mid (f mid)))

(cond ((or (zero? f-mid) (< (abs (- mid lo)) epsilon) (< (abs (- mid hi)) epsilon)) mid)

((= (signum f-lo) (signum f-mid))

(loop mid f-mid hi f-hi))

(else (loop lo f-lo mid f-mid))))))

For example, we can find the root between 1 and 10 of the function sin(*x*) * *x*^{3} in any of four ways:

`> (bisection f 1. 10. 1e-12)`

3.141592653589697

> (bisection f 10. 1. 1e-12)

3.141592653589697

> (regula-falsi f 1. 10. 1e-12)

3.1415926535883956

> (regula-falsi f 10. 1. 1e-12)

3.1415926535883956

The `signum`

function is +1 if its argument is positive, −1 if its argument is negative, and 0 if its argument is zero; it’s implementation is given at http://programmingpraxis.codepad.org/jtw5uNay, where you can run the program.

Pages: 1 2

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.