Newton-Raphson Method (Univariate)

In general, if more information can be assumed available, a more effective and efficient method can be expected. The Newton-Raphson method is yet another way to solve the general equation #tex2html_wrap_inline2962#, which requires more information (derivative #tex2html_wrap_inline2964#) and converges more quickly (quadratic) than the methods previously discussed.

Specifically, we first consider the Taylor series expansion of the function #tex2html_wrap_inline2966# at any #tex2html_wrap_inline2968# as an initial guess of the root:

#math305# #tex2html_wrap_indisplay6576# (44)

If #tex2html_wrap_inline2970# is linear, i.e., its slope #tex2html_wrap_inline2972# is a constant for any #tex2html_wrap_inline2974#, then the second and all higher order terms are all zero, and the equation becomes

#math306# #tex2html_wrap_indisplay6581# (45)

solving which we get the root #tex2html_wrap_inline2976#:

#math307# #tex2html_wrap_indisplay6584# (46)

where #math308##tex2html_wrap_inline2978# is the step or increment we need to take to go from the initial guess #tex2html_wrap_inline2980# to the root #tex2html_wrap_inline2982#:

#math309# #tex2html_wrap_indisplay6589# (47)

If #tex2html_wrap_inline2992# is nonlinear, the sum of the first two terms of the Taylor series is its approximation, and the result in Eq. (#NR1linear#919>) is only an approximation of the root, which can be further improved iteratively to move from the initial guess #tex2html_wrap_inline2994# towards the root #tex2html_wrap_inline2996#, as illustrated in the figure below:

#math310# #tex2html_wrap_indisplay6594# (48)

**<#6595#>Figure<#6595#> 1.10:** <#6596#>Newton-Raphson Method<#6596#>
[width=70mm]<#927#>figures/NewtonRaphson.eps<#927#>

The Newton-Raphson method can be considered as the fixed-point iteration #math311##tex2html_wrap_inline2998# based on

#math312# #tex2html_wrap_indisplay6600# (49)

based on the assumption that #tex2html_wrap_inline3000#. The root #tex2html_wrap_inline3002# at which #tex2html_wrap_inline3004# is also the fixed point of #tex2html_wrap_inline3006#, i.e., #tex2html_wrap_inline3008#. For the iteration to converge, #tex2html_wrap_inline3010# needs to be a contraction with #tex2html_wrap_inline3012#. Consider

#math313# #tex2html_wrap_indisplay6609# (50)

At the root #tex2html_wrap_inline3014# where #tex2html_wrap_inline3016#, if #tex2html_wrap_inline3018#, then #tex2html_wrap_inline3020#, i.e., #tex2html_wrap_inline3022# is a contraction and the iteration #math314##tex2html_wrap_inline3024# converges quadratically when #tex2html_wrap_inline3026# is close enough to #tex2html_wrap_inline3028#.

Here are some additional considerations of the Newton-Raphson methods:

