ON SOME AITKEN-STEFFENSEN-HALLEY-TYPE METHODS
FOR APPROXIMATING THE ROOTS OF SCALAR EQUATIONS

ION PĂVĂLOIU^∗

Abstract.

In this note we extend the Aitken-Steffensen method to the Halley transformation. Under some rather simple assumptions we obtain error bounds for each iteration step; moreover, the convergence order of the iterates is $3$ , i.e. higher than for the Aitken-Steffensen case.

1991 Mathematics Subject Classification:

65H05

^∗”T. Popoviciu” Institute of Numerical Analysis, P.O. Box 68-1, 3400 Cluj–Napoca, Romania, e-mail: pavaloiu@ictp-acad.math.ubbcluj.ro.

1. Introduction

Let $f:\left[a,b\right]\rightarrow\mathbb{R}$ , $a,b\in\mathbb{R}$ , $a<b$ and suppose that $f\in C^{4}\left[a,b\right]$ , and $f^{\prime}\left(x\right)>0$ , $\forall x\in\left[a,b\right]$ . Consider the function $h:\left[a,b\right]\rightarrow\mathbb{R}$ given by

h\left(x\right)=\tfrac{f\left(x\right)}{\sqrt{f^{\prime}\left(x\right)}}.

As it was shown in [2], the Halley method for solving:

(1)

f\left(x\right)=0,

is given by

(2)

x_{n+1}=x_{n}-\tfrac{h\left(x_{n}\right)}{h^{\prime}\left(x_{n}\right)},\qquad n% =0,1,\ldots,\;x_{0}\in\left[a,b\right].

This sequence is in fact generated by the Newton method for solving $h\left(x\right)=0.$

The first and second order derivatives of $h$ are given by

(3)

\displaystyle h^{\prime}\left(x\right)

\displaystyle=\tfrac{2(f^{\prime}\left(x\right))^{2}-f^{\prime\prime}\left(x% \right)\cdot f\left(x\right)}{2\left(f^{\prime}\left(x\right)\right)^{3/2}}

(4)

\displaystyle h^{\prime\prime}\left(x\right)

\displaystyle=\tfrac{3(f^{\prime\prime}\left(x\right))^{2}-2f^{\prime\prime% \prime}\left(x\right)f^{\prime}\left(x\right)}{4(f^{\prime}\left(x\right))^{5/% 2}}\cdot f\left(x\right)

which yield the following equalities for a solution $\bar{x}$ of (1):

(5)		$\displaystyle h^{\prime}\left(\bar{x}\right)$	$\displaystyle=\left(f^{\prime}\left(\bar{x}\right)\right)^{1/2},\qquad\text{and}$
(6)		$\displaystyle h^{\prime\prime}\left(\bar{x}\right)$	$\displaystyle=0.$

Relation (6) ensures the convergence order $3$ for the sequence $\left(x_{k}\right)_{k\geq 0}$ .

In the papers [2]–[8] and [12] there are studied the convergence and the convergence order of some sequences generated by some interpolatory methods applied to equation $h\left(x\right)=0$ .

We shall consider other two equations equivalent to (1) of the form:

(7)		$\displaystyle x-\varphi_{1}\left(x\right)$	$\displaystyle=0,\qquad\text{and}$
(8)		$\displaystyle x-\varphi_{2}\left(x\right)$	$\displaystyle=0$

The Aitken method for solving $h\left(x\right)=0$ is given by the iteration

(9)

x_{n+1}=\varphi_{1}\left(x_{n}\right)-\tfrac{h\left(\varphi_{1}\left(x_{n}% \right)\right)}{\left[\varphi_{1}\left(x_{n}\right),\varphi_{2}\left(x_{n}% \right);h\right]},\qquad n=0,1,\ldots,\ x_{0}\in\left[a,b\right].

In this note we shall study the convergence of these iterates. We shall show that the functions $\varphi_{1}$ and $\varphi_{2}$ may be chosen in order to obtain bilateral approximations at each iteration step; this fact allows the control of the errors. On the other hand, the convergence order of $\left(x_{n}\right)_{n\geq 0}$ given by (9) is at least equal to $3$ .

