On a Halley-Steffensen method for approximating the solutions of scalar equations

Ion Păvăloiu
(original), html, paper

Abstract

We show that the Steffensen method for solving the scalar equation \(f(x)=0\), applied to equation $$h(x)=\frac{f(x)}{\sqrt{f'(x)}}=0,$$ leads to bilateral approximations for the solution. Moreover, the convergence order is at least 3, i.e. as in the case of the Halley method.

Author

Ion Păvăloiu
(Tiberiu Popoviciu Institute of Numerical Analysis)

Keywords

nonlinear equations in R; Steffensen method; Halley method; monotone iterations.

PDF

PDF-LaTeX file.

Cite this paper as:

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.

About this paper

Journal

Revue d’Analyse Numérique et de Théorie de l’Approximation

Publisher Name

Editions de l’Academie Roumaine

Article on the journal website

https://ictp.acad.ro/jnaat/journal/article/view/2001-vol30-no1-art9

Print ISSN

1222-9024

Online ISSN

2457-8126

References

[1] Adi Ben-Israel, Newton’s method with modi ed functions, Contemp. Math., 204 (1997),pp. 39-50.
[2] G. H. Brown, Jr., On Halley’s variation of Newton’s method, Amer. Math. Monthly, 84 (1977), 726{728.
[3] V. Candela and A. Marquina, Recurrence relations for rational cubic methods I: the Halley’s method , Computing 44 (1990), 169{184.
[4] G. Deslauries and S. Dubuc, Le calcul de la racine cubique selon Heron , El. Math., 51 (1996), 28{34.
[5] D. Luca and I. Pavaloiu, On the Heron’s method for the approximation of the cubic root of a real number , Rev. Anal. Numer. Theor. Approx., 28 (1997), 103{108.
[6] A. M. Ostrowski, The Solution of Equations and Systems of Equations , Academic Press, New York-London, 1960.
[7] I. Pavaloiu, On the monotonicity of the sequences of approximations obtained by Steffensen’s method , Mathematica (Cluj) 35 (58) (1993), 71-76.
[8] I. Pavaloiu, Approximation of the roots of equations by Aitken-Ste ensen-type monotonic sequences , Calcolo, 32 (1995), 69{82.
[9] T. Popoviciu, Sur la delimitation de l’erreur dans l’approximation des racines d’une equation par interpolation lineaire ou quadratique , Rev. Roumaine Math. Pures Appl., 13 (1968), 75-78.

Google Scholar Profile

Paper (preprint) in HTML form

ON A HALLEY-STEFFENSEN METHOD FOR APPROXIMATING THE SOLUTIONS OF SCALAR EQUATIONS

ON A HALLEY-STEFFENSEN METHOD
FOR APPROXIMATING THE SOLUTIONS
OF SCALAR EQUATIONS

ION PĂVĂLOIU∗ Dedicated to the memory of Acad. Tiberiu Popoviciu
Abstract.

In the present paper we show that the Steffensen method for solving the scalar equation f⁢(x)=0, applied to equation

h⁢(x)=f⁢(x)f′⁢(x)=0,

leads to bilateral approximations for the solution. Moreover, the convergence order is at least 3, i.e. as in the case of the Halley method.

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 a,b∈ℝ, a<b, and f:[a,b]→ℝ be given. Assume that f∈C4⁢[a,b] and f′⁢(x)>0,∀x∈[a,b]. Consider the function h:[a,b]→ℝ given by h⁢(x)=f⁢(x)/f′⁢(x). As it is well known (see e.g. [2]), the Halley method for solving

(1) f⁢(x)=0

consists in constructing the sequence (xn)n≥0 by

(2) xn+1=xn−h⁢(xn)h′⁢(xn),n=0,1,…,x0∈[a,b]

As it can be easily noticed, (2) is the Newton method applied to equation h⁢(x)=0. The advantage of using the function h instead of f in (2) consists

in the fact that h obeys h′′⁢(x¯)=0, where x¯ is a solution of (1). It is well known that h′′⁢(x¯)=0 ensures for (2) the convergence order 3 (see [2]).

Starting from an algorithm proposed by Heron for approximating 1003, the authors of [4] establish the following relation:

(3) N3≃Φ⁢(N;α,β)=α+β⁢d1β⁢d1+α⁢d2⁢(β−α)

where d1=N−α3, d2=β3−N and α3≤N≤β3. The Heron algorithm is obtained from (3) for α=4 and β=5.

In the paper [5], the authors noticed that the approximation given by (3) for N3 is obtained by applying one step of the chord method to equation φ⁢(x)=0, where φ⁢(x)=x2−N/x, x>0.

In [5] it is noticed that if one considers equation f⁢(x)=x3−N, then, apart of a constant factor, equation φ⁢(x)=0 is equivalent to

h⁢(x)=f⁢(x)f′⁢(x)=0,x>0,

i.e., 1/3⁢(x2−N/x)=0. Therefore there exists a connection between the Halley method (2) and the Heron algorithm concerning the function h. In the case of the Halley method there is applied the Newton method to h⁢(x)=0 whereas in the Heron method there is applied the chord method to h⁢(x)=0. The both methods benefit from the advantages implied by h′′⁢(x¯)=0. These remarks have led in [5] to generalizations of the results from [4]. A brief analysis of the convergence order of the chord method applied to h⁢(x)=0 in the general case (quasi-Halley method) is given in [1].

In this note we shall study the convergence of an iterative method obtained by applying the Steffensen algorithm to equation h⁢(x)=0, where h⁢(x)=f⁢(x)/f′⁢(x). As we shall see, this method has some advantages over the Halley and chord methods applied to h. The most important one is the fact that the method we propose allows the control of the absolute error at each iteration step. Its convergence order is the same as for the Halley method, being higher than the order of the chord method.

For solving (1) we shall consider the sequence

(4) xn+1=xn−h⁢(xn)[xn,φ⁢(xn);h],n=0,1,…,x0∈[a,b]

where φ will be suitably chosen, and [x,y;f]=(f⁢(y)−f⁢(x))/(y−x) denotes

the first order divided difference of f on x and y. We shall call this method the Halley-Steffensen method.

2. Local convergence and error bounds

Concerning the function f we shall assume the following conditions:

  • i.

    f∈C4⁢[a,b];

  • ii.

    f′⁢(x)>0 for all x∈[a,b];

  • iii.

    equation (1) has a solution x¯∈]a,b[;

  • iv.

    the function φ from (4) is given by

    (5) φ⁢(x)=x−f⁢(x)λ

    where 0<λ<fd′⁢(a), and fd′⁢(a) is the right derivative of f at a;

  • v.

    f′⁢(x)<2⁢λ,∀x∈[a,b];

  • vi.

    f′′⁢(x)>0,∀x∈[a,b].

We notice in the beginning that

xn−h⁢(xn)[xn,φ⁢(xn);h]=φ⁢(xn)−h⁢(φ⁢(xn))[xn,φ⁢(xn);h],n=0,1,…

which shows that the Halley-Steffensen sequence obeys

(6) xn+1=φ⁢(xn)−h⁢(φ⁢(xn))[xn,φ⁢(xn);h],n=0,1,…,

while for the first and second order derivatives we obtain

(7) h′⁢(x)= 2⁢(f′⁢(x))2−f′′⁢(x)⁢f⁢(x)2⁢(f′⁢(x))3/2;
(8) h′′⁢(x)= 3⁢(f′′⁢(x))2−2⁢f′′′⁢(x)⁢f′⁢(x)4⁢(f′⁢(x))5/2⁢f⁢(x).

Relation (8) implies h′′⁢(x¯)=0, while (7) implies h′⁢(x¯)=(f′⁢(x¯))1/2>0. Since h′ is continuous and h′⁢(x¯)>0 it follows the existence of α,β∈ℝ, a≤α<x¯<β≤b, such that h′⁢(x)>0,∀x∈[α,β].

We obtain the following result:

Theorem 1.

Assume that the function f and the initial approximation x0 satisfy:

  • i1.

    the number x0 is sufficiently close to x¯ and φ⁢(x0)∈[α,β], with α and β determined above;

  • ii2.

    the function f obeys (i)–(vi);

Then the Halley-Steffensen sequence (1.4) converges to the solution x¯ and, moreover,

(9) |xn+1−x¯|≤ max⁡{|xn+1−xn|,|xn+1−φ⁢(xn)|},n=0,1,…,
(10) |xn+1−x¯|≤ K⁢|xn−x¯|3,n=0,1,…,

where K is a constant which does not depend on n.

Proof.

Since f′′⁢(x)>0,∀x∈[a,b], it follows that f′ is increasing on [a,b] and hence φ′⁢(x)=1−f′⁢(x)/λ obeys φ′⁢(x)<0,∀x∈[a,b]. The existence of the interval [α,β]⊆[a,b] such that h′⁢(x)>0, ∀x∈[α,β], has been proved above. Assumption iv) implies x¯=φ⁢(x¯) and so, if x0<x¯, we get φ⁢(x0)>x¯. Analogously, x0>x¯⇒φ⁢(x0)<x¯, i.e., x¯∈I0, I0 being the interval determined by x0 and φ⁢(x0). From h′⁢(x)>0, ∀x∈[α,β], it follows h⁢(x0)<0 for x0<x¯ resp. h⁢(x0)>0 for x0>x¯. Relation (4) implies x1>x0 when x0<x¯ resp. x1<x0 when x0>x¯. By (6) we get x1<φ⁢(x0) when x0<x¯ resp. x1>φ⁢(x0) when x0>x¯, i.e. x1∈I0. We shall show that φ⁢(x1)∈I0. For this we prove that x0<φ⁢(φ⁢(x0)) when x0<x¯ resp. x0>φ⁢(φ⁢(x0)) when x0>x¯. For φ⁢(φ⁢(x0)) we easily obtain the following expression:

φ⁢(φ⁢(x0))=x0−2λ⁢f⁢(x0)+1λ2⁢f′⁢(ξ0)⁢f⁢(x0),ξ0∈I0,

whence, taking into account (v) and f⁢(x0)<0 for x0<x¯, we obtain φ⁢(φ⁢(x0)) −x0>0. Analogously, if x0>x¯ then φ⁢(φ⁢(x0))−x0<0. So, φ⁢(φ⁢(x0))∈I0. Let x0<x¯, and so φ⁢(x0)>x¯ and x0<x1<φ⁢(x0). Since φ is decreasing we get φ⁢(x1)>φ⁢(φ⁢(x0))>x0, and, on the other hand, from x0<x1⇒φ⁢(x0)>φ⁢(x1), i.e. φ⁢(x1)∈I0. Analogously, if x0>x¯⇒φ⁢(x1)∈I0. Denoting by I1 the closed interval determined by x1 and φ⁢(x1) then

(11) x¯∈I1⁢ and ⁢I0⊃I1.

Let Is denote the closed intervals determined by the points xs and φ⁢(xs), s=0,k¯. Suppose that

(12) I0⊃I1⊃…⊃Ik−1⊃Ik,

and x¯∈Ik. As we have shown for x0, we can prove that the interval Ik+1, determined by xk+1 and φ⁢(xk+1), obeys

Ik⊃Ik+1

and x¯∈Ik+1. From the above reasons, it follows that relations (9) are true. It remains to show that (10) holds, which implies the convergence of (xn)n≥0 generated by (4). For this purpose we shall use the identity

h⁢(x¯)=h⁢(xn)+[xn,φ⁢(xn);h]⁢(x¯−xn)+[x¯,xn,φ⁢(xn);h]⁢(x¯−xn)⁢(x¯−φ⁢(xn)),

whence, taking into account (4) and h⁢(x¯)=0, it follows (see [9])

(13) x¯−xn+1=−[x¯,xn,φ⁢(xn);h][xn,φ⁢(xn);h]⁢(x¯−xn)⁢(x¯−φ⁢(xn)),n=0,1,…

By (ii) and (v) we get |φ′⁢(x)|<1,∀x∈I0, and so

(14) |x¯−φ⁢(xn)|<|x¯−xn|,n=0,1,…

On the other hand, from the mean value theorems for divided differences one obtains

(15) [x¯,xn,φ⁢(xn);h] =h′′⁢(ξn)2!,ξn∈In, and
(16) [xn,φ⁢(xn);h] =h′⁢(ηn),ηn∈In.

From (15) and from h′′⁢(x¯)=0 we get

(17) |[x¯,xn,φ⁢(xn);h]|=12⁢|h′′⁢(ξn)−h′′⁢(x¯)|=12⁢h′′′⁢(δn)⁢|ξn−x¯|,

where δn∈In. Further, by (2.10) it follows

(18) |ξn−x¯|≤max⁡{|x¯−xn|,|x¯−φ⁢(xn)|}≤|x¯−xn|.

Denote m3=supx∈I0|h′′′⁢(x)| and m1=infx∈I0|h′⁢(x)|. Relations (13)–(18) lead to

|xn+1−x¯|≤m32⁢m1⁢|xn−x¯|3,n=0,1,…,

i.e., (10) with K=m3/(2⁢m1). The proof is complete. ∎

3. Numerical example

Consider the equation

f⁢(x)=x3−20,x>0,

and the function h⁢(x)=13⁢(x2−20/x). Obviously, h′⁢(x)=2⁢(x+10/x2)>0,∀x>0. It can be easily seen that 2.6<203<2.8. We choose φ⁢(x)=x−(x3−20)/20.28. Then, for x0=2.6, φ⁢(x0)<2.8, and hence our theorem may be applied. We obtain the following results:

n xn φ⁢(xn) h⁢(xn)
0 2,600 000 000 0⋅10+00 2,719 526 627 2⋅10+00 -9,323 076 923 2⋅10-01
1 2,714 420 633 0⋅10+00 2,714 417 345 3⋅10+00 2,456 359 652 6⋅10-05
2 2,714 417 616 6⋅10+00 2,714 417 616 6⋅10+00 -1,455 191 522 8⋅10-11

References

  • [1] Adi Ben-Israel, Newton’s method with modified functions, Contemp. Math., 204 (1997), pp. 39–50.
  • [2] G. H. Brown, Jr., On Halley’s variation of Newton’s method, Amer. Math. Monthly, 84 (1977), 726–728.
  • [3] V. Candela and A. Marquina, Recurrence relations for rational cubic methods I: the Halley’s method, Computing 44 (1990), 169–184.
  • [4] G. Deslauries and S. Dubuc, Le calcul de la racine cubique selon Héron, El. Math., 51 (1996), 28–34.
  • [5] ††margin: clickable → 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 (1997), 103–108.
  • [6] A. M. Ostrowski, The Solution of Equations and Systems of Equations, Academic Press, New York–London, 1960.
  • [7] ††margin: clickable → I. Păvăloiu, On the monotonicity of the sequences of approximations obtained by Stef- fensen’s method, Mathematica (Cluj) 35 (58) (1993), 71–76.
  • [8] ††margin: clickable → I. Păvăloiu, Approximation of the roots of equations by Aitken-Steffensen-type monoto- nic sequences, Calcolo, 32 (1995), 69–82.
  • [9] T. Popoviciu, ††margin: available soon,
    refresh and click here →         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 (1968), 75–78.

Received June 17, 2000.

2001

Related Posts