On the Heron’s method for approximating the cubic root of a real number

Abstract

(soon)

Authors

Dan Luca
Tiberiu Popoviciu Institute of Numerical Analysis

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

Keywords

PDF

Scanned paper: on the journal website.

PDF-LaTeX version of the paper.

Cite this paper as:

D. Luca, I. Păvăloiu, On the Heron’s method for approximating the cubic root of a real number, Rev. Anal. Numér. Théor. Approx., 26 (1997) nos. 1-2, pp. 103-108.

About this paper

Print ISSN

1222-9024

Online ISSN

2457-8126

References

[1] G. Deslauries and S. ubuc, Le calcul de la racine cubique selon Heron, Elemente der 51, I (1996), pp. 28-34.

[2] M. Ostrowski, A Solution of Equations and Systems of Equation, Academic Press, New York-London, 1960.

[3] I. Păvăloiu I., On the monotonicity of the sequences of approximations obtained by Steffensen,s method, Mathematica (Cluj) 35 (58),1 (1993), pp. 71-76.

[4] T. Popoviciu, Sur la delimiation de l’erreur dans l’approximation des racines d’une equation par interpolation lineaire ou quadratique, Rev. Roumaine Math. Pures Appl. XIII, 1 (1968), pp. 75-78.

Paper (preprint) in HTML form

On the Heron’s method for approximating the cubic root of a real number

On the Heron’s method for approximating
the cubic root of a real number

Dan Luca, Ion Păvăloiu
1991 Mathematics Subject Classification:
65G05, 65B05

1. Introduction

In this paper we shall specify and go deeply into some problems presented in [2], concerning the Heron’s method for approximating the cubic root of a positive number.

The authors of [2] construct a method based on the Heron’s algorithm for computing the cubic root of 100.

The method works as follows: Given two real numbers a and b satisfying a3<N<b3, the Heron’s method for approximating N3 is

(1) ϕ⁢(N,a,b)=a+b⁢d1b⁢d1+a⁢d2⁢(b−a),

where d1=N−a3 and d2=b3−N. We shall show that the approximation (1) of N3 follows from the regula falsi applied to the equation x2−Nx=0 [3]. This will given a rigorous interpretation of (1), and the results from [2] will be reached again.

Using results from [5], we shall give other error bounds than those in [2]. On the other hand, the method is generalized to the case Np,p∈ℕ, p≥2, the method also offering bilateral approximations. Some remarks on applying the results in [5] for the error bounds will lead us to the generalization of the Heron’s method.

2. Herons’s method and regula falsi

A. In order to approximate the cubic root of N>0 by (1), consider the function f:[a,b]→ℝ, f⁢(x)=x3−N,0<a<b and the function g:[a,b]→ℝ, g⁢(x)=f⁢(x)x.

It is well known that regula falsi applied to the equation g⁢(x)=0 leads to the following approximation of its root

(2) c=a−g⁢(a)[a,b;g],

[u,v;g]denoting the first-order divided difference of g on the nodes u and v. It can be easily verified that c=ϕ⁢(N,a,b).

Taking into account that c∈(a,b) and denoting by [u,v,w;g] the second-order divided difference of g on the points u,v,w, we get

(3) g⁢(x)=g⁢(a)+[a,b;g]⁢(x−a)+[a,b,x;g]⁢(x−a)⁢(x−b)

for all x∈(a,b).

For x=N3 in (3) we obtain

g⁢(a)+[a,b;g]⁢(N3−a)+[a,b,N3;g]⁢(N−a3)⁢(N3−b)=0,

from which, by dividing [a,b;g] it follows

(4) c−N3=[a,b,N3;g][a,b;g]⁢(N3−a)⁢(N3−b).

An elementary calculation on [a,b,N3;g][a,b;g] shows that

(5) c−N3N3=N3+a⁢bN3⁢[a⁢b⁢(a+b)+N]⁢(N3−a)⁢(N−b3)⁢(N3−a⁢b),

which gives Theorem 3, [2].

Taking into account the above remarks and using the evaluations obtained by T. Popoviciu in [5], (4) gives the following error bounds

(6) m2M1⁢(N3−a)⁢(b−N3)≤|c−N3|≤M2m1⁢(N3−a)⁢(b−N3),

where

m1= 3⁢a
m2= min⁡{Na3−1,1−Nb3}
M1= max⁡{2⁢a3+Na2,2⁢b3+Nb2}
M2= max⁡{Na3−1,1−Nb3}.

Note that (6) leads to a very good error evalutation; since a and b are close to N, then m2 and M2 are close to zero. This is implied by the fact that the function g and its second derivative vanish at the same point x=N3.

B. It can be easily seen that the method presented at A can be generalized. For the approximation of the root of order p of the real number N,p∈ℕ, p≥2, consider the function f1:[a1,b1]→ℝ,

f1⁢(x)=xp−N,0<a1<b1,a1p<N<b1p

and the function g1:[a1,b1]→ℝ,

g1⁢(x)=f1⁢(x)xq,where⁢q=p−12.

The function g1satisfies g1⁢(Np)=g1′′⁢(Np).

Applying regula falsi to the equation g1⁢(x)=0, we obtain

(7) c1=a1−g1⁢(a1)[a1,b1;g1]

Similarly to A, we obtain

(8) c1−Np=[a1,b1,Np;g1][a1,b1;g1]⁢(Np−b1)⁢(Np−a1),

which gives

(9) t22⁢T1⁢(Np−a1)⁢(b1−Np)≤|c1−Np|≤T22⁢t1⁢(Np−a1)⁢(b1−Np),

where

