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.

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}$.