Fixed-point iteration

Fixed-point iteration seeks a fixed point of a map $F$ by repeatedly setting $x_{k+1}=F(x_k)$. Convergence requires additional hypotheses; for example, a contraction mapping on a complete metric space has a unique fixed point reached by this iteration.

Iterating an affine map gives $x_k=M^{k-1}{x}_1+{\sum }_{j=0}^{k-2}{M}^{j}c$. A fixed point exists exactly when $c$ is in the image of a linear map $I-M$. If the spectral radius of $M$ is below one, its matrix powers tend to zero and every orbit converges to the unique fixed point $(I-M{)}^{-1}c$.

An iteration converging to $x_{\ast }$ has exact asymptotic order $p$ if its nonzero errors $e_k=x_k-x_{\ast }$ satisfy the displayed limit. A bound $\Vert e_{k+1}\Vert \le C\Vert e_k{\Vert }^p$ instead asserts at least order $p$. Finite termination is treated separately because the error ratios become undefined.

An iteration of a map has linear convergence to its limit when its nonzero errors $e_k=x_k-\alpha$ satisfy $|e_{k+1}|/|e_k|\to \rho$ for some $0<\rho <1$. The error eventually shrinks by approximately the same factor at each step. This is exact order of convergence one, in contrast to quadratic convergence.

A sequence with errors $e_k=x_k-x^{\ast }$ converges Q-linearly in a specified norm if there is a constant $q<1$ with $\Vert e_{k+1}\Vert \le q\Vert e_k\Vert$ eventually. The limsup of consecutive nonzero error ratios is its asymptotic factor. This is stronger than merely having a bound $\Vert e_k\Vert \le C{q}^k$, which is called R-linear convergence. The norm and whether an iteration is one coordinate step or an entire sweep must be specified when quoting a factor.

An iteration has at least cubic convergence when its errors eventually satisfy the displayed inequality with fixed $C>0$. Exact order of convergence three requires a positive finite limit of $\Vert e_{k+1}\Vert /\Vert e_k{\Vert }^3$. If $C^{1/2}\Vert e_N\Vert <1$, setting $d_k=C^{1/2}\Vert e_k\Vert$ gives $d_{k+1}\le d_k^3$, hence $d_{N+j}\le d_N^{3^j}$.