t1= p⁢a1p−12
t2= min⁡{(p−1)⁢(p+1)⁢(N−a1p)4⁢a1p+32;(p−1)⁢(p+1)⁢(b1p−N)4⁢b1p+32}
T1 =max⁡{(p+1)⁢a1p+(p−1)⁢N2⁢a1p+12;(p+1)⁢b1p+(b−1)⁢N2⁢b1p+12}
T2 =max⁡{(p−1)⁢(p+1)⁢(N−a1p)4⁢a1p+32;(p−1)⁢(p+1)⁢(b1p−N)4⁢b1p+32}.

3. Steffensen’s method for approximating the pth-order root

Let I=[α,β],α<β be an interval of the real axis.

Consider the equation

(10) F⁢(x)=0,

where F:I→ℝ. Suppose that equation (10)has a root x¯∈(α,β). Consider also a function h:I→ℝ such that equation

(11) x−h⁢(x)=0

is equivalent to (10).

The Steffensen’s method consists in the generation of two sequences (xn) and (h⁢(xn)) by the relations

(12) xn+1=xn−F⁢(xn)[xn,h⁢(xn);F],n=0,1,…,x0∈I.

As we shall see, this method offers the possibility to obtain better both upper and lower approximations, by starting with a lower approximation of Np. Then, by applying only once the regula falsi (7), the precision can be increased.

As concerns the convergence of (xn) and (h⁢(xn)) in (12), in [4] the following theorem is proved.

Theorem 3.1.

[4]. If the functions F:I→ℝ and h:I→ℝ are continuous and satisfy the following conditions:

  • i)

    the function h is decreasing on I,

  • ii)

    the function F is increasing and convex on I,

  • iii)

    there exists x0∈I such that F⁢(x0)<0 and h⁢(x0)∈I,

  • iv)

    the equations (10) and (11) are equivalent,

then the following properties hold:

  • j)

    the sequence (xn) is increasing,

  • jj)

    the sequence (h⁢(xn)) is decreasing,

  • jjj)

    limxn=limh⁢(xn)=x¯

  • jv)

    the relations xn≤xn+1≤x¯≤h⁢(xn) hold for all n=0,1,…,

  • v)

    x¯−xn+1<h⁢(xn)−xn+1.

Applying this Theorem for F:[α,β]→ℝ, F⁢(x)=xp−N,h:[α,β]→ℝ,

h⁢(x)=x−F⁢(x)p⁢αp−1,

where 0<α<β and p∈ℕ, p≥2, we obtain

xn+1=xn+(p⁢αp−1)p−1⁢(xn−N)2(p⁢αp−1⁢xn−xnp+N)p−(p⁢αp−1⁢xn)p,n=0,1,…,x0=α;αp<N.

Since F is increasing and convex [α,β], it follows that h is decreasing on [α,β], and the equations F⁢(x)=0 and h⁢(x)−x=0 are equivalent. So the conclusion of Theorem 3.1 follows.

The sequences (xn) and (h⁢(xn)) being convergent, it follows that for all ε>0 there exists n0∈ℕ such that for n≥n0 we have

h⁢(xn)−xn<ε,

which implies Np−xn<ε and h⁢(xn)−Np<ε.

If we use (7) for a1=xn and b1=h⁢(xn) and g1⁢(x)=F⁢(x)xp−12, and we denote the approximation obtained by cn, then by (9) we have

|cn−Np|≤T2′2⁢t1′⁢ε2,

where

{T2′=max⁡{(p−1)⁢(p+1)⁢(N−xnp)4⁢xnp+32;(p−1)⁢(p+1)⁢(hp⁢(xn)−N)4⁢h⁢(xn)p+32}t1′=p⁢xnp−12.

4. A Numerical example

We intend to apply the method described in Section 3 for the approximation of the number 1005, i.e., for solving the equation x3−100=0. In this case we have

F⁢(x)=x5−100

and, taking α=2, for the function h we have

h⁢(x)=x−180⁢F⁢(x).

Considering x0=α=2 and using (12), with F and h given above, we obtain for the sequences (xn)n≥0 and (h⁢(xn))n≥0 the following values:

n xn h⁢(xn) εn=h⁢(xn)−xn
0 2.000 000 000 0 2.850 000 000 0 8.500 000 000 0⋅10−01
1 2.370 444 507 2 2.684 911 796 6 3.144 672 894 1⋅10−01
2 2.492 753 689 2 2.539 639 492 8 4.688 580 357 8⋅10−02
3 2.511 465 149 3 2.512 513 019 4 1.047 870 071 5⋅10−03
4 2.511 886 221 3 2.511 886 744 3 5.229 121 597 9⋅10−07
5 2.511 886 431 5 2.511 886 431 5 3.637 978 807 1⋅10−12.
Table 1.

References

  • [1]
  • [2] G. Deslauries and S. Dubuc, Le calcul de la racine cubique selon Héron, Elemente der Mathematik 51, (1996) 1, 28–34.
  • [3] M. Ostrowski, The solution of Equations and Systems of Equations, Academic Press, New York-London, 1960.
  • [4] ††margin: clickable → I. Păvăloiu, On the monotonicity of the sequences of approximations obtained by Steffensen’s method, Mathematica (Cluj) 35 (58), (1993) 1, 71–76.
  • [5] T. Popoviciu, Sur la dèlimitation de ††margin: available soon,
    refresh and click here →
    l’erreur dans l’approximation des racines d’une équation par interpolation linéaire ou quadratique
    , Rev. Roumaine Math. Pures Appl. XIII, (1968) 1, 75–78.
1997

Related Posts