Bisection and Fixed-Point Iteration

Finding the roots of an equation $f(x) = 0$ is one of the oldest problems in mathematics. For linear and quadratic equations, explicit closed-form formulas give exact answers immediately. But symbolic inversion quickly runs into insurmountable barriers: the Abel-Ruffini theorem famously proves that general polynomial equations of degree five and higher possess no closed-form radical solutions, and transcendental equations such as $\cos(x) = x$ or $x^3 + 4x^2 = 10$ completely defy algebraic rearrangement.

When analytical formulas fail, computation takes over through iterative approximation. Instead of seeking an instantaneous closed form, an iterative method constructs a sequence of approximations $x_0, x_1, x_2, \dots$ designed to march inexorably toward the true root $x^*$.

This note explores two foundational paradigms for solving nonlinear equations on the real line:

1. Bisection: A geometric, bracketing strategy that traps the root inside an ever-halving interval. Backed by Bolzano’s Intermediate Value Theorem, it is slow (gaining exactly one bit of precision per step) but indestructible.
2. Fixed-Point Iteration: A dynamical systems transformation that converts a static root equation $f(x) = 0$ into an iterative feedback map $x_{n+1} = g(x_n)$. Governed by Banach’s Contraction Principle, it reveals how the local derivative slope $|g'(x^*)| < 1$ creates a gravitational basin of attraction.

Roots, fixed points, and sequences

Before analyzing convergence, we establish the formal link between finding a zero of a function and finding an invariant state of an iteration map.

DefinitionRoot

A number $x^*$ is a root or zero of $f$ when $f(x^*) = 0$.

DefinitionFixed point

For a function $g \colon D \to \mathbb{R}$, a point $x^* \in D$ is a fixed point when $g(x^*) = x^*$. Geometrically, fixed points are the intersections of the curve $y = g(x)$ with the diagonal line $y = x$.

DefinitionFixed-point iteration

Given an initial guess $x_0 \in D$, the iteration sequence generated by $g$ is

$$x_{n+1} = g(x_n), \qquad n = 0,1,2,\dots$$

whenever every required evaluation is defined.

DefinitionConvergence of a sequence

The notation $x_n \to x^*$ means that for every error tolerance $\varepsilon > 0$, there exists an integer $N$ such that $|x_n - x^*| < \varepsilon$ for all $n \ge N$. A shifted sequence inherits the identical limit: $x_n \to x^*$ implies $x_{n+1} \to x^*$.

Any root problem $f(x) = 0$ can be algebraically converted into infinitely many fixed-point formats $x = g(x)$. For example, for any non-zero parameter $\lambda$, we may define

$$g_\lambda(x) = x - \lambda f(x).$$

Then $f(x) = 0$ if and only if $g_\lambda(x) = x$. The roots of $f$ are precisely the fixed points of $g_\lambda$. However, algebraic equivalence is only the first step: whether the iterative dynamical system $x_{n+1} = g(x_n)$ converges or diverges depends entirely on the analytical properties of $g$.

ExampleAlgebraic conversion versus dynamical convergence

Consider finding the positive root of $f(x) = x^2 - 2 = 0$. We can rewrite this in multiple ways:

1. $x = x - \tfrac{1}{4}(x^2 - 2)$
2. $x = 2 / x$
3. $x = \tfrac{1}{2}(x + 2/x)$

All three share the identical fixed point $x^* = \sqrt{2} \approx 1.4142$. Yet their numerical dynamics could not be more different: the second formulation oscillates in an endless 2-cycle ($x_0 = 1 \to 2 \to 1 \to 2 \dots$), while the third formulation (Babylonian/Newton iteration) doubles its correct digits with every single step.

Converting $f(x)=0$ into $x=g(x)$ is therefore not a solution; it is a design choice that must be justified through contraction analysis.

Two existence tools

TheoremIntermediate Value Theorem

If $f$ is continuous on $[a,b]$ and $f(a)f(b) < 0$, then there is a point $x^* \in (a,b)$ such that $f(x^*) = 0$.

Proof

Assume $f(a)<0<f(b)$, replacing $f$ by $-f$ if necessary. Let $S=\{x\in[a,b]:f(x)<0\}$ and $c=\sup S$, which exists by completeness of the real numbers. Continuity at the endpoints places $c$ strictly between them. If $f(c)<0$, continuity gives a larger point still in $S$, contradicting the supremum. If $f(c)>0$, a whole neighborhood of $c$ contains no point of $S$, contradicting that points of $S$ approach its supremum from below. Thus $f(c)=0$.

