Reach Us +44-1474-556909
The Systematic Formation of High-Order Iterative Methods | OMICS International
ISSN: 2168-9679
Journal of Applied & Computational Mathematics
Make the best use of Scientific Research and information from our 700+ peer reviewed, Open Access Journals that operates with the help of 50,000+ Editorial Board Members and esteemed reviewers and 1000+ Scientific associations in Medical, Clinical, Pharmaceutical, Engineering, Technology and Management Fields.
Meet Inspiring Speakers and Experts at our 3000+ Global Conferenceseries Events with over 600+ Conferences, 1200+ Symposiums and 1200+ Workshops on Medical, Pharma, Engineering, Science, Technology and Business
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


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.


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

Equation (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

Equation (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

Equation (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

Equation (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

Equation (5)

which is actually quadratic

Equation (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

Equation (7)

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

Equation (8)

which we solve for w(x) as

Equation (9)

to have Halley’s method

Equation (10)

which is, indeed, cubic

Equation (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

Equation (12)

which is quartic

Equation (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

Equation (14)


Equation (15)

is such that

Equation (16)

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

Equation (17)

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

Equation (18)

with which we still have third order convergence

Equation (19)

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

Equation (20)

which is, indeed, cubic

Equation (21)

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

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

Equation (22)

Further, if F3(x) is such that

Equation (23)


Equation (24)

is such that

Equation (25)

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

Equation (26)

It is well known that the modified Newton’s method

Equation (27)

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

Equation (28)

Indeed, assuming that

Equation (29)

we obtain for the method in equation (28)

Equation (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

Equation (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

Equation (32)

which is now cubic, or third order

Equation (33)

See also Traub [2] page 164 equations (8-12).

The modified method

Equation (34)

is cubic

Equation (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

Equation (36)

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

Equation (37)

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

Equation (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

Equation (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

Equation (40)

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

Equation (41)

and we set

Equation (42)

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

Doing the same to the rational method

Equation (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,

Equation (44)

is quartic

Equation (45)

Traub [2,3,6-8]

See also page 184 equation (8-78).

The polynomial in r method

Equation (46)

is also quartic

Equation (47)

The multistep method

Equation (48)

is quintic

Equation (49)

Sextic and Octic Multistep Methods

The multistep method

Equation (50)

is sextic

Equation (51)

The method

Equation (52)

is octic

Equation (53)


Contrarily converging super-quadratic methods

We write


for undetermined coefficient P, and have


We request that


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


for any constant k, and


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

The interest in the method


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


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

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


Alternaingly Converging Super-Linear and Super- Cubic Methods

We start by modifying Newton’s method


to have


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


for the undetermined coefficient Q, and have that


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

Correction for Multiple Roots by Undetermined Coefficients

We rewrite Newton’s method as


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


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


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


upholds cubic convergence


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

The method


is also cubic


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


and determine by power series expansion that for


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


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


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


We approximate the solution of the increment equation


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


and have upon substitution and collection that


from which we have that


where s0=f”0/f’0

The methods




are both cubic


provided that f’(a) ≠0.

The method


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


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

Still Higher Order Methods

Starting with


we obtain the iterative method






The methods


are both quartic


provided that f’(a) ≠ 0.

Unknown Root Multiplicity

The two single-step methods


converge contrarily to root a of any multiplicity m


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


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


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

Share This Article

Article Usage

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