1 Definition and basic idea
Fixed-point iteration is an iterative numerical procedure for finding a value that remains unchanged under a given function. If a function is written as \(g(x)\), the goal is to identify a point \(x\) for which \(x = g(x)\). The method begins from an initial estimate and repeatedly applies the same transformation to produce a sequence of approximations.
The approach is widely used because it is simple to implement and often effective for nonlinear problems. Its performance depends strongly on the form of the function and on whether the repeated updates move the sequence toward a stable limit.
1.1 Fixed point of a function
A fixed point is an input that is mapped to itself. In other words, if \(x^\ast\) is a fixed point of \(g\), then \(g(x^\ast) = x^\ast\). Such points may represent steady states, equilibria, or self-consistent solutions in applied settings.
A function can have no fixed points, one fixed point, or several fixed points. When more than one exists, the iteration may converge to different limits depending on the starting value.
1.2 Iterative form of the method
The method constructs a sequence by repeated substitution: \[ x_{n+1} = g(x_n). \] Here, \(x_0\) is the initial guess, and each new term is obtained by evaluating the function at the previous term. If the process converges, the limit is a fixed point of \(g\).
This form makes the method especially natural for computer implementation. Each step requires only one application of the function, so the procedure is often inexpensive per iteration.
1.3 Relation to solving equations
Fixed-point iteration is frequently used to solve equations of the form \(f(x) = 0\). Such an equation can sometimes be rewritten in equivalent fixed-point form \(x = g(x)\). Once rewritten, the root-finding problem becomes one of locating a fixed point of \(g\).
Different rearrangements of the same equation can lead to very different convergence behavior. A formulation that works well for one initial guess may fail for another, which makes the choice of representation important.
2 Mathematical formulation
The mathematical basis of fixed-point iteration is the repeated application of a mapping to generate a sequence. The target is a point that satisfies the consistency condition \(x = g(x)\), and the iteration is designed to approach that condition progressively.
2.1 Rearranging equations into fixed-point form
Many nonlinear equations can be rewritten in the form \(x = g(x)\) by algebraic manipulation. For example, an equation \(f(x) = 0\) may be rearranged as \(x = x - \lambda f(x)\), where \(\lambda\) is a chosen parameter. Different rearrangements correspond to different iteration functions.
The usefulness of a fixed-point form depends on whether the resulting map brings successive approximations closer to a solution. A poor rearrangement can amplify errors or produce slow convergence.
2.2 Iteration sequence
Once a fixed-point form is chosen, the method generates a sequence of approximations. The sequence may converge to a fixed point, cycle among a small number of values, or diverge entirely.
2.2.1 Recursive update rule
The update rule is recursive: \[ x_{n+1} = g(x_n), \qquad n = 0,1,2,\dots \] This relation defines the full iteration from the initial value onward. Each term depends only on the previous one, which gives the method a straightforward computational structure.
2.2.2 Notation and terminology
The values \(x_n\) are usually called iterates. The starting value \(x_0\) is the initial guess, and the limiting value, if it exists, is the fixed point. The function \(g\) is often called the iteration function or iteration map.
In numerical analysis, the sequence may also be described as successive substitution, especially when each update substitutes the previous approximation into the right-hand side.
2.3 Convergence to a fixed point
Convergence occurs when the iterates approach a limiting value \(x^\ast\) as \(n\) increases. If the sequence converges and \(g\) is continuous at the limit, then \(x^\ast = g(x^\ast)\). Thus, any converged limit is necessarily a fixed point.
However, convergence is not guaranteed. The sequence may settle slowly, oscillate, or move away from the desired point, depending on the local behavior of the mapping.
3 Convergence theory
The convergence of fixed-point iteration is governed by properties of the iteration function near the target point and, in many cases, on a suitable region around it. Mathematical convergence theory provides conditions under which the method is guaranteed to succeed.
3.1 Contraction mappings
A central sufficient condition for convergence is that the iteration function act as a contraction on a region of interest. Informally, a contraction brings points closer together under repeated application.
3.1.1 Contraction constant
A function \(g\) is called a contraction if there exists a constant \(L\) with \(0 \le L < 1\) such that \[
| g(x) - g(y) | \le L | x-y |
|---|
\] for all relevant \(x\) and \(y\). The constant \(L\) measures how strongly the map compresses distances.
Smaller values of \(L\) generally imply faster convergence. If \(L\) is close to 1, convergence may be slow even when it occurs.
3.1.2 Banach fixed-point theorem
The Banach fixed-point theorem states that a contraction on a complete metric space has a unique fixed point in the region, and that iteration from any starting point in that region converges to it. This result is one of the most important guarantees in fixed-point theory.
The theorem also provides a practical foundation for numerical iteration. When its hypotheses are satisfied, it ensures both existence and uniqueness of the solution and the reliability of the iterative process.
3.2 Local convergence
Even when a function is not a contraction on a large domain, it may still converge locally near a particular fixed point. Local convergence examines the behavior of iterates in a neighborhood of the solution.
3.2.1 Stability of the fixed point
A fixed point is stable if nearby starting values lead to iterates that move toward it. If small perturbations grow instead, the fixed point is unstable. Stability is therefore a key predictor of whether iteration will succeed from an approximate initial guess.
A stable fixed point can attract iterates from a limited region, while an unstable one usually repels them. Numerical methods typically rely on stable fixed points to ensure practical convergence.
3.2.2 Role of derivatives
| For differentiable scalar functions, the derivative at the fixed point often determines local behavior. If \( | g'(x^\ast) | < 1\), the fixed point is locally attracting; if \( | g'(x^\ast) | > 1\), it is typically repelling. The case \( | g'(x^\ast) | = 1\) requires more detailed analysis. |
|---|
In higher dimensions, the Jacobian matrix plays a similar role. Its spectral properties near the fixed point help determine whether the iteration contracts or expands nearby errors.
3.3 Divergence and oscillation
When the iteration function is poorly chosen, the sequence may diverge instead of converging. Divergence can take the form of unbounded growth, escape from the region of interest, or increasingly erratic behavior.
Oscillation is another common failure mode. The iterates may alternate between two values or cycle through a longer repeating pattern. Such behavior often indicates that the map does not sufficiently damp errors.
4 Error analysis
Error analysis studies the difference between the current iterate and the true fixed point. It is essential for assessing progress, choosing stopping rules, and estimating the reliability of numerical results.
4.1 Absolute and relative error
| The absolute error at step \(n\) is commonly measured by \( | x_n - x^\ast | \), where \(x^\ast\) is the exact fixed point. Relative error scales this difference by the magnitude of the solution, often using \( | x_n - x^\ast | / | x^\ast | \) when \(x^\ast \neq 0\). |
|---|
In practice, the exact solution is usually unknown. As a result, error measures often rely on quantities that can be computed from the iterates themselves.
4.2 A priori error estimates
A priori estimates predict the error before the computation is completed. Under contraction assumptions, one can often bound the distance to the fixed point using the contraction constant and the initial error.
These estimates are useful for understanding how many iterations may be needed. They provide theoretical guidance, though they may be conservative compared with observed behavior.
4.3 A posteriori error estimates
| A posteriori estimates are based on the computed iterates. A common indicator is the difference between successive values, \( | x_{n+1} - x_n | \), which can serve as a proxy for the remaining error. |
|---|
Such estimates are practical because they do not require knowledge of the exact solution. They are widely used in software to monitor convergence in real time.
4.4 Stopping criteria
Stopping criteria determine when the iteration should end. Typical rules include requiring the update difference to fall below a tolerance, limiting the maximum number of iterations, or combining several tests.
Good stopping criteria balance accuracy and efficiency. If the tolerance is too strict, computation may be unnecessarily long; if too loose, the result may be unreliable.
5 Numerical implementation
Implementing fixed-point iteration requires choices that affect speed, robustness, and numerical stability. The basic update is simple, but practical performance depends on several algorithmic decisions.
5.1 Choice of initial guess
The initial guess can strongly influence the outcome. For functions with multiple fixed points, different starting values may lead to different limits or may fail to converge altogether.
In many applications, the initial guess is chosen from physical intuition, graphing, prior approximations, or a coarser numerical method. A good starting value often reduces the iteration count substantially.
5.2 Iteration count and termination
A program usually tracks both the number of iterations and a termination test. If convergence is slow, the required iteration count may be high even when each step is inexpensive.
Maximum-iteration safeguards prevent endless computation when the method fails. In practice, termination logic is designed to detect both successful convergence and pathological behavior.
5.3 Acceleration techniques
Acceleration methods modify the basic iteration to improve convergence. They are especially useful when the original map converges but does so slowly.
5.3.1 Relaxation methods
Relaxation introduces a weighted update between the old iterate and the mapped value. A typical form is \[ x_{n+1} = (1-\omega)x_n + \omega g(x_n), \] where \(\omega\) is a relaxation parameter. Choosing \(\omega\) appropriately can stabilize the sequence or speed it up.
5.3.2 Aitken acceleration
Aitken acceleration uses successive iterates to estimate a better approximation, often reducing the effect of linear convergence. It is commonly applied to scalar sequences and can markedly improve efficiency when the iteration behaves regularly.
The method is especially helpful when the sequence approaches the limit steadily but slowly. Its use is more delicate when the iterates are noisy or irregular.
5.3.3 Anderson acceleration
Anderson acceleration combines information from multiple past iterates to form an improved update. It is widely used in large-scale computations because it can accelerate many nonlinear fixed-point processes without requiring explicit derivative calculations.
The method is particularly effective for vector-valued problems and iterative solvers arising in scientific computing. Its extra storage and algebraic work are often justified by faster convergence.
6 Applications
Fixed-point iteration appears across applied mathematics and computation because many problems can be reformulated as self-consistency conditions. It is useful whenever a solution can be expressed as the point where an update rule reproduces its own input.
6.1 Solving nonlinear equations
A common use is solving nonlinear scalar equations. By rewriting the equation in fixed-point form, one can apply repeated substitution to approximate a root.
This approach is simple and adaptable. It is often used as a standalone method or as a preliminary step before a more advanced solver.
6.2 Systems of equations
The method extends naturally to systems of nonlinear equations. In that setting, the iteration function maps a vector to another vector, and convergence depends on multidimensional stability properties.
Such schemes are important in numerical analysis, engineering models, and computational science. They often require careful design to ensure that all components of the vector improve together.
6.3 Integral equations
Many integral equations can be cast into fixed-point form. Repeated substitution then produces a sequence of functions that may converge to a solution.
This is a foundational idea in analysis and mathematical physics. In these contexts, fixed-point iteration often appears as an approximation scheme with theoretical convergence guarantees under suitable conditions.
6.4 Optimization and computational algorithms
Fixed-point ideas also appear in optimization, signal processing, and algorithm design. An algorithm may be described as seeking a point that remains unchanged under an update operator.
This perspective helps unify many iterative methods. It is especially useful when the update rule is easier to analyze than the original problem formulation.
7 Examples
Examples help show how different fixed-point forms can behave. Even for simple equations, the iteration function chosen can determine whether the process converges quickly, slowly, or not at all.
7.1 Simple scalar iteration
Consider a map such as \(g(x) = \cos x\). Starting from an initial guess, the sequence \[ x_{n+1} = \cos(x_n) \] may converge to a fixed point satisfying \(x = \cos x\). This is a classic illustration of self-consistent iteration.
The example shows that a simple recursive rule can generate a meaningful approximation even when the original equation is nonlinear and cannot be solved in closed form.
7.2 Iteration for transcendental equations
Transcendental equations often resist algebraic solution but can still be handled by fixed-point iteration. An equation involving exponential, logarithmic, or trigonometric functions may be rearranged into a form suitable for repeated substitution.
The success of the method depends on the specific rearrangement. Some formulations converge rapidly, while others produce instability or slow progress.
7.3 Comparison with Newton's method
Compared with Newton's method, fixed-point iteration is usually simpler per step but often less powerful. Newton's method uses derivative information to achieve faster local convergence, while fixed-point iteration generally relies only on function evaluation.
As a result, fixed-point iteration may be preferred when derivatives are unavailable or expensive, whereas Newton-type methods are often chosen when rapid convergence is essential.
8 Variants and related methods
Several methods are closely related to fixed-point iteration. Some are special cases, while others use the same conceptual framework with different update rules or in more general settings.
8.1 Picard iteration
Picard iteration is a classical fixed-point scheme used especially for differential and integral equations. It repeatedly substitutes the current approximation into an integral operator to produce a new approximation.
The method is important in analysis because it connects existence theory with constructive approximation. It also serves as a foundation for more elaborate iterative procedures.
8.2 Successive substitution
Successive substitution is another name for basic fixed-point iteration, especially when used to solve equations by repeatedly replacing a variable with an expression involving itself. The method is common in algebraic and numerical contexts.
The term emphasizes the mechanical nature of the update: one formula is substituted into another until the values stabilize.
8.3 Functional iteration in higher dimensions
In higher-dimensional problems, the same idea applies to vector-valued maps. The iteration takes the form \[ \mathbf{x}_{n+1} = G(\mathbf{x}_n), \] where \(\mathbf{x}_n\) is a vector and \(G\) acts on a space of states.
Such functional iteration is central in numerical linear algebra, nonlinear systems, and scientific computing. The analysis is more complex than in the scalar case because different directions may contract at different rates.
8.4 Relation to root-finding methods
Fixed-point iteration is one member of a larger family of root-finding methods. Many solvers can be interpreted as fixed-point schemes after rewriting the problem appropriately.
This viewpoint helps compare methods by their update operators, convergence speed, and stability. It also clarifies why some algorithms succeed only under specific assumptions about the underlying function.
</INTERNAL_LINK_CANDIDATES> Contraction mapping (a function that brings points closer together) Banach fixed-point theorem (a theorem guaranteeing a unique fixed point for contractions) Initial guess (the starting value for an iteration) Iterate (a successive approximation in an iterative process) Convergence (the process of approaching a limit) Divergence (the failure of an iteration to approach a limit) Oscillation (repeating back-and-forth behavior in iterates) Relaxation method (a weighted modification of an iteration) Aitken acceleration (a technique for speeding up convergence) Anderson acceleration (a multi-step convergence acceleration method) Nonlinear equation (an equation that can be written in fixed-point form) Root-finding method (a numerical method for solving equations) Picard iteration (a classical fixed-point scheme for integral or differential equations) Successive substitution (repeated replacement of a variable by an expression) Jacobian matrix (the multidimensional derivative used in convergence analysis) Spectral property (an eigenvalue-related feature affecting stability) Integral equation (an equation involving an unknown function under an integral) Newton's method (a derivative-based root-finding method) Stopping criterion (a rule for ending an iteration) Stability (the tendency of nearby iterates to move toward or away from a fixed point)