The early history of convergence acceleration methods

The history of convergence acceleration methods in the 17th century is surveyed. Acceleration methods are classified into three categories.     

Upper bounds for convergence rates of acceleration methods with initial iterations

GMRES(n,k), a version of GMRES for the solution of large sparse linear systems, is introduced. A cycle of GMRES(n,k) consists of n Richardson iterations followed by k iterations of GMRES. Such cycles can be repeated until convergence is achieved. The advantage in this approach is in the opportunity to use moderate k, which results in time and memory saving. Because the number of inner products among the vectors of iteration is about k^2/2, using a moderate k is particularly attractive on message-passing parallel architectures, where inner products require expensive global communication. The present analysis provides tight upper bounds for the convergence rates of GMRES(n,k) for problems with diagonalizable coefficient matrices whose spectra lie in an ellipse in 0. The advantage of GMRES(n,k) over GMRES(k) is illustrated numerically.     

A note on two convergence acceleration methods for ordinary continued fractions

In this note we compare two recent methods of convergence acceleration for ordinary continued fractions, the first one introduced by Thron and Waadeland [13], and further developed by Brezinski [1], the second one by Jacobsen and Waadeland [4,5].     

On the stability of a class of convergence acceleration methods for power series

In this paper we study the problem of evaluating the sum of a power series whose terms are given numerically with a moderate accuracy. For a large class of divergent series a sum may be defined using analytic continuation. This sum may be estimated using the values of a finite number of terms. However, it is established here that the accuracy of this estimate will generally deteriorate if we use an ever-growing number of terms. A result on the stability of product quadrature is also obtained as a corollary of our main stability theorem.Dedicated to professor Germund Dahlquist, on the occasion of his 60th birthday     

Gaussian quadrature and acceleration of convergence

The aim of this paper is to take up again the study done in previous papers, to the case where the integrand possesses an algebraic singularity within the interval of integration. The singularities or poles close to the interval of integration considered in this paper are only real or purely imaginary. This revised version was published online in August 2006 with corrections to the Cover Date.     

Stable convergence acceleration using Laplace transforms

Summary We consider the general class of power series where the terms may be expressed as the Laplace transforms of known functions. The sum of the series can then be evaluated efficiently and accurately by means of quadrature schemes, recently published by Frank Stenger. The method works also far outside the region of convergence as will be illustrated by numerical examples.Dedicated to Professor Lothar Collatz on the occasion of his 75th birthday     

A method of convergence acceleration of some continued fractions

A new method of convergence acceleration is proposed for continued fractions , where and are polynomials in (, ) for sufficiently large. It uses the fact that the modified approximant approaches the continued fraction value, if is sufficiently close to the th tail . Presented method is of iterative character; in each step, by means of an approximation , it produces a new better approximation of the th tail . Formula for is very simple and contains only arithmetical operations. Hence described algorithm is fully rational.     

A method of convergence acceleration of some continued fractions II

Most of the methods for convergence acceleration of continued fractions K(a _m /b _m ) are based on the use of modified approximants S _m (ω _m ) in place of the classical ones S _m (0), where ω _m are close to the tails f ^(m) of the continued fraction. Recently (Nowak, Numer Algorithms 41(3):297–317, 2006), the author proposed an iterative method producing tail approximations whose asymptotic expansion accuracies are being improved in each step. This method can be successfully applied to a convergent continued fraction K(a _m /b _m ), where $a_m = \alpha_{-2} m^2 + \alpha_{-1} m + \ldots$ , b _m ?=?β _???1 m?+?β ₀?+?... (α _???2?≠?0, $|\beta_{-1}|^2+|\beta_{0}|^2\neq 0$ , i.e. $\deg a_m=2$ , $\deg b_m\in\{0,1\}$ ). The purpose of this paper is to extend this idea to the class of two-variant continued fractions K (a _n /b _n ?+?a _n ′/b _n ′) with a _n , a _n ′, b _n , b _n ′ being rational in n and $\deg a_n=\deg a_n'$ , $\deg b_n=\deg b_n'$ . We give examples involving continued fraction expansions of some elementary and special mathematical functions.     

Local convergence of tensor methods

Mathematical Programming - In this paper, we study local convergence of high-order Tensor Methods for solving convex optimization problems with composite objective. We justify local superlinear...     

The convergence of shooting methods

Shooting methods for nonlinear boundary value problems are examined. It is shown that the methods converge whenever the problem is well posed in the sense that the solution to be computed is isolated.     

Multiplier convergence in trust-region methods with application to convergence of decomposition methods for MPECs