Hypotheses $f\in C^{4}\left[a,b\right]$ and $f^{\prime}\left(x\right)>0$ , $\forall x\in\left[a,b\right]$ imply, taking into account (5), that there exist $\alpha,\beta\in\mathbb{R},$ $a\leq\alpha<\bar{x}<\beta\leq b$ such that $h^{\prime}\left(x\right)>0,\forall x\in\left[\alpha,\beta\right]$ .

2. ERROR EVALUATION AND LOCAL CONVERGENCE

Consider the interval $\left[\alpha,\beta\right]$ given above. We shall make the following assumptions on $\varphi_{1}$ and $\varphi_{2}$ :

i.

the function $f\in C^{4}\left[a,b\right];$
ii.

equation (1) has the solution $\bar{x}\in[a,b];$
iii.

the inequality $f^{\prime}\left(x\right)>0$ holds for $x\in\left[\alpha,\beta\right];$
iv.

the function $\varphi_{1}$ verifies the relation $0<\left[x,y;\varphi_{1}\right]<1$ for all $x,y\in\left[\alpha,\beta\right]$ , where $\left[x,y;\varphi\right]$ denotes the first order divided difference of $\varphi$ on $x$ and $y$ ;
v.

the function $\varphi_{2}$ verifies the relations $-1<\left[x,y;\varphi_{2}\right]<0$ for all $x,y\in\left[\alpha,\beta\right].$

We can state the following result:

Theorem 2.1.

Assume that i–v hold, and for some $x_{0}\in\left[\alpha,\beta\right]$ sufficiently close to $\bar{x}$ we have $\varphi_{1}\left(x_{0}\right),\varphi_{2}\left(x_{0}\right)\in\left[\alpha,% \beta\right].$ Then the following relations hold:

j.

the sequences $\left(x_{n}\right)_{n\geq 0},\left(\varphi_{1}\left(x_{n}\right)\right)_{n\geq 0}$ and $\left(\varphi_{2}\left(x_{n}\right)\right)_{n\geq 0}$ converge to $\bar{x}$ ;
jj.

for any $n=0,1,\ldots,$ one has

$\left|\bar{x}-x_{n+1}\right|\leq\max\big\{\left|x_{n+1}-\varphi_{1}\left(x_{n}% \right)\right|,\left|x_{n+1}-\varphi_{2}\left(x_{n}\right)\right|\big\};$
jjj.

there exists $k\in\mathbb{R},$ $k>0,$ which does not depend on $n\in\mathbb{N}$ such that

$\left|x_{n+1}-\bar{x}\right|\leq k\left|x_{n}-\bar{x}\right|^{3},\qquad n=0,1,\dots$

Proof.

By $\varphi_{1}(x_{0}),\varphi_{2}(x_{0})\in[\alpha,\beta]$ it obviously follows that $h^{\prime}(\varphi_{1}(x_{0}))>0$ and $h^{\prime}(\varphi_{2}(x_{0}))>0.$ Denote by $I_{0}$ the interval having the extremities $\varphi_{1}(x_{0})$ and $\varphi_{2}(x_{0}).$ We notice, taking into account the mean formula, that

[\varphi_{1}(x_{0}),\varphi_{2}(x_{0});h]>0.

When $x_{0}<\bar{x},$ by iv. and $\bar{x}=\varphi_{1}(\bar{x})$ it follows $\varphi_{1}(x_{0})<\bar{x}$ . Analogously, $\varphi_{1}(x_{0})>\bar{x}$ for $x_{0}>\bar{x}.$ Taking into account v. and $\bar{x}=\varphi_{2}(\bar{x})$ we get $\varphi_{2}(x_{0})>\bar{x}$ for $x_{0}<\bar{x}$ and $\varphi_{2}(x_{0})<\bar{x}$ for $x_{0}>\bar{x}.$ It is obvious that in both situations $\bar{x}\in I.$ It can be easily seen that for all $n=0,1,\ldots$ we have

\varphi_{1}\left(x_{n}\right)-\tfrac{h\left(\varphi_{1}\left(x_{n}\right)% \right)}{\left[\varphi_{1}\left(x_{n}\right),\varphi_{2}\left(x_{n}\right);h% \right]}=\varphi_{2}\left(x_{n}\right)-\tfrac{h\left(\varphi_{2}\left(x_{n}% \right)\right)}{\left[\varphi_{1}\left(x_{n}\right),\varphi_{2}\left(x_{n}% \right);h\right]},

