The Accelerated and Modified Newton Methods

The Accelerated and Modified Newton Methods

Background

Newton's method is commonly used to find the root of an equation.If the root is simple then the extension to Halley's method will increase the order of convergence from quadratic to cubic.At a multiple root it can be speed up with the accelerated Newton-Raphson and modified Newton-Raphson methods.

Theorem (Newton-Raphson Theorem ).Assume that and there exists a number , where .If, then there exists a such that the sequence defined by the iteration

for

will converge to for any initial approximation.

Definition (Order of a Root)Assume thatf(x)and its derivativesare defined and continuous on an interval aboutx = p.We say thatf(x) = 0has a root of ordermatx = pif and only if

.

A root of orderm = 1is often called a simple root, and ifm > 1it is called a multiple root.A root of orderm = 2is sometimes called a double root, and so on.The next result will illuminate these concepts.

Definition (Order of Convergence)Assume that converges top,and set.If two positive constantsexist, and



then the sequence is said to converge topwith order of convergence R.The numberAis called the asymptotic error constant.The casesare given specialconsideration.

(i)If, the convergence ofis called linear.

(ii)If, the convergence ofis called quadratic.

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

Ifpis a simple root, then convergence is quadratic andforksufficiently large.

Ifpis a multiple root of orderm,then convergence is linear andforksufficiently large.

Algorithm (Newton-Raphson Iteration).To find a root ofgiven an initial approximationusing the iteration

for.

Mathematica Subroutine (Newton-Raphson Iteration).

Theorem (Acceleration of Newton-Raphson Iteration)Given that the Newton-Raphson algorithm produces a sequence that converges linearly to the rootof order.Then the accelerated Newton-Raphson formula

for

will produce a sequence that converges quadratically top.

Mathematica Subroutine (Accelerated Newton-Raphson Iteration).

Example.Use the accelerated Newton's method to find the double root,of the cubic polynomial.Use the starting value
Solution.

More Background

Iff(x)has a root of multiplicitymatx=p, thenf(x)can be exssed in the form



where.In this situation, the functionh(x)is defined by



and it is easy to prove thath(x)has a simple root atx=p.When Newton's method is applied for finding the rootx=pofh(x)we obtain the following result.

Theorem (Modified Newton-Raphson Iteration)Given that the Newton-Raphson algorithm produces a sequence that converges linearly to the rootof multiplicity.Then the modified Newton-Raphson formula



which can be simplified as

for

will produce a sequence that converges quadratically top.

Mathematica Subroutine (Modified Newton-Raphson Iteration).