Newton's Method for Systems

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

Vocabulary

Local convergence, Quadratic rate of convergence, Function Iteration, Jacobian matrix

Concepts

Newton's method derivations via
Generalization of Newton's method for single variable functions
Taylor series
Quadratic rate of convergence and number of significant digits
"Derivative" appears as a matrix
Requires solution of a "totally new" linear system at each iteration step
Non-convergence and slow convergence of Newton's method:
Jacobian matrix may become singular
Oscillation similar to one dimensional case
Flat surface
Multiple root

 

Method properties:

Strength

Weaknesses

Derivation of method may be obtained from Taylor series

Determination of starting guess may not be trivial

Local convergence when approximation is close to root

Convergence or rate of convergence is not guaranteed when not close to the root

Quadratic rate of convergence when approximation is close to root

Method may not converge or may converge very slowly

Reasonably easy to implement if Jacobian matrix can be symbolically calculated

Method requires evaluation of the Jacobian matrix as well as solution of a linear system

at each iteration

 

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

Extra:
Can still view Newton's method as a fixed point iteration
Quadratic convergence follows from general theory of fixed point iteration
Theory for system of non-linear equations is still incomplete
In implementation, some approximates Jacobian matrix via finite differencing (naïve) or "automatic differencing" (sophisticated)

 

Correction to Misconceptions