1. Motivation and basic definitions

Sequence acceleration refers to techniques that replace a slowly converging sequence \(\{s_n\}\) by a new sequence \(\{\tilde{s}_n\}\) (computed from finitely many terms of \(\{s_n\}\)) such that \(\tilde{s}_n\to s\) more rapidly to the same limit \(s\). The defining idea is to modify the observable sequence so that the dominant part of the error is reduced, often by canceling leading asymptotic contributions.

These methods are motivated by the practical reality that many algorithms produce approximations with predictable error patterns. Rather than increasing computational effort to achieve finer accuracy, sequence acceleration uses existing data to improve the convergence rate.

1.1 Convergence speed and error models

Convergence speed is commonly quantified by how fast the error \(e_n=s_n-s\) decays as \(n\) grows. Many acceleration methods implicitly assume an error model of the form \[ e_n \sim a\,\phi(n), \] where \(\phi(n)\) captures the leading behavior (e.g., \(\phi(n)=q^n\) for geometric decay or \(\phi(n)=n^{-p}\) for algebraic decay). When the dominant term is known (or sufficiently well-approximated), one can construct transformations that eliminate it, leaving a smaller next-order remainder.

In numerical contexts, errors may include both truncation error (from an approximation scheme) and perturbations from floating-point round-off or measurement noise. Acceleration aims primarily at truncation error, but its sensitivity can also amplify other error sources, which is addressed in later sections.

1.2 Sequence vs. series acceleration

Sequence acceleration typically targets a sequence of approximations. Series acceleration targets a series partial sum \[ s_n=\sum_{k=0}^{n} a_k \] where \(s_n\) converges slowly to the series sum \(s\). Because partial sums form a sequence, series acceleration can often be phrased as sequence acceleration applied to \(\{s_n\}\). The distinction is mostly one of context and typical structure: series methods often exploit properties of the terms \(a_k\) such as alternating signs, regular asymptotic expansions, or known remainder behavior.

1.3 Terminology: extrapolation, transformation, and acceleration operators

Terminology varies across texts. “Extrapolation” usually refers to predicting the limit value from a sequence of approximations. “Transformation” emphasizes that a mapping is applied to existing data. “Acceleration operator” denotes a specific algorithmic rule that produces \(\tilde{s}_n\) from a finite window of input terms.

A typical pattern is:

  • Choose an operator \(T\).
  • Define \(\tilde{s}_n = T(s_{n}, s_{n+1}, \ldots, s_{n+m})\).
  • Study how \(\tilde{s}_n-s\) behaves relative to \(s_k-s\).

1.4 Assumptions on the input sequence

Most acceleration schemes require at least some regularity:

  • The sequence should approach the limit in a controlled manner (monotone convergence, alternating convergence, or a stable asymptotic form).
  • The error should admit an asymptotic expansion whose leading terms are not pathologically irregular.
  • The numerical evaluation of terms should be sufficiently accurate so that the transformation does not become dominated by round-off.

When the input sequence is irregular (e.g., strongly oscillatory without a discernible envelope, or contaminated by significant noise), many classical methods lose effectiveness or become unstable.

2. Classic acceleration methods

Classical methods are often derived from simple local models of the error and are designed to cancel one or more leading asymptotic components.

2.1 Aitken’s Δ² process

Aitken’s \(\Delta^2\) process accelerates sequences that converge linearly with respect to an index step. It uses three consecutive terms.

For a sequence \(\{s_n\}\), define the forward differences \[ \Delta s_n = s_{n+1}-s_n,\quad \Delta^2 s_n = \Delta(\Delta s_n)=s_{n+2}-2s_{n+1}+s_n. \] The accelerated value is \[ \tilde{s}_n = s_n - \frac{(\Delta s_n)^2}{\Delta^2 s_n}, \] provided \(\Delta^2 s_n\neq 0\).

2.1.1 Derivation from local linear error behavior

If the error behaves locally like \[ e_{n+1} \approx \lambda e_n \]

