From Convergence to a Certified Error
The Banach fixed-point theorem guarantees convergence of contraction iteration in a complete metric space. For computation, convergence alone is not enough: after a finite number of steps, we want a numerical bound on how far the current iterate may be from the limit. The contraction constant supplies that bound, either before starting the iteration or by measuring the most recent step.
Let \((X,d)\) be a complete metric space. A map \(T:X\to X\) is a contraction with constant \(q\) if \(0\le q<1\) and \(d(Tx,Ty)\le qd(x,y)\) for all \(x,y\in X\). Given \(x_0\in X\), define the iterates by \(x_{n+1}=T(x_n)\) for \(n\ge0\). The Banach fixed-point theorem, proved in the earlier material on that theorem, says that there is a unique \(p\in X\) with \(T(p)=p\), and that \(x_n\to p\).
Proof. First, for every \(k\ge0\), the contraction inequality gives \(d(x_{k+1},x_k)=d(Tx_k,Tx_{k-1})\le qd(x_k,x_{k-1})\) when \(k\ge1\). Starting with \(d(x_1,x_0)\), induction therefore gives \(d(x_{k+1},x_k)\le q^k d(x_1,x_0)\) for all \(k\ge0\). For \(m>n\), the triangle inequality now gives \(d(x_n,x_m)\le\sum_{k=n}^{m-1}d(x_k,x_{k+1})\le d(x_1,x_0)\sum_{k=n}^{m-1}q^k\). Since \(x_m\to p\), taking \(m\to\infty\) yields \(d(x_n,p)\le d(x_1,x_0)\sum_{k=n}^{\infty}q^k=\frac{q^n}{1-q}d(x_1,x_0)\). The same argument starting with \(k=n\) gives \(d(x_n,p)\le\sum_{k=n}^{\infty}d(x_k,x_{k+1})\le\frac{1}{1-q}d(x_{n+1},x_n)\), proving the second inequality. Finally, for any \(z\in X\), the triangle inequality and \(T(p)=p\) imply \(d(z,p)\le d(z,Tz)+d(Tz,Tp)\le d(z,Tz)+qd(z,p)\). Subtracting \(qd(z,p)\) and dividing by \(1-q>0\) proves the residual bound. These inequalities also cover \(q=0\); in the first inequality \(q^0=1\). \(\square\)
The first estimate is called a priori because its right-hand side uses only the initial step and the iteration count. The second is a posteriori: it uses the step just computed. The residual version applies to any proposed approximation \(z\), not just an iterate. In practice, if the desired error is at most \(\varepsilon>0\), the a priori estimate certifies \(x_n\) whenever \(\frac{q^n}{1-q}d(x_1,x_0)\le\varepsilon\); the a posteriori estimate certifies it whenever \(d(x_{n+1},x_n)\le(1-q)\varepsilon\).
Using the A Priori Bound
Worked Example: Choosing the Number of Iterations
Let \(X=\mathbb{R}\) with its usual metric, and define \(T(x)=\frac{x}{2}+1\). This is a self-map of \(\mathbb{R}\), which is complete, and \(|T(x)-T(y)|=\frac12|x-y|\), so it is a contraction with \(q=\frac12\). Starting from \(x_0=0\), find an iteration count that guarantees error at most \(\frac{1}{100}\).
The fixed point solves \(p=\frac p2+1\), so \(p=2\). The first iterate is \(x_1=T(0)=1\), and thus \(d(x_1,x_0)=1\). The a priori estimate becomes \(d(x_n,2)\le\frac{(1/2)^n}{1-1/2}\cdot1=2^{1-n}\). At \(n=7\), this bound is \(2^{-6}=\frac{1}{64}\), which is greater than \(\frac{1}{100}\). At \(n=8\), it is \(2^{-7}=\frac{1}{128}\), which is less than \(\frac{1}{100}\). Therefore eight iterations suffice according to this bound.
Check: Repeated substitution gives \(x_n=2(1-2^{-n})\): it holds at \(n=0\), and if it holds at \(n\), then \(T(x_n)=2(1-2^{-n})/2+1=2(1-2^{-(n+1)})\). Consequently \(d(x_8,2)=2^{-7}=\frac{1}{128}\), matching the bound. This exact check confirms the iteration count and the error calculation.
The a priori bound is useful when the initial displacement and a contraction constant are known. It can be conservative: it uses a worst-case geometric estimate for every later step. Once some iterates have been computed, the a posteriori bound may be more informative because it uses their actual separation.
Using the Latest Step as a Certificate
Worked Example: Certifying an Iterate from Its Successor
On \(\mathbb{R}\), let \(T(x)=\frac{x}{3}+2\). Its contraction constant is \(q=\frac13\), since \(|T(x)-T(y)|=\frac13|x-y|\). Start at \(x_0=0\), and use the a posteriori bound to estimate the error at \(x_2\).
The iterates are \(x_1=T(0)=2\) and \(x_2=T(2)=\frac23+2=\frac83\). The next iterate is \(x_3=T(\frac83)=\frac89+2=\frac{26}{9}\). Thus \(d(x_3,x_2)=|\frac{26}{9}-\frac83|=|\frac{26}{9}-\frac{24}{9}|=\frac29\). The bound at \(x_2\) is therefore \(d(x_2,p)\le\frac{1}{1-1/3}\cdot\frac29=\frac32\cdot\frac29=\frac13\).
Check: Solving \(p=\frac p3+2\) gives \(p=3\). Directly, \(d(x_2,p)=|\frac83-3|=\frac13\), so the certified bound is attained in this example. The calculation also shows why the actual most recent step, rather than merely the initial step, can be used to check accuracy.
The residual form avoids requiring a successor to be part of a recorded iteration: compute \(Tz\), measure \(d(z,Tz)\), and divide by \(1-q\). It is essential that \(q<1\), since the rearrangement in the proof divides by \(1-q\). A small residual is useful because the contraction property ensures that the remaining distance to the fixed point cannot exceed the stated multiple of that residual.
A Scalar Equation with Certified Accuracy
A scalar equation can be solved by rewriting it as a fixed-point equation \(x=T(x)\). The method is valid only after checking both that \(T\) maps the chosen complete space into itself and that it is a contraction there. For a differentiable real function on an interval, a bound \(|T'(x)|\le q<1\) throughout the interval implies the contraction inequality by the mean value theorem.
Worked Example: A Certified Approximation to a Root
Consider \(x^2+2x-2=0\). Rewrite this as \(x=T(x)\), where \(T(x)=\frac{x+2}{x+3}\), and work on \([0,1]\) with the usual metric. For \(0\le x\le1\), the numerator \(x+2\) and denominator \(x+3\) are positive, and \(x+2\le x+3\); hence \(0<T(x)\le1\), so \(T\) maps \([0,1]\) into itself. Its derivative is \(T'(x)=\frac{1}{(x+3)^2}\), so \(0<T'(x)\le\frac19\) on this interval. The mean value theorem gives \(|T(x)-T(y)|\le\frac19|x-y|\) for all \(x,y\in[0,1]\). The interval is complete, so the iteration has a unique fixed point there.
Start with \(x_0=0\). Direct substitution gives \(x_1=T(0)=\frac23\), \(x_2=T(\frac23)=\frac{8/3}{11/3}=\frac8{11}\), and \(x_3=T(\frac8{11})=\frac{30/11}{41/11}=\frac{30}{41}\). To use the a posteriori bound at \(x_3\), compute its successor: $$ x_4=T\left(\frac{30}{41}\right) =\frac{112/41}{153/41} =\frac{112}{153}. $$ Thus $$ d(x_4,x_3)=\left|\frac{112}{153}-\frac{30}{41}\right| =\left|\frac{4592-4590}{6273}\right| =\frac{2}{6273}. $$ With \(q=\frac19\), the error satisfies $$ d(x_3,p)\le\frac{1}{1-1/9}\cdot\frac{2}{6273} =\frac98\cdot\frac{2}{6273} =\frac{18}{50184} =\frac{1}{2788}. $$ Therefore \(\frac{30}{41}\) is a certified approximation to the unique fixed point, with error at most \(\frac{1}{2788}\).
Check: The fixed-point equation is \(x=\frac{x+2}{x+3}\). Since \(x+3>0\) on \([0,1]\), multiplying by \(x+3\) is valid and gives \(x^2+2x-2=0\). Its root in \([0,1]\) is \(\sqrt3-1\), because \((\sqrt3-1)^2+2(\sqrt3-1)-2=0\), and \(1<\sqrt3<2\) implies \(0<\sqrt3-1<1\). The certified interval can be written exactly as \([\frac{30}{41}-\frac{1}{2788},\frac{30}{41}+\frac{1}{2788}]\); the bound proves that the fixed point lies in this interval.
A Common Error in Reading the Estimate
Common pitfall. Omitting the factor \(\frac{1}{1-q}\) from the a priori estimate gives the incorrect claim \(d(x_n,p)\le q^n d(x_1,x_0)\). For the map \(T(x)=\frac{x}{2}+1\) starting at \(x_0=0\), the fixed point is \(2\), \(x_1=1\), and \(d(x_1,p)=|1-2|=1\). The incorrect expression at \(n=1\) is \(\frac12\cdot1=\frac12\), which does not bound the actual error \(1\). The correct expression is \(\frac{(1/2)^1}{1-1/2}\cdot1=1\). The missing factor accounts for the full tail of all the future steps, not just the next step.
Both estimates are certificates: their conclusions follow from the contraction hypothesis, not from how close a sequence of decimal outputs happens to look. A rigorous computation should therefore state the invariant complete space, the contraction constant, the chosen iterate, and the bound used to certify its error.
Check Your Understanding
For each question, identify which contraction estimate applies and state the hypotheses needed for its use.
- If \(q=\frac14\) and \(d(x_1,x_0)=2\), what a priori bound does the theorem give for \(d(x_3,p)\)?
- For \(q=\frac25\) and \(d(x_{n+1},x_n)=\frac{3}{10}\), what a posteriori bound does it give for \(d(x_n,p)\)?
- Explain why a bound on \(d(z,Tz)\) gives a bound on \(d(z,p)\), even when \(z\) is not an iterate.
- For \(T(x)=\frac{x}{4}+3\) on \(\mathbb{R}\), find its contraction constant and fixed point.
- Why must a scalar fixed-point map be shown to carry the chosen interval into itself before applying the contraction iteration theorem?