1 Basic notions and problem settings

1.1 Fixed-point and root-finding formulations

Iterative convergence studies start from an underlying mathematical problem. Two common formulations are:

  • Fixed-point problem: Find \(x^\*\) such that \(x^\* = G(x^\*)\) for a given map \(G\).
  • Root-finding problem: Find \(x^\*\) such that \(f(x^\*)=0\), which can often be rewritten as a fixed-point problem by setting \(x = G(x)\) where \(G\) is constructed from \(f\) (for example, through an equation rearrangement or an algorithmic update rule).

These viewpoints are closely related. Many iterative algorithms can be expressed as repeatedly applying an update map \(G\), and convergence analysis focuses on how the iterates approach the desired solution.

1.2 Iteration schemes and notation

A general fixed-point iteration is written \[ x_{n+1} = G(x_n), \] where \(x_0\) is an initial guess. For root-finding, a typical scheme is \[ x_{n+1}=x_n - \Phi(x_n), \] but convergence can still be analyzed by translating the update into a fixed-point form (or by tracking error via Taylor expansions).

In analysis, the iterate sequence \(\{x_n\}\) is considered together with the target \(x^\*\) when it exists, and with quantities that quantify progress (residuals, differences between iterates, or linearized error recurrences).

1.3 Error, residual, and their relationships

Let \(x^\*\) denote a fixed point or root. The error is often \[ e_n = x_n - x^\*, \]

measured in a norm \(\|\cdot\|\) on the underlying space. The residual depends on the formulation:
  • For a fixed-point map, a natural residual is \(r_n = x_n - G(x_n)\), since \(r_n=0\) exactly at the fixed point.
  • For a root problem, the residual is \(r_n = f(x_n)\).
A central theme is that residuals can be computed from \(x_n\), while errors usually cannot be computed directly. Convergence theory supplies bounds that relate \(\|e_n\|\) to \(\|r_n\|\) under assumptions such as Lipschitz conditions or non-singularity of derivatives near \(x^\*\).

1.4 Types of convergence (pointwise, norm, Q-linear, R-linear, superlinear)

Convergence can be described in several strengths:

  • Pointwise convergence: \(x_n \to x^\*\) in the sense of the underlying topology (often equivalent to norm convergence in finite-dimensional spaces).
- Norm convergence: \(\|x_n-x^\*\|\to 0\) explicitly.

Rates are often classified as:

- Q-linear convergence: errors shrink at least geometrically up to a multiplicative factor; formally one often writes \(\|e_{n}\|\le C q^{n}\) for some \(q\in(0,1)\) after some index.
- R-linear convergence: a related but slightly different “eventual ratio” viewpoint: \(\limsup_{n\to\infty}\|e_{n+1}\|/\|e_n\| <1\).
- Superlinear convergence: the ratio \(\|e_{n+1}\|/\|e_n\|\to 0\).
- Higher-order convergence: quantified by an order \(p\ge 2\), often expressed as \(\|e_{n+1}\|\le C \|e_n\|^p\) near the solution.

These categories help distinguish methods that converge merely “reliably” from those that become dramatically more accurate as iterates approach the target.

2 Convergence criteria for iterative maps

2.1 Contraction mapping principle

The contraction mapping principle provides a foundational, widely used criterion for convergence and for uniqueness of the fixed point.

2.1.1 Conditions in metric spaces

Let \((X,d)\) be a complete metric space and suppose \(G:X\to X\) satisfies \[ d(G(x),G(y)) \le q\, d(x,y) \] for all \(x,y\in X\) with some constant \(q\in(0,1)\). Then:

  1. \(G\) has a unique fixed point \(x^\*\in X\).
  2. For any starting value \(x_0\in X\), the iteration \(x_{n+1}=G(x_n)\) converges to \(x^\*\).
  3. Errors satisfy a geometric estimate tied to \(q\), yielding explicit rate information.

2.1.2 Local vs global contraction results

Global contraction requires the inequality on the whole domain. In practice, one often obtains local contraction: there exists a neighborhood around \(x^\*\) where the map contracts. Then convergence holds provided the initial guess falls inside the attracting neighborhood (the basin of attraction).

