0
$\begingroup$

I am attempting to resolve the following problem:

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

From what I understand, $\sqrt{5}$ has to be placed in function of $x$ but I am not sure where to go from there.

Also, a function in Mathematica are given 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.

1 Answers 1

1

The bisection method is a method for finding the roots of a continuous function ie finding $ x $ such that $ f(x) $ equals zero. Thus, you need a function which has a zero equal to $ \sqrt{5} $. The function $x^2 - 5 = f(x)$ will do.

Then, select an initial interval $[a, b]$ which contains the root. and for which $f(a)$ and $f(b)$ have different signs. The interval $[2, 3]$ will do.

The bisection method converges by repeatedly cutting the length of this interval in half.

Here is pseudocode from wikipedia:

N ← 1
While N ≤ NMAX # limit iterations to prevent infinite loop
  c ← (a + b)/2 # new midpoint
  If f(c) = 0 or (b – a)/2 < TOL then # solution found
    Output(c)
    Stop
  EndIf
  N ← N + 1 # increment step counter
  If sign(f(c)) = sign(f(a)) then a ← c else b ← c # new interval
EndWhile
Output("Method failed.") # max number of steps exceeded

The difference between the midpoint of the $n-th$ interval and the root $c$ is given by $$|c_n - c| \leq \frac{|b-a|}{2^n}$$ which follows directly from the fact that the interval is halved each iteration. You can figure out the number of iterations necessary for the desired $\epsilon$ using this formula.