for some \(\lambda\) (with \(\lambda<1\)), then \(s_n\) can be approximated by an affine-exponential form near the index range. In that setting, \(\Delta s_n\) and \(\Delta^2 s_n\) encode the geometric component of the error, and the formula for \(\tilde{s}_n\) effectively removes the dominant exponential mode, yielding a faster approach to the limit.

2.1.2 Practical implementation and stopping criteria

Implementation typically proceeds by:

  • Computing \(\Delta s_n\) and \(\Delta^2 s_n\) from three terms.
- Applying the formula when \(\Delta^2 s_n\) is not too small relative to \(\Delta s_n\), to avoid division by nearly zero quantities.
  • Stopping when successive accelerated estimates stabilize or when an external error estimate indicates no further improvement.

Because Aitken’s method can be sensitive when \(\Delta^2 s_n\) is small, careful safeguards are often necessary in floating-point arithmetic.

2.2 Euler transformation for alternating series

The Euler transformation accelerates certain alternating series, especially those whose term magnitudes decay regularly. For an alternating series with partial sums \(s_n\), the Euler transform reshapes the convergence by effectively replacing a slowly decreasing alternating remainder with a faster-decaying one.

2.2.1 Conditions for applicability

Applicability commonly relies on:

  • Alternating signs in the terms or a predictable alternation in the remainder.
  • A sufficiently smooth decay of term magnitudes so that remainder estimates admit a structured asymptotic form.
  • No dominant non-alternating component that would undermine the cancellation mechanism.

2.2.2 Effect on convergence rate

When conditions hold, the Euler transform can significantly reduce the leading asymptotic behavior of the alternating remainder. In favorable cases, it improves an algebraic convergence rate by canceling the largest-order terms in an expansion for the tail of the series. The achievable rate depends on how many terms of regularity are effectively exploited by the transformation.

2.3 Shanks’ transformation

Shanks’ transformation generalizes the idea of eliminating leading error terms using a rational form inferred from a finite set of sequence values. It is closely related to Padé-type approximants and continued-fraction constructions.

Given three consecutive values \(s_{n}, s_{n+1}, s_{n+2}\), one form of Shanks’ transformation can be written so that the output cancels an assumed leading error component by solving for parameters consistent with these terms.

2.3.1 Relation to Padé-type approximants

In many settings, Shanks’ transformation corresponds to approximants that mimic the behavior of a function’s Taylor series filtered through rational approximation. When the underlying sequence behaves like sampling of a function with a meromorphic structure (or when an asymptotic expansion has a rational-like remainder), the transformation aligns with rational extrapolation ideas.

This connection provides intuition for why Shanks-type methods are effective on sequences whose errors resemble a superposition of simple decaying modes.

2.3.2 Choice of parameters and stability

Practical variants often involve selecting a window length (how many terms are used) and handling potential numerical instability:

  • Larger windows may remove more leading error contributions but can worsen conditioning.
  • If the sequence values are nearly linearly dependent in the relevant algebraic system, small round-off errors can cause large perturbations.
  • Stability checks can be based on changes between consecutive transformed estimates and on the magnitude of denominators in the rational expressions.

2.4 Wynn’s ε-algorithm

Wynn’s ε-algorithm is a widely used recursive method for sequence transformation that systematically constructs a table of accelerated approximations. It generalizes Shanks’ approach and can be applied without explicitly specifying an error model, though underlying assumptions remain implicit.

2.4.1 Continued-fraction viewpoint

The ε-algorithm can be interpreted through continued fractions: each new diagonal entry corresponds to a rational function approximation whose coefficients are determined from the input data. This view explains why the method often captures multi-mode decay better than single-step formulas.

2.4.2 Recursive computation

A standard recursion defines quantities \(\varepsilon_{k}^{(n)}\) arranged in a triangular table. Typically:

  • Even-indexed entries \(\varepsilon_{2m}^{(n)}\) provide accelerated approximations.
  • Odd-indexed entries \(\varepsilon_{2m+1}^{(n)}\) serve as auxiliary quantities defined by a recurrence involving neighboring entries.

The computational procedure uses only additions, subtractions, and divisions, so numerical safeguards (e.g., avoiding divisions by very small denominators) are important.

2.5 Richardson extrapolation (sequence form)

