Burden & Faires, 9th Ed. - §2.2
Chapter 3: Fixed-Point Iteration
Rewriting $f(x)=0$ as $x=g(x)$ · The Fixed-Point Theorem · Cobweb diagrams · Why the rearrangement you choose matters enormously
Bisection only ever needed a sign change. Fixed-Point Iteration needs something stronger - and in exchange, when it works, it can converge much faster. The idea is deceptively simple: rewrite $f(x)=0$ as an equivalent equation $x=g(x)$, then just keep applying $g$ starting from a guess: $p_{n} = g(p_{n-1})$. The catch, and the entire content of this chapter, is that there are infinitely many ways to rearrange the same equation into this form, and most of them will not converge at all. Telling the good rearrangements from the bad ones - before wasting a single iteration - is the actual skill.
Section 3.1
Fixed Points
From Roots to Fixed Points
Definition - Fixed Point
A number $p$ is a fixed point of $g$ if $g(p)=p$. Any root-finding problem $f(x)=0$ can be rewritten as a fixed-point problem - e.g. $g(x)=x-f(x)$ always works algebraically, but as §3.3 shows, "works algebraically" and "converges numerically" are entirely different questions.
Existence of a Fixed Point
Theorem 3.1 - Existence
If $g\in C[a,b]$ and $g(x)\in[a,b]$ for every $x\in[a,b]$ (i.e. $g$ maps the interval into itself), then $g$ has at least one fixed point in $[a,b]$.
Why. Define $h(x)=g(x)-x$. Then $h(a)=g(a)-a\ge0$ (since $g(a)\ge a$) and $h(b)=g(b)-b\le0$ (since $g(b)\le b$). By the Intermediate Value Theorem (Chapter 1), $h(c)=0$ for some $c\in[a,b]$ - meaning $g(c)=c$.
Section 3.2
The Fixed-Point Theorem
Convergence and Uniqueness
Theorem 3.2 - Fixed-Point Theorem
Suppose, in addition to the hypotheses of Theorem 3.1, that $g'$ exists on $(a,b)$ and a constant $k<1$ exists with
$$|g'(x)| \le k \quad \text{for all } x\in(a,b)$$
Then: (i) $g$ has a unique fixed point $p$ in $[a,b]$; and (ii) for any starting value $p_0\in[a,b]$, the sequence $p_n=g(p_{n-1})$ converges to $p$.
p₀ = 1.500000
Cobweb diagram for $x^3+4x^2-10=0$ on $[1,2]$ (true root $p\approx1.365230$). The staircase alternates between the curve $y=g(x)$ and the line $y=x$. Try all three rearrangements from the same starting point $p_0=1.5$ - one spirals in tightly, one crawls in slowly, one flies off the screen within two steps.
Error Bounds
Corollary - A Priori and A Posteriori Bounds
Under Theorem 3.2's hypotheses, for every $n\ge1$:
$$|p_n - p| \le k^n \max(p_0-a,\, b-p_0) \qquad\text{(a priori - from } p_0 \text{ alone)}$$
$$|p_n - p| \le \frac{k^n}{1-k}\,|p_1-p_0| \qquad\text{(a priori - from the first step)}$$
$$|p_n - p| \le \frac{k}{1-k}\,|p_n-p_{n-1}| \qquad\text{(a posteriori - after running the iteration)}$$
Fixed-point iteration is linearly convergent with asymptotic constant $\lambda = |g'(p)|$ (Chapter 1, Definition) - the smaller $|g'(p)|$ is, the faster it converges, and $|g'(p)|\ge1$ means it will not converge at all near $p$.
📘 Example 3.1 - Four Rearrangements of the Same Equation
$f(x)=x^3+4x^2-10=0$ has a unique root in $[1,2]$, $p\approx1.365230013$. Compare these rearrangements, all starting from $p_0=1.5$:
$$g_1(x)=x-x^3-4x^2+10, \quad g_2(x)=\sqrt{\tfrac{10}{x}-4x}, \quad g_3(x)=\tfrac12\sqrt{10-x^3}, \quad g_4(x)=\sqrt{\tfrac{10}{4+x}}$$
Solution
Differentiate each and evaluate $|g_i'(p)|$ at the root:
Sample iterates:
Only $g_3$ and $g_4$ have $|g_i'(p)|<1$, so only they are guaranteed to converge - and among them, $g_4$'s smaller derivative at the root makes it converge roughly $4\times$ faster per iteration. $g_1$'s derivative magnitude of $15.5$ means each iteration multiplies the error by about $15$, so it blows up almost immediately despite being the most "obvious" algebraic rearrangement of $f(x)=0$.
| $g_i$ | $g_i'(x)$ | $|g_i'(p)|$ | Behavior |
|---|---|---|---|
| $g_1$ | $1-3x^2-8x$ | $15.51$ | diverges violently |
| $g_2$ | $\tfrac12(10/x-4x)^{-1/2}(-10/x^2-4)$ | $3.43$ | diverges |
| $g_3$ | $-3x^2/(4\sqrt{10-x^3})$ | $0.51$ | converges, slowly |
| $g_4$ | $-5/[(4+x)^2\sqrt{10/(4+x)}]$ | $0.13$ | converges, quickly |
| $n$ | $g_3$ (slow) | $g_4$ (fast) |
|---|---|---|
| 0 | 1.500000 | 1.500000 |
| 1 | 1.286953 | 1.348399 |
| 2 | 1.402540 | 1.367376 |
| 3 | 1.345350 | 1.364957 |
| 4 | 1.375080 | 1.365265 |
| 8 | $\approx$1.365(±0.002) | 1.365230 |
Section 3.3
Choosing a Good $g(x)$
There Is No Free Formula for Finding $g$
Theorem 3.2 tells you how to verify a candidate $g$ converges - bound $|g'(x)|$ on the interval - but it does not tell you how to construct a good one. In practice: differentiate your candidate, evaluate the bound near the expected root, and if $|g'|$ is close to or above $1$, try rewriting the equation differently (isolate a different power of $x$, divide through by a different term, or - as Chapter 4 shows - use $g(x)=x-f(x)/f'(x)$, which is always a good choice near a simple root because $g'(p)=0$ there).
📘 Example 3.2 - Verifying the Hypotheses on an Interval
Show that $g_4(x)=\sqrt{10/(4+x)}$ satisfies the Fixed-Point Theorem's hypotheses on $[1,2]$.
Solution
Self-map: $g_4$ is decreasing for $x>0$ (larger denominator $\Rightarrow$ smaller value), so on $[1,2]$: $g_4(2)=\sqrt{10/6}=1.291$ and $g_4(1)=\sqrt{10/5}=1.414$. Both lie in $[1,2]$, and since $g_4$ is monotonic, every value in between does too - so $g_4([1,2])\subset[1,2]$. ✓
Derivative bound: $g_4'(x) = -\dfrac{5}{(4+x)^2\sqrt{10/(4+x)}}$. This is negative and increasing in magnitude as $x$ decreases toward $1$ (smaller $4+x$). Worst case at $x=1$: $|g_4'(1)| = 5/(25\cdot1.414) = 5/35.36=0.1414$. So $k=0.1414<1$ works uniformly on all of $[1,2]$. Both hypotheses hold with $k\approx0.1414$ - so Theorem 3.2 guarantees convergence to the unique fixed point in $[1,2]$ from any starting guess in that interval, not just $p_0=1.5$.
Derivative bound: $g_4'(x) = -\dfrac{5}{(4+x)^2\sqrt{10/(4+x)}}$. This is negative and increasing in magnitude as $x$ decreases toward $1$ (smaller $4+x$). Worst case at $x=1$: $|g_4'(1)| = 5/(25\cdot1.414) = 5/35.36=0.1414$. So $k=0.1414<1$ works uniformly on all of $[1,2]$. Both hypotheses hold with $k\approx0.1414$ - so Theorem 3.2 guarantees convergence to the unique fixed point in $[1,2]$ from any starting guess in that interval, not just $p_0=1.5$.
Practice
Practice Problem
Try this problem yourself before expanding the solution below.
✏️ Practice Problem 3.1 - Choosing a Convergent Fixed-Point Form
The equation $x^3-x-1=0$ has a root near $p\approx1.324718$. Two candidate fixed-point forms are $g_1(x)=(x+1)^{1/3}$ and $g_2(x)=x^3-1$. Use the Fixed-Point Theorem to decide which one converges near the root, then compute $p_1$ through $p_4$ of the convergent iteration starting from $p_0=1.5$.
Solution
Differentiating both forms:
$$g_1'(x)=\frac{1}{3}(x+1)^{-2/3}, \qquad g_2'(x)=3x^2.$$
At the root $p\approx1.324718$: $g_1'(p)\approx0.1899$, so $|g_1'(p)|<1$ - the Fixed-Point Theorem guarantees local convergence. But $g_2'(p)\approx3(1.324718)^2\approx5.265$, so $|g_2'(p)|>1$ and $g_2$ diverges near the root (confirmed by $g_2(1.5)=2.375$, $g_2(2.375)=12.396$, blowing up immediately).
Iterating $g_1$ from $p_0=1.5$:
$g_1$ converges ($p_4=1.324939$, error $\approx2.2\times10^{-4}$); $g_2$ diverges. The deciding factor is $|g'(p)|<1$, not which form "looks" simpler.
Iterating $g_1$ from $p_0=1.5$:
| $n$ | $p_n=g_1(p_{n-1})$ | $|p_n-p|$ |
|---|---|---|
| 1 | 1.357209 | 0.032491 |
| 2 | 1.330861 | 0.006143 |
| 3 | 1.325884 | 0.001166 |
| 4 | 1.324939 | 0.000221 |
Connections Across the Course
- The self-map and derivative-bound conditions here are a special case of the general contraction-mapping idea reused for the Jacobi and Gauss-Seidel methods in Chapter 14, where "$|g'(p)|<1$" becomes "spectral radius of the iteration matrix $<1$."
- Newton's Method, next chapter, is fixed-point iteration in disguise with $g(x)=x-f(x)/f'(x)$ - and $g'(p)=0$ at a simple root is exactly why it converges quadratically instead of linearly.
- The error-bound machinery (a priori / a posteriori) is identical in structure to the bounds used for the iterative linear-system solvers in Chapter 14.