alexa
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

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

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)

then

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)

then

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)

[6,9]

Contrarily converging super-quadratic methods

We write

Equation(54)

for undetermined coefficient P, and have

Equation(55)

We request that

Equation(56)

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

Equation(57)

for any constant k, and

Equation(58)

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

The interest in the method

Equation(59)

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

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

Equation(61)

Alternaingly Converging Super-Linear and Super- Cubic Methods

We start by modifying Newton’s method

Equation(62)

to have

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

Equation(64)

for the undetermined coefficient Q, and have that

Equation(65)

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

Correction for Multiple Roots by Undetermined Coefficients

We rewrite Newton’s method as

Equation(66)

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

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

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

Equation(69)

upholds cubic convergence

Equation(70)

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

The method

Equation(71)

is also cubic

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

Equation(73)

and determine by power series expansion that for

Equation(74)

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

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

Equation(76)

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

Equation(77)

We approximate the solution of the increment equation

Equation(78)

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

Equation(79)

and have upon substitution and collection that

Equation(80)

from which we have that

Equation(81)

where s0=f”0/f’0

The methods

Equation(82)

or

Equation(83)

are both cubic

Equation(84)

provided that f’(a) ≠0.

The method

Equation(85)

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

Equation(86)

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

Still Higher Order Methods

Starting with

Equation(87)

we obtain the iterative method

Equation(88)

where

Equation(89)

with

Equation(90)

The methods

Equation(91)

are both quartic

Equation(92)

provided that f’(a) ≠ 0.

Unknown Root Multiplicity

The two single-step methods

Equation(93)

converge contrarily to root a of any multiplicity m

Equation(94)

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

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