Richardson extrapolation accelerates convergence by combining approximations computed at different “step sizes” or scales. In its sequence form, it assumes a known scaling relationship between successive approximations.

2.5.1 Step-size scaling and order cancellation

Suppose the approximation depends on a parameter \(h_n\) and admits an expansion \[ s_n = s + c h_n^p + \text{higher-order terms}. \] If \(h_{n+1}\) is a scaled version of \(h_n\) (for instance, \(h_{n+1}=h_n/\rho\)), then one can form a linear combination of two approximations that cancels the \(h^p\) term. The resulting estimate has a higher-order remainder, often increasing the convergence rate by the same factor that the canceled term was dominant.

2.5.2 Error order estimation

In practice, the exponent \(p\) may not be exactly known. Methods based on Richardson extrapolation may therefore require either:

  • Prior knowledge of the asymptotic order,
  • Estimation of \(p\) from observed error differences, or
  • Use of a flexible variant where the exponent is treated as an additional quantity inferred from data.

If the assumed order is wrong, cancellation may fail or even degrade results, illustrating the importance of robust diagnostics.

3. Interpolation and rational-function perspectives

Many acceleration schemes can be reinterpreted as building an approximating function—usually a polynomial or rational function—from the available sequence values and then evaluating it at the limit location.

3.1 Transformations as sequence-to-sequence maps

A broad perspective treats acceleration as a map \(T\) from a finite list of samples to a new value. Under suitable assumptions, the transformation corresponds to:

  • Interpolating a model of the error behavior,
  • Constructing an auxiliary approximant (polynomial or rational) whose evaluation yields the accelerated estimate.

This viewpoint connects acceleration with classical approximation theory.

3.2 Polynomial interpolation and extrapolation

If one assumes that the sequence values \(s_n\) (or related remainders) can be approximated by a polynomial in \(1/n\) near infinity, then fitting such a polynomial and evaluating at \(1/n=0\) produces an extrapolated limit. This underlies many simple Richardson-style and interpolation-based constructions.

However, polynomial extrapolation can be unstable if the fitted polynomial oscillates (a manifestation of ill-conditioning in high-degree fits). Consequently, rational approaches are often preferred when the sequence has singularities or multi-scale behavior.

3.3 Padé approximants and their role in acceleration

Padé approximants approximate a function by a ratio of two polynomials. In acceleration, they appear because rational approximants can represent meromorphic behavior and can mimic the structure of errors that resemble sums of decaying exponentials or algebraic tails.

When the sequence is generated by evaluating partial sums or iterative schemes that correspond to function expansions, Padé-type methods can produce dramatically improved convergence by capturing poles or branch-like features in the approximated remainder.

3.4 Determinantal forms and computational variants

Rational interpolation and Padé approximants admit determinantal formulas that express the approximants using determinants of Hankel or related matrices built from sequence values. Such formulas offer:

  • Insight into how coefficients depend on input samples.
  • Alternative computational routes, sometimes enabling reuse of intermediate quantities.

Different variants trade between algebraic clarity, numerical stability, and computational cost.

3.5 Modeling remainders with asymptotic expansions

A common modeling strategy is to assume an asymptotic expansion for the remainder: \[ s_n = s + \sum_{j=1}^{m} c_j\,\phi_j(n) + \text{smaller terms}, \] where \(\phi_j(n)\) are known or guessed basis functions (powers, exponentials, logarithmic corrections, etc.). Acceleration methods then choose parameters so that the leading terms in this expansion are canceled. Interpolation and rational-function perspectives provide a computational framework for effecting this cancellation.

4. General theory of convergence improvement

General results organize acceleration methods around error cancellation, nonlinear transformation behavior, and the interplay between theoretical convergence and numerical stability.

4.1 Asymptotic cancellation of leading error terms

The central mechanism is cancellation of dominant asymptotic contributions. If the remainder has an expansion and an acceleration rule is designed so that the first \(r\) components vanish, then the transformed error is often reduced to the next non-canceled order. This can yield a higher effective convergence rate.

