Newton's Method

Objectives
Newton's method derivations
strength and weaknesses of the method
interpretation of quadratic convergence

Vocabulary

Local convergence, Quadratic rate of convergence, Function Iteration

Concepts

Newton's method derivations via
Taylor series
Graphical linear approximation
Quadratic rate of convergence and number of significant digits
Non-convergence of Newton's method:
Iterant at extremal point
Flat curve at infinity
Oscillation
Slow convergence of Newton's method
Multiple zeros
Flat curve

Method properties:

Strength

Weaknesses

Derivation of method may be obtained from Taylor series and graphical approaches

Determination of Starting guess may not be trivial

Local, Quadratic rate of convergence when approximation is close to root

Convergence rate is not guaranteed when approximation is not close to the root

Occasionally method may have an even higher rate of convergence

Method may not converge

Error estimate available under reasonable assumptions

Method may converge very slowly

Reasonably Easy to implement

Method requires evaluation of functions and derivatives at each iteration

Very efficient method to find roots of polynomials

Stopping criteria choice not obvious

May be used to find complex roots

Requires initial guess to be complex in order to find a complex root

Method may be extended to higher dimension

Construction of derivative (Jacobian matrix) in higher dimension is not trivial

Extra:
Modification of Newton's method for multiple zeros
Use of m f/f': Drawback - need a priori knowledge of number of multiple zeros
Apply Newton's method to f/f': Drawback - need to evaluate f'' and have round error problem
Horner's scheme and Newton's method for polynomials
Cubic convergence of Newton's method
Basin of attraction and fractal - logistic equation and cubic root.

Correction to Misconceptions

In practice, it is possible to have convergence for Newton's method even if the initial guess is far away from the zeros. 

Back to Top