Compute $\sqrt{5}$ using Newton's method and regula falsi method

Question

I am trying to find how many iterations it takes to find $\sqrt5 \text{ to } 15$ digit accuracy using Newton's method and regula falsi method. I know the newton method is $x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$ and the regula falsi method is given as $x_k = \frac{lf(r) - rf(l)}{f(r)-f(l)}$. But I'm not sure how to use these to calculate $\sqrt5$?

EDIT:

Using Python I was able to find the number of iterations for Newton's method:

def newtonSqrt(n):  
    approx = 0.5 * n  
    better = 0.5 * (approx + n/approx)  
    while (better != approx):  
        approx = better  
        better = .5 * (approx + n/approx)  
        print(approx)  
    return approx  

print(newtonSqrt(5))  

Still unsure about regula falsi

Answer 1

In general, if $f$ is convex, differentiable, $f(x^*) = 0$, $f'(x^*) >0$ and we have some $x_0$ such that $f'(x_0) > 0$, then Newton's iteration starting at $x_0$ will converge to $x^*$. Furthermore, the iterates $x_1,x_2,...$ are non increasing and $x_n \downarrow x^*$.

In particular, the accuracy is always improving (or, at least, never gets worse).

In fact, it is not hard to show that if $f$ is $C^2$, then $x_n \to x^*$ quadratically.

To get an explicit upper bound on the distance from a solution, note that since $f$ is convex, we have $f(x) -f(x^*)\ge f'(x^*)(x-x^*)$, so $x-x^* \le {f(x) \over f'(x^*)}$.

In particular, for $n\ge 1$ we have $x_n -\sqrt{5} \le {x_n^2-5 \over 2 \sqrt{5}} \le {x_n^2-5 \over 6}$. (I have replaced the $\sqrt{5}$ by 3 so that the distance estimate does not use $\sqrt{5}$ to compute the distance :-).)

So, stop iterating when ${x_n^2-5 } \le 6\cdot10^{-15}$.

Answer 2

Never compare floating point values in numerical algorithms for equal bit patterns, as you do in

better != approx

Always use the intended absolute or relative error.

"15 digits" indicates a relative error, thus the condition should be `

abs(better-approx) > 5e-16*abs(better)