An Improved Newton's Method

Theorem 1 (Convergence Rate for Newton-Raphson Iteration)Assume that Newton-Raphson iteration (2) produces a sequence that converges to the rootpof the function.

(6)Ifpis a simple root, then convergence is quadratic and

forksufficiently large.

(7)Ifpis a multiple root of orderm,then convergence is linear and

forksufficiently large.

There are two common ways to use Theorem 1 and gain quadratic convergence at multiple roots. We shall call these methods A and B (see Mathews, 1987, p. 72 and Ralston & Rabinowitz, 1978, pp. 353-356).

Method A.Accelerated Newton-Raphson

Suppose thatpis a root of order .Then the accelerated Newton-Raphson formula is:

(8).

Let the starting valuebe close top, and compute the sequence iteratively;

(9)for

Then the sequence generated by (9) will converge quadratically top.

Mathematica Subroutine (Accelerated Newton-Raphson Iteration).

On the other hand, ifthen one can show that the functionhas a simple root at.

Usingin place ofin formula (1) yields Method B.

Method B.Modified Newton-Raphson

Suppose thatpis a root of order .Then the modified Newton-Raphson formula is:

(10)

Let the starting valuebe close top, and compute the sequenceiteratively;

(11)
for

Then the sequence generated by (11) converges quadratically top.

Mathematica Subroutine (Modified Newton-Raphson Iteration).

Limitations of Methods A and B

Method A has the disadvantage that the ordermof the root must be known a priori.Determiningmis often laborious because some type of mathematical analysis must be used.It is usually found by looking at the values of the higher derivatives of.That is ,has a root of order mat if and only if

(12).

Dodes (1978, pp. 81-82) has observed that in practical problems it is unlikely that we will know the multiplicity.However, a constantmshould be used in (8) to speed up convergence, and it should be chosen small enough so that does not shoot to the wrong side ofp.Rice (1983, pp. 232-233) has suggested a way to empirically findm.If is a good approximation topand , and somewhat distant fromthenmcan be determined by the calculation:

.

Method B has a disadvantage, it involves three functions.Again, the laborious task of finding the formula forcould detract from using Method B.Furthermore, Ralston and Rabinowitz (1978, pp. 353-356) have observed thatwill have poles at points where the zeros ofare not roots of .Hence,may not be a continuous function.

The New Method C.Adaptive Newton-Raphson

The adaptive Newton-Raphson method incorporates a linear search method with formula (8).Starting with,the following values are computed:

(13)for.

Our task is to determine the valuemto use in formula (13), because it is not known a priori.First, we take the derivative ofin formula (5), and obtain:

(14)

When (5) and (14) are substituted into formula (1) we have which can be simplified to get

.

This enables us to rewrite (13) as

(15).

We shall assume that the starting valueis close enough topso that

(16),where.

The iterates in (15) satisfy the following:

(17)for

If we subtractpfrom both sides of (17) then



and the result after simplification is:

(18).

Since,the iteratesget closer topasjgoes from,which is manifest by the inequalities:

(19).

The valuesare shown in Figure 1.

Notice that if the iteration (15) was continued forthencould be larger than.This is proven by using the derivatives in (12) and the Taylor polynomial approximation of degreemforexpanded about:

(20).

Figure 1.The valuesfor the "linear search" obtained by using formula (15)
near a "double root"p(of order).Notice that.

Ifis closer topthanthen (19) and (20) imply that, hence we have:

(21).

Therefore, the way to computationally determinemis to successively compute the valuesusing formula (13) foruntil we arrive at.

The New Adaptive Newton-Raphson Algorithm

Start with,then we determine the next approximation as follows:

Observe that the above iteration involves a linear search in either the intervalwhenor in the intervalwhen.In the algorithm, the valueis stored so that unnecessary computations are avoided.After the pointhas been found, it should replaceand the process is repeated.

Mathematica Subroutine (Adaptive Newton-Raphson Iteration).

Example.Use the valueand compare Methods A,B and C for finding the double rootof the equation.
Solution.

Behavior at a Triple Root

When the function has a triple root, then one more iteration for the linear search in (13) is necessary.The situation is shown in Figure 2.

Figure 2. The valuesfor the "linear search" obtained by using formula (15)
near a "triple root"p(of order
).Notice that
.