Local results can be derived via continuity and differentiability: if \(G\) is differentiable at \(x^\*\) and the derivative behaves like a contraction (in a suitable operator norm) then a small neighborhood inherits contraction-like behavior.

2.2 Banach and variants for existence/uniqueness of fixed points

Banach’s theorem is the archetype for fixed-point existence and uniqueness. Variants adjust assumptions, for example by weakening strict contraction to conditions such as:

  • Contractions on closed subsets: the map contracts on a restricted complete subset.
  • Iterative contractivity conditions: the iterated map \(G^m\) becomes a contraction even if \(G\) itself is not.
  • Mixed regularity conditions: use of partial contraction or weighted norms to capture convergence directions more precisely.

These tools are valuable because many algorithms are not globally contractive yet still converge from reasonable starting points.

2.3 Non-expansive and averaged operators (stability perspectives)

When \(G\) is not contractive, convergence can still occur under structure. Two widely used stability classes are:

  • Non-expansive maps: \(d(G(x),G(y)) \le d(x,y)\). These maps do not expand distances but may not contract them, so convergence may be slower or require additional arguments.
  • Averaged operators: \(G\) is expressed as a convex combination of the identity and a non-expansive mapping. Averagedness often yields convergence of sequences using fixed-point iterations and related algorithmic schemes, sometimes with monotonicity of averaged residuals.

This perspective aligns convergence analysis with operator-theoretic stability: the method remains “tame” even if it does not shrink errors uniformly in one step.

2.4 Continuity and differentiability assumptions

Many convergence results rely on regularity near the solution. Typical assumptions include:

  • Continuity of \(G\) to ensure limits propagate correctly.
  • Differentiability to enable linearization and spectral analysis.
  • Higher derivatives to justify higher-order convergence rates (e.g., quadratic behavior for Newton-like methods).

The role of these assumptions is to connect observable iteration changes (such as residual decrease) with theoretical error recurrences derived from local expansions.

3 Local convergence analysis

3.1 Linearization near the fixed point

If \(G\) is differentiable at \(x^\*\), then for \(x\) near \(x^\*\), \[ G(x) \approx G(x^\*) + DG(x^\*)(x-x^\*) = x^\* + DG(x^\*)(x-x^\*). \] Subtracting \(x^\*\) yields an approximate error propagation: \[ e_{n+1} \approx DG(x^\*)\, e_n. \] This linearization is the starting point for most local rate theorems: the behavior of the iteration near the fixed point is governed by the derivative (Jacobian) of the update map.

3.2 Jacobian/spectral radius criteria

The derivative \(DG(x^\*)\) can be analyzed via operator norms or eigenstructure.

3.2.1 Spectral radius and implications for divergence

The spectral radius \(\rho(DG(x^\*))\) is the maximum magnitude of eigenvalues (or, in general operator spectrum). If \(\rho(DG(x^\*))&gt;1\), then errors can amplify along unstable modes, often implying divergence for generic initial perturbations. Conversely, if \(\rho(DG(x^\*))&lt;1\), one expects local attraction, provided the map is well-behaved and norms are compatible with the spectral information.

3.2.2 Norm bounds and induced operator norms

A practical sufficient condition is \[

\|DG(x^\*)\| < 1

\] in an induced operator norm. This implies local contractivity in a neighborhood and yields a Q-linear convergence rate. Even when the spectral radius is less than one, the precise rate can depend on the chosen norm and on how the operator behaves relative to that norm (for instance, non-normal matrices may lead to transient growth even if the asymptotic spectral radius is favorable).

3.3 Stable/unstable manifolds (qualitative view)

In nonlinear settings, the linearized picture may not fully determine global behavior. Qualitatively, the space near a fixed point can split into directions where perturbations decay (stable directions) and directions where perturbations grow (unstable directions). This yields a geometric intuition for why convergence may depend strongly on the initial guess: starting too close in an unstable direction can lead to escape rather than convergence.

3.4 Influence of the initial guess on basin of attraction

When convergence is only guaranteed locally, the initial point must lie in a set from which iterates remain within the region where the linearization or contraction estimate is valid. This set can be small, complicated, and sensitive to the method and problem structure. In practice, iterative solvers often use continuation, damping, or globalization strategies to enlarge the effective basin.

