Third Order Convergence for Square Roots Using Newton's Method
08-27-2019, 06:32 PM (This post was last modified: 08-28-2019 01:41 AM by Namir.)
Post: #1 Namir Senior Member Posts: 810 Joined: Dec 2013
Third Order Convergence for Square Roots Using Newton's Method
Hi All,

Most of us are familiar with the second order converging algorithm for obtaining the square root of N:

X(n+1) = (X(n) + N/X(n)) / 2
where X(0) is the initial guess for the square root of N.

I stumbled on a third order converging algorithm in an book about ODEs and PDEs. The algorithm is:

X(n+1) = X(n)*(X(n)^2 + 3*N)(3*X(n)^2 + N)
where X(0) is the initial guess for the square root of N.

I compared the two algorithms using Excel and the second one does converge faster than the first one.

The pseudo-code for the second algorithm is:

Given N and X (initial guess) and tolerance toler:

Code:
 Repeat   Y = X*X;   X = X * (Y + 3*N) / (3*Y + N) Until Abs(X*X-N) <= toler

Enjoy!

Namir
 « Next Oldest | Next Newest »

 Messages In This Thread Third Order Convergence for Square Roots Using Newton's Method - Namir - 08-27-2019 06:32 PM RE: Third Order Convergence for Square Roots Using Newton's Method - ijabbott - 08-27-2019, 07:49 PM RE: Third Order Convergence for Square Roots Using Newton's Method - Namir - 08-28-2019, 01:39 AM RE: Third Order Convergence for Square Roots Using Newton's Method - KeithB - 08-27-2019, 09:44 PM RE: Third Order Convergence for Square Roots Using Newton's Method - Albert Chan - 08-27-2019, 09:55 PM RE: Third Order Convergence for Square Roots Using Newton's Method - Namir - 08-28-2019, 01:40 AM RE: Third Order Convergence for Square Roots Using Newton's Method - rprosperi - 08-28-2019, 01:52 AM RE: Third Order Convergence for Square Roots Using Newton's Method - bshoring - 08-28-2019, 07:32 PM RE: Third Order Convergence for Square Roots Using Newton's Method - C.Ret - 09-16-2021, 07:45 PM RE: Third Order Convergence for Square Roots Using Newton's Method - Albert Chan - 09-16-2021, 01:39 PM RE: Third Order Convergence for Square Roots Using Newton's Method - ttw - 09-16-2021, 05:18 PM RE: Third Order Convergence for Square Roots Using Newton's Method - Albert Chan - 09-16-2021, 07:58 PM RE: Third Order Convergence for Square Roots Using Newton's Method - Gamo - 09-17-2021, 12:30 AM RE: Third Order Convergence for Square Roots Using Newton's Method - Albert Chan - 09-17-2021, 01:33 AM RE: Third Order Convergence for Square Roots Using Newton's Method - Namir - 09-18-2021, 10:15 PM RE: Third Order Convergence for Square Roots Using Newton's Method - ttw - 09-20-2021, 10:04 AM

User(s) browsing this thread: 1 Guest(s)