Programming Praxis

[ Today’s exercise was written by guest author Paul Hofstra, who holds a PhD in Theoretical Nuclear Physics from the Free University in Amsterdam and is now retired from a major oil company. Guest authors are always welcome; contact me at the link in the menu bar if you are interested in writing for Programming Praxis. ]

We studied root finding by the bisection and regula falsi methods in a previous exercise. Both methods have linear convergence, meaning that the error is reduced by a constant factor at each iteration; for example, for bisection the error reduces by half at each iteration. Of the two methods, the regula falsi method can be fast some times and slow other times, so the more consistent bisection method is generally preferred. In today’s exercise we look at two other methods, the secant method and Dekker’s method, which both have super-linear convergence.

The secant method is similar to regula falsi, but whereas the regula falsi method holds one endpoint constant, the secant method can move either endpoint, using the last two iterates to calculate the new point. That means the secant method can wander off outside the original interval in its attempt to find a root.

Theodorus Dekker’s 1969 method combines the root bracketing property of the bisection method with the super-linear convergence of the secant method. Dekker uses three points, a and b which bracket the solutions (so f(a) and f(b) have opposite signs) and c which tracks the last position of b. Every iteration does:

1. If f(b is not the smallest of the three points (in an absolute sense), then swap a and b and make c equal to a.
2. Calculate the bisections step x = (a − b) / 2.
3. If f(b) is zero or |x| is less than the desired tolerance return b.
4. Calculate the secant step s, making sure not to divide by zero.
5. Set c to the current value of b. If s is in the interval [0, x] then set b = b + s, otherwise set b = b + x.
6. If the new b has the opposite sign as the old b, set a to c.

Step 5 contains the main logic. If the secant step is between b and (a − b) / 2, then take the secant step, otherwise take the bisection step. Dekker’s method is simple, very powerful, fast, and works on any continuous function.

Your task is to write programs that implement the secant and Dekker root finders. 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.

Pages: 1 2