Reach Us
+44-1474-556909

**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

Consider the paradigmatic fixed point iteration

(1)

to locate fixed point a, F(a)=a of contracting function F(x). We write x_{1}−a=F(x_{0}) 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)

which is actually quadratic

(6)

where f’=f’(a) ≠ 0, f”=f”(a) < ∞, and where x0 is the iterative input and x_{1} 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].

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)=F_{2}(x) is such that

(14)

then

(15)

is such that

(16)

with which the iterative method x_{1}=F_{3}(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 F_{2}(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 F_{3}(x) is such that

(23)

then

(24)

is such that

(25)

and the iterative method x_{1}=F_{4}(x_{0}) 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.

Having computed x_{1}=x_{0} – f_{0}/f_{0} we return to correct it as the midpoint method

(32)

which is now cubic, or third order

(33)

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

The modified method

(34)

is cubic

(35)

and one sided. At least asymptotically, if x_{0}−a > 0, then also x_{2}−a > 0, and if x_{0}−a < 0, then also x_{2} − a < 0

Using the approximation

(36)

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

(37)

where u_{0}=f_{0}/f_{0} , x_{1}=x_{0} − u_{0}, f_{1}=f(x_{1}). All three methods of equation (37) are cubic

(38)

Convergence of this method is also one sided.

Halley’s method, or for that matter any other higher order method, can be constructed by writing δx, x_{1}=x_{0} + δx, as a power series of u_{0}=f_{0}/f’_{0} , or even of merely f_{0}=f(x_{0}). 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’^{2}_{0} ), with which the classical Halley’s method of equation (10) is recovered.

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

(44)

is quartic

(45)

See also page 184 equation (8-78).

The polynomial in r method

(46)

is also quartic

(47)

The multistep method

(48)

is quintic

(49)

The multistep method

(50)

is sextic

(51)

The method

(52)

is octic

(53)

**Contrarily converging super-quadratic methods**

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)

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.

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].

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].

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

(76)

and take f(x_{1}=x_{0} + δx)=0, ξ=x_{0} 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 s_{0}=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).

**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.

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).

- Householder AS (1970) The Numerical Treatment of a Single Nonlinear Equation. McGraw-Hill, New-York.
- Traub JF (1977) Iterative Methods for the Solution of Equations. Chelsea Publishing Company,New York.
- Petkovi´c MS, Petkovi´c LD, D?zuni´c J (2010) Accelerating generators of iterative methodsfor finding multiple roots of nonlinear equations.Computers and Mathematics withApplications 59: 2784-2793.
- Sharma JR(2005) A composite third order Newton-Steffenson method for solving nonlinear equations.Appl Math Comput169: 242-246.
- Ostrowski A (1960)Solution of Equations and Systems of Equations, Academic Press, NewYork.
- Petkovi´c M(2009) On optimal multipoint methods for solving nonlinear equations.Novi SadJ Math 39: 123-130.
- NetaB (1979) A sixth-order family of methods for nonlinear equations.Intern J ComputerMath section B 7: 157-161.
- KhattriSK, Argyros IK (2010) How to develop fourth and seventh order iterativemethods.Novi Sad J Math 40: 61-67.
- Weihong B, Hongmin R,Qingbiao W (2009) Three-step iterative methods with eighthorderconvergence for solving nonlinear equations.Journal of Computational and AppliedMathematics 225: 105-112.
- Fried I (2013) High-order iterative bracketing methods.Int J Numer Meth Engng 94: 708-714.
- King RF (1973) A family of fourth-order methods for nonlinear equations.SIAM Journal ofNumerical Analysis 10: 876-879.
- OsadaN (1994) An optimal multiple root-finding method of order three,” J ComputApplMath 51: 131-133.
- Changbum C, Hwa JB, Beny N (2009) New families of nonlinear third-order solversfor finding multiple roots.Computers Mathematics with Applications57: 1574-1582.

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

- Adomian Decomposition Method
- Algebraic Geometry
- Analytical Geometry
- Applied Mathematics
- Axioms
- Balance Law
- Behaviometrics
- Big Data Analytics
- Binary and Non-normal Continuous Data
- Binomial Regression
- Biometrics
- Biostatistics methods
- Clinical Trail
- Complex Analysis
- Computational Model
- Convection Diffusion Equations
- Cross-Covariance and Cross-Correlation
- Differential Equations
- Differential Transform Method
- Fourier Analysis
- Fuzzy Boundary Value
- Fuzzy Environments
- Fuzzy Quasi-Metric Space
- Genetic Linkage
- Hamilton Mechanics
- Hypothesis Testing
- Integrated Analysis
- Integration
- Large-scale Survey Data
- Matrix
- Microarray Studies
- Mixed Initial-boundary Value
- Molecular Modelling
- Multivariate-Normal Model
- Noether's theorem
- Non rigid Image Registration
- Nonlinear Differential Equations
- Number Theory
- Numerical Solutions
- Physical Mathematics
- Quantum Mechanics
- Quantum electrodynamics
- Quasilinear Hyperbolic Systems
- Regressions
- Relativity
- Riemannian Geometry
- Robust Method
- Semi Analytical-Solution
- Sensitivity Analysis
- Smooth Complexities
- Soft biometrics
- Spatial Gaussian Markov Random Fields
- Statistical Methods
- Theoretical Physics
- Theory of Mathematical Modeling
- Three Dimensional Steady State
- Topology
- mirror symmetry
- vector bundle

- Total views:
**12118** - [From(publication date):

July-2014 - Jul 19, 2019] - Breakdown by view type
- HTML page views :
**8328** - PDF downloads :
**3790**

**Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals**

International Conferences 2019-20