Lecture 6

Newton's method and the secant method for finding the roots of arbitrary functions.

Motivated by finding something that converges quicker that the bisection algorithm we looked at two additional methods for root finding, Newton's method is based on the Taylor expansion of a function at a point that we "guess" is close to the root. If conditions are favorable then Newton's algorithm converges toward the root very quickly. One drawback though, is that we need to determine the first derivative of the function. The secant method deals with this issue by approximating the first derivative by using a finite difference.

A rough guide to the convergence rates of these methods is as follows
convergence rate
Bisection O(n)
Newton O(n2)
Secant O(n1.6)

The convergence rates are just one aspect of each method. There are also issues regarding arithmetic accuracy, and implementation details, An industrial strength root finding method would use a hybrid approach that borrows good aspects from each method to reach an effective and practical solution,

On Monday I plan to illustrate the MATLAB implementations of these methods and briefly touch upon some practical consideration.

This weeks lectures are based on material in section 5.3 (Taylor series and truncation errors), and
sections 6.3 6.4 and 6.5. The Ellis notes classes 1 and 4 covers Taylors theorem and convergence issues. Classes 5 and 6 cover Bisection, Newton, and secant methods for root finding.

Posted: Fri - September 24, 2004 at 12:33 PM