A sign change guarantees existence, not uniqueness. Conversely, $f(a)f(b) > 0$ does not prove that no root exists: an even number of crossings may lie inside the interval.

TheoremMean Value Theorem

If $g$ is continuous on $[a,b]$ and differentiable on $(a,b)$, then for any distinct $x,y \in [a,b]$ there is a point $c$ between them such that

$$g(x) - g(y) = g'(c)\,(x-y).$$

Proof

For $x<y$, subtract the secant line:

$$h(t)=g(t)-g(x)-\frac{g(y)-g(x)}{y-x}(t-x).$$

Then $h(x)=h(y)=0$. Rolle’s theorem and its proof give $h'(c)=0$ at an interior point. Substitution yields the formula; exchanging $x,y$ covers the other order.

IVT creates a root or a fixed point. MVT turns a derivative bound into a bound on changes in the function.

Lipschitz and contraction conditions

DefinitionLipschitz condition

Let $g \colon [a,b] \to \mathbb{R}$. The function $g$ is Lipschitz on $[a,b]$ if there exists a finite constant $L \in [0,\infty)$ such that, for every $x,y \in [a,b]$,

$$|g(x) - g(y)| \le L |x-y|.$$

Any such $L$ is a Lipschitz constant. There is no requirement that $L < 1$.

DefinitionContraction condition

A Lipschitz function $g \colon [a,b] \to \mathbb{R}$ is a contraction on $[a,b]$ if the Lipschitz inequality holds for some constant in the strictly smaller range $L \in [0,1)$. If, in addition, $g([a,b]) \subseteq [a,b]$, then $g$ is a contraction self-map of $[a,b]$: the contraction brings points closer together, while the self-map keeps every iterate inside the interval.

This note uses $L$ for both a Lipschitz constant and, when $L < 1$, a contraction factor. If $L = 0$, then $g$ is constant. A finite global bound $|g'(x)| \le L < \infty$ proves that $g$ is Lipschitz. It proves that $g$ is a contraction only when the bound can be chosen with $L < 1$. Finding one point where $|g'(x)| > 1$ rules out the derivative-based contraction test, but does not rule out Lipschitz continuity.

PropositionDerivative bound gives a Lipschitz estimate

If $g$ is continuous on $[a,b]$, differentiable on $(a,b)$, and $|g'(s)| \le L$ for some finite $L \ge 0$ and all $s \in (a,b)$, then $|g(x)-g(y)| \le L |x-y|$ for every $x,y \in [a,b]$. Hence $g$ is Lipschitz. If the same bound can be obtained with $L < 1$, then $g$ is a contraction.

Proof

If $x = y$, the claim is immediate. If $x \neq y$, the Mean Value Theorem gives a point $c$ between $x$ and $y$ with $g(x)-g(y) = g'(c)(x-y)$. Taking absolute values and using the derivative bound gives $|g(x)-g(y)| = |g'(c)|\,|x-y| \le L |x-y|$.

The global constant is a bound over the whole interval. It is not generally the single number $|g'(x^*)|$.

The bisection method

Suppose $f$ is continuous on $[a_0,b_0]$ and $f(a_0)f(b_0) < 0$. By the Intermediate Value Theorem, at least one root lies inside the initial bracket. For $k \ge 1$, let $x_k = (a_{k-1}+b_{k-1})/2$ be the midpoint. If $f(x_k) = 0$, stop. Otherwise retain the half interval whose endpoint values still have opposite signs.

PropositionBracket invariant

Until an exact root is returned, every bisection update produces an interval $I_k = [a_k,b_k]$ such that

$$f(a_k)f(b_k) < 0, \qquad b_k - a_k = (b_0-a_0)/2^k,$$

and $I_k$ contains at least one root. The intervals are nested: $I_k \subseteq I_{k-1}$.

Proof

The claim holds for $I_0$ by the initial assumptions and the Intermediate Value Theorem. Assume it holds for $I_{k-1}$. Its midpoint divides the interval into two closed halves. If the midpoint is not a root, exactly one of $f(a_{k-1})f(x_k)$ and $f(x_k)f(b_{k-1})$ is negative. Retaining that half preserves a sign-changing bracket and hence contains at least one root. It is a subset of the previous bracket and has half its width, so induction gives nestedness and the displayed width formula.

