In numerical analysis, fixed-point iteration is a method of computing fixed points of iterated functions. More specifically, given a function defined on the real numbers with real values and given a point in the domain of, the fixed point iteration is which gives rise to the sequence which is hoped to converge to a point. If is continuous, then one can prove that the obtained is a fixed point of, i.e., More generally, the function can be defined on any metric space with values in that same space.
The fixed-point iteration converges to the unique fixed point of the function for any starting point This example does satisfy the assumptions of the Banach fixed point theorem. Hence, the error after n steps satisfies When the error is less than a multiple of for some constant q, we say that we have linear convergence. The Banach fixed-point theorem allows one to obtain fixed-point iterations with linear convergence.
The fixed-point iteration will diverge unless. We say that the fixed point of is repelling.
The requirement that f is continuous is important, as the following example shows. The iteration
converges to 0 for all values of . However, 0 is not a fixed point of the function as this function is not continuous at, and in fact has no fixed points.
Halley's method is similar to Newton's method but, when it works correctly, its error is . In general, it is possible to design methods that converge with speed for any. As a general rule, the higher the, the less stable it is, and the more computationally expensive it gets. For these reasons, higher order methods are typically not used.
The Picard–Lindelöf theorem, which shows that ordinary differential equations have solutions, is essentially an application of the Banach fixed point theorem to a special sequence of functions which forms a fixed point iteration, constructing the solution to the equation. Solving an ODE in this way is called Picard iteration, Picard's method, or the Picard iterative process.
If a function defined on the real line with real values is Lipschitz continuous with Lipschitz constant, then this function has precisely one fixed point, and the fixed-point iteration converges towards that fixed point for any initial guess This theorem can be generalized to any metric space. Proof of this theorem: Since is Lipschitz continuous with Lipschitz constant, then for the sequence, we have: and Combining the above inequalities yields: Since, as Therefore, we can show is a Cauchy sequence and thus it converges to a point. For the iteration, let go to infinity on both sides of the equation, we obtain. This shows that is the fixed point for. 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 metric space is similar.