which, for $n=0$ imply $x_{1}>\varphi_{1}(x_{0})$ and $x_{1}<\varphi_{2}(x_{0})$ if $x_{0}<\bar{x},$ respectively $x_{1}<\varphi_{1}(x_{0})$ and $x_{1}>\varphi_{2}(x_{0})$ if $x_{0}>\bar{x},$ i.e., $x_{1}\in\operatorname*{int}I_{0}.$ It is clear now that, analogously, $x_{1}<\varphi_{1}(x_{1})<\bar{x}<\varphi_{2}(x_{1})$ if $x_{1}<\bar{x}$ or $x_{1}>\varphi_{1}(x_{1})>\bar{x}>\varphi_{2}(x_{1})$ if $x_{1}>\bar{x}.$ Denoting by $I_{1}$ the interval determined by $\varphi_{1}(x_{1})$ and $\varphi_{2}(x_{1})$ then

I_{1}\subset I_{0},

and the element $x_{2}$ constructed by (9) satisfies $x_{2},\bar{x}\in I_{1}.$

Repeating the above reason we get $x_{n+1},\bar{x}\in I_{n},$ the interval being determined by $\varphi_{1}(x_{n}),\varphi_{2}(x_{n}),$ and also that

I_{n+1}\subset I_{n}.

and $\bar{x}\in I_{n+1}.$ It is clear now that jj. holds. In order to obtain jjj. we shall use the identity

	$\displaystyle h\left(\bar{x}\right)=$	$\displaystyle h\left(\varphi_{1}\left(x_{n}\right)\right)+\left[\varphi_{1}% \left(x_{n}\right),\varphi_{2}\left(x_{n}\right);h\right]\left(\bar{x}-\varphi% _{1}\left(x_{n}\right)\right)$
		$\displaystyle+\left[\bar{x},\varphi_{1}\left(x_{n}\right),\varphi_{2}\left(x_{% n}\right);h\right]\left(\bar{x}-\varphi_{1}\left(x_{n}\right)\right)\left(\bar% {x}-\varphi_{2}\left(x_{n}\right)\right),$

which, together with (9) and $h(\bar{x})=0$ , imply

\bar{x}-x_{n+1}=-\tfrac{\left[\bar{x},\varphi_{1}\left(x_{n}\right),\varphi_{2% }\left(x_{n}\right);h\right]}{\left[\varphi_{1}\left(x_{n}\right),\varphi_{2}% \left(x_{n}\right);h\right]}\left(\bar{x}-\varphi_{1}\left(x_{n}\right)\right)% \left(\bar{x}-\varphi_{2}\left(x_{n}\right)\right).

For the difference $\bar{x}-\varphi_{1}\left(x_{n}\right)$ , by iv. one gets

\bar{x}-\varphi_{1}\left(x_{n}\right)=\left[\bar{x},x_{n};\varphi_{1}\right]% \left(\bar{x}-x_{n}\right),

i.e.,

\bar{x}-\varphi_{1}\left(x_{n}\right)<\left|\bar{x}-x_{n}\right|.

Analogously, by v. we get

\left|\bar{x}-\varphi_{2}\left(x_{n}\right)\right|<\left|\bar{x}-x_{n}\right|.

The mean formula for divided differences implies

	$\displaystyle\left[\bar{x},\varphi_{1}\left(x_{n}\right),\varphi_{2}\left(x_{n% }\right);h\right]$	$\displaystyle=\tfrac{1}{2}h^{\prime\prime}\left(\xi_{n}\right),\qquad\text{% with }\xi_{n}\in I_{n},\ \text{and}$
	$\displaystyle\left[\varphi_{1}\left(x_{n}\right),\varphi_{2}\left(x_{n}\right)% ;h\right]$	$\displaystyle=h^{\prime}\left(\eta_{n}\right),\qquad\eta_{n}\in I_{n}.$

For $h^{\prime\prime}\left(\xi_{n}\right)$ we have

\left|h^{\prime\prime}\left(\xi_{n}\right)\right|=\left|h^{\prime\prime}\left(% \xi_{n}\right)-h^{\prime\prime}\left(\bar{x}\right)\right|=\left|h^{\prime% \prime\prime}\left(\theta_{n}\right)\right|\left|\bar{x}-\xi_{n}\right|.