Intuitively, bisection searches for the interval where root existence is guaranteed by IVT, and stops when that interval is small enough. It always converges when the hypotheses hold, but the convergence is slow.

Algorithm 1 Bisection with cached endpoint values

Require: continuous $f$, endpoints $a < b$, tolerance $\varepsilon > 0$, maximum midpoint count $N_{\max}$

1:evaluate and cache $f_a = f(a)$ and $f_b = f(b)$

2:if $f_a = 0$ then

3:return $a$

4:end if

5:if $f_b = 0$ then

6:return $b$

7:end if

8:if $f_a f_b > 0$ then

9:reject the interval: it is not a certified bracket

10:end if

11:for $k \gets 1$ to $N_{\max}$ do

12:$x \gets (a+b)/2$, evaluate $f_x = f(x)$ once

13:if $f_x = 0$ then

14:return $x$

15:end if

16:if $f_a f_x < 0$ then

17:$b \gets x$, $f_b \gets f_x$

18:else

19:$a \gets x$, $f_a \gets f_x$

20:end if

21:if $(b-a)/2 < \varepsilon$ then

22:return midpoint of the updated bracket

23:end if

24:end for

25:report that the maximum iteration count was reached

After the two initial endpoint evaluations, each loop needs only one new function evaluation.

TheoremBisection convergence and a priori error

Let $f$ be continuous on $[a_0,b_0]$ with $f(a_0)f(b_0) < 0$. The nested bisection brackets determine a root $x^*$. If $x_k$ is the $k$th midpoint, then

$$|x^* - x_k| \le \Bigl(\frac{1}{2}\Bigr)^k (b_0 - a_0).$$

Consequently $x_k \to x^*$.

Proof

By the bracket invariant, the intervals $I_k$ are nested, closed, nonempty, and have lengths $(b_0-a_0)/2^k \to 0$. The nested interval principle gives a unique point $x^*$ in every $I_k$. For each $k$, IVT supplies a root $r_k \in I_k$. Since $r_k$ and $x^*$ both lie in $I_k$, $|r_k - x^*| \le b_k - a_k \to 0$. Thus $r_k \to x^*$, and continuity gives $f(x^*) = \lim f(r_k) = 0$.

At the start of iteration $k$, both this root $x^*$ and the midpoint $x_k$ lie in $I_{k-1}$. The farthest any point of this interval can be from its midpoint is half the interval width, so

$$|x^* - x_k| \le \frac{b_{k-1}-a_{k-1}}{2} = \frac{b_0-a_0}{2^k}.$$

The right-hand side tends to zero, so $x_k \to x^*$.

This is an a priori estimate: it uses only the initial width and the iteration number. It does not require knowing the root or differentiating $f$.

PropositionSufficient midpoint count for strict tolerance

Given $\varepsilon > 0$, the integer

$$K = \Bigl\lfloor \log\bigl((b_0-a_0)/\varepsilon\bigr) / \log 2 \Bigr\rfloor + 1$$

is sufficient to ensure $|x^* - x_K| < \varepsilon$.

Proof

The a priori estimate is strictly below $\varepsilon$ whenever $(b_0-a_0)/2^K < \varepsilon$. Since all quantities are positive, this is equivalent to $K > \log((b_0-a_0)/\varepsilon)/\log 2$. For any real $r$, the smallest integer known to satisfy $K > r$ is $\lfloor r \rfloor + 1$.

If the target is the non-strict bound $|x^*-x_K| \le \varepsilon$, then $K = \lceil \log_2((b_0-a_0)/\varepsilon) \rceil$ is sufficient. The difference appears only when the logarithmic ratio is already an integer.

Let $N$ be the number of midpoint iterations. From the stopping result, $N = O(\log((b_0-a_0)/\varepsilon))$. If one evaluation of $f$ costs $T_f$, the algorithm takes $O(N T_f)$ time. Rolling storage is $O(1)$. “Linear convergence” describes how the error contracts. Big-O running time counts operations. They answer different questions even when both contain a logarithm.

