The Bisection Method Revision Notes for VCE SSCE Mathematical Methods

The Bisection Method

What is the bisection method?

The bisection method helps us find approximate solutions to equations of the form $f(x) = 0$ , where $f$ is a polynomial function. This numerical technique is particularly useful for higher degree polynomials where finding exact solutions algebraically becomes very difficult or impossible.

For polynomials of degree 5 and higher, there is no general formula to find all solutions. Even when exact solutions exist, they can be extremely complex. The bisection method provides a practical way to find numerical approximations to any desired level of accuracy.

infoNote

Numerical methods like the bisection method are essential tools in mathematics and engineering because many real-world equations cannot be solved using algebraic formulas alone. They allow us to find solutions to virtually any equation, regardless of complexity.

Why do we need the bisection method?

Consider the cubic function $f(x) = x^3 + 3x + 6$ . The equation $f(x) = 0$ has only one real solution. The exact solution is:

x = \frac{-1}{(-3 + \sqrt{10})^{1/3}} + (-3 + \sqrt{10})^{1/3}

This exact form is extremely complicated to calculate by hand. Instead, we can use the bisection method to find a numerical approximation that is accurate enough for practical purposes.

chatImportant

While exact solutions may exist mathematically, they are often too complex to be practical. The bisection method provides a straightforward way to find solutions that are accurate enough for real-world applications, without the need for complicated algebraic manipulations.

The general bisection algorithm

The bisection method works by repeatedly halving an interval that contains the solution. Here's how it works:

Starting point: We need an equation $f(x) = 0$ that has one solution $\alpha$ in the interval $[a_1, b_1]$ .

Key observation: The sign of $f(a_1)$ must be opposite to the sign of $f(b_1)$ . This is because $f(\alpha) = 0$ , so the function must change from positive to negative (or vice versa) as we move from $a_1$ to $b_1$ .

infoNote

Understanding the Sign Change

When a continuous function crosses the x-axis (where $f(x) = 0$ ), it must change from positive to negative or from negative to positive. This sign change is the key property that makes the bisection method work. If $f(a_1)$ and $f(b_1)$ have opposite signs, we are guaranteed that a root exists between them.

The algorithm steps:

Calculate the midpoint: $m_1 = \frac{a_1 + b_1}{2}$
Evaluate the function at the midpoint: find $f(m_1)$
Determine which half contains the solution:
- If $f(a_1) \times f(m_1) < 0$ , choose the interval $[a_1, m_1]$
- Otherwise, choose the interval $[m_1, b_1]$
Repeat the process with the new interval until the required accuracy is reached

This process works because at each step, we're identifying which half of the interval contains the sign change, and therefore contains the root.

Using a spreadsheet for the bisection method

Let's work through a complete example using the function $f(x) = x^3 + 3x + 6$ to solve the equation $x^3 + 3x + 6 = 0$ .

lightbulbExample

Worked Example: Finding a Root Using the Bisection Method

Initial observation:

We note that $f(-2) = -8 < 0$ and $f(-1) = 2 > 0$

Since the function values have opposite signs, we know there is a solution in the interval $[-2, -1]$ .

Step 1:

Starting with the interval $[-2, -1]$ :

m_1 = \frac{-2 + (-1)}{2} = -1.5

f(-1.5) = -1.875 < 0

Since $f(-1.5) < 0$ and $f(-1) > 0$ , the solution lies between $-1.5$ and $-1$ .

Step 2:

New interval: $[-1.5, -1]$

m_2 = \frac{-1.5 + (-1)}{2} = -1.25

f(-1.25) = 0.296875 > 0

The solution lies between $-1.5$ and $-1.25$ .

Step 3:

New interval: $[-1.5, -1.25]$

m_3 = \frac{-1.5 + (-1.25)}{2} = -1.375

f(-1.375) = -0.724609 < 0

The solution lies between $-1.375$ and $-1.25$ .

Step 4:

New interval: $[-1.375, -1.25]$

At this point, we know the solution is in the interval $[-1.375, -1.25]$ .

Continuing with the spreadsheet:

From the table, we can see that after 11 iterations, the midpoint value is approximately $-1.28759766$ .

Conclusion: The solution is -1.29 correct to two decimal places.

Understanding error reduction

An important property of the bisection method is that the error decreases predictably:

If the starting interval has length $1$ unit, the error is at most $\frac{1}{2}$ after one step
After $n$ steps, the error is at most $\left(\frac{1}{2}\right)^{n-1}$

This means each iteration halves the maximum possible error, allowing us to achieve any desired accuracy by performing enough iterations.

infoNote

The predictable error reduction is one of the bisection method's greatest strengths. Unlike some other numerical methods, we can always calculate exactly how many iterations we need to achieve a desired accuracy level.

Using pseudocode for the bisection method

Computers cannot understand natural language instructions directly. Instead, we need to write instructions in a programming language. Pseudocode is an informal way of writing algorithms that is closer to natural language but structured enough to be translated into actual programming code.

lightbulbExample

Worked Example: Writing a Bisection Algorithm in Pseudocode

Problem: The equation $x^3 + 3x + 6 = 0$ has one real solution in the interval $[-2, -1]$ . Write an algorithm using pseudocode to find this solution correct to within $0.01$ .

Pseudocode solution:

define f(x):
    return x³ + 3x + 6

a ← -2
b ← -1
m ← -1.5

while b - a > 2 × 0.01
    if f(a) × f(m) < 0 then
        b ← m
    else
        a ← m
    end if
    m ← (a + b)/2
    print a, m, b, f(a), f(m), f(b)
end while

print m

Explanation of the pseudocode:

We first define the function $f(x) = x^3 + 3x + 6$
We assign initial values: left endpoint $a = -2$ , right endpoint $b = -1$ , and midpoint $m = -1.5$
We use a while loop because we don't know in advance how many iterations will be needed. The loop continues until $b - a \leq 2 \times 0.01$ (meaning the interval is small enough)
Inside the loop:
- We use an if-then block to update either the left endpoint $a$ or the right endpoint $b$ based on which half contains the solution
- We recalculate the midpoint $m$
- We print the current values at the end of each iteration
After the loop completes, we print the final value of $m$ , which is our approximate solution

Execution results

The following table shows what happens when we run this algorithm:

Analysis:

The initial row shows our starting values
Each subsequent row shows the values after each pass through the loop
After the 6th pass, we have $b - a = 0.015625 \leq 0.02$ , so we exit the loop
The final value of $m$ is -1.289063

To achieve greater accuracy, we would change the condition in the while loop to require a smaller interval width.

chatImportant

Critical Consideration for Programming

The stopping condition $b - a > 2 \times 0.01$ ensures that our interval is small enough to guarantee the solution is accurate to within $0.01$ . When implementing the bisection method, always carefully choose your stopping condition based on the required accuracy.

bookmarkSummary

Key Points to Remember:

The bisection method finds approximate solutions to equations of the form $f(x) = 0$ by repeatedly halving an interval
You need a starting interval $[a, b]$ where $f(a)$ and $f(b)$ have opposite signs
At each step, calculate the midpoint $m = \frac{a + b}{2}$ and check which half-interval contains the sign change
The error approximately halves with each iteration, making it predictable and reliable
The method can be implemented using spreadsheets or programmed using pseudocode and programming languages
The bisection method always converges to a solution if one exists in the initial interval

The Bisection Method (VCE SSCE Mathematical Methods): Revision Notes