Fixed-point iteration

In numerical analysis, fixed-point iteration is a method of computing fixed points of a function.
More specifically, given a function formula_1 defined on the real numbers with real values and given a point formula_2 in the domain of formula_1, the fixed point iteration is
which gives rise to the sequence formula_5 which is hoped to converge to a point formula_6. If formula_1 is continuous, then one can prove that the obtained formula_6 is a fixed point of formula_1, i.e.,
More generally, the function formula_1 can be defined on any metric space with values in that same space.
Examples.
converges to 0 for all values of formula_2.
However, 0 is "not" a fixed point of the function
as this function is "not" continuous at formula_28, and in fact has no fixed points.
Contractions.
If a function formula_1 defined on the real line with real values is Lipschitz continuous with Lipschitz constant formula_43, then this function has precisely one fixed point, and the fixed-point iteration converges towards that fixed point for any initial guess formula_17 This theorem can be generalized to any complete metric space.
Proof of this theorem:
Since formula_1 is Lipschitz continuous with Lipschitz constant formula_43, then for the sequence formula_47, we have:
and
Combining the above inequalities yields:
Since formula_43, formula_52 as formula_53
Therefore, we can show formula_54 is a Cauchy sequence and thus it converges to a point formula_55.
For the iteration formula_56, let formula_57 go to infinity on both sides of the equation, we obtain formula_58. This shows that formula_55 is the fixed point for formula_1. So we proved the iteration will eventually converge to a fixed-point.
This property is very useful because not all iterations can arrive at a convergent fixed-point. When constructing a fixed-point iteration, it is very important to make sure it converges. There are several fixed-point theorems to guarantee the existence of the fixed point, but since the iteration function is continuous, we can usually use the above theorem to test if an iteration converges or not. The proof of the generalized theorem to complete metric spaces is similar.
Convergence acceleration.
The speed of convergence of the iteration sequence can be increased by using a convergence acceleration method such as Aitken's delta-squared process. The application of Aitken's method to fixed-point iteration is known as Steffensen's method, and it can be shown that Steffensen's method yields a rate of convergence that is at least quadratic.