Obtain an aproximation to $\sqrt{5}$ using other numeric methods

Question

From the original problem:

Find an approximation to $\sqrt{5}$ correct to an exactitude of $10^{-10}$ using the bisection algorithm.

In which I have a function in Mathematica to do the calculations in which the function $f(x)$, $a$ and $b$ (from the interval $[a, b]$ where $f(a)$ and $f(b)$ have opposite signs), the tolerance and the number of iterations.

I managed to determine that, if $\sqrt{5}$ is a possible root of the function then $f(x)$ can be written as:

$$ f(x) = x - \sqrt{5} = x^2 - 5 = 0 $$

As for the interval, I used $[a, b] = [2, 3]$ as:

$$ f(2) = 2^2 - 5 = -1 \\ f(3) = 3^2 - 5 = 4 $$

Then it is given that the tolerance is $10^{-10}$ and using $20$ iterations (Is there a way to calculate it?), I obtained a result of $1.36511$ after $13$ iterations.

Now I am trying to:

Obtain the same aproximation with the same exactitude in at least half the number of iterations (Using another method).

These methods would be either:

• Fixed Point Method
• Newton's Method
• Secant Method
• False Position Method

But I don't fully understand the problem as the other methods only accept one point ($a$) instead of two and when I enter those into the algorithm, I get different results.

For example, using Newton's Method, I get $2.23607$ in only $6$ interations which seems to be a better result but from the questions is seems that I am suppose to be getting the same result from the Bisection methos.

How do I proceed?

Answer 1

As already stated in comments to the previous question, the bisection method starting from the interval $[2,3]$ requires 30 iterations to get the remaining interval length to $2^{-30}=(2^{10})^{-3}<10^{-3\cdot 3}$, add 3 or 4 iterations to meet the bound $10^{-10}$.

---

As for a fixed-point method, observe that $0=x^2-5=x^2-4-1=(x-2)(x+2)-1$, so that one can formulate $$ x_{n+1}=g(x_n)=2+\frac1{x_n+2} $$ To get a handle on the convergence, compute the Lipschitz constant, for $x,y\in [2,3]$ you get $$ |g(x)-g(y)|=\frac{|x-y|}{(2+x)(2+y)}\le \frac1{16}|x-y|. $$ By the a-priori estimate of the Banach fixed-point theorem, the accuracy after $n$ steps is $\frac{L^n}{1-L}|x_1-x_0|$ which with $|x_1-x_0|<1$ and $L=\frac1{16}$ is smaller than $2^{4-4n}/15$, so that one step of the fixed-point iteration would be equivalent to 4 bisection steps.

---

Let's see this in practice

x = 2.5
for k in range(20): 
    print "%6d: x=%20.15f, f(x)=%15.8g"%(k, x, x**2-5); 
    x = 2+1/(2+x)

which gives the table

 0: x=   2.500000000000000, f(x)=           1.25
 1: x=   2.222222222222222, f(x)=   -0.061728395
 2: x=   2.236842105263158, f(x)=   0.0034626039
 3: x=   2.236024844720497, f(x)= -0.00019289379
 4: x=   2.236070381231672, f(x)=  1.0749822e-05
 5: x=   2.236067843544479, f(x)= -5.9906634e-07
 6: x=   2.236067984964864, f(x)=  3.3384826e-08
 7: x=   2.236067977083775, f(x)= -1.8604718e-09
 8: x=   2.236067977522973, f(x)=  1.0368062e-10
 9: x=   2.236067977498498, f(x)= -5.7784888e-12
10: x=   2.236067977499862, f(x)=  3.2240877e-13
11: x=   2.236067977499786, f(x)= -1.7763568e-14
12: x=   2.236067977499790, f(x)=  8.8817842e-16

so that indeed in 8 (=32/4) iterations the accuracy goal is met (note that the distance to the root is approximately $-f(x)/f'(x)\approx -f(x)/4$).