Reach Us +44-1474-556909
The Systematic Formation of High-Order Iterative Methods | OMICS International
ISSN: 2168-9679
Journal of Applied & Computational Mathematics
All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

# The Systematic Formation of High-Order Iterative Methods

Isaac Fried*

Department of Mathematics, Boston University, Boston, MA 02215, USA

*Corresponding Author:
Isaac Fried
Department of Mathematics, Boston University
Boston, MA 02215, USA
Tel: 1 617-353-2000
E-mail: [email protected]

Received Date: March 29, 2014; Accepted Date: May 09, 2014; Published Date: June 16, 2014

Citation: Fried I (2014) The Systematic Formation of High-Order Iterative Methods. J Appl Computat Math 3:165. doi: 10.4172/2168-9679.1000165

Copyright: © 2014 Fried I. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

Visit for more related articles at Journal of Applied & Computational Mathematics

#### Abstract

Fixed point iteration and the Taylor-Lagrange formula are used to derive, some new, efficient, high-order, up to octic, methods to iteratively locate the root, simple or multiple, of a nonlinear equation. These methods are then systematically modified to account for root multiplicities greater than one. Also derived, are super-quadratic methods that converge contrarily, and super-linear and super-cubic methods that converge alteratingly, enabling us, not only to approach the root, but also to actually bound and bracket it.

#### Keywords

Fixed point iteration; The generation of high order iterative functions; The Taylor-Lagrange formula; High-order iterative methods; Undetermined coefficients; Contrary and alternating convergence; Root bracketing

#### Fixed Point Iteration

Consider the paradigmatic fixed point iteration

(1)

to locate fixed point a, F(a)=a of contracting function F(x). We write x1−a=F(x0) a and have by power series expansion that

(2)

implying that if 0<|F’(x)|<1 near x=a, namely, if F(x) is indeed contracting, then the fixed point iteration converges linearly, and if F’(a)=0, then the fixed point iteration converges quadratically, and so on.

Suppose now that we are seeking root a, f(a)=0, f’(a) ≠ 0, of function f(x). To secure a quadratic iterative method we rewrite f(x)=0 as the equivalent fixed point problem

(3)

for weight function w(x),w(a) ≠ 0, which we seek to fix to our advantage. For a quadratic method we need w(x) to be such that

(4)

for x near a. Since f (a)=0, we choose to ignore w’(x) f(x) in the above equation, to have w(x)=−1/f’(x), and with it, Newton’s method

(5)

(6)

where f’=f’(a) ≠ 0, f”=f”(a) < ∞, and where x0 is the iterative input and x1 the iterative output.

From the two zero conditions

(7)

we obtain, after ignoring f(x) w”(x) in the second of equations (7), the system of equations

(8)

which we solve for w(x) as

(9)

to have Halley’s method

(10)

which is, indeed, cubic

(11)

provided that f(a)=0, but f’(a) ≠ 0

Requesting that F(a)=a, F’(a)=0, F”(a)=0, F’”(a)=0, we similarly obtain the method

(12)

which is quartic

(13)

provided that f’=f’(a) ≠ 0.

Higher order single-point methods are readily obtained by requesting higher order derivatives of F(x)=x+w(x) f(x) to to zero at x=a, f (a)=0 [1].

#### A Recursive Determination of the Higher Order Iterative Function

There are various ways to recursively generate a new higher order iterative function F(x) of equation (1) from a known lower order one. Traub [2] has suggested such a rational recursive formula. If, for example, F(x)=F2(x) is such that

(14)

then

(15)

is such that

(16)

with which the iterative method x1=F3(x0) to locate fixed point a, F(a)=a becomes cubic

(17)

Instead of rational formula (15) we suggest the product formula

(18)

with which we still have third order convergence

(19)

For example, for Newton’s method F2(x)=x–f(x)/f’(x). Using formula (18) we obtain by it the method

(20)

which is, indeed, cubic

(21)

provided that f’=f’(a) ≠0.

Iterative method (20) is also obtained from Halley’s method of equation (10) using the approximation

(22)

Further, if F3(x) is such that

(23)

then

(24)

is such that

(25)

and the iterative method x1=F4(x0) to locate fixed point a is quartic

(26)

It is well known that the modified Newton’s method

(27)

converges quadratically to a root of any multiplicity m ≥ 1. From equation (24) we derive the third order method

(28)

Indeed, assuming that

(29)

we obtain for the method in equation (28)

(30)

where A=g(a), B=g’(a), C=g”(a), and m is the multiplicity index of repeating root a [3].

From equation (29) we have

(31)

by which we may, knowing an x close to a, estimate m.

#### A One-Sided Third-Order Two-Step, or Chord, Method

Having computed x1=x0 – f0/f0 we return to correct it as the midpoint method

(32)

which is now cubic, or third order

(33)

The modified method

(34)

is cubic

(35)

and one sided. At least asymptotically, if x0−a > 0, then also x2−a > 0, and if x0−a < 0, then also x2 − a < 0

Using the approximation

(36)

equation (32) becomes the two-step, or chord, method

