Root Approximation - Bisection

Root approximation through bisection is a simple method for determining the root of a function. By testing different $x$-values in a function, the root can be gradually found by simply narrowing down the range of the function's sign change.

Assumption: The function is continuous and continuously differentiable in the given range where we see the sign change. This assumption is key as it will guarantee a root exists in the range by the intermediate value theorem.

Below is a graph of the function $x^{2}+2x-1.$

In order to find the root between $[0, 2]$, for example, $x$-values can be plugged into the function starting with the original domain:

$$\begin{aligned} f(0)&=0^{2}+2(0)-1\\&= -1\\\\ f(2)&= 2^{2}+2(2)-1\\&= 7. \end{aligned}$$

Because the function is continuous and there is a sign change, by intermediate value theorem, there must be a root between $(0,2)$. The midpoint between every domain is halved until the approximation becomes sufficiently close. In the previous example, the domain can be narrowed down through the midpoint, i.e. $\frac{x_{1}+x_{2}}{2}$:

$$\begin{aligned} f(1)&=1^{2}+2(1)-1\\&= 2\\\\ f(0.5)&=0.5^{2}+2(0.5)-1\\&= 0.25\\\\ f(0.25)&=0.25^{2}+2(0.25)-1\\&= -0.4375. \end{aligned}$$

The root has been established to lie within (0.25, 0.5). Bisection can be further continued:

$$\begin{aligned} f(0.375)&=0.375^{2}+2(0.375)-1\\&= -0.109\\\\ f(0.4375)&=0.4375^{2}+2(0.4375)-1\\&= 0.06640625. \end{aligned}$$

Now, the root's domain lies somewhere within (0.375, 0.4375). Bisection can be continued as precision dictates.

Can you find the root of the equation $y = \frac{1}{x}$ in the interval between $y(-1) = -1$ and $y(1) = 1$?

---

By the intermediate value theorem you might expect that since the sign changes between $x=-1$ and $x=1$, that there should be a root between these two $x$ values; however, this equation is not continuous on this interval. Specifically, at $x=0$.

• $$\lim_{x\rightarrow0+}{\frac{1}{x}} = +\infty$$
• $$\lim_{x\rightarrow0-}{\frac{1}{x}} = -\infty$$

Therefore, $\boxed{no}$ this method cannot be used to find a root in this interval.

Can you find the root of the equation $y = x^2$ in the interval between$x=-1$ and $x = 1$?

---

Although, clearly a root exists in this interval, specifically $y(0) = 0$, and the function is continuous and continuously differentiable in this range, the root approximation bisection method can't be used in this case since y never takes on a negative value in this range.

So $\boxed{no}$ this method cannot be used to find a root in this interval.

Given that the function $f(x)=2x^{3}+x^{2}-2x+1$ has a root between 0 and -2, find the root to one decimal place.

---

First we evaluate the function at both intervals:

$$f(0)=1,\quad f(-2)=-7.$$

Now we bisect and repeat:

$$\begin{aligned} f(-1)&=2\\ f(-1.5)&=-0.5\\ f(-1.25)&=1.156\\ f(-1.375)&=0.441. \end{aligned}$$

We know the root lies somewhere between -1.5 and -1.375. Taking the midpoint, $\frac{-1.5+-1.375}{2}=-1.4375$. So we know the value to 1 decimal place of the root between 0 and -2 of the equation $2x^{3}+x^{2}-2x+1$ is $-1.4.\ _\square$

Given that the function $f(x)=\frac{1}{3}-\frac{1}{x}$ has a root between $1$ and $4$, find the root to one decimal place.

---

Your first reaction might be to say, "Hey wait, this function isn't continuous or differentiable at $x=0$. However, $x=0$ isn't in the interval between $1$ and $4$, so this method can be used.

$$f(1)=-\frac{2}{3},\quad f(4)=\frac{1}{12}.$$

Now we bisect and repeat:

\[\begin{align} f(2.5)&=-.067\\ f(3.25)&=0.025\\ f(2.875)&=-0.014\\ f(3.0625)&=0.0068\\ f(2.969)&=-0.0035.

\end{align}\]

This has narrowed the search to between $x=2.969$ and $3.0625$. Taking the midpoint gives us an answer of $\boxed{x=2.99}$ to within a decimal point.

For the last example, we could see from the equation that the root would approach 3. However, for this example, it is not so obvious. In fact, it might be quite difficult to find the roots without the use of this bisection method.

Given that the function $f(x)=x^5 -4x^4+3x^2-x+2$ has a root between $3$ and $4$, find the root to one decimal place.

---

$$f(3)=-55,\quad f(4)=46.$$

Now we bisect and repeat:

$$\begin{aligned} f(3.5)&=-39.78\\ f(3.75)&=-9.00\\ f(3.875)&=14.99\\ f(3.8125)&=2.18\\ f(3.78125)&=-3.61. \end{aligned}$$

This has narrowed the search to between $x=3.8125$ and $3.78125$. Taking the midpoint gives us an answer of $\boxed{x=3.80}$ to within a decimal point.

Here is a Python implementation of the algorithm:

1
2
3
4
5
6
7
8
9

def bisection(f, a, b, eps):  #take two points where the sign of the result is negative and positive respectively and an error bound
   mid = (a+b)/2
   while abs(f(mid)) > eps:
      if f(mid) < 0:
         a = mid
      else:
         b = mid
      mid = (a+b)/2
   return mid

Now we could run it like this, for example:

1
2

>>> bisection(lambda x: x**2-2, 0, 2, 0.001)
1.4140625

• Newton's method