The Bisection Method: A Root-Finding Algorithm

Introduction to the Bisection Method

The bisection method is a fundamental root-finding algorithm in numerical analysis. It is based on the Intermediate Value Theorem (IVT), which ensures the existence of at least one root if a continuous function changes sign over a closed interval. The method works by repeatedly halving the interval, effectively narrowing down the root's location with increasing precision.

While the bisection method may not be the fastest algorithm available, its simplicity, reliability, and guaranteed convergence make it an invaluable tool in various applications. It is particularly useful when other root-finding methods fail to converge or when dealing with functions that are continuous but not necessarily differentiable.

For Example

Consider the function $f(x) = x^2 - 4$, and we want to find the root of this function in the interval $[1, 3]$.

• Start with the interval $[1, 3]$. Since $f(1) = -3$ and $f(3) = 5$, the function changes sign over this interval, meaning there is a root.
• Find the midpoint:
  $$m = \frac{1 + 3}{2} = 2$$
  Evaluate $f(2) = 0$, which means we’ve found the root: $x = 2$.

In this simple case, the root is found after the first iteration, but in most cases, the method continues halving the interval until the desired accuracy is reached.

Principle of the Bisection Method

The bisection method is rooted in the Intermediate Value Theorem, which states that for a continuous function $f(x)$ on a closed interval $[a, b]$, if $f(a)$ and $f(b)$ have opposite signs, then there exists at least one point $c$ in $(a, b)$ such that $f(c) = 0$.

The method exploits this theorem by continuously dividing the interval in half and selecting the subinterval where the sign change occurs. This process progressively narrows down the location of the root.

The Bisection Algorithm

The algorithm can be summarized as follows:

1. Choose an initial interval $[a, b]$, such that $f(a)f(b) < 0$.
2. Compute the midpoint $c = \frac{a + b}{2}$ and evaluate $f(c)$.
3. If $f(c) = 0$ or $|b - a|$ is less than the desired tolerance, then $c$ is the approximated root.
4. Otherwise, update the interval:
• If $f(a)f(c) < 0$, set $b = c$.
• If $f(b)f(c) < 0$, set $a = c$.
5. Repeat steps 2-4 until the desired tolerance is reached or the maximum number of iterations is exceeded.

Example

Let's apply the bisection method to find the root of the function $f(x) = x^3 - x - 2$ in the interval $[1, 2]$.

• Start with the interval $[1, 2]$. Since $f(1) = -2$ and $f(2) = 4$, the function changes sign, indicating a root exists in this interval.
• Compute the midpoint:
  $$c = \frac{1 + 2}{2} = 1.5$$
  Evaluate $f(1.5) = -0.125$. Since $f(1)f(1.5) < 0$, we update the interval to $[1, 1.5]$.
• Repeat the process: Compute the next midpoint
  $$c = \frac{1 + 1.5}{2} = 1.25$$
  Evaluate $f(1.25) = -1.796875$. Since $f(1.25)f(1.5) < 0$, the new interval is $[1.25, 1.5]$.
• Continue this process until the desired accuracy is reached. In this case, after several iterations, the root will be approximately $x \approx 1.521$.

More Examples with Solutions

Example 1: Solving a Polynomial Equation

Find the root of the equation $f(x) = x^3 - x - 2$ using the bisection method in the interval $[1, 2]$ to a tolerance of $10^{-6}$.

Solution:

1. Initial interval: $[1, 2]$
2. Check: $f(1) = -2$ and $f(2) = 4$, so $f(1)f(2) < 0$. The condition is satisfied.
3. Iterations:

Iteration	a	b	c	f(c)
1	1	2	1.5	0.375
2	1	1.5	1.25	-0.796875
3	1.25	1.5	1.375	-0.196533
...	...	...	...	...
20	1.324717	1.324718	1.3247175	-0.000001

4. The final root approximation is $x \approx 1.324718$.

Example 2: Finding the Root of a Trigonometric Function

Find the root of the equation $f(x) = \cos(x) - x$ in the interval $[0, 1]$ to a tolerance of $10^{-6}$.

Solution:

1. Initial interval: $[0, 1]$
2. Check: $f(0) = 1$ and $f(1) \approx -0.4597$, so $f(0)f(1) < 0$. The condition is satisfied.
3. Iterations:

Iteration	a	b	c	f(c)
1	0	1	0.5	0.377583
2	0.5	1	0.75	-0.018155
3	0.5	0.75	0.625	0.189349
...	...	...	...	...
20	0.739085	0.739086	0.7390855	-0.000001

4. The final root approximation is $x \approx 0.739085$.

Example 3: Solving a Transcendental Equation

Find the root of the equation $f(x) = e^x - 3x$ in the interval $[0, 1]$ to a tolerance of $10^{-6}$.

Solution:

1. Initial interval: $[0, 1]$
2. Check: $f(0) = 1$ and $f(1) = e - 3 \approx -0.281718$, so $f(0)f(1) < 0$. The condition is satisfied.
3. Iterations:

Iteration	a	b	c	f(c)
1	0	1	0.5	0.148721
2	0.5	1	0.75	-0.090804
3	0.5	0.75	0.625	0.023398
...	...	...	...	...
19	0.619061	0.619062	0.6190615	-0.000001

4. The final root approximation is $x \approx 0.619061$.

Convergence Analysis

The bisection method has a linear convergence rate. The error in the approximation is reduced by half in each iteration. We can express this mathematically as:

Where $x_n$ is the nth approximation, $r$ is the true root, $a$ and $b$ are the initial interval endpoints, and $n$ is the number of iterations.

The number of iterations required to achieve a desired tolerance $\epsilon$ can be estimated using the formula:

This logarithmic relationship between the number of iterations and the desired tolerance explains why the bisection method can be relatively slow for high-precision requirements.

Extended Examples and Applications

Example 4: Finding the Square Root

Let's use the bisection method to find the square root of 5 by solving the equation $f(x) = x^2 - 5$ in the interval $[2, 3]$ to a tolerance of $10^{-6}$.

Solution:

1. Initial interval: $[2, 3]$
2. Check: $f(2) = -1$ and $f(3) = 4$, so $f(2)f(3) < 0$. The condition is satisfied.
3. Iterations:

Iteration	a	b	c	f(c)
1	2	3	2.5	1.25
2	2	2.5	2.25	0.0625
3	2	2.25	2.125	-0.484375
...	...	...	...	...
19	2.236067	2.236068	2.2360675	-0.000001

4. The final root approximation is $x \approx 2.236068$.

This example demonstrates how the bisection method can be used to compute irrational numbers like $\sqrt{5}$.

Example 5: Solving a Physics Problem

In projectile motion, the time $t$ at which a projectile reaches a certain height $h$ is given by the equation:

Where $v_0$ is the initial velocity and $g$ is the acceleration due to gravity. Let's find the time at which a ball thrown upward with an initial velocity of 20 m/s reaches a height of 15 m.

We need to solve the equation:

Let's use the interval $[0, 4]$ and a tolerance of $10^{-6}$.

Solution:

1. Initial interval: $[0, 4]$
2. Check: $f(0) = -15$ and $f(4) = -63.6$, so $f(0)f(4) > 0$. We need to adjust our interval.
3. Let's try $[0, 2]$: $f(0) = -15$ and $f(2) = 0.4$, so $f(0)f(2) < 0$. The condition is now satisfied.
4. Iterations:

Iteration	a	b	c	f(c)
1	0	2	1	0.1
2	0	1	0.5	-8.775
3	0.5	1	0.75	-3.759375
...	...	...	...	...
18	0.922957	0.922958	0.9229575	0.000001

5. The final root approximation is $t \approx 0.922958$ seconds.

This example illustrates how the bisection method can be applied to solve real-world physics problems.

Advantages and Limitations

Advantages:

• Guaranteed convergence: If the initial conditions are met, the method always converges to a root.
• Simplicity: The algorithm is straightforward to understand and implement.
• Robustness: It works well even for functions that are not differentiable or have discontinuous derivatives.
• No need for derivatives: Unlike methods like Newton-Raphson, the bisection method doesn't require knowledge of the function's derivative.

Limitations:

• Slow convergence: Compared to other methods, bisection can be relatively slow, especially for high-precision requirements.
• Requires a sign change: The method only works if the function changes sign over the given interval.
• May miss roots: If there are multiple roots in the interval, the method will only find one of them.
• Not suitable for complex roots: The bisection method can only find real roots.

Practical Implementation Tips

1. Choose a good initial interval: Try to select an interval where you're confident a root exists.
2. Handle edge cases: Implement checks for when $f(a) = 0$ or $f(b) = 0$ at the start.
3. Use a tolerance for zero: Instead of checking for exact zero, use a small tolerance, e.g., $|f(c)| < \epsilon$.
4. Limit iterations: Implement a maximum iteration count to prevent infinite loops.
5. Consider machine precision: Be aware of the limitations of floating-point arithmetic in your calculations.

Conclusion

The bisection method, while simple, is a powerful tool in numerical analysis. Its guaranteed convergence and robustness make it valuable in many applications, from solving equations in physics and engineering to finding optimal values in computer science and finance. While it may not be the fastest method available, its reliability and ease of implementation make it an excellent choice for many problems, especially when dealing with well-behaved continuous functions.

As you continue your studies in numerical methods, remember that each technique has its strengths and weaknesses. The bisection method serves as a solid foundation for understanding more advanced root-finding algorithms. Its principles of interval halving and sign checking are fundamental concepts that appear in various forms in more sophisticated numerical methods.