= Contraction iteration error bound
{title2=$d(x_n,x_*)\leq L^n d(x_1,x_0)/(1-L)$}
Successive steps satisfy $d(x_{n+1},x_n)\leq L^n d(x_1,x_0)$. Summing the remaining steps with the <triangle inequality> gives a bound available before the iteration starts:
$$
d(x_n,x_*)\leq\frac{L^n}{1-L}\,d(x_1,x_0)\qquad(n\geq0).
$$
After computing a new step, the <contraction mapping> gives the often sharper bound
$$
d(x_n,x_*)\leq\frac{L}{1-L}\,d(x_n,x_{n-1})\qquad(n\geq1).
$$
Equivalently, the residual at any $z\in X$ satisfies $d(z,x_*)\leq d(z,Tz)/(1-L)$. These estimates convert visible step sizes into guaranteed distances to an unknown <fixed point>. When $L$ is close to one, the factor $1/(1-L)$ can be large: a small step alone needs interpretation through the contraction constant.
Back to article page
