Newtons Method
jo...@emi.net
Hello everyone,
Has anyone ever heard of Newtons Method? It's an alogarithm used to
find the square roots of numbers. The alogarithm goes something like
this: (Number*guess)+guess/2 =guess
Number is the number which you are trying to find the square of
Guess is what ever number you choose other than 0
You keep plugging the guess in until it reaches Epsilon. (1.0E-09)
Basically, no matter what number you guess....in the end you have the
square of that number.
Problem????? Could anyone tell me how to modify the formula to work
for cubes?
thank you,
joel
Richard H Gould
In article <53c94p$a...@cambridge.emi.net>, jo...@emi.net writes
>Hello everyone,
> Has anyone ever heard of Newtons Method?
Your post is a bit confusing - I'm not sure whether you're trying to
find squares or square roots!
If you are referring to the Newton-Raphson method for finding the
approximate zeros of functions, the method, for a general function f(x)
is:
x_n+1=x_n-f(x_n)/f'(x_n)
If you draw a diagram, you will see that the intersection of the tangent
at (x_n,f(x_n)) with the x axis is used successively as a better
approximation than x_n
For square roots you are solving x^2-N=0 and this would give:
Guess=Guess/2+Number/(2*Guess)
For cube roots you are solving x^3-N=0 and the formula would be:
Guess=2*Guess/3+Number/(3*Guess^2)
This is generally a very powerful method, but can occasionally result in
oscillations about the answer and it sometimes heads off in the wrong
direction (speaking technically!).
--
Richard H Gould
rhg...@gocomp.demon.co.uk
Turnpike evaluation. For Turnpike information, mailto:in...@turnpike.com
Teach
jo...@emi.net wrote:
>Hello everyone,
The method is quite general, since it is averaging between your guess
and the true value. That average gets closer and closer.
The problem is that you *do* have to do some arithmetic to whatever
number of decimals you require [You determine that from the start.]
If the problem is great, then you have a LOT of arithmetic to do (long
division.) If that becomes onerous, you flip out the handy dandy
calculator. But then you might as well use that in the first place.
Although Newton's method does work, it is far too busy with arithmetic
to make it worthwhile. I.E. Use only if stuck on a deserted island
without a calculator, and if you have lots of paper, patience, and
time.
David.
mike hurley
> Hello everyone,
> Has anyone ever heard of Newtons Method? It's an alogarithm used to
> find the square roots of numbers. The alogarithm goes something like
> this: (Number*guess)+guess/2 =guess
> Number is the number which you are trying to find the square of
> Guess is what ever number you choose other than 0
> You keep plugging the guess in until it reaches Epsilon. (1.0E-09)
> Basically, no matter what number you guess....in the end you have the
> square of that number.
>
> Problem????? Could anyone tell me how to modify the formula to work
> for cubes?
> thank you,
> joel
The method for square roots is newGuess = [(N/guess) + guess]/2 and was known
in antiquity to (at least) the Babylonians, probably because guess
and N/guess are two sides of a rectangle of area N. If the rectangle
is not a square, one of these two sides is bigger than the square root and
the other is too small, so they averaged the two.
A similar process
can be derived for cube roots. Take a cubic solid with a square base
of side guess. If the volume is N, then the height is N/guess^2, and
the average of the 3 dimensions is [guess + guess + N/guess^2]/3. Unlike
the square root case, there are bad initial guesses other than 0, but
as long as the initial guess has the same sign as N, the process will
converge to the cube root of N.
Newton's method is an algorithm from calculus that is used to
find roots of functions. To approximate solutions of f(x) = 0, pick
a good initial guess x and then use
newGuess = x - [f(x)/f'(x)].
For f(x) = x^2 - N or f(x) = x^3 - N, you get the formulas above.
--
mike hurley
dept. of mathematics
case western reserve univ.
mg...@po.cwru.edu
Jeffrey A. Young
In article <53c94p$a...@cambridge.emi.net>, <jo...@emi.net> wrote:
>Hello everyone,
> Has anyone ever heard of Newtons Method? It's an alogarithm used to
>find the square roots of numbers. The alogarithm goes something like
>this: (Number*guess)+guess/2 =guess
>Number is the number which you are trying to find the square of
>Guess is what ever number you choose other than 0
>You keep plugging the guess in until it reaches Epsilon. (1.0E-09)
>Basically, no matter what number you guess....in the end you have the
>square of that number.
>
>Problem????? Could anyone tell me how to modify the formula to work
>for cubes?
>thank you,
> joel
Well, to really modify it, you'll need to understand why it works,
but you can find the explanation in any one of many many intermediate
math books yourself. If you just want to play with the algorithm
a little, here is the Newton formula for approximating any root
(let's call it nth root) of any Number:
NextGuess = [ LastGuess*(n-1) + Number/(LastGuess^(n-1)) ] / n
For n=1
NextGuess = Number
For n=2 (square root)
NextGuess = (LastGuess + Number/LastGuess) / 2
For n=3 (cube root)
NextGuess = (2*LastGuess + Number/(LastGuess^2)) / 3
etc.
Have fun.
Jeff
Zdislav V. Kovarik
In article <53c94p$a...@cambridge.emi.net>, <jo...@emi.net> wrote:
>Hello everyone,
> Has anyone ever heard of Newtons Method? It's an alogarithm used to
(Sorry, but before it burns in: the spelling is "algorithm")
>find the square roots of numbers.
And much more.
>The alogarithm goes something like
>this: (Number*guess)+guess/2 =guess
Correction: ((Number/guess) + guess) / 2 = (new guess)
(And this special case was known to Heron, long before Newton.)
>Number is the number which you are trying to find the square of
>Guess is what ever number you choose other than 0
>You keep plugging the guess in until it reaches Epsilon. (1.0E-09)
I can guess what you mean, but it's hardly what you wrote. Perhaps "until
the difference decreases in relative magnitude below Epsilon"?
>Basically, no matter what number you guess....in the end you have the
>square of that number.
"In the limit" sounds better than "in the end" (I should live that
long!).
For finding square roots of positive numbers starting with a positive
guess, it indeed works.
>
>Problem????? Could anyone tell me how to modify the formula to work
>for cubes?
>thank you,
> joel
>
If you know Calculus, a recipe for improving guesses to a solution of
f(x)=0 is
(new guess) = guess - f(guess) / f'(guess)
and one has to be careful about where to start, unless we have a very
simple situation (like finding square roots).
Heron's formula is actually a re-arrangement of
(new guess) = guess - (guess^2 - Number) / (2 * guess)
designed to solve x^2 - Number = 0 (x>0).
Try to convince yourself that cube root guesses will improve under
(new guess) = (Number/(guess^2) + 2 * guess) / 3
The number of correct digits approximately doubles each time we "turn the
crank" . (In slightly more delicate calculations using my pocket
calculator, I had to improve the last two digits of a cube root using
Newton's method. Example:
Calculator value of 7^(1/3) is 1.91293 118, that is 9 digits. The
calculator can hold 11 digits, and one step of Newton's method gives
1.91293 11828, the exact value correctly rounded to 11 digits.)
Have fun, ZVK (Slavek).
John McGowan
In article <53c94p$a...@cambridge.emi.net>, jo...@emi.net wrote:
> Hello everyone,
> Has anyone ever heard of Newtons Method? It's an alogarithm used to
> this: (Number*guess)+guess/2 =guess
> Number is the number which you are trying to find the square of
> Guess is what ever number you choose other than 0
> You keep plugging the guess in until it reaches Epsilon. (1.0E-09)
> square of that number.
It works for funtions f(x) where you want to find the root to f(r)=0 and
f'(r) is not zero (if f'(r) is zero, it converges much more slowly) and
for general functions one must start with a guess "close" to the root.
It works as follows:
Replace the guess x with x-f(x)/f'(x)
For example, to solve x^2=N (find the square root of N), f(x)=x*2-N and
f'(x)=2x so x-f(x)/f'(x)=x-(x^2-N)/(2x)=(x+N/x)/2 (take your guess,
divide it into N and take the average of the two).
For cubes, use x^3=N (to find the cube root of N) and f(x)=x^3-N,
f'(x)=3x^2 and replace x with x-(x^3-N)/(3x^2)=(2x+N/x^2)/3, a weighted
average of your original guess, x, and N/x^2 (of course, if x^3 IS the
cube root of N, then N/x^2 will be x again, and the weighted average will
just give x).
For finding the "a"th root of N, use f(x)=x^a-N, f'(x)=a*x^(a-1) and
replace x with x-(x^a-N)/(a*x^(a-1)) = [(a-1)x + N/x^(a-1)]/a, again a
weighted average of your original guess, x (weight (a-1)/a) and N/x^(a-1)
(weight 1/a) (those two numbers will be the same if you have a root).
The convergence is quadratic (about doubling the number of decimal places
each time you replace the guess) (if f'(root)<>0 and you are close enough
to the root with your guess).
Arthur Guetter
mar...@cnwl.igs.net (Teach) writes:
>
> jo...@emi.net wrote:
>
> >Hello everyone,
> > Has anyone ever heard of Newtons Method? It's an alogarithm used to
> >find the square roots of numbers. The alogarithm goes something like
> The method is quite general, since it is averaging between your guess
> and the true value. That average gets closer and closer.
>
> The problem is that you *do* have to do some arithmetic to whatever
> number of decimals you require [You determine that from the start.]
> If the problem is great, then you have a LOT of arithmetic to do (long
> division.) If that becomes onerous, you flip out the handy dandy
> calculator. But then you might as well use that in the first place.
> Although Newton's method does work, it is far too busy with arithmetic
> to make it worthwhile. I.E. Use only if stuck on a deserted island
> without a calculator, and if you have lots of paper, patience, and
> time.
You are correct that a calculator is a quicker method of finding square roots,
but to find the square root of 2 does not require a "LOT of arithmetic".
Newton's method converges very fast -- finding the square root of two with an
initial approximation of 1 gives the sequence:
1, 3/2, 17/12, 577/408, 665857/470832
A bit of arithmetic, but no long division yet. The error in the last fraction
is less than 1.6*10^(-10).
I don't have the reference in front of me, but I recall a quote by Newton that
runs something like "I am embarrassed to say how much time I have spent on
these calculations, having nothing better to do at the time".
------------------------------------------------------------------------------
Art Guetter Chair, Dept of Mathematics
ague...@piper.hamline.edu Hamline University
http://www.hamline.edu/~aguetter/ St Paul, MN 55104
------------------------------------------------------------------------------
Life is good for only two things, discovering mathematics and teaching
mathematics. (Simeon Poisson)
Simon Read
>In article <53c94p$a...@cambridge.emi.net>, jo...@emi.net wrote:
>> Hello everyone,
>> Has anyone ever heard of Newtons Method? It's an alogarithm used to
>> find the square roots of numbers. The alogarithm goes something like
It should be
(Number/guess +guess )/2 = new guess
Other posters have commented on Newton's method. The above formula
is Newton's method applied to square roots. Newton's method can be
applied to solve many types of equations.
Simon
Douglas S. McVey
Newton's method of approximation can be used to determine real zeros of
functions in on e variable (i.e. the solutions of equations in one
variable). It also has applications in higher dimensions using partial
derivatives, etc., but they can be extrapolated from the following
explanation:
To use it, you need a function which is continuous around the root in
question (applying it only to polynomial functions, which are of course
continuous everywhere, solves the problem of how close is "around").
Let f(x) equal the function's value at any x and f'(x) equal the value
of the derivative (i.e., the slope of the tangent line) at any x. The
formula is:
b=a-[f(a)/f'(a)]
This makes perfect sense if you think about it...if you doubt the sense,
post another message, and I'll give the "common sense" explanation. It
can be proven that the new guess sometimes diverges (i.e., is further
away than the original guess), but this USUALLY only happens when there
is a horizontal tangent (i.e. 1st deriv.=0) in the area. If we apply
this to the function y=x^.5 (the sq. rt. of x), we can solve and get an
algorithm which was discussed earlier.
Bill Dubuque
Actually there is a very general viewpoint that relates Newton's method
and similar successive approximation schemes, e.g. Hensel's lemma, which
is employed in most polynomial factorization algorithms. There are even
connections with Grobner bases. See my message below for further pointers.
-Bill
Date: Tue, 15 Oct 96 05:30:09 -0400
From: Bill Dubuque <w...@martigny.ai.mit.edu>
To: Multiple recipients of list <GAP-...@Math.RWTH-Aachen.DE>
Subject: Re: Hensel/Newton lifting
Tim Boykett asked:
>
> I have been digging around the code for roots of unity in the
> rings Z_n, and have found a technique called the "Newton/Hensel
> method of lifting". Does anyone have a reference that might explain
> the algorithm, proof of its validity, etc.
See the following Math Reviews for entry points into the literature.
There is also a nice treatment in Zippel's text "Effective Polynomial
Computation", Kluwer, 1993.
-Bill Dubuque
------------------------------------------------------------------------------
85j:12012 12J20 65P05
von zur Gathen, Joachim (3-TRNT-C)
Hensel and Newton methods in valuation rings. (English)
Math. Comp. 42 (1984), no. 166, 637--661.
------------------------------------------------------------------------------
Hensel's lemma is a fundamental tool in the study of algebraic equations over
$p$-adic fields. In the folklore of number theory it has been known for a long
time that Hensel's and Newton's method are formally the same (this remark
appears in printed form in an article by D. J. Lewis published in a book
edited by W. J. LeVeque [Studies in number theory, 25--75, see p. 29,
Prentice-Hall, Englewood Cliffs, N.J., 1969; MR 39 #2699]).
A generalized version of Hensel's lemma in suitable valuation rings is
contained in N. Bourbaki's book [Elements of mathematics, 23, Commutative
algebra (French), see Chapter III, Section 4, Theorem 1 and Theorem 2,
Hermann, Paris, 1958; MR 20 #4576].
This paper also deals with the study of Hensel's method in valuation rings and
shows that Newton's method is a special case of Hensel's. The presentation
emphasizes the algorithmic point of view and is very detailed and clear. The
linear and quadratic cases of Hensel's lemma are both given. Newton's method
is applied to systems of nonlinear partial differential equations. Then the
author presents an algorithm for the computation of a shortest nonzero vector
in a non-Archimedean valuation module. These results are applied in the last
section, which contains an algorithm for factoring polynomials over a ring
with valuations.
Reviewed by Maurice Mignotte
------------------------------------------------------------------------------
87a:12014 12J10 13A18
Ribenboim, Paulo (3-QEN)
Equivalent forms of Hensel's lemma. (English)
Exposition. Math. 3 (1985), no. 1, 3--24.
------------------------------------------------------------------------------
From the introduction: "The celebrated Hensel's lemma, which is the
cornerstone of the theory of $p$-adic numbers, has been the object of
extensive studies. However, our aim in this paper is not to describe the
development of ideas and applications centered around Hensel's lemma, but
rather to examine closely the various formulations found in the literature. We
place ourselves in the framework of the theory of valued fields and show that
Hensel's lemma is logically equivalent to many propositions concerning the
number of extensions of the valuation to algebraic extensions, or the lifting
of polynomials from the residue field, or the determination of zeroes of a
polynomial by a method which dates back to Newton, or even to a geometric
formulation concerning the mutual distance between the zeroes of
polynomials. These facts are of a `folkloric' nature, yet no complete proof of
their equivalence has appeared in any one paper.
"This article is written at the level of research students."
Reviewed by Antonio Jose Engler
------------------------------------------------------------------------------
90f:68096 68Q40 13A18 13J10
Miola, A. (I-ROME-I); Mora, T. (I-GENO)
Constructive lifting in graded structures: a unified view of Buchberger
and Hensel methods. (English)
Computational aspects of commutative algebra.
J. Symbolic Comput. 6 (1988), no. 2-3, 305--322.
------------------------------------------------------------------------------
A graded structure is a filtered commutative ring $A$ which is filtered by a
totally ordered group and has a graded associated ring and a ring
completion. The authors define a process for solving, in the ring completion,
a polynomial multivariate equation over $A$ by successive approximations. They
discuss under which conditions this process converges.
The main interest of this theory is that Hensel lifting, Buchberger's
algorithm for Grobner basis computations in polynomial rings and Hironaka's
division process by a standard basis in rings of formal power series are
instances of the above process. For example, Hensel lifting is an
approximative resolution of $yz-a=0$, which needs some conditions on $a$ and
on the initial values of $y$ and $z$ to be convergent.
{For the entire collection see MR 89j:68004}.
Reviewed by Daniel Lazard
Timothy E. Vaughan
|> Has anyone ever heard of Newtons Method? It's an alogarithm used to
|> find the square roots of numbers.
<snip>
|> Problem????? Could anyone tell me how to modify the formula to work
|> for cubes?
Newton's method is actually an iterative technique for solving a more
general class of problems: f(x) = 0. The specific formula for the
square root problem is called the "Babylonian square root method,"
and was known more than 2000 year ago by the Babylonians!
General formula [for f(x) = 0]:
x_[n+1] = x_n - f(x_n) / f'(x_n),
where
"x_n" is the current guess;
"x_[n+1]" is the new guess;
"f(x_n)" is the function evaluated at x_n; and
"f'(x_n)" is the derivative of f(x) evaluated at x_n
For square root of A [f(x) = x^2 - A = 0]:
x_[n+1] = x_n - (x_n^2 - A) / ( 2*x_n )
= (x_n + A/x_n) / 2
For cube root of B [f(x) = x^3 - B = 0]:
x_[n+1] = x_n - (x_n^3 - B) / (3*x_n^2)
= ( 2*x_n + B/(x_n^2) ) / 3
I hope this helps, and I hope this wasn't your homework!
Tim
P.S. The word is "algorithm", not "alogarithm".
Brian David Rothbach
Simon Read wrote:
>
> >In article <53c94p$a...@cambridge.emi.net>, jo...@emi.net wrote:
> >> Hello everyone,
> >> Has anyone ever heard of Newtons Method? It's an alogarithm used to
> >> this: (Number*guess)+guess/2 =guess
Actually, I just had to do a homework problem showing that if {xn} are
the series of guesses, and En=x-sqrt(number) is the error in the nth
guess, and you start with x1>=sqrt(number) then
En=2sqrt(number)*(E1)^(2^n)
So this converges relatively quickly.
And no, I'm not asking for help on this problem.
Brian Rothbach
Zdislav V. Kovarik
In article <3270E6...@owlnet.rice.edu>,
The statement is false, even for number=1 and x1=3.
(Perhaps with equality replaced by <= and under suitable extra
assumptions about E1 it will be true.)
There is, however, a true statement which looks like the one you
mentioned: define Fn=(xn-sqrt(number))/(xn+sqrt(number)), then a nice
simple statement can be made (as an exercise) about Fn and its relation
to F0.
This formula was known to Cayley (and to many before him), and he was
unsuccessful in finding anything similarly explicit for cube roots found
by Newton's Method. These were the humble beginnings of the study of
fractals.
Hope I did not help you, ZVK (Slavek):-)
Simon Read
>Actually, I just had to do a homework problem showing that if {xn} are
>the series of guesses, and En=x-sqrt(number) is the error in the nth
>guess, and you start with x1>=sqrt(number) then
>En=2sqrt(number)*(E1)^(2^n)
>
Certainly each error is proportional to the square of the previous
error, but that only applies for small E1. If E1 is greater than
1, your formula for En makes it diverge.
Simon
A foolish consistency is the hobgoblin of small minds.