Let \( f \) be a continuous function on the interval \([a, b]\), such that \( f(a) \cdot f(b) < 0 \). Then there exists at least one root \( r \in [a, b] \) such that \( f(r) = 0 \).

If, in addition, \( f \) is strictly monotonic on \([a, b]\), then the root is unique.

The bisection method consists of dividing the interval \([a, b]\) into two equal parts:

\[ c = \frac{a + b}{2} \]

Then, we evaluate \( f(c) \):

• If \( f(c) = 0 \), then \( c \) is the root.
• If \( f(a) \cdot f(c) < 0 \), then the root lies in \([a, c]\).
• Otherwise, the root lies in \([c, b]\).

This process is repeated until the interval length is less than a prescribed tolerance \( \varepsilon > 0 \), or until \( |f(c)| < \varepsilon \).

Convergence

Let \([a_n, b_n]\) be the successive intervals. Each iteration halves the interval length:

\[ b_{n+1} - a_{n+1} = \frac{1}{2}(b_n - a_n) \quad \Rightarrow \quad b_n - a_n = \frac{b_0 - a_0}{2^n} \]

The sequences \( (a_n) \) and \( (b_n) \) are monotonic and converge to the same limit:

\[ \lim_{n \to \infty} a_n = \lim_{n \to \infty} b_n = r \quad \Rightarrow \quad f(r) = 0 \]

Error Estimation

Let \( c_n = \frac{a_n + b_n}{2} \). The error at iteration \( n \) is bounded by:

\[ |r - c_n| \leq \frac{1}{2}(b_n - a_n) = \frac{b_0 - a_0}{2^{n+1}} \]

Theorem

Let \([a_n, b_n]\) be the interval at iteration \( n \). Then:

• \( \lim_{n \to \infty} a_n = \lim_{n \to \infty} b_n = r \)
• If \( c_n = \frac{a_n + b_n}{2} \), then:

\[ |r - c_n| \leq \frac{b_0 - a_0}{2^{n+1}} \]

To ensure an error \( |r - c_n| < \varepsilon \), it is sufficient to choose an integer \( k_{\min} \) such that:

\[ k_{\min} > \log_2 \left( \frac{b_0 - a_0}{\varepsilon} \right) \]

Example

Solve the equation:

\[ f(x) = x^3 + x^2 - 3x - 3 \]

on the interval \([1, 2]\). Verify that \( f(1) = -4, f(2) = 3 \Rightarrow f(1) \cdot f(2) < 0 \).

To reach an absolute error less than \( \varepsilon = 5 \times 10^{-2} \), we compute:

\[ k_{\min} > \log_2 \left( \frac{2 - 1}{0.05} \right) \approx 4.32 \quad \Rightarrow k_{\min} = 5 \]