4 Rate of convergence

4.1 Q-linear and R-linear convergence definitions

Rate definitions formalize how quickly errors decrease once the iterates are close enough to the solution.

- Q-linear: there exist constants \(C>0\) and \(q\in(0,1)\) such that eventually \(\|e_{n}\|\le C q^{n}\).
- R-linear: the error ratio approaches a value below one in a limsup sense, often expressed as \(\limsup_{n\to\infty}\|e_{n+1}\|/\|e_n\|\le q<1\).

These distinctions matter because the observable behavior in computations can involve transient phases before the asymptotic regime begins.

4.2 Superlinear convergence mechanisms

Superlinear convergence occurs when the linear term in the error recursion is effectively canceled or dominated by higher-order terms. For differentiable maps, superlinear behavior often corresponds to having a derivative at the solution that is zero or has special structure, making the leading error propagation term vanish. Then the next nonzero term determines how quickly the method accelerates as the iterate approaches \(x^\*\).

4.3 Quadratic convergence and Newton-type methods

Newton’s method for solving \(f(x)=0\) typically converges quadratically near a simple root under suitable smoothness and non-singularity of \(f&#039;(x^\*)\). After linearization, the method cancels the first-order error term, leaving an error recurrence dominated by the square of the current error: \[

\|e_{n+1}\| \le C \|e_n\|^2.

\] This is one reason Newton-type algorithms are popular: once in the local regime, they become very fast.

4.4 Higher-order convergence (order p ≥ 3)

Methods that achieve order \(p\ge 3\) generalize this cancellation idea further. Achieving higher order often requires additional derivative information or carefully designed update formulas (for example, higher-order Taylor expansions or multi-step corrections). In practice, such methods can be attractive when derivative computation is cheap or when high accuracy is needed quickly, though stability and cost per iteration must be considered.

4.5 Examples of rate comparisons in common iterations

Typical comparisons include:

  • Fixed-point iteration with a contracting derivative yields linear convergence.
  • Newton’s method yields quadratic convergence under standard regularity.
  • Damped Newton or relaxed updates can reduce the local order but improve global reliability.
  • Quasi-Newton approaches often recover superlinear behavior when the approximate Jacobian improves sufficiently, though the exact order depends on update rules and problem features.

Rate comparisons help interpret observed iteration counts and guide method selection.

5 Error bounds and a priori/a posteriori estimates

5.1 A priori bounds based on constants (Lipschitz, contraction factors)

A priori bounds estimate the error before running the iteration, using known (or assumed) constants. For contractions with factor \(q\), one can bound \[

\|e_n\| \le \frac{q^n}{1-q}\|x_1-x_0\|

\quad\text{or similar geometric forms,} \] depending on the exact setup. For more general schemes, Lipschitz constants of derivatives or higher derivatives can be used to predict when the method enters the contraction regime and what rate to expect.

5.2 A posteriori estimates using residuals

Since residuals are computable, many methods use estimates of the form \[

\|e_n\| \le \kappa\, \|r_n\|

\] near the solution, where \(\kappa\) depends on properties like invertibility of a Jacobian or local Lipschitz bounds. For Newton-like updates, residual-based logic can support both stopping decisions and adaptive damping choices.

5.3 Relating error norms to computable quantities

