# Solving $f(x) = x^5 +x + 1 = 0$ with halving the interval / bisection method

Question:

Use halving the interval / bisection method to approximately solve:

$$f(x) = x^5+ x + 1 = 0$$

with a precision of $\pm 0.1$

Attempted solution:

The general idea, as I understand it, is to find two points e. g. $x_1,x_2$ where e. g.

$$x_1 \leq x_2$$

and

$$f(x_1) < a < f(x_2)$$

Then take the point half-way between $x_1$ and $x_2$, and then, depending on what side of the RHS of the equation it is, form a new, smaller interval and repeat the process until sufficient precision has been obtained.

Trial-and-error locates

$$x_1 = -1 \Rightarrow f(x_1) = -1$$

$$x_2 = 0 \Rightarrow f(x_2) = 1$$

In other words:

$$-1 < a < 0$$

Half of $x_1$ and $x_2$ becomes:

$$x_3 = -\frac{1}{2} \Rightarrow f(x_3) = 0.469$$

Then

$$x_4 = -\frac{3}{4} \Rightarrow f(x_4) = 0.013$$ $$x_5 = -\frac{7}{8} \Rightarrow f(x_5) = -0.388$$

This results in the following interval:

$$-\frac{7}{8} < a < -\frac{3}{4}$$

Half of that is:

$$x_6 = -\frac{13}{16} \approx -0.8$$

This method can be continued for a very long time in many cases, but how do I know the required precision has been obtained? The textbook procedure works something like this:

$x_6$ lies at a distance from the root a being searched for that is at most half of the interval length

$$\frac{1}{2} \left( -\frac{3}{4} + \frac{7}{8} \right) = \frac{1}{16}$$

and thus we can conclude that $a = -0.8 \pm 0.1$.

However, I do not understand this last step. What is it that evaluates to $+0.1$ or $-0.1$ or less? How do I know when I am done and have attained the requested precision?

The thing that evaluates to $0.1$ or less is the absolute error.

Since $f(x)=x^5+x+1$ is continuous, $f(-\frac 78)<0$, and $f(-\frac 34)>0$, the intermediate value theorem guarantees that there is a root of $f(x)$ in the interval

$$-\frac 78<x<-\frac 34$$

Another way of writing that inequality is

$$\left| x-\left(-\frac{13}{16}\right) \right|<\frac 1{16}$$

So if we take our estimate as $-\frac{13}{16}$, we are sure that our error in that choice is less than $\frac 1{16}$. Since that error is less than $0.1$, we are sure that our error is less than $0.1$.

The absolute error in a measurement $a$ to the correct value of $x$ is defined as

$$\text{Absolute error}=|x-a|$$

This gives us the distance from the estimate to the correct value, in absolute terms. Sometimes the relative error is wanted, which gives the error as a fraction of the correct value. This is defined as

$$\text{Relative error}=\left| \frac{x-a}{x} \right|$$

How do you know you have obtained the required precision? When you know your absolute error is less than desired. In other words, when half the interval length is less than desired. You are then sure that your estimate is "close enough" to the actual answer.

The bisection method approximates the roots to the function. Since it's an approximation, there exists some error. Your precision tells you how close you want the approximation to be compared to the actual value (the actual root). So basically, the number of steps $n$ you need to take to get a particular precision $\epsilon$ is given by $$n = \log_2{\frac{b - a}{\epsilon}}$$

Here $a, b$ are the initial two values you found (ie, your $x_1$ and $x_2$). You are also given the precision so now you can get the value for $n$. In your case with $a = -1, b = 0$ you have $\log_2{\frac{1}{0.1}} = 3.32$. So you'd a minimum of 4 steps to get to your precision. Ofcourse, more steps will make your approximation even better.