(37)

where u0=f0/f0 , x1=x0 − u0, f1=f(x1). All three methods of equation (37) are cubic

(38)

See Traub [2-4].

Convergence of this method is also one sided.

#### Construction of High-Order Iterations by Undetermined Coefficients

Halley’s method, or for that matter any other higher order method, can be constructed by writing δx, x1=x0 + δx, as a power series of u0=f0/f’0 , or even of merely f0=f(x0). For example, we write the quadratic

(39)

and then sequentially fix the undetermined coefficients P and Q for highest attainable order of convergence.

Thus, at first we have from equation (39) that

(40)

and we set P=−1/f’0 . With this P we have next that

(41)

and we set

(42)

with which the polynomial method of equation (20) is recovered.

Doing the same to the rational method

(43)

we determine by power series expansion that cubic convergence is assured for P=−1/f00,

Q=0, R=1, S=−f”0/(2f’20 ), with which the classical Halley’s method of equation (10) is recovered.

#### Quartic and Quintic Multistep Methods

The rational two-step method (a generalization of the method in equation (37)) of Ostrowski [5] appendix G,

(44)

is quartic

(45)

Traub [2,3,6-8]

The polynomial in r method

(46)

is also quartic

(47)

The multistep method

(48)

is quintic

(49)

#### Sextic and Octic Multistep Methods

The multistep method

(50)

is sextic

(51)

The method

(52)

is octic

(53)

[6,9]

We write

(54)

for undetermined coefficient P, and have

(55)

We request that

(56)

for parameter k, by which the iterative method in equation (54) turns into

(57)

for any constant k, and

(58)

This super-quadratic method converges from above if k>0, and from below if k<0

The interest in the method

(59)

is that it ultimately converges oppositely to Newton’s method,

(60)

as is seen by comparing equation (60) with equation (6).

The average of Newton’s method and the method of equation (59) is cubic,

(61)

#### Alternaingly Converging Super-Linear and Super- Cubic Methods

We start by modifying Newton’s method

(62)

to have

(63)

indicating that, invariably, the method converges, at least asymptotically, alternatingly. For k > 0, if x0 − a > 0, then x1 − a < 0, and vice versa. For a higher-order alternating method we rewrite the originally quartic method of equation (46) as

(64)

for the undetermined coefficient Q, and have that

(65)

This super cubic method converges alternatingly if parameter k > 0.

#### Correction for Multiple Roots by Undetermined Coefficients

We rewrite Newton’s method as

(66)

for undetermined coefficient P, and have that for a root of multiplicity m ≥ 1

(67)

where A=g(a), B=g’(a) for g(x) in equation (29). Quadratic convergence is restored, as is well known, with P=m.

With P=m(1−k), k<0 the modified Newton’s method of equation (66) becomes superliner and ultimately of alternating convergence [10].

Next, we rewrite the method in equation (37) as

(68)

and seek to fix correction coefficients P and Q so that convergence remains cubic even in the event that root a is of multiplicity m > 1. By power series expansion we determine that

(69)

upholds cubic convergence

(70)

where A=g(a), B=g’(a),C=g”(a) for g(x) in equation (29)

The method

(71)

is also cubic

(72)

where A=g(a), B=g’(a), C=g”(a) for g(x) in equation (29) [11-13].

#### Correction of Halley’s Method for Multiple Roots

We rewrite Halley’s method of equation (10) for the undetermined coefficient P and Q as

(73)

and determine by power series expansion that for

(74)

convergence remains cubic for a root of any multiplicity m ≥ 1

(75)

where A=g(a), B=g’(a),C=g”(a) for g(x) in equation (29) [11,12].

#### Use of the Taylor-Lagrange formula

We write the second order version of the Taylor-Lagrange formula

(76)

and take f(x1=x0 + δx)=0, ξ=x0 to obtain the iterative method

(77)

We approximate the solution of the increment equation

(78)

or, for that matter, any such higher order algebraic equation, by the power series

(79)

and have upon substitution and collection that

(80)

from which we have that

(81)

where s0=f”0/f’0

The methods

(82)

or

(83)

are both cubic

(84)

provided that f’(a) ≠0.

The method

(85)

converges cubically as well to a root of any multiplicity m ≥ 1

(86)

where A=g(a), B=g’(a),C=g”(a) for g(x) in equation (29).

#### Still Higher Order Methods

Starting with

(87)

we obtain the iterative method

(88)

where

(89)

with

(90)

The methods

(91)

are both quartic

(92)

provided that f’(a) ≠ 0.

#### Unknown Root Multiplicity

The two single-step methods

(93)

converge contrarily to root a of any multiplicity m

(94)

where A=g(a), B=g’(a) for g(x) in equation (29). Their average is a cubic method

(95)

where A=g(a), B=g’(a),C=g”(a) for g(x) in equation (29).

#### References

Select your language of interest to view the total content in your interested language

### Article Usage

• Total views: 12118
• [From(publication date):
July-2014 - Jul 19, 2019]
• Breakdown by view type
• HTML page views : 8328