Since $\xi_{n}\in I_{n}$ it follows

\left|\bar{x}-\xi_{n}\right|<\left|\bar{x}-x_{n}\right|.

Denoting $m_{1}=\inf_{x\in[\alpha,\beta]}\left|h^{\prime}\left(x\right)\right|,$ $M_{3}=\sup_{x\in[\alpha,\beta]}\left|h^{\prime\prime\prime}\left(x\right)% \right|,$ the above relations lead to

\left|\bar{x}-x_{n+1}\right|\leq\tfrac{M_{3}}{2m_{1}}\left|\bar{x}-x_{n}\right% |^{3},\qquad n=0,1,\ldots,

i.e., jjj. for $k=\frac{M_{3}}{2m_{1}}$ .

Since the initial approximation $x_{0}$ was supposed sufficiently close to the solution $\bar{x},$ then

\sqrt{\tfrac{M_{3}}{2m_{1}}}\left|\bar{x}-x_{0}\right|<1

implies, together with jjj., statement j. ∎

Remark 2.1.

Supposing that $f^{\prime\prime}(x)\geq 0$ for all $x\in[a,b]$ , and if instead of iii. we assume that $f^{\prime}(x)>0,$ then obviously $f(x)<0$ for $a\leq x<\bar{x},$ and so in Theorem 2.1 we may take $\alpha=a.$ From the above conditions it follows that $h^{\prime}(x)>0$ for $x\in[a,\bar{x}],$ and since $f(\bar{x})=0$ , one gets $\beta>\bar{x}.$ ∎

3. DETERMINING THE FUNCTIONS $\varphi_{1}$ AND $\varphi_{2}$

Under reasonable hypotheses on $f$ , we shall show that there exist two classes of functions among we can choose the functions $\varphi_{1}$ and $\varphi_{2}$ such that hypotheses iv. and v. to be satisfied.

Besides assumptions i.–iii. on $f,$ we shall suppose that $f$ is strictly convex, i.e., $f^{\prime\prime}(x)>0,$ $\forall x\in[a,b].$ This condition implies that $f^{\prime}$ is increasing on $[a,b]$ . If, moreover, $f^{\prime}(x)<2\lambda,$ with $0<\lambda\leq f_{r}^{\prime}(a),$ then we may consider the functions

(10)		$\displaystyle\varphi_{1}\left(x\right)$	$\displaystyle=x-\frac{f\left(x\right)}{\mu}\qquad\text{and}$
(11)		$\displaystyle\varphi_{2}\left(x\right)$	$\displaystyle=x-\frac{f\left(x\right)}{\lambda}$

where $\mu$ may be taken as any real number greater than the left derivative of $f$ at $b,$ $f_{l}^{\prime}(b).$

In the following we shall show that the functions $\varphi_{1}\left(x\right)$ and $\varphi_{2}\left(x\right)$ chosen above obey iv. and v. The derivatives of these functions are given by

\varphi_{1}^{\prime}\left(x\right)=1-\frac{f^{\prime}\left(x\right)}{\mu},% \qquad\text{ resp. }\varphi_{1}^{\prime}\left(x\right)=1-\frac{f^{\prime}\left% (x\right)}{\lambda}.

Obviously, $0\leq\varphi_{1}^{\prime}\left(x\right)<1.$ Also, the monotonicity of $f^{\prime}$ implies $\varphi_{2}^{\prime}\left(x\right)<0$ , while $f^{\prime}(x)<2\lambda$ implies $-1<\varphi_{2}^{\prime}\left(x\right).$

Taking into account Remark 2.1, under the above hypotheses it is obvious that if $x_{0}<\bar{x},$ then condition $\varphi_{1}\left(x_{0}\right)\in[\alpha,\beta]$ from Theorem 2.1 is obviously satisfied. Indeed, this fact follows from $\varphi_{1}^{\prime}\left(x\right)<1,$ since $\varphi_{1}\left(x_{0}\right)-\bar{x}=\varphi_{1}\left(x_{0}\right)-\varphi_{1% }\left(\bar{x}\right)=\varphi_{1}^{\prime}\left(\xi\right)\left(x_{0}-\bar{x}% \right)<0,\;x_{0}<\theta<\bar{x},$ i.e., $\varphi_{1}\left(x_{0}\right)<\bar{x}.$

