Higher-order root solving. Arithmonic mean. Newton, Halley, Householder,...

A Higher-order algorithm for the square root of any number P.

General methods for roots of any degree can be found at:

http://mipagina.cantv.net/arithmetic/rmdef.htm

All theprocedures shown here are excerpts of the webpages at:
http://mipagina.cantv.net/arithmetic

and the book: LA QUINTA OPERACIÓN ARITMÉTICA. Arithmonic Mean. © Domingo Gomez Morin. Copyright. All rights reserved. 2006



-----------------------------------PRELIMINARY NOTE-----------------------------------
The Rational Mean of the fractions: f1=a1/b1 and f2=a2/b2 is:

Rm[f1, f2] = (a1+a2)/(b1+b2)

By agency of such a simple arithmetical operation you can produce all the Householder expressions for the Nth root of any number P.
Notice that if you change the form of the fraction a1/b1= (x/x)*(a1/b1)= (x*a1)/(x*b1) then you will get another result (provided that x is not equal to 1):

For example: Rm[(x/x)*f1, f2]= (x*a1 + a2) / (x*b1 + b2)


--------------------------------END OF NOTE----------------------------------------


A SIMPLE EXAMPLE ON THE SQUARE ROOT OF ANY NUMBER P.
Higher-order rational process based on the Rational Mean.

FUNDAMENTAL PRINCIPLE:
Any two fractions whose product is P represent two rational approximations --by defect and excess-- to the square root of P.

If departing from those two fractions you can compute two mean values whose product is also P then you have another two closer approximations to the root. By continuing this process you will get a root-solving algorithm for the square root of P, moreover, by using the Rational Mean you will get a higher-order root-solving algorithm.

Starting with a set of two fractions f1, f2 whose product is f1*f2 = P.
For example:
f1 =x/1 f2=P/x

Compute the following two rational means:

Rm[(x/x)*f1, f2] = (P+x^2) / (2x) (Newton, Arithmetic mean)

Rm [(P/P)*f1, (x/x)*f2]= (2Px) / (P+x^2) (Harmonic Mean)

These results were known by ancient mathematicians, however, they never used the Rational Mean concept.

We have two expressions whose product is trivial and equal to P and they are closer to the square root of P.
You can use each of those new functions as independent iterating functions both of them holding quadratic convergence.

If you don't like quadratic convergence then compute another two similar rational means by previously assigning those functions to f1 and f2, as follows:

f1 = (P+x^2) / (2x)
f2 = (2Px) / (P+x^2)

Computing again the rational means yields:
Rm [(x/x)*f1, f2] = (x^3 + 3Px) / (P+3x^2) (Halley)
Rm [(P/P)*f1, (x/x)*f2]= (P^2 + 3Px^2) / (x^3 + 3Px)

two expressions whose product is trivial and equal to P, both of them multiply by THREE the number of exact digits in each iteration.

If you prefer more convergence speed, then make:

f1 = (x^3 + 3Px) / (P+3x^2)

f2 = (P^2 + 3Px^2) / (x^3 + 3Px)

and compute other two rational means:

Rm [(x/x)*f1, f2] = (x^4 + 6Px^2 + P^2) / (4x^3 + 4Px) (Householder)


Rm [(P/P)*f1, (x/x)*f2]= (4Px^3 + 4xP^2)/ (x^3 + 3Px)

Two expressions whose product is trivial and equal to P, both of them multiply by FOUR the number of exact digits in each iteration.

By continuing this process, in the next step you will get two functions which multiply by five the number of exact digits in each iteration.

And so on.


Based on theevidence at hand, this so naïve, trivial, natural and simple rational process has no precedents since Sumerians times up to now. We have not used neither any Cartesian-decimal system, nor any derivatives, nor infinitesimal calculus, at all
Indeed, it is disturbing to realize these so simple rational processes based on the rational mean do not appear in any book on numbers since ancient times up to now.

All this is fully explained in my book:
LA QUINTA OPERACIÓN ARITMÉTICA. Arithmonic Mean © Domingo Gomez Morin. Copyright. All rights reserved. 2006

and its webpage:
http://mipagina.cantv.net/arithmetic


Best regards,
Domingo Gomez Morin
.

Relevant Pages

  • Re: newton convergence
    ... the Householder expressions for the Nth root of any number P. ... A SIMPLE EXAMPLE ON THE SQUARE ROOT OF ANY NUMBER P. ... Higher-order rational process based on the Rational Mean. ... multiply by THREE the number of exact digits in each iteration. ...
    (sci.math.num-analysis)
  • Re: Is Truth Mysterious?
    ... but I don't like to think about the Liar too much ... being totally void of meaning. ... "A negative square root of Tuesday blushes isomorphically." ... In Chapter 11 he goes on to consider Boolean expressions ...
    (sci.logic)
  • Higher-order root solving. Newton. Halley, Householder, Bernoulli
    ... A Higher-order algorithm for the square root of any number P. ... By agency of such a simple arithmetical operation you can produce all the Householder expressions for the Nth root of any number P. ... Two expressions whose product is trivial and equal to P, both of them multiply by FOUR the number of exact digits in each iteration. ...
    (sci.math.num-analysis)
  • Re: exact fixed-point inverse square root
    ... I know about the Newton-Raphson iteration, but this one does not work if you're looking for an exact result because each step requires a multiplication which in fixed point math always goes along with a loss of precision. ... I have never seen a inverse square root iteration that is not based on the Newton-Raphson iteration and I wonder why. ...
    (comp.arch.arithmetic)
  • Re: cube root of a given number
    ... GENERAL HURTWITZ's ROOT-SOLVING METHOD? ... Higher-order rational process based on the Rational Mean: ... approximations -by defect and excess-- to the square root of P. ... multiply by THREE the number of exact digits in each iteration. ...
    (sci.math)