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+bd1bd1+ad2(ba),

where d1=Na3 and d2=b3N. We shall show that the approximation (1) of N3 follows from the regula falsi applied to the equation x2Nx=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, p2, 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)=x3N,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=ag(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](xa)+[a,b,x;g](xa)(xb)

for all x(a,b).

For x=N3 in (3) we obtain

g(a)+[a,b;g](N3a)+[a,b,N3;g](Na3)(N3b)=0,

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

(4) cN3=[a,b,N3;g][a,b;g](N3a)(N3b).

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

(5) cN3N3=N3+abN3[ab(a+b)+N](N3a)(Nb3)(N3ab),

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(N3a)(bN3)|cN3|M2m1(N3a)(bN3),

where

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

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, p2, consider the function f1:[a1,b1],

f1(x)=xpN,0<a1<b1,a1p<N<b1p

and the function g1:[a1,b1],

g1(x)=f1(x)xq,whereq=p12.

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

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

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

Similarly to A, we obtain

(8) c1Np=[a1,b1,Np;g1][a1,b1;g1](Npb1)(Npa1),

which gives

(9) t22T1(Npa1)(b1Np)|c1Np|T22t1(Npa1)(b1Np),

where

t1= pa1p12
t2= min{(p1)(p+1)(Na1p)4a1p+32;(p1)(p+1)(b1pN)4b1p+32}
T1 =max{(p+1)a1p+(p1)N2a1p+12;(p+1)b1p+(b1)N2b1p+12}
T2 =max{(p1)(p+1)(Na1p)4a1p+32;(p1)(p+1)(b1pN)4b1p+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) xh(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=xnF(xn)[xn,h(xn);F],n=0,1,,x0I.

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 x0I 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 xnxn+1x¯h(xn) hold for all n=0,1,,

  • v)

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

Applying this Theorem for F:[α,β], F(x)=xpN,h:[α,β],

h(x)=xF(x)pαp1,

where 0<α<β and p, p2, we obtain

xn+1=xn+(pαp1)p1(xnN)2(pαp1xnxnp+N)p(pαp1xn)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 nn0 we have

h(xn)xn<ε,

which implies Npxn<ε and h(xn)Np<ε.

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

|cnNp|T22t1ε2,

where

{T2=max{(p1)(p+1)(Nxnp)4xnp+32;(p1)(p+1)(hp(xn)N)4h(xn)p+32}t1=pxnp12.

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 x3100=0. In this case we have

F(x)=x5100

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

h(x)=x180F(x).

Considering x0=α=2 and using (12), with F and h given above, we obtain for the sequences (xn)n0 and (h(xn))n0 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 01001
1 2.370 444 507 2 2.684 911 796 6 3.144 672 894 11001
2 2.492 753 689 2 2.539 639 492 8 4.688 580 357 81002
3 2.511 465 149 3 2.512 513 019 4 1.047 870 071 51003
4 2.511 886 221 3 2.511 886 744 3 5.229 121 597 91007
5 2.511 886 431 5 2.511 886 431 5 3.637 978 807 11012.
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