On the other hand, $\left|\varphi_{1}\left(x_{0}\right)-\bar{x}\right|<\left|x_{0}-\bar{x}\right|,$ and so the relations $x_{0}<\varphi_{2}\left(x_{0}\right)<\bar{x}$ hold. The hypothesis $\varphi_{2}\left(x_{0}\right)\in[\alpha,\beta]$ must be kept.

References

[1] A. Ben-Israel, Newton’s method with modified functions, Contemp. Math., 204, pp. 39–50, 1997.
[2] G.H. Brown, Jr., On Halley’s variation of Newton’s method, Amer. Math. Monthly, 84, pp. 726–728, 1977.
[3] V. Candela and A. Marquina, Recurrence relations for rational cubic methods I: The Halley’s method, Computing, 44, pp. 169–184, 1990.
[4] G. Deslauries and S. Dubuc, Le calcul de la racine cubique selon Héron, El. Math., 51, pp. 28–34, 1996.
[5] W.F. Ford and J.A. Pennline, Accelerated convergence in Newton method, SIAM Rev., 38, pp. 658–659, 1996.
[6] J. Gerlach, Accelerated convergence in Newton’s method, SIAM Rev., 36, pp. 272–276, 1994.
[7] ^†^†margin: clickable $\rightarrow$ D. Luca and I. Păvăloiu, On the Heron’s method for the approximation of the cubic root of a real number, Rev. Anal. Numér. Théor. Approx., 28, pp. 103–108, 1997.
[8] A. Melman, Geometry and convergence of Euler’s and Halley’s methods, SIAM Rev., 39, pp. 728–735, 1997.
[9] A.M. Ostrowski, The Solution of Equations and Systems of Equations, Academic Press, New York–London, 1960.
[10] ^†^†margin: clickable $\rightarrow$ I. Păvăloiu, On the monotonicity of the sequences of approximations obtained by Stef- fensen method, Mathematica (Cluj), 35 (58), pp. 171–76, 1993.
[11] ^†^†margin: clickable $\rightarrow$ I. Păvăloiu, Approximation of the roots of equations by Aitken–Steffensen-type mono- tonic sequences, Calcolo, 32, pp. 69–82, 1995.
[12] ^†^†margin: clickable $\rightarrow$ I. Păvăloiu, On a Halley-Steffensen method for approximating the solutions of scalar equations, Rev. Anal. Numér. Théor. Approx., 30, 2001 no. 1, pp. 69–74.
[13] T. Popoviciu, ^†^†margin: available soon,
refresh and click here $\rightarrow$ Sur la délimitation de l’erreur dans l’approximation des racines d’une équation par interpolation linéaire ou quadratique, Rev. Roumaine Math. Pures Appl., 13, pp. 75–78, 1968.
[14]

Received June 13, 2000.

On some Aitken-Steffensen-Halley-type method for approximating the roots of scalar equations

Abstract

Author

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

Article on the journal website

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

ON SOME AITKEN-STEFFENSEN-HALLEY-TYPE METHODS
FOR APPROXIMATING THE ROOTS OF SCALAR EQUATIONS

Abstract.

1991 Mathematics Subject Classification:

1. Introduction

2. ERROR EVALUATION AND LOCAL CONVERGENCE

Theorem 2.1.

Proof.

Remark 2.1.

3. DETERMINING THE FUNCTIONS $\varphi_{1}$ AND $\varphi_{2}$

References

Related Posts

On some Aitken-Steffensen-Halley-type method for approximating the roots of scalar equations

Abstract

Author

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

Article on the journal website

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

ON SOME AITKEN-STEFFENSEN-HALLEY-TYPE METHODS FOR APPROXIMATING THE ROOTS OF SCALAR EQUATIONS

Abstract.

1991 Mathematics Subject Classification:

1. Introduction

2. ERROR EVALUATION AND LOCAL CONVERGENCE

Theorem 2.1.

Proof.

Remark 2.1.

3. DETERMINING THE FUNCTIONS φ1 AND φ2

References

Related Posts

ON SOME AITKEN-STEFFENSEN-HALLEY-TYPE METHODS
FOR APPROXIMATING THE ROOTS OF SCALAR EQUATIONS

3. DETERMINING THE FUNCTIONS $\varphi_{1}$ AND $\varphi_{2}$