Relating error to residual often uses the idea that the residual behaves like a linear approximation to the error. For differentiable problems, Taylor expansions provide:

  • a local model linking \(f(x_n)\) with \(f'(x^\*)e_n\),
- and therefore a bound on \(\|e_n\|\) in terms of \(\|f(x_n)\|\) when \(f'(x^\*)\) is well-conditioned.

In practice, such estimates can be conservative; nevertheless, they help translate theoretical convergence into computable diagnostics.

5.4 Propagation of uncertainty through iterations

Numerical computations involve perturbations (rounding errors, approximate function evaluations, or inexact linear solves). Convergence studies incorporate error propagation, showing how small perturbations affect future iterates. Stability results often depend on whether the iteration map is contractive (which dampens perturbations) or only non-expansive (where perturbations may persist).

6 Convergence of linear iterative methods

6.1 Stationary iterations (splitting methods)

Linear systems are often written in fixed-point form: \[ x = Tx + c \quad\Rightarrow\quad x_{n+1} = Tx_n + c. \] Such schemes are stationary: the same linear update is applied each step. Convergence is determined by properties of the iteration matrix \(T\), including its spectral radius in the appropriate norm.

Splitting methods (like Jacobi and Gauss–Seidel) arise by decomposing operators into parts that are treated explicitly or implicitly.

6.2 Convergence of Jacobi and Gauss–Seidel schemes

For common stationary iterations applied to well-posed linear problems, convergence depends on the structure of the matrix (e.g., diagonal dominance or symmetry/positive definiteness conditions in classical analyses).

  • Jacobi iteration updates each component using values from the previous iterate.
  • Gauss–Seidel uses newly updated components as soon as they are available.

In many standard settings, Gauss–Seidel has a better effective contraction factor than Jacobi, leading to fewer iterations for the same tolerance.

6.3 Successive over-relaxation (SOR) and acceleration intuition

SOR modifies the stationary iteration by introducing a relaxation parameter \(\omega\): \[ x_{n+1} = (1-\omega)x_n + \omega\, \text{(Gauss–Seidel-like update)}. \] With an appropriate choice of \(\omega\), the iteration can damp unfavorable modes faster and accelerate convergence. The analysis typically reduces to how \(\omega\) changes the spectral properties of the effective iteration matrix.

6.4 Krylov-type iterations and operator viewpoints (overview)

Krylov subspace methods (such as GMRES or conjugate gradient, depending on symmetry and definiteness) are not stationary in the same way as Jacobi/SOR; instead, they build approximations in growing subspaces based on matrix-vector products. Convergence theory uses residual minimization or energy norms and often relates performance to the spectrum of the operator and to how the method exploits polynomial approximations to the inverse. This section is commonly treated as an operator-theoretic expansion of the stationarity-based viewpoint.

6.5 Conditioning effects on convergence behavior

Even when an iterative method converges in theory, the rate and iteration count can be heavily influenced by conditioning of the problem, such as sensitivity to eigenvalue clustering or extreme singular values. Conditioning affects both the size of constants in error bounds and the effectiveness of polynomial/rational approximations used in iterative schemes.

7 Nonlinear iterative methods

7.1 Picard iteration and general fixed-point iteration

Picard iteration refers to applying a fixed-point map repeatedly: \[ x_{n+1}=G(x_n). \] For integral or differential equation formulations and many nonlinear operator equations, Picard iteration serves as a basic nonlinear analogue of stationary iterations. Convergence is often established through contraction or monotone operator arguments, leading to existence and sometimes uniqueness.

7.2 Newton’s method convergence conditions

Newton’s method for \(f(x)=0\) is \[ x_{n+1} = x_n - [f&#039;(x_n)]^{-1}f(x_n). \] Local convergence requires:

  • smoothness of \(f\) near \(x^\*\),
  • invertibility of \(f'(x^\*)\) (for a simple root),
  • and an initial guess sufficiently close to \(x^\*\) so that higher-order terms remain controlled.

When these conditions hold, quadratic convergence is typical.

7.3 Quasi-Newton methods and approximate Jacobians

Quasi-Newton methods replace the exact Jacobian inverse or solve with an updated approximation \(B_n^{-1}\) to \(f&#039;(x_n)^{-1}\). Classic updates aim to mimic curvature information while reducing the cost per iteration. Under appropriate assumptions, quasi-Newton schemes can recover superlinear convergence, though the exact rate depends on how the approximation is updated and on how accurately it reflects the true Jacobian.

7.4 Damped/relaxed iterations and line search ideas

Newton-like steps may be damped: \[ x_{n+1}=x_n + \alpha_n s_n, \] where \(s_n\) is the Newton direction and \(\alpha_n\in(0,1]\) is chosen to ensure decrease of a merit function or to satisfy sufficient conditions. Damping sacrifices some local order in exchange for improved global convergence behavior, enlarging the region of attraction.

7.5 Levenberg–Marquardt style damping (conceptual overview)

Levenberg–Marquardt addresses least-squares problems by blending Gauss–Newton behavior with gradient-like stabilization. Conceptually, it adjusts step size based on a damping parameter that prevents steps from becoming too aggressive when the Jacobian approximation is poor or the linearization is unreliable. The goal is to balance rapid progress near the solution with robustness farther away.

8 Robustness and failure modes

8.1 Divergence scenarios and diagnostic indicators

Divergence can occur when:

  • the update map is not locally contractive,
  • the derivative at the fixed point has an unstable eigenvalue direction,
  • or the iteration enters a region where assumptions fail (e.g., the Jacobian becomes ill-conditioned).

Diagnostic indicators include residual growth, erratic oscillations, and increasing norms of iterate differences, though these signals are heuristic unless accompanied by theory.

8.2 Cycling and stagnation behaviors

Some methods may fail to converge but exhibit repeating patterns (cycling) or remain stuck with slowly changing iterates (stagnation). Cycling can happen if the map behaves like an involution or rotates in a way that prevents approaching a fixed point. Stagnation often comes from a mismatch between the iteration and the problem geometry, poor scaling, or the iteration reaching a noise floor due to rounding and inexact solves.

8.3 Sensitivity to perturbations and rounding errors

Finite precision arithmetic perturbs the computed update map. If the method is contractive, perturbations are typically attenuated. If the method is only marginally stable, rounding errors may accumulate or dominate the convergence trend, flattening the observed rate. Robustness analyses quantify how perturbations propagate through linearized dynamics.

8.4 Influence of approximate function/Jacobian evaluations

Inexact evaluations—such as approximate Jacobians, numerical derivatives, or approximate linear solves—introduce additional errors at each step. Convergence can still be achieved if these errors decrease sufficiently fast or if the method tolerates a controlled level of inexactness. Otherwise, the iteration may converge to an approximate solution with a residual floor, or fail to converge entirely.

8.5 Methods for recovery: damping, reinitialization, restarts

When failures occur, common remedies include:

  • damping/relaxation to restore stability,
  • reinitialization using a different starting point,
  • restarts for Krylov-like methods or nonlinear schemes,
  • adaptive tolerance for inexact solves.

These strategies aim to move the iterates back into a regime where theoretical convergence conditions approximately hold.

9 Stopping criteria and practical convergence tests

9.1 Residual-based vs error-based stopping

Error-based stopping (\(\|e_n\|\)) is rarely available directly, so practical algorithms use residual-based criteria such as:
- fixed-point residual: \(\|x_n-G(x_n)\|\),
- root residual: \(\|f(x_n)\|\),
  • or stationarity measures in optimization contexts.

Residual norms are tied to error norms under assumptions, but the equivalence is local; therefore stopping thresholds should reflect expected reliability near the solution.

9.2 Monotone vs non-monotone convergence checks

Some methods produce residuals that decrease monotonically, enabling straightforward checks. Others may exhibit non-monotonic behavior, especially when damping or line search chooses step sizes dynamically. In such cases, convergence tests may use windowed checks (e.g., whether residual has decreased sufficiently over several iterations) rather than requiring strict monotonicity.

9.3 Stopping thresholds and tolerances

Choosing tolerances balances accuracy and computational effort. Typical stopping decisions require:

  • an absolute tolerance (to reach a target accuracy),
  • and possibly a relative tolerance (to scale with problem magnitude).

For ill-conditioned problems, overly strict tolerances may not be meaningful due to uncertainty amplification and floating-point limitations.

9.4 Estimating convergence rate on the fly

Algorithms can estimate an empirical rate using successive residuals or errors proxies, such as computing \[

\frac{\|r_{n+1}\|}{\|r_n\|}

\quad\text{or}\quad

\frac{\log\|r_{n+1}\|-\log\|r_n\|}{\log\|r_n\|-\log\|r_{n-1}\|},

\] to infer whether the method appears linear, superlinear, or stalled. Such estimates are approximate but useful for debugging and performance tuning.

9.5 Computational cost vs convergence guarantees

Stopping early can save time but risks inaccurate solutions if residual-to-error relationships are weak. Stopping too late wastes computation, particularly for methods with expensive iterations (e.g., requiring solves or Jacobian factorization). Practical convergence management combines theoretical guarantees with cost models for each iteration.

10 Special topics and extensions

10.1 Convergence in Banach vs Hilbert spaces

The functional-analytic setting influences which norms and inequalities are available. In Banach spaces, one generally relies on metric and norm completeness plus Lipschitz-type arguments. In Hilbert spaces, additional geometric structure (inner products) enables energy estimates, orthogonality arguments, and stronger convergence claims for certain operator classes.

10.2 Semigroup and iterative regularization perspectives (high-level)

In inverse problems and evolution equations, iterations can be interpreted as discrete approximations of dynamical processes or as regularization schemes. Semigroup viewpoints connect stability and smoothing properties of continuous operators to discrete iteration behavior. Iterative regularization frameworks also address the trade-off between data fidelity and stability against noise.

10.3 Stochastic/perturbed iterations (overview)

When iteration uses randomness (stochastic gradients) or when steps are perturbed, convergence analysis typically becomes probabilistic. The goal is often to show almost-sure or in-expectation convergence, sometimes to neighborhoods of solutions rather than exact points, depending on the noise level and step-size schedule.

10.4 Inexact iteration and tolerances per step

Inexact iterations allow controlled errors in subproblems (e.g., approximate solves for Newton steps). Convergence can be preserved if the inexactness is reduced as the main iteration approaches the solution, or if conditions like summability of errors hold. This extension connects theoretical convergence to practical implementations where exact operations are expensive.

10.5 Connections to dynamical systems viewpoints (qualitative)

Iterative methods can be viewed as discrete dynamical systems \(x_{n+1}=G(x_n)\). Fixed points correspond to equilibria, and convergence corresponds to trajectories attracted to equilibria. Qualitative dynamics tools—stability, basins, and bifurcation-like behavior—provide intuition for why some iterations converge rapidly while others exhibit complex behavior.

11 Worked examples and canonical demonstrations

11.1 Contraction example in one dimension

Consider a one-dimensional update \(x_{n+1}=G(x_n)\) with \(G(x)=a x + b\) where \(a<1\). The map contracts distances by \(a\), so there is a unique fixed point \(x^\*=b/(1-a)\). The error satisfies \(e_{n+1}=a e_n\), yielding geometric decay \(e_n=a^ne_0\). This example illustrates how global contraction directly produces existence, uniqueness, and a rate.

11.2 Spectral-radius example for linear fixed-point iterations

For a linear fixed-point system \(x_{n+1}=T x_n + c\), the error evolves as \(e_{n+1}=T e_n\). If \(\rho(T)<1\), then \(T^n\to 0\), implying \(e_n\to 0\). If \(\rho(T)>1\), there exists an eigen-direction where errors grow, so divergence is typical for initial guesses with a nontrivial component in that direction. This example shows how spectral information predicts long-term behavior.

11.3 Newton convergence example near a simple root

Take \(f(x)=x^2-2\), whose simple roots are \(x^\*=\sqrt{2}\) and \(-\sqrt{2}\). Newton’s iteration is \[ x_{n+1}=x_n - \frac{x_n^2-2}{2x_n}=\frac12\left(x_n+\frac{2}{x_n}\right). \] For \(x_0\) close to \(\sqrt{2}\), one observes rapid error reduction consistent with quadratic convergence. The mechanism is explained by Taylor expansion: the leading linear error term cancels, leaving a quadratic remainder.

11.4 A damping/relaxation example to ensure convergence

Suppose a fixed-point map is locally unstable, but a relaxed iteration \[ x_{n+1}=(1-\omega)x_n+\omega G(x_n) \] can be tuned so that the effective derivative has norm below one near the fixed point. Choosing \(\omega\in(0,1)\) appropriately can convert an unstable update into a contractive one, improving robustness at the cost of potentially lower local order compared with the undamped method.

11.5 Computing rate from iterates (toy datasets)

A toy demonstration uses computed residuals \(r_n\) to estimate an empirical rate. For instance:

  • If the residual decreases approximately by a constant factor each step, the method behaves linearly.
  • If the residual roughly squares at each step, it indicates quadratic behavior.
By fitting \(\log\|r_n\|\) vs. iteration index (for linear) or comparing successive ratios (for superlinear), one can classify the observed regime and decide whether the iteration is functioning as expected.