Bisection and Fixed-Point Iteration

Root-finding algorithms solve equations of the form $f(x) = 0$ where $f: \mathbb{R} \to \mathbb{R}$ is continuous. The bisection method and fixed-point iteration provide fundamental approaches with different convergence guarantees.

DefinitionBisection Method

Given a continuous function $f: [a,b] \to \mathbb{R}$ with $f(a)f(b) < 0$ , the bisection method iteratively halves the interval:

Compute $c = (a+b)/2$
If $f(c) = 0$ , stop
If $f(a)f(c) < 0$ , set $b := c$ ; otherwise set $a := c$
Repeat until $|b-a| < \epsilon$

The intermediate value theorem guarantees a root $r \in [a,b]$ . After $n$ iterations, $|r - x_n| \leq (b-a)/2^{n+1}$ , giving linear convergence with rate $1/2$ .

The bisection method is robust and always converges when $f(a)$ and $f(b)$ have opposite signs, but converges slowly. It requires only function evaluations, not derivatives, making it suitable for non-smooth functions.

DefinitionFixed-Point Iteration

A fixed point of $g: \mathbb{R} \to \mathbb{R}$ is a value $p$ satisfying $g(p) = p$ . The fixed-point iteration is: $x_{n+1} = g(x_n), \quad n = 0,1,2,\ldots$

To solve $f(x) = 0$ , rewrite as $x = g(x)$ where $g(x) = x + \alpha f(x)$ for some $\alpha \neq 0$ .

ExampleSquare Root Computation

To compute $\sqrt{a}$ , solve $x^2 - a = 0$ . Rewriting as $x = (x + a/x)/2$ gives the iteration: $x_{n+1} = \frac{1}{2}\left(x_n + \frac{a}{x_n}\right)$

This is Newton's method for $f(x) = x^2 - a$ . For $a = 2$ with $x_0 = 1$ :

$x_1 = (1 + 2)/2 = 1.5$
$x_2 = (1.5 + 2/1.5)/2 = 1.41\overline{6}$
$x_3 = 1.414215686...$

The error decreases quadratically: $|x_3 - \sqrt{2}| \approx 2 \times 10^{-9}$ .

Remark

Convergence Theorem: If $g \in C[a,b]$ with $g([a,b]) \subseteq [a,b]$ and $|g'(x)| \leq k < 1$ for all $x \in (a,b)$ , then:

$g$ has a unique fixed point $p \in [a,b]$
The iteration $x_{n+1} = g(x_n)$ converges to $p$ for any $x_0 \in [a,b]$
$|p - x_n| \leq k^n|p - x_0|/(1-k)$

The constant $k$ is the contraction factor. Convergence is linear with rate $k$ .

The choice of $g$ dramatically affects convergence. For $f(x) = x^2 - a$ , setting $g(x) = a/x$ yields divergent oscillation, while $g(x) = (x + a/x)/2$ converges quadratically. This motivates Newton's method, which automatically constructs an optimal $g$ using derivative information.

Practical implementations incorporate stopping criteria based on both absolute error $|x_{n+1} - x_n|$ and relative error $|x_{n+1} - x_n|/|x_{n+1}|$ , along with maximum iteration limits. The bisection method provides guaranteed but slow convergence, while fixed-point iterations can converge rapidly if $g$ is well-chosen but may diverge otherwise.