If #tex2html_wrap_inline3030# (with a horizontal tangent line), the iteration cannot proceed, but we can modify #tex2html_wrap_inline3032# by adding a small value #tex2html_wrap_inline3034# to #tex2html_wrap_inline3036# so that #math315##tex2html_wrap_inline3038#.
It is difficult to know the number of roots of a nonlinear equation (unlike the case of a linear equation), which can vary from zero (e.g., #tex2html_wrap_inline3040#) to infinity (e.g., #tex2html_wrap_inline3042#). One can try different initial guesses in the range of interest to see if different roots can be found.
Sometime a parameter #tex2html_wrap_inline3044# can be used to control the step size of the iteration:
#math316# #tex2html_wrap_indisplay6627# (51)
- If #tex2html_wrap_inline3046#, the iteration is de-accelerated. Although the convergence becomes slower, this may be desirable if the function #tex2html_wrap_inline3048# is not smooth with many local variations.
- If #tex2html_wrap_inline3050#, the iteration is accelerated. The convergence may or may not be accelerated. Due to the greater step size, the root may be skipped and missed. Sometimes the convergence may become significantly slowed or even oscillate around the true root, such as the example shown in the figure below with #tex2html_wrap_inline3052#.
<#6632#>Figure<#6632#> 1.11: <#6633#>Ocsillation<#6633#>
[width=70mm]<#952#>figures/ocsillation.eps<#952#>

**<#6632#>Figure<#6632#> 1.11:** <#6633#>Ocsillation<#6633#>
[width=70mm]<#952#>figures/ocsillation.eps<#952#>

The Newton-Raphson method converges quadratically:

#math317# #tex2html_wrap_indisplay6636# (52)

as shown in Appendix 2 of this chapter, i.e., it converges more quickly than both the bisection method (#tex2html_wrap_inline3054#) and the secant method (#tex2html_wrap_inline3056#).

<#962#>Example:<#962#>

#math318# #tex2html_wrap_indisplay6640# (53)

Obviously this equation has a repeated root #tex2html_wrap_inline3058# as well as a single root #tex2html_wrap_inline3060#. We have

#math319# #tex2html_wrap_indisplay6644# (54)

Note that at the root #tex2html_wrap_inline3062# we have #math320##tex2html_wrap_inline3064#. We further find:

#math321# #tex2html_wrap_indisplay6648# (55)

and

#math322#

#tex2html_wrap_indisplay6650#	#tex2html_wrap_indisplay6651#	#tex2html_wrap_indisplay6652#
	#tex2html_wrap_indisplay6653#	#tex2html_wrap_indisplay6654#

We therefore have

#math323# #tex2html_wrap_indisplay6656# (56)

We see that the iteration converges quadratically to the single root #tex2html_wrap_inline3066#, but only linearly to the repeated root #tex2html_wrap_inline3068#.

We consider in general a function with a repeated root at #tex2html_wrap_inline3070# of multiplicity #tex2html_wrap_inline3072#:

#math324# #tex2html_wrap_indisplay6662# (57)

its derivative is

#math325# #tex2html_wrap_indisplay6664# (58)

As #tex2html_wrap_inline3074#, the convergence of the Newton-Raphson method to #tex2html_wrap_inline3076# is linear, rather than quadratic.

In such case, we can accelerate the iteration by using a step size #tex2html_wrap_inline3078#:

#math326# #tex2html_wrap_indisplay6669# (59)

and

#math327# #tex2html_wrap_indisplay6671# (60)

Now we show that this #tex2html_wrap_inline3080# is zero at the repeated root #tex2html_wrap_inline3082#, therefore the convergence to this root is still quadratic.

We substitute #math328##tex2html_wrap_inline3084#, #math329##tex2html_wrap_inline3086#, and

#math330#

	#tex2html_wrap_indisplay6677#
#tex2html_wrap_indisplay6678#	#tex2html_wrap_indisplay6679#
	#tex2html_wrap_indisplay6680#	(61)

into the expression for #tex2html_wrap_inline3088# above to get (after some algebra):

#math331#

#tex2html_wrap_indisplay6683#	#tex2html_wrap_indisplay6684#	#tex2html_wrap_indisplay6685#
	#tex2html_wrap_indisplay6686#	#tex2html_wrap_indisplay6687#	(62)

At #tex2html_wrap_inline3090#, we get

#math332# #tex2html_wrap_indisplay6690# (63)

i.e., the convergence to the repeated root at #tex2html_wrap_inline3092# is no longer linear but quadratic.

The difficulty, however, is that the multiplicity #tex2html_wrap_inline3094# of a root is unknown ahead of time. If #tex2html_wrap_inline3096# is used blindly some root may be skipped, and the iteration may oscillate around the real root.

<#1029#>Example:<#1029#>

#math333# #tex2html_wrap_indisplay6695# (64)

This equation has a double root #tex2html_wrap_inline3098# and a single root #tex2html_wrap_inline3100#. We compare the iteration based on either #math334##tex2html_wrap_inline3102# or #math335##tex2html_wrap_inline3104#.

First use an initial guess #tex2html_wrap_inline3106#.
- When #tex2html_wrap_inline3108# is used, the convergence is linear around the double root #tex2html_wrap_inline3110#. It takes 16 iterations to get #math336##tex2html_wrap_inline3112# with #math337##tex2html_wrap_inline3114#:
  
  #math338# #tex2html_wrap_indisplay6706#
- When #tex2html_wrap_inline3116# is used, the convergence is quadratic around the double root #tex2html_wrap_inline3118#. It takes only 3 iterations to get #tex2html_wrap_inline3120# with #tex2html_wrap_inline3122#:
  
  #math339# #tex2html_wrap_indisplay6712#
  
  <#6713#>Figure<#6713#> 1.12: <#6714#>Newton-Raphson Method Example 1<#6714#>
  [width=110mm]<#1049#>figures/NRg1.eps<#1049#>
Next use a different initial guess #tex2html_wrap_inline3124#.
- If #tex2html_wrap_inline3126# is used, it takes 7 iterations to get #tex2html_wrap_inline3128# with #tex2html_wrap_inline3130#, the convergence is quadratic.
  
  #math340# #tex2html_wrap_indisplay6721#
  
  <#6722#>Figure<#6722#> 1.13: <#6723#>Newton-Raphson Method Example 2<#6723#>
  [width=110mm]<#1062#>figures/NRg3.eps<#1062#>
- If #tex2html_wrap_inline3132# is used, oscillation happens as shown in the figure below. However, if a better initial guess #tex2html_wrap_inline3134# is used instead of #tex2html_wrap_inline3136#, it takes only one step to get #tex2html_wrap_inline3138# with #tex2html_wrap_inline3140#, the convergence is significantly accelerated.
  #math341# #tex2html_wrap_indisplay6731#
  
  <#6732#>Figure<#6732#> 1.14: <#6733#> Example 3<#6733#>
  [width=110mm]<#1073#>figures/NRg4.eps<#1073#>
  
  132
<#6735#>Figure<#6735#> 1.15: <#6736#>Fixed Point Example 4<#6736#>
[width=100mm]<#1079#>figures/NRg2b.eps<#1079#>

133