As a concrete example, consider applying bisection to $f(x) = x^3 + 4x^2 - 10$ on $[1,2]$. The initial bracket is valid because $f(1) = -5 < 0$ and $f(2) = 14 > 0$. For a target error tolerance $\varepsilon = 10^{-4}$, the strict theoretical midpoint count is $K = 14$. A naive residual check might stop earlier ($|f(x_9)| < 10^{-4}$), but the residual measures vertical distance to zero, whereas the bisection error certificate guarantees horizontal proximity to the true root using bracket width.

This interactive figure needs JavaScript.

Fixed-point iteration

To turn $f(x) = 0$ into a fixed-point problem, choose a nonzero constant $\lambda$ and define $g_\lambda(x) = x - \lambda f(x)$. Then the roots of $f$ are exactly the fixed points of $g_\lambda$. The associated algorithm is $x_{n+1} = x_n - \lambda f(x_n)$. Different choices of $\lambda$ produce different maps. Here $g_\lambda'(x) = 1 - \lambda f'(x)$, so $\lambda$ changes local attraction or repulsion.

PropositionThe limit of a convergent iteration is a fixed point

Suppose $x_{n+1} = g(x_n)$, $x_n \to x^*$, and $g$ is continuous at $x^*$. Then $g(x^*) = x^*$.

Proof

Since $x_n \to x^*$, we have $x_{n+1} \to x^*$. By the iteration rule, $x_{n+1} = g(x_n)$, so $\lim x_{n+1} = \lim g(x_n)$. Continuity of $g$ at $x^*$ gives $g(x_n) \to g(x^*)$. Therefore $g(x^*) = x^*$.

This is necessary, not sufficient. A map may have a fixed point while an iteration diverges from it. Passing a limit through $g$ uses continuity of $g$, not linearity of $g$. For example, $g(u) = u^2$ is nonlinear but continuous.

TheoremFixed-point theorem on a closed interval

Let $g$ be continuous on $[a,b]$ and satisfy $g([a,b]) \subseteq [a,b]$. Then $g$ has at least one fixed point in $[a,b]$.

Further suppose that $g'$ exists on $(a,b)$ and that there is a constant $0 \le L < 1$ with $|g'(x)| \le L$ for all $x \in (a,b)$. Then the fixed point is unique, and for every $x_0 \in [a,b]$ the iteration $x_{n+1} = g(x_n)$ remains in $[a,b]$ and converges to that fixed point.

The notation $g([a,b])$ means the set of outputs obtained by applying $g$ to every input in $[a,b]$. The derivative bound is a convenient sufficient test for a contraction. It does not replace the self-map condition. A common omission in introductory texts is the self-map condition $g([a,b]) \subseteq [a,b]$. Without it, neither the existence of a fixed point within the interval nor the invariance of subsequent iterates is guaranteed.

Proof

Existence. A point $x^*$ is a fixed point of $g$ exactly when $g(x^*)-x^* = 0$. Let $q(x) = g(x)-x$. It is continuous on $[a,b]$. Because $g$ maps the interval into itself, $a \le g(a) \le b$ and $a \le g(b) \le b$, which implies $q(a) \ge 0$ and $q(b) \le 0$. If either value is zero, that endpoint is a fixed point. Otherwise $q(a) > 0 > q(b)$, and IVT gives $x^* \in (a,b)$ with $q(x^*) = 0$.

Uniqueness. Suppose $p$ and $q$ are fixed points. Then $p-q = g(p)-g(q)$. The derivative hypothesis and the Mean Value Theorem give $|p-q| = |g(p)-g(q)| \le L |p-q|$. Since $L < 1$, this forces $p = q$.

Invariance and convergence. The self-map keeps every iterate in $[a,b]$. Let $x^*$ be the unique fixed point. Then $|x^*-x_{n+1}| = |g(x^*)-g(x_n)| \le L |x^*-x_n|$, so by induction $|x^*-x_n| \le L^n |x^*-x_0|$. Since $L < 1$, the right-hand side tends to zero.

A local derivative test explains behaviour near an individual fixed point: if $|g'(x^*)| < 1$, the fixed point is locally attractive under suitable continuity assumptions on $g'$; if $|g'(x^*)| > 1$, it is locally repelling. A local test does not prove convergence from every point in a large interval.

Algorithm 2 Fixed-point iteration with a posteriori test

Require: map $g$, initial value $x_0$, contraction bound $0 \le L < 1$, target error $\varepsilon > 0$, maximum count $N_{\max}$

1:$x \gets x_0$