We study piecewise decomposition methods for mathematical programs with equilibrium constraints (MPECs) for which all constraint functions are linear. At each iteration of a decomposition method, one step of a nonlinear programming scheme is applied to one piece of the MPEC to obtain the next iterate. Our goal is to understand global convergence to B-stationary points of these methods when the embedded nonlinear programming solver is a trust-region scheme, and the selection of pieces is determined using multipliers generated by solving the trust-region subproblem. To this end we study global convergence of a linear trust-region scheme for linearly-constrained NLPs that we call a trust-search method. The trust-search has two features that are critical to global convergence of decomposition methods for MPECs: a robustness property with respect to switching pieces, and a multiplier convergence result that appears to be quite new for trust-region methods. These combine to clarify and strengthen global convergence of decomposition methods without resorting either to additional conditions such as eventual inactivity of the trust-region constraint, or more complex methods that require a separate subproblem for multiplier estimation.      

Linearity-preserving flux correction and convergence acceleration for constrained Galerkin schemes

This paper is concerned with the development of general-purpose algebraic flux correction schemes for continuous (linear and multilinear) finite elements. In order to enforce the discrete maximum principle (DMP), we modify the standard Galerkin discretization of a scalar transport equation by adding diffusive and antidiffusive fluxes. The result is a nonlinear algebraic system satisfying the DMP constraint. An estimate based on variational gradient recovery leads to a linearity-preserving limiter for the difference between the function values at two neighboring nodes. A fully multidimensional version of this scheme is obtained by taking the sum of local bounds and constraining the total flux. This new approach to algebraic flux correction provides a unified treatment of stationary and time-dependent problems. Moreover, the same algorithm is used to limit convective fluxes, anisotropic diffusion operators, and the antidiffusive part of the consistent mass matrix.The nonlinear algebraic system associated with the constrained Galerkin scheme is solved using fixed-point defect correction or a nonlinear SSOR method. A dramatic improvement of nonlinear convergence rates is achieved with the technique known as Anderson acceleration (or Anderson mixing). It blends a number of last iterates in a GMRES fashion, which results in a Broyden-like quasi-Newton update. The numerical behavior of the proposed algorithms is illustrated by a grid convergence study for convection-dominated transport problems and anisotropic diffusion equations in 2D.     

Generalizations of Shanks transformation and corresponding convergence acceleration algorithms via pfaffians

Numerical Algorithms - Firstly, a new sequence transformation that can be expressed in terms of a ratio of two pfaffians is derived based on a special kernel. It can be regarded as a direct...     

Asymptotic expansions and acceleration of convergence for higher order iteration processes

Summary We analyze the convergence behavior of sequences of real numbers {x _n }, which are defined through an iterative process of the formx _n :=T(x _n –1), whereT is a suitable real function. It will be proved that under certain mild assumptions onT, these numbersx _n possess an asymptotic (error) expansion, where the type of this expansion depends on the derivative ofT in the limit point ; this generalizes a result of G. Meinardus [6].It is well-known that the convergence of sequences, which possess an asymptotic expansion, can be accelerated significantly by application of a suitable extrapolation process. We introduce two types of such processes and study their main properties in some detail. In addition, we analyze practical aspects of the extrapolation and present the results of some numerical tests. As we shall see, even the convergence of Newton's method can be accelerated using the very simple linear extrapolation process.Dedicated to Professor Dr. Günter Meinardus on the occasion of his 65^th birthday     

Generalized conjugate-gradient acceleration of nonsymmetrizable iterative methods

Conjugate-gradient acceleration provides a powerful tool for speeding up the convergence of a symmetrizable basic iterative method for solving a large system of linear algebraic equations with a sparse matrix. The object of this paper is to describe three generalizations of conjugate-gradient acceleration which are designed to speed up the convergence of basic iterative methods which are not necessarily symmetrizable. The application of the procedures to some commonly used basic iterative methods is described.     

A new approach to acceleration of convergence of a sequence of vectors

The vector epsilon algorithm (VEA) has many advantages as a method for accelerating the convergence of a sequence of vectors. A vector Padé approximantP (z)/Q(z) of type [n/2k] can be associated with each entry of the vector epsilon table. In the scalar case, it reduces to the Padé approximantp(z)/q(z) of type [n–k/k]. It is thought that the disadvantages of VEA are (indirectly) attributable to the positivity property ofQ(x), x , recalling that in the scalar case,Q(z)q(z) ². In this paper, a specification of a polynomial (z) of degreek is given, such that (z)²Q(z). The coefficients of (z) specify an accelerator for a sequence of vectors which should avoid many of the numerical difficulties of VEA.This work was supported in part by the EC-HCM project ROLLS under contract CHRX-CT93-0416.     

Asymptotic behavior of the Eckhoff method for convergence acceleration of trigonometric interpolation

Convergence acceleration of the classical trigonometric interpolation by the Eckhoff method is considered, where the exact values of the jumps are approximated by solution of a system of linear equations. The accuracy of the jump approximation is explored and the corresponding asymptotic error of interpolation is derived. Numerical results validate theoretical estimates.     

A nonlinear method for the acceleration of the convergence of multidimensional sequences

In this paper a nonlinear method for the acceleration of multidimensional sequences {S_k} is described. The method is developed by generalising a connection between the ε-algorithm and Padé approximants. A convergence result and an application to the numerical calculation of multiple integrals are briefly discussed.