Fixed-point iteration

An iterative method for solving an equation written as x = g(x), generating successive approximations by repeatedly applying g. Its convergence depends on the function and starting value.

Fixed point: A value that a function maps to itself. The iteration seeks a value unchanged by the chosen map.
Iterative method: A numerical procedure that improves an approximation through repeated computational steps. Fixed-point iteration is one member of this broad family of algorithms.
Newton's method: A root-finding algorithm that repeatedly uses a function's tangent line to improve an approximation. It can be written as fixed-point iteration with map x − f(x)/f′(x).
Bisection method: A root-finding method that repeatedly halves an interval containing a sign-changing root. It guarantees interval shrinkage under its assumptions, unlike unconstrained fixed-point iteration.
Contraction mapping theorem: A theorem guaranteeing a unique fixed point for a contraction on a complete metric space. It provides a strong condition under which repeated application converges.
Recurrence relation: A rule that defines each term of a sequence from earlier terms. The iterates form a sequence through the recurrence xₙ₊₁ = g(xₙ).
Jacobi method: An iterative method for solving linear systems by updating each variable from the previous iterate. Its simultaneous updates define a fixed-point map for a linear system.
Secant method: A root-finding method that estimates derivatives from two previous function values. It updates using function evaluations rather than a prescribed fixed-point rearrangement.
Banach fixed-point theorem: A fixed-point theorem asserting existence and uniqueness for contractions on complete metric spaces. Its completeness and contraction assumptions explain one rigorous convergence guarantee.
Root-finding algorithm: A numerical method for approximating a value at which a function equals zero. Solving f(x)=0 can be recast as finding a fixed point of a suitable map.

Linked from 10 pages