2:for $n \gets 0$ to $N_{\max}-1$ do

3:$y \gets g(x)$

4:if $L = 0$ then

5:return $y$

6:end if

7:if $L/(1-L)\, |y-x| \le \varepsilon$ then

8:return $y$

9:end if

10:$x \gets y$

11:end for

12:report that the maximum iteration count was reached

The stopping test follows from the computable estimate

$$|x^* - x_{n+1}| \le \frac{L}{1-L}\, |x_{n+1}-x_n|.$$

Proof

By the contraction estimate, $|x_{j+1}-x_j| \le L |x_j-x_{j-1}|$ for every $j \ge n+1$, hence $|x_{j+1}-x_j| \le L^{j-n} |x_{n+1}-x_n|$. For $m > n+1$, the triangle inequality and a geometric series give

$$|x_m - x_{n+1}| \le |x_{n+1}-x_n| \sum_{j=n+1}^{m-1} L^{j-n}.$$

Letting $m \to \infty$ yields $|x^*-x_{n+1}| \le \frac{L}{1-L}|x_{n+1}-x_n|$.

The a priori estimate $|x^*-x_n| \le L^n |x^*-x_0|$ implies that $N$ grows logarithmically with $1/\varepsilon$, but the constant deteriorates as $L$ approaches one. Rolling storage is $O(1)$.

This interactive figure needs JavaScript.

Worked examples

ExerciseCosine iteration

Consider $\cos x - x = 0$ on $I = [0,1]$. Write the equation as $x = g(x)$ with $g(x) = \cos x$. Starting from $x_0 = 1/2$, consider $x_{n+1} = g(x_n)$. Prove that the equation has exactly one root in $[0,1]$, that $g([0,1]) \subseteq [0,1]$, and that the iteration converges.

Proof

Let $F(x) = \cos x - x$. It is continuous, $F(0) = 1 > 0$, and $F(1) = \cos 1 - 1 < 0$, so IVT gives a root. Moreover $F'(x) = -\sin x - 1 < 0$ on $[0,1]$, so $F$ is strictly decreasing and the root is unique.

For $x \in [0,1]$, monotonicity of cosine gives $\cos 1 \le \cos x \le 1$. Since $0 < \cos 1 < 1$, the map sends $[0,1]$ into itself.

The function $g(x) = \cos x$ is continuous on $[0,1]$ and differentiable on $(0,1)$. Moreover $|g'(x)| = \sin x \le \sin 1 < 1$ for every $x \in (0,1)$. All hypotheses of the fixed-point theorem hold with $L = \sin 1$. Therefore $g$ has a unique fixed point in $[0,1]$, and the iteration converges for every $x_0 \in [0,1]$, including $x_0 = 1/2$.

ExerciseTesting the hypotheses

Let $g(x) = x - \frac{1}{\pi}\sin(\pi x)$ for $x \in [0,1]$. Show that $g$ maps $[0,1]$ into itself, deduce that it has at least one fixed point, show that the derivative condition for uniqueness fails, and solve $g(x) = x$ on $[0,1]$.

Proof

Since $g'(x) = 1 - \cos(\pi x) \ge 0$ on $[0,1]$, the function $g$ is increasing. Its endpoint values are $g(0) = 0$ and $g(1) = 1$. Hence $0 \le g(x) \le 1$ for every $x \in [0,1]$. Continuity and the self-map give at least one fixed point.

The uniqueness derivative condition fails: $|g'(2/3)| = |1 - \cos(2\pi/3)| = 3/2 > 1$, so there is no $L < 1$ with $|g'(x)| \le L$ throughout $(0,1)$. The map is still Lipschitz, with admissible constant $L = 2$, because $0 \le g'(x) \le 2$. That Lipschitz estimate alone does not give uniqueness.

The fixed-point equation is $\sin(\pi x) = 0$, which on $[0,1]$ holds exactly when $x = 0$ or $x = 1$. So $g$ has two fixed points.

Continuity together with an invariant interval guarantees existence. A global contraction bound further guarantees uniqueness and convergence from every initial value in that interval. If the self-map condition fails, the theorem yields no conclusion. If only the contraction bound fails, a fixed point may still exist, but uniqueness and global convergence must be investigated by other means.

The next note treats Newton’s method as a specially chosen fixed-point map. This page belongs to the Computational Mathematics reading path.