Unit 2:  Open Methods

III. Newton-Raphson Method (Most widely used) 

  • Newton method approximates any given f(x) by a linear function (linear model); solves the linear model to get a new guess. 
  • Derivations:


    • Expand f(x) using Taylor Series:  f(x) = f(xk) + f'(xk)(x-xk)

    At the solution f(x) = 0 = f(xk) + f'(xk)(x-xk)
     
    Rearranging: 


Multi-dimensional case for Newton-Raphson Method:
 
Talyor Series of m functions with n variables:


 

where

 
 
= J (Jacobian)

with m = n
Set 

Advantages and Disadvantages:

     
  • The method is very expensive - It needs the function evaluation and then the derivative evaluation. 
  • If the tangent is parallel or nearly parallel to the x-axis, then the method does not converge. 
  • Usually Newton method is expected to converge only near the solution.
  • The advantage of the method is its order of convergence is quadratic.
  • Convergence rate is one of the fastest when it does converges


When Newton's Method Does not Converge: 

Rewrite as:   , where

k - is a scalar parameter which is adjusted to either less than 1 or more than 1 (=1 is the original Newton method) to force convergence. 
Nonlinear System of Equations:

Recall that the Newton equation for nonlinear equation is:

where J is the numerical Jacobian matrix calculated at every iteration using the current solution xk.  The above equation can be modified such that there is no need for an inverse (inverse costs twice as much to solve as the following): 
where correction step sk is calculated by solving 
To solve a system of nonlinear equations using Newton method, in each iteration we solve a system of linear equations using the current Jacobian matrix.
 

Example: Find x, where x3 = 3