Re: newton convergence


vsgdp ha escrito:

Hi, my book shows Newton's method can converge quadratically, but the
only example they give is a comparison between fixed point iteration
and Newton's method, and just shows that after three iterations
Newton's method is doing good while fixed point is not. How does this
show it is quadratic? More generally, how does one experimentally show
Newton's method is quadratic? What is the test?


If you really want to know the true behind Newton's, Halley's,
Bernoulli's, Householder's methods then you need to take a look at:

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

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


What follows is just an extremely simple example which you can also
find at my web page.
Indeed, it is a real shame that these trivial and Natural Arithmetical
high-order methods do not appear in any text on numbers since ancient
times up to now.
Best regards, Domingo Gomez.

Example:

-----------------------------------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: 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)
  • Re: rapidly converging rational sqrt
    ... Note that after iteration 6 we have ... > more than 100 significant digits. ... I don't wish to denigrate your algorithm unduly, but square root algorithms ...
    (sci.math.research)
  • 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)
  • Higher-order root solving. Arithmonic mean. Newton, Halley, Householder,...
    ... 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)