The effectiveness depends on whether:

  • The assumed error basis matches the actual asymptotic behavior.
  • The transformation uses enough degrees of freedom (window size) to cancel the leading terms.
  • The computation is stable enough that rounding does not dominate the reduced remainder.

4.2 Nonlinear transformations and fixed points

Many acceleration schemes are nonlinear because they involve rational expressions or recursive definitions. Nonlinearity affects both analysis and behavior. In some frameworks, one studies fixed points or invariant subspaces for the transformation: if the transformation maps sequences with a certain error structure into sequences with higher-order remainder, then repeated or diagonal extraction from the transformation table can be justified.

This theory often borrows from approximation theory and dynamical system ideas, though the details vary by method.

4.3 Stability and sensitivity to round-off

A key practical question is whether small perturbations in \(s_n\) produce small changes in \(\tilde{s}_n\). Stability is related to conditioning of the algebraic system implicit in the transformation:

  • When denominators in formulas become small, sensitivity increases.
  • When input values are nearly linearly dependent in the constructed interpolation space, the transformation can amplify noise.

Asymptotic error reduction may therefore come at the cost of numerical robustness, especially for large windows or near-singular configurations.

4.4 Robustness under model mismatch

Acceleration assumes some structure in the error. If the sequence violates the assumed model (e.g., different decay law, irregular oscillations, or missing terms), cancellation may be incomplete. Robustness is improved when:

  • The method does not rely heavily on a precise exponent (unlike basic Richardson with unknown order).
  • The transformation adapts across a table so that diagonals correspond to different effective models.
  • Diagnostics detect when the transformation no longer improves accuracy.

4.5 Convergence theorems and rate comparisons (overview)

Convergence improvement theorems generally provide:

  • Conditions under which the transformed sequence converges to the same limit.
  • Statements about accelerated rate or elimination of specific error orders.
  • Comparisons across methods in terms of how many leading terms can be canceled given a certain amount of data.

Because different methods rely on different structures (alternation, rational remainder, continued fraction representation), rate comparisons are often conditional rather than universal.

5. Efficiency and numerical considerations

Even when a method is theoretically effective, its performance depends on cost, conditioning, and reliable stopping criteria.

5.1 Computational cost vs. achieved acceleration

Acceleration can reduce the number of original terms needed for a given accuracy, but the transformation itself introduces overhead:

  • Some transformations require additional arithmetic and storage (e.g., table-based schemes like ε-algorithm).
  • Others are lightweight (e.g., Aitken’s Δ² uses three terms).

Efficiency is assessed by accuracy gained per unit runtime, often under realistic floating-point constraints.

5.2 Data requirements: number of terms and smoothness

Most schemes require a window of several consecutive terms. Larger windows can cancel more leading asymptotic components but require:

  • More computed input values.
  • Greater regularity of the sequence to avoid instability or overfitting.

Smoothness in the asymptotic sense (controlled changes in differences, predictable decay envelopes) tends to correlate with successful acceleration.

5.3 Conditioning and ill-conditioning

Transformations involving division by small quantities or solving implicitly determined linear systems can be ill-conditioned. Conditioning can worsen when:

  • The remainder becomes very small (leading to denominators near machine precision).
  • The sequence has near-degenerate structure in the relevant algebraic basis.
  • High-order extrapolation amplifies floating-point noise.

Mitigations include limiting window sizes, using stabilization techniques, and combining multiple diagonals or transforms.

5.4 Choice of window size (indices) in practical algorithms

Window selection affects the balance between:

Practical workflows typically compute a range of transformed values across indices and then select the best estimate based on consistency, expected monotonicity of error indicators, or agreement across different methods.

5.5 Stopping rules and error estimation

Stopping rules decide when to stop increasing the amount of input data or when to accept an accelerated approximation. Because the true error is unknown, one uses proxies such as:

  • Differences between successive accelerated estimates,
  • Residual checks in the underlying iterative scheme (when available),
  • Comparisons across methods or across nearby diagonals,
  • Externally known target values in benchmark situations.

Reliable stopping criteria are essential to avoid “false convergence,” where the transformed sequence appears stable while error is dominated by noise.

6. Applications in analysis and computation

Sequence acceleration is used wherever limits are approached slowly, including iterative numerical methods and the numerical evaluation of series.

6.1 Accelerating limits from iterated methods

Many iterative algorithms produce approximations \(s_n\) that converge linearly or with predictable asymptotic patterns. Applying acceleration to the resulting sequence can reduce the number of iterations required for a desired tolerance.

In such applications, acceleration is often paired with diagnostics to ensure that the iterates behave regularly enough for the chosen transform.

6.2 Series acceleration in numerical evaluation

When a quantity is defined by a slowly convergent series, acceleration can improve numerical evaluation by transforming the sequence of partial sums. This is especially important when truncating the series early would incur large tail errors.

Series acceleration methods often exploit structural properties such as alternation, known term asymptotics, or recurrence relations for the series coefficients.

6.3 Summation of alternating and slowly decaying terms

Alternating series are frequently amenable to Euler-type transformations and related rational-extrapolation ideas. For slowly decaying terms (e.g., algebraic tails), cancellation of leading tail contributions can substantially improve convergence.

The practical challenge is ensuring that the assumed decay regime has been reached; early terms may not reflect the asymptotic form and can reduce effectiveness.

6.4 Spectral methods and post-processing of computed sequences

In spectral and pseudospectral computations, one may obtain sequences of approximations indexed by resolution parameters (e.g., number of modes). If the spectral error decays slowly due to regularity limitations or boundary effects, acceleration can be used as post-processing to extrapolate to the infinite-resolution limit.

Because spectral errors may reflect mixed exponential/algebraic behaviors, rational and ε-algorithm approaches can be particularly useful.

6.5 Benchmarks and typical performance metrics

Performance is commonly reported using:

  • Reduction in number of terms/iterations to reach a target accuracy,
  • Observed order of convergence after transformation,
  • Robustness measures such as stability under perturbations and sensitivity to floating-point noise,
  • Computational throughput (time per accurate digit).

Benchmarks often compare multiple acceleration schemes on the same test family to reveal which error models they match best.

7. Practical workflow and diagnostics

Successful use of acceleration depends on monitoring behavior, comparing schemes, and handling irregular input.

7.1 Monitoring convergence and detecting divergence

Before applying a transform, one checks whether the underlying sequence is approaching a plausible limit:

  • Examine whether \(s_{n+1}\) and \(s_n\) get closer.
  • Track differences \(\Delta s_n\) to detect oscillations or growth.
  • Identify sequences where the transformation produces wildly varying estimates, suggesting divergence or model failure.

7.2 Cross-checking with multiple acceleration schemes

Because different transforms rely on different structural assumptions, cross-checking is a practical safeguard:

  • Compare Aitken-type results with ε-algorithm diagonals or rational interpolation estimates.
  • If accelerated outputs agree within expected tolerance, confidence increases.
  • If only one method yields stability while others diverge, the result may be suspect.

7.3 Handling irregular inputs and noise

When input terms are noisy or irregular, classical acceleration formulas may amplify errors. Common strategies include:

  • Using smaller windows to reduce sensitivity.
  • Smoothing or averaging input terms (when theoretically justified).
  • Switching to methods that effectively regularize through table-based rational approximation.

If noise level dominates the remainder signal, no deterministic acceleration can reliably recover the true limit.

7.4 Visualization of transformed sequences

Plotting both the original and transformed estimates versus index can provide qualitative insight:

  • Accelerated convergence appears as a rapid approach to a plateau.
  • Instability appears as rapid oscillations between adjacent transformed values.
  • “Late onset” behaviors can be detected by observing when the transform begins to consistently improve.

Visualization is especially helpful during method selection and debugging.

7.5 Common failure modes and mitigations

Common failure modes include:

  • Division by nearly zero leading to spurious large outputs.
  • Over-aggressive window sizes producing ill-conditioned rational fits.
  • Model mismatch causing cancellation of the wrong components.
  • False convergence where accelerated values stabilize due to floating-point rounding rather than true remainder reduction.

Mitigations include choosing conservative window sizes, using stability checks on denominators, relying on agreement across methods, and incorporating error proxies into stopping decisions.