(12C) Square Root
09-28-2020, 05:18 PM
Post: #4
 Albert Chan Senior Member Posts: 2,555 Joined: Jul 2018
RE: (12C) Square Root
(10-02-2019 02:36 PM)Albert Chan Wrote:  guess = 0.365 * (1 + n) reduced max_rel_err to 27%, thus required at most 4 iterations.

Turns out above is not the optimal. It should be guess = 0.37913 * (1+n), 0.1 ≤ n ≤ 10

For increasing function, Newton's method preferred a guess on the right.

One application of Newton's method automatically gives a guess, to the right of actual root.
Example, sqrt(n = 0.7) ≈ 0.83666

x = 0.37913*(1+n) ≈ 0.64452 (guess to the left of root)
x = (x + n/x) / 2 ﻿ ﻿ ﻿ ﻿ ≈ 0.86530 (guess, now to the right)

XCas> nt(x,n) := (x + n/x)/2
XCas> relerr(k,n) := 1 - nt(k*(1+n),n) / sqrt(n) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ // note: relative error ≤ 0
XCas> solve(relerr(k,1) = relerr(k,10) and k>0, k) ﻿ ﻿ ﻿ → $$[\sqrt{\sqrt{10} / 22}]$$
XCas> k0 := approx(ans()[0])﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ → 0.379130444101

Relative error (worst case) at n=0.1, or 1., or 10.
With guess = k0*(1+n), how many iterations to ensure full convergence ? Try n=1 (note: √1=1)

XCas> nt(k0*2﻿, 1) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿→ 1.03853409762
XCas> nt(ans(), 1) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ → 1.00071489067
XCas> nt(ans(), 1) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ → 1.00000025535
XCas> nt(ans(), 1) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ → 1.0

4 Newton iterations will converged to full 12 digits

P.S. above shows Newton's method on square-root, convergence rate ≈ ε²/2
 « Next Oldest | Next Newest »

 Messages In This Thread (12C) Square Root - Gamo - 10-02-2019, 10:23 AM RE: (12C) Square Root - Albert Chan - 10-02-2019, 02:36 PM RE: (12C) Square Root - Albert Chan - 09-28-2020 05:18 PM RE: (12C) Square Root - Albert Chan - 09-28-2020, 07:14 PM RE: (12C) Square Root - Gamo - 10-03-2019, 02:01 AM RE: (12C) Square Root - SlideRule - 09-28-2020, 09:45 PM RE: (12C) Square Root - Albert Chan - 06-08-2021, 03:36 PM RE: (12C) Square Root - depor - 12-21-2023, 11:50 PM RE: (12C) Square Root - Dave Hicks - 12-23-2023, 01:48 AM RE: (12C) Square Root - Thomas Klemm - 12-23-2023, 04:26 AM

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