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