CTK Exchange
CTK Wiki Math
Front Page
Movie shortcuts
Personal info
Awards
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Products to download and subscription Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "Newton & Roots"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange Thoughts and Suggestions Topic #86
Reading Topic #86
John Ungar
guest
Jun-25-10, 10:22 AM (EST)
 
"Newton & Roots"
 
   Hello everybody!
I found this one => https://www.cut-the-knot.org/wiki-math/index.php?n=Calculus.ApproximationOfRoots
on your Webproject and it'seems to be a pretty hot hot piece of math. But one question is still open for me: Whilst the old Newton-mechanism in his approximation is correlating to the chosen N, the Reineke Algorhythm seems not to do anything like that. Seems this nice little formula has not any relation to the size of a chosen N, its always approxying in 5-9 steps. And the question therefor is:
Is there a way to an analytic proof to show, that there is a relation between a chosen N and the number of approximations on the one hand and no relation between N and the approx count in the Reineke algorhythm on the other?

Thank U so far
John Martin Ungar


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
2523 posts
Jun-26-10, 09:38 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
1. "RE: Newton & Roots"
In response to message #0
 
   As far as I understand, Chris did not mean to apply this formula iteratvely. But you are right. An estimate is still missing.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
C. Reineke
guest
Jun-28-10, 08:54 AM (EST)
 
2. "RE: Newton & Roots"
In response to message #1
 
   Alex,

you wrote:

“As far as I understand, Chris did not mean to apply this formula iteratively.”

Yes and no. Do you remember my example when I computed sqrt(66) with two
iterations? With a “good” initial guess you can use the formula to approximate a root
in one step, but with a “poor” initial guess you need more iterations, of course.

However, I would like to repeat John’s observation:

Assume we want to compute the nth root(1000), the initial guess is always=1, desired accuracy: EXCEL’s 14 digits.

Now let n increase, say, 2, 3, 4, 5, 10, 100, 1000. Then you will see that the number of iterations needed to reach the desired accuracy does not increase – contrary to Newton’s method. To compute the 1000th root(1000) Newton’s algorithm needs 692 iterations, the new algorithm needs (always) 7!

So it'seems that the number of iterations does not depend on n.
I’ve got absolutely no explanation for this property, but maybe it’s possible to prove
it mathematically, as John wrote.

By the way, the algorithm also converges if n is negative.

Kind regards

Chris


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

Copyright © 1996-2018 Alexander Bogomolny

Search:
Keywords:

Google
Web CTK