From Iteration to an Error Certificate
The contraction arguments developed earlier establish when a fixed point exists and is unique, and they give estimates for the errors of successive iterates. In applications, however, a point may come from a numerical calculation rather than from an exact iteration. It is useful to have an estimate that applies directly to any proposed approximation, whether or not it lies on an iterative orbit.
The quantity that makes this possible is the fixed-point residual: at a point \(x\), it measures how far \(f(x)\) is from \(x\). If this residual is small and \(f\) is a contraction, then \(x\) must be close to the fixed point. The contraction constant determines how strongly the residual controls the error.
A small residual is not automatically a guarantee of a small error. The useful estimate below depends on a contraction constant that applies to the map on its whole domain. When that hypothesis holds, the estimate does not require \(x\) to be an iterate of any starting point.
The Residual Error Estimate
Proof. Since \(f(p)=p\), the triangle inequality and the contraction inequality give
Subtract \(q\,d(x,p)\) from both sides. Since \(1-q>0\), division by \(1-q\) preserves the inequality and yields
This proves the estimate. \(\square\)
If \(X\) is complete and nonempty, the Contraction Mapping Theorem supplies the fixed point \(p\), and the Uniqueness of a Fixed Point theorem ensures it is the only one. The estimate itself only requires that a fixed point already exists; completeness is used to guarantee existence, not in the inequality's proof.
The bound turns a residual into an a posteriori certificate: once \(d(x,f(x))\) is evaluated and a valid contraction constant is known, the distance from \(x\) to the fixed point is bounded without knowing the fixed point. The factor \(1/(1-q)\) matters. When \(q\) is close to \(1\), a small residual may still give a relatively weak distance bound.
Worked Examples: Certifying an Approximation
Worked Example: An Affine Contraction on the Real Line
Define \(f:\mathbb{R}\to\mathbb{R}\) by \(f(x)=x/3+2/3\). For \(x,y\in\mathbb{R}\),
Thus \(f\) is a contraction with \(q=1/3\). Its fixed point satisfies \(p=p/3+2/3\), so \(2p/3=2/3\) and \(p=1\). Consider the approximation \(x=7/5\). Its image and residual are
The residual error bound gives
In this example the actual error is \(\left|7/5-1\right|=2/5\), so the estimate is exact. This also shows why the denominator \(1-q\) cannot generally be discarded: here the residual is only \(2/3\) of the actual error.
Worked Example: A Residual Bound on a Closed Interval
Let \(X=[0,1]\) with its usual metric and define \(f(x)=x/5+3/5\). For \(x\in[0,1]\), \(3/5\leq f(x)\leq4/5\), so \(f\) maps \(X\) into itself. Also,
so \(f\) is a contraction with \(q=1/5\). Solving \(p=p/5+3/5\) gives \(p=3/4\). At the proposed approximation \(x=7/10\),
Consequently,
The actual error is \(3/4-7/10=15/20-14/20=1/20\). As in the first example, the affine map makes the residual bound exact. The fact that the map preserves the interval is important: the contraction estimate is being applied to a self-map of the stated metric space.
For an exact fixed-point iteration \(x_{n+1}=f(x_n)\), the residual at \(x_n\) is precisely \(d(x_n,x_{n+1})\). The residual theorem can therefore be applied to any iterate. Earlier in this course, the A Posteriori Error Bound gives an estimate tailored to an exact contraction orbit, while the A Priori Error Bound from the First Step controls its error using the initial step. The residual estimate is useful in a different way: it applies to an arbitrary proposed point, including one produced by a separate computation.
When Each Iterative Step Is Approximate
A numerical procedure may not calculate \(f(x_n)\) exactly. It may instead produce a point \(x_{n+1}\) whose distance from \(f(x_n)\) is bounded by a known tolerance. These per-step errors can accumulate, but contraction reduces the influence of earlier errors. The following estimate quantifies both effects.
Proof. For every \(n\geq0\), the triangle inequality, the step-error hypothesis, and the contraction inequality imply
We prove the claimed bound by induction. At \(n=0\), it reads \(d(x_0,p)\leq d(x_0,p)\), so it holds. Suppose it holds at \(n\). Substituting that bound into the one-step inequality gives
This is the required estimate with \(n+1\) in place of \(n\), completing the induction. The proof also applies when \(q=0\), with \(q^0=1\). \(\square\)
The powers of \(q\) show how errors are weighted. An error introduced at step \(j\) contributes at most \(q^{n-1-j}\varepsilon_j\) to the bound at step \(n\). Errors from earlier steps undergo more contractions; an error from the most recent step has weight \(q^0=1\).
The initial distance \(d(x_0,p)\) in this estimate may itself be unknown. If \(f\) is a contraction and \(x_0\in X\), the Fixed-Point Residual Error Bound supplies \(d(x_0,p)\leq d(x_0,f(x_0))/(1-q)\). Substitution gives a fully computable version:
This estimate needs only the initial residual, a contraction constant, and bounds on the errors made at each step. It does not require knowing \(p\) or the exact initial distance to \(p\).
Worked Example: Accumulated Error in an Inexact Iteration
Take \(X=\mathbb{R}\), \(f(x)=x/2\), and \(x_0=2\). The map is a contraction with \(q=1/2\), and its fixed point is \(p=0\). Suppose the computed steps satisfy
at every step. If the calculation returns \(x_1=11/10\), \(x_2=13/20\), and \(x_3=17/40\), then each step has error exactly \(1/10\):
Using the inexact-iteration estimate at \(n=3\), with each \(\varepsilon_j=1/10\), gives
Here \(x_3=17/40\) and \(p=0\), so the bound is attained. The example shows that later step errors have a larger weight than earlier ones, while the initial error is reduced by three applications of the contraction factor.
Using Error Estimates with Care
A residual-based estimate is only as reliable as its hypotheses. In particular, the contraction constant must be valid for all points in the domain under consideration, and the map must send that domain into itself. An observed decrease in distance for a few test pairs does not establish a global contraction inequality.
Without a contraction hypothesis, a small residual need not place a point near any fixed point. For example, on \(\mathbb{R}\), let \(g(x)=x+1/100\). Every point has residual \(|x-g(x)|=1/100\), but \(g\) has no fixed point: the equation \(x=x+1/100\) has no solution. Thus a residual alone is not a certificate. The contraction bound provides the missing link between residual size and distance to a fixed point.
In practice, if an approximation \(x\) has computed residual at most \(\eta\), and the contraction inequality is known with constant \(q\), then the theorem certifies \(d(x,p)\leq\eta/(1-q)\). For an inexact iteration, the accumulated-error estimate adds the weighted step tolerances. Both estimates are most informative when \(q\) is well below \(1\); when \(q\) is near \(1\), the geometric reduction is slow and the error factors become large.
Check Your Understanding
Use the residual and inexact-iteration estimates to answer the following questions.
- Why does the Fixed-Point Residual Error Bound require \(q<1\) when dividing by \(1-q\)?
- For an exact iteration \(x_{n+1}=f(x_n)\), what is the residual at \(x_n\) in terms of two successive iterates?
- In the inexact-iteration estimate, what is the weight of the error introduced at step \(j\) when estimating \(d(x_n,p)\)?
- How can the initial distance \(d(x_0,p)\) be replaced by a quantity that can be computed from \(x_0\) and \(f(x_0)\)?
- Why does a small fixed-point residual fail to certify proximity to a fixed point if no contraction hypothesis is available?