On some papers that appeared at the Mathematical Spectrum Magazine

somehow related to the root-solving methods based on the Rational Mean

 

 

 

In a letter to the Math Spectrum editor Mr. Bob Bertuello (See Math. Spectrum, Volume 40, 2007/2008, No. 3., p. 134) showed a very particular iterating function for computing square roots (developed by agency of the Rational Mean, See Volume 39, 2007/2007, No. 2, p.80-82), and explained that it converges rather faster than Bor-Yann’s  algorithm which was published in the same magazine (See Math Spectrum, Volume 40, 2007/2008, No. 1, p. 39-40). 

The iteration function shown by Bertuello in the Math Spectrum magazine, apart from other different expressions were fully stated and explained in the first edition of my book “La Quinta Operación Aritmética, revolución del número”(Year: 2000), I.S.B.N.: 980-07-6632-4, and it was also defined their connection, if any, to Newton’s, Halley’s or Householder’s method.

 

The Bor-Yann Chen’s method mentioned by Mr. Bertuello yields approximations by means of the equation:

 

                                                                                                                              (1)

 

For instance, in order to approximate   by using his algorithm, he got the sequence of values (y/x):

 

 

 

However, as we can see the values 3/2, 333/218, 36627/23978,… do not comply with equation (1), and even if starting with (xo, yo)=(36,55) which satisfy equation (1) then alternating values produced by Bor-yann Chen’s method will not satisfy equation (1), anyhow, his method converges to the root.

 

Considering all that, it is important to know that in order to compute roots of any degree we can produce -- by agency of the Rational Mean – an uncountable number of iterating functions for any desired convergence speed.  Moreover,    we can produce many rational processes --based on the Rational Mean--  for generating  a sequence of values (y/x) which certainly satisfy the equation (1) at each  stage,  also converging rather faster than Bor-Yann’s  algorithm. Next we will see some examples on such algorithms based on the Rational mean.

 

Preliminaries on the Rational Mean (Cauchy, Cours d’analyse de l’ecole Royale Polytechnique, 1821, opening chapter, preliminaries, p.15):

Given any pair of values (xo, yo) and  two fractions        always  holding positive values in their denominators ,    then The Rational Mean of a/b and c/d is always a mean value between them and may be expressed this way: 

 

 

Hereinafter the values  will be called ‘Form Factors’ because  they do not modify the values of a/b and c/d but just their forms.   If (xo, yo) = (1, 1) then the Rational Mean becomes the well known Mediant operation often used in Theory of Numbers.

 More information on the Rational mean can be found at the book: “La Quinta Operación Aritmética. Media Aritmónica”, author Domingo Gomez Morin, 2006 Edition, Venezuela.  Also at the webpage:

http://mipagina.cantv.net/arithmetic

 

 

First algorithm based on the Rational Mean and the Diophantine equation:

 

Being P any rational number, let’s approximate   by using the following set of two fractions:

 

 

whose product is trivial and equal to P, that is, a set of two approximations by defect an excess to   .

Given a  fraction yo/xo,  and two pair of values  (x,y) and  (xo, yo) always  satisfying equation (1), let’s call y1/x1  the Rational Mean of y/x and  Px/y   using  the aforementioned Forms Factors (yo/yo) and (xo/xo):

 

 

 

It is fairly easy to show by algebraic manipulation that:

 

 

Thus, the Rational Mean bring us a remarkable Mean Value which  certainly satisfy  equation (1) in the same way the two pair of values  (x, y) and  (xo, yo) do.

 

So we can trivially construct a new set of two approximations, by defect and excess,  and closer to ,  as shown:

 

 

Note: It’s important to realize that    is also a Rational Mean of x/y and Px/y  :

 

 

 

 

 

 

 

We can do exactly the same with  ,   and find another new set of two fractions    closer to  .  This procedure can be repeated many times to get more closer approximations by defect and excess to  , with all the values (xo, yo), (x1, y1), (x2, y2), (x3, y3),… satisfying equation (1).

 

As an example, being P=  ,  and  (xo,yo) = (36,55) which certainly satisfy the equation (1), then the initial set of values  is:

 

 

and the sequence of approximations   by defect and excess to   is:

 

 

,   ,   ,   and so on …

 

 

Notice that if we choose an initial set (xo,yo) not satisfying equation (1) then the algorithm will certainly converge to the root but all the values (x1,y1), (x2,y2), (x3,y3),… will  not necessarily satisfy it. Bor-yann Chen’s method does not comply with equation (1) even when using the initial value: (55/36).

 

 

 

 

Second algorithm based on the Rational Mean and the Diophantine Equation:

 

Let’s now  compute a very particular case of Rational Mean of the values    by previously making equal their denominators, which is equivalent to compute the well known  Arithmetic Mean (AM), and again let’s call it y1/x1:

 

                                                                                    (2)      

 

 

It is fairly easy to show by algebraic manipulation that:

 

We can now construct  new set of two approximations to   in the same way we did before:

 

 

 

And by computing the AM of this new expressions and repeating this procedure, we will get a sequence of two approximations   by defect and excess to .  As an example, being P=    and  (yo,xo) = (36,55), by applying this procedure the sequence of approximations will be:

 

 

,   ,   and so on …

 

 

 

Very important note on the Second algorithm (High-order convergence speed):

 

It can be easily proved that the expressions  produced in the first step can be used as independent iterating functions, so  there is no need of computing the AM in each step of the process, that is, starting from an initial value   one can use only the first expression as an iterating function of the form: ,  such expression is the same iterating function of Newton’s method for approximating  square roots, so in many cases it has quadratic convergence.

 

Moreover,  if after computing   in the Second Algorithm we calculate a new Rational Mean using exactly the same Form Factors  and  as those used in the first step, then we will get the following set of two expressions whose product is  P,  representing two approximations, by defect and excess, closer to  , that is, being    then let’s compute:

 

 

Thus the second set  of values whose product is P will be:

 

  =

 

It can be also easily proved that such expressions can be used as independent iterating functions of the form:  

 

And we can check that this function triples the number of digits in each step , and corresponds to the well known Halley’s high-order method for computing square roots, as well as to the one shown by  Bob Bertuello (See Volume 40, 2007/2008, No. 3., p. 134).

 

For example, given    and  the initial fraction yo/xo= 55/36, the resulting sequence of approximations satisfying  equation (1) is:

 

 

Whose corresponding errors when compared to the true value of    are: ,  …   

But that is just the beginning ¡¡¡.

Being     let’s start a third step by computing another Rational Mean by using, again, the same Form Factors:

 

 

 

 

 

And the new set of expressions whose product is P  will be :

 

  =

 

 

These new independent  iterations functions will multiply by four the number of exact digits in each step, and corresponds to the well known Householder’s high-order method.

We may continue this process and produce iterating functions of any desired convergence speed. 

It is important to notice that in the First Algorithm the Forms Factors are always the same constant values, while in the Second Algorithm are variables.

Notice that by using an extremely simple arithmetical concept ‘The Rational mean’ we got Bernoulli’s, Newton’s, Halley’s, Householder’s and other iterating functions, always without using neither any derivatives nor infinitesimal calculus, at all. Moreover, there is an uncountable number of different rational processes which can be generated in a similar way, and more important, these methods based on the Rational Mean are not restricted to the computation of just square roots, but can be trivially extended to roots of any degree, as well as complex roots and polynomials.

 

Ing. Domingo Gomez Morin

Structural Engineer.

Caracas, Venezuela

djesusg@gmail.com

djesusg@cantv.net

 

 

[TOP PAGE]

 

Copyright © Domingo Gómez Morín 1993-2006

All rights reserved under international Copyright Conventions.

No part of this page may be reproduced, stored or transmitted in any form or by any means.

All the contents of this webpage are excerpts of the book:

“La Quinta Operación Aritmética”, ISBN:980-12-1671-9.

Last revision: 2006