Newton-Raphson Method (Univariate)

To solve equation , we first consider the Taylor series expansion of at any point :

 (66)

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

 (67)

Solving this equation we get the root at which :

 (68)

where is the step we need to take to go from the initial point to the root :

 (69)

If is nonlinear, the sum of the first two terms of the Taylor expansion is only an approximation of , and the resulting found above can be treated as an approximation of the root, which can be improved iteratively to move from the initial point towards the root, as illustrated in the figure below:

 (70)

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

 (71)

The root at which is also the fixed point of , i.e., . For the iteration to converge, needs to be a contraction with . Consider

 (72)

• At the root where , if , then , i.e., is a contraction and the iteration converges quadratically when is close to .
• If (the tangent is horizontal), the iteration cannot proceed, but we can modify by adding a small value to so that .
• 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., ) to infinity (e.g., ). One can try different initial guesses in the range of interest to see if different roots can be found.
• Sometime a parameter can be used to control the step size of the iteration:

 (73)

• If , the iteration is de-accelerated. Although the convergence becomes slower, this may be desirable if the function is not smooth with many local variations.

• If , 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 .

The order of convergence of the Newton-Raphson iteration can be found based on the Taylor expansion of at the neighborhood of the root :

 (74)

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

 i.e. (75)

into the equation above, we get
 0 (76)

i.e.

 (77)

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

 (78)

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

 (79)

Subtracting from both sides we get:

 (80)

Now we find and :

 (81)

and
 (82)

Evaluating these at at which , and substituting them back into the expression for above, the linear term is zero as , i.e., the convergence is quadratic, and we get the same result:

 (83)

We see that, if , then the order of convergence of the Newton-Raphson method is , and the rate of convergence is . However, if , the convergence is linear rather than quadratic, as shown in the example below.

Example: Consider solving the equation

 (84)

which has a repeated root as well as a single root . We have

 (85)

Note that at the root we have . We further find:

 (86)

and

We therefore have

 (87)

We see the iteration converges quadratically to the single root , but only linearly to the repeated root .

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

 (88)

its derivative is

 (89)

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

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

 (90)

and

 (91)

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

We substitute , , and

 (92)

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

At , we get

 (94)

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

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

Example: Consider solving , with a double root and a single root . In the following, we compare the performance of both and .

• First use an initial guess .
• When is used, the convergence is linear around the double root . It takes 16 iterations to get with :

• When is used, the convergence is quadratic around the double root . It takes only 3 iterations to get with :

• Next use a different initial guess .
• If is used, it takes 7 iterations to get with , the convergence is quadratic.

• If is used, oscillation happens as shown in the figure below. However, if a better initial guess is used instead of , it takes only one step to get with , the convergence is significantly accelerated.