Appendix 2: Order of Convergence of the Newton-Raphson Method

The order of convergence of the Newton-Raphson iteration can be found based on the Taylor expansion of #tex2html_wrap_inline3418# at the neighborhood of the root #tex2html_wrap_inline3420# (Section #TalorSeries#1927>):

#math468# #tex2html_wrap_indisplay7003# (104)

where #tex2html_wrap_inline3422# is the error at the nth step. Substituting the Newton-Raphson's iteration

#math469# #tex2html_wrap_indisplay7006# (105)

into the equation above, we get

#math470#

#tex2html_wrap_indisplay7008#	#tex2html_wrap_indisplay7009#	#tex2html_wrap_indisplay7010#
	#tex2html_wrap_indisplay7011#	#tex2html_wrap_indisplay7012#
	#tex2html_wrap_indisplay7013#	#tex2html_wrap_indisplay7014#	(106)

i.e.

#math471# #tex2html_wrap_indisplay7016# (107)

When #math472##tex2html_wrap_inline3424# all the higher order terms disappear, and the above can be written as

#math473# #tex2html_wrap_indisplay7019# (108)

Alternatively, we can get the Taylor expansion in terms of #tex2html_wrap_inline3426#:

#math474# #tex2html_wrap_indisplay7022# (109)

Subtracting #tex2html_wrap_inline3428# from both sides we get:

#math475# #tex2html_wrap_indisplay7025# (110)

Now we find #tex2html_wrap_inline3430# and #tex2html_wrap_inline3432#:

#math476# #tex2html_wrap_indisplay7029# (111)

and

#math477#

#tex2html_wrap_indisplay7031#	#tex2html_wrap_indisplay7032#	#tex2html_wrap_indisplay7033#
	#tex2html_wrap_indisplay7034#	#tex2html_wrap_indisplay7035#	(112)

Evaluating these at #tex2html_wrap_inline3434# at which #tex2html_wrap_inline3436#, and substituting them back into the expression for #tex2html_wrap_inline3438# above, we see that the linear term is zero as #tex2html_wrap_inline3440#, and get the same result as in Eq. (#NRconvergence1#1993>):

#math478# #tex2html_wrap_indisplay7041# (113)

We see that if #tex2html_wrap_inline3442#, the order of convergence of the Newton-Raphson method is #tex2html_wrap_inline3444# with the rate of convergence #math479##tex2html_wrap_inline3446#. However, if #tex2html_wrap_inline3448#, the convergence is linear rather than quadratic, as shown in some of the examples.