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     

Determinantal representations for the J transformation

Summary. The iterative J transformation [Homeier, H. H. H. (1993): Some applications of nonlinear convergence accelerators. Int. J. Quantum Chem. 45, 545-562] is of similar generality as the well-known E algorithm [Brezinski, C. (1980): A general extrapolation algorithm. Numer. Math. 35, 175-180. Havie, T. (1979): Generalized Neville type extrapolation schemes. BIT 19, 204-213]. The properties of the J transformation were studied recently in two companion papers [Homeier, H. H. H. (1994a): A hierarchically consistent, iterative sequence transformation. Numer. Algo. 8, 47-81. Homeier, H. H. H. (1994b): Analytical and numerical studies of the convergence behavior of the J transformation. J. Comput. Appl. Math., to appear]. In the present contribution, explicit determinantal representations for this sequence transformation are derived. The relation to the Brezinski-Walz theory [Brezinski, C., Walz, G. (1991): Sequences of transformations and triangular recursion schemes, with applications in numerical analysis. J. Comput. Appl. Math. 34, 361-383] is discussed. Overholt's process [Overholt, K. J. (1965): Extended Aitken acceleration. BIT 5, 122-132] is shown to be a special case of the J transformation. Consequently, explicit determinantal representations of Overholt's process are derived which do not depend on lower order transforms. Also, families of sequences are given for which Overholt's process is exact. As a numerical example, the Euler series is summed using the J transformation. The results indicate that the J transformation is a very powerful numerical tool. Received May 24, 1994 / Revised version received November 11, 1994     

A Levin-type algorithm for accelerating the convergence of Fourier series

A nonlinear sequence transformation is presented which is able to accelerate the convergence of Fourier series. It is tailored to be exact for a certain model sequence. As in the case of the Levin transformation and other transformations of Levin-type, in this model sequence the partial sum of the series is written as the sum of the limit (or antilimit) and a certain remainder, i.e., it is of Levin-type. The remainder is assumed to be the product of a remainder estimate and the sum of the first terms oftwo Poincaré-type expansions which are premultiplied by two different phase factors. This occurrence of two phase factors is the essential difference to the Levin transformation. The model sequence for the new transformation may also be regarded as a special case of a model sequence based on several remainder estimates leading to the generalized Richardson extrapolation process introduced by Sidi. An algorithm for the recursive computation of the new transformation is presented. This algorithm can be implemented using only two one-dimensional arrays. It is proved that the sequence transformation is exact for Fourier series of geometric type which have coefficients proportional to the powers of a numberq, |q|<1. It is shown that under certain conditions the algorithm indeed accelerates convergence, and the order of the convergence is estimated. Finally, numerical test data are presented which show that in many cases the new sequence transformation is more powerful than Wynn's epsilon algorithm if the remainder estimates are properly chosen. However, it should be noted that in the vicinity of singularities of the Fourier series the new sequence transformation shows a larger tendency to numerical instability than the epsilon algorithm.     

Small transversals in hypergraphs

For each positive integerk, we consider the setA _k of all ordered pairs [a, b] such that in everyk-graph withn vertices andm edges some set of at mostam+bn vertices meets all the edges. We show that eachA _k withk2 has infinitely many extreme points and conjecture that, for every positive , it has only finitely many extreme points [a, b] witha. With the extreme points ordered by the first coordinate, we identify the last two extreme points of everyA _k , identify the last three extreme points ofA ₃, and describeA ₂ completely. A by-product of our arguments is a new algorithmic proof of Turán's theorem.     

Acceleration methods based on convergence tests

Summary In this paper we propose an acceleration method based on a general convergence test and depending on an auxiliary sequence (x _n). For different choices of (x _n) we obtain some known and some new transformations and for each one sufficient conditions for acceleration are given.     

On richardson extrapolation for finite difference methods on regular grids

Summary Difference solutions of partial differential equations can in certain cases be expanded by even powers of a discretization parameterh. If we haven solutions corresponding to different mesh widthsh ₁,...,h _n we can improve the accuracy by Richardson extrapolation and get a solution of order 2n, yet only on the intersection of all grids used, i.e. normally on the coarsest grid. To interpolate this high order solution with the same accuracy in points not belonging to all grids, we need 2n points in an interval of length (2n–1)h ₁.This drawback can be avoided by combining such an interpolation with the extrapolation byh. In this case the approximation depends only on grid points in an interval of length 3/2h ₁. The length of this interval is independent of the desired order.By combining this approach with the method of Kreiss, boundary conditions on curved boundaries can be discretized with a high order even on coarse grids.This paper is based on a lecture held at the 5th Sanmarinian University Session of the International Academy of Sciences San Marino, at San Marino, 1988-08-27-1988-09-05     

A note on a conjecture of Ryser

A special case of a conjecture of Ryser states that if a 3-partite 3-uniform hypergraph has at mostv pairwise disjoint edges then there is a set of vertices of cardinality at most 2v meeting all edges of the hypergraph. The best known upper bound for the size of such a set is (8/3)v, given by Tuza [7]. In this note we improve this to (5/2)v.     

Packing random intervals

Summary Letn random intervalsI ₁, ...,I _n be chosen by selecting endpoints independently from the uniform distribution on [0.1]. Apacking is a pairwise disjoint subset of the intervals; itswasted space is the Lebesgue measure of the points of [0,1] not covered by the packing. In any set of intervals the packing with least wasted space is computationally easy to find; but its expected wasted space in the random case is not obvious. We show that with high probability for largen, this best packing has wasted space . It turns out that if the endpoints 0 and 1 are identified, so that the problem is now one of packing random arcs in a unit-circumference circle, then optimal wasted space is reduced toO(1/n). Interestingly, there is a striking difference between thesizes of the best packings: about logn intervals in the unit interval case, but usually only one or two arcs in the circle case.     

Hypergraph families with bounded edge cover or transversal number

The transversal number, packing number, covering number and strong stability number of hypergraphs are denoted by τ, ν, ϱ and α, respectively. A hypergraph family t is called τ-bound (ϱ-bound) if there exists a “binding function”f(x) such that τ(H)≦f(v(H)) (ϱ(H)≦f(α(H))) for allH ∈ t. Methods are presented to show that various hypergraph families are τ-bound and/or ϱ-bound. The results can be applied to families of geometrical nature like subforests of trees, boxes, boxes of polyominoes or to families defined by hypergraph theoretic terms like the family where every subhypergraph has the Helly-property.     

An asymptotically hierarchy-consistent, iterative sequence transformation for convergence acceleration of Fourier series

We derive the I transformation, an iterative sequence transformation that is useful for the convergence acceleration of certain Fourier series. The derivation is based on the concept of hierarchical consistency in the asymptotic regime. We show that this sequence transformation is a special case of the J transformation. Thus, many properties of the I transformation can be deduced from the known properties of the J transformation (like the kernel, determinantal representations, and theorems on convergence behavior and stability). Besides explicit formulas for the kernel, some basic convergence theorems for the I transformation are given here. Further, numerical results are presented that show that suitable variants of the I transformation are powerful nonlinear convergence accelerators for Fourier series with coefficients of monotonic behavior. This revised version was published online in August 2006 with corrections to the Cover Date.     

Para-orthogonal Laurent polynomials and associated sequences of rational functions

On the space, , of Laurent polynomials (L-polynomials) we consider a linear functional which is positive definite on (0, ) and is defined in terms of a given bisequence, { _k } _– . Two sequences of orthogonal L-polynomials, {Q _n (z) ₀ and , are constructed which span in the order {1,z ^–1,z,z ^–2,z ²,...} and {1,z,z ^–1,z ²,z ^–2,...} respectively. Associated sequences of L-polynomials {P _n (z) ₀ , and are introduced and we define rational functions , wherew is a fixed positive number. The partial fraction decomposition and integral representation of,M _n (z, w) are given and correspondence of {M _n (z, w)} is discussed. We get additional solutions to the strong Stieltjes moment problem from subsequences of {M _n (z, w)}. In particular when { _k } _– is a log-normal bisequence, {M _2n (z, w)} and {M _2n+1 (z, w)} yield such solutions.Research supported in part by the National Science Foundation under Grant DMS-9103141.     

The Euler Maclaurin expansion for the Cauchy Principal Value integral

Summary The classical Euler Maclaurin Summation Formula expresses the difference between a definite integral over [0, 1] and its approximation using the trapezoidal rule with step lengthh=1/m as an asymptotic expansion in powers ofh together with a remainder term. Many variants of this exist some of which form the basis of extrapolation methods such as Romberg Integration. in this paper a variant in which the integral is a Cauchy Principal Value integral is derived. The corresponding variant of the Fourier Coefficient Asymptotic Expansion is also derived. The possible role of the former in numerical quadrature is discussed.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under contract W-31-109-Eng-38     

On rates of acceleration of extrapolation methods for oscillatory infinite integrals

The purpose of this work is to complement and expand our knowledge of the convergence theory of some extrapolation methods for the accurate computation of oscillatory infinite integrals. Specifically, we analyze in detail the convergence properties of theW- and -transformations of the author as they are applied to three integrals, all with totally different behavior at infinity. The results of the analysis suggest different convergence and acceleration of convergence behavior for the above mentioned transformations on the different integrals, and they improve considerably those that can be obtained from the existing convergence theories.     

Exhaustive weakly wandering sequences

A sequence of integers {n_i : i = 0, 1…} is an exhaustive weakly wandering sequence for a transformation T if for some measurable set W, X=^∞_i=0TⁿⁱW(disj. We introduce a hereditary Property (H) for a sequence of integers associated with an infinite ergodic transformation T, and show that it is a sufficient condition for the sequence to be an exhaustive weakly wandering sequence for T. We then show that every infinite ergodic transformation admits sequences that possess Property (H), and observe that Property (H) is inherited by all subsequences of a sequence that possess it. As a corollary, we obtain an application to tiling the set of integers with infinite subsets.     

Estimation of convergence orders in repeated richardson extrapolation

LetA(h) be an approximation depending on a single parameterh to a fixed quantityA, and assume thatA–A(h)=c ₁ h k ₁ +c ₂ h ^k ₂ +.... Given a sequence ofh-valuesh ₁>h ₂>...>h _n and corresponding computed approximationsA(h _i ), the orders for repeated Richardson extrapolation are estimated, and the repeated extrapolation is performed. Hence in this case the algorithm described here can do the same work as Brezinski'sE-algorithm and at the same time provide a check whether repeated extrapolation is justified.     

Studies on the squaring construction

The code formulas for the iterated squaring construction for a finite group partition chain, derived by Forney [2], are extended to the case with a bi-infinite group partition chain, and the derivation presented here is much simpler than the one given by Forney for the finite case. It is also proven that the iterated squaring construction indeed generates the Reed-Muller codes. Moreover, the generalization of the code formulas to the bi-infinite case is used to derive code formulas for the lattices Λ(r,n) andRΛ(r,n), which correct some errors in [2]. Further, Gaussian integer lattices are discussed. A definition of their dual lattices is given, which is more general than the definition given by Forney [1]. Using this definition, some interesting properties of dual lattices and the squaring construction are obtained and then formulas of the duals of the Barnes-Wall lattices and their principal sublattices are derived, and one assumption from the derivation given by Forney [2] can be eliminated.     

An asymptotic expansion in wavelet analysis and its application to accurate numerical wavelet decomposition

We consider a dilation operatorT admitting a scaling function with compact support as fixed point. It is shown that the adjoint operatorT*admits a sequence of polynomial eigenfunctions and that a smooth functionf admits an expansion in these eigenfunctions, which reveals the asymptotic behavior ofT* forn.Due to this asymptotic expansion, an extrapolation technique can be applied for the accurate numerical computation of the integrals appearing in the wavelet decomposition of a smooth function. This extrapolation technique fits well in a multiresolution scheme.     

Stability of Riemann solutions with large oscillation for the relativistic Euler equations

We are concerned with entropy solutions of the 2×2 relativistic Euler equations for perfect fluids in special relativity. We establish the uniqueness of Riemann solutions in the class of entropy solutions in L^∞∩BV_loc with arbitrarily large oscillation. Our proof for solutions with large oscillation is based on a detailed analysis of global behavior of shock curves in the phase space and on special features of centered rarefaction waves in the physical plane for this system. The uniqueness result does not require specific reference to any particular method for constructing the entropy solutions. Then the uniqueness of Riemann solutions yields their inviscid large-time stability under arbitrarily largeL¹∩L^∞∩BV_loc perturbation of the Riemann initial data, as long as the corresponding solutions are in L^∞ and have local bounded total variation that allows the linear growth in time. We also extend our approach to deal with the uniqueness and stability of Riemann solutions containing vacuum in the class of entropy solutions in L^∞ with arbitrarily large oscillation.     

Limit periodic Schur algorithms,the case 441-1441-1441-1

We show that if a function bounded in the unit disk gives rise to a limit periodic Schur algorithm with ||=1, d _n ,< then the function can be continued analytically to a meromorphic function in the entire plane except, possibly, for an essential singularity at z=–1. The lpS provides a very good approximation to the function.This research was supported in part by the US National Science Foundation under Grant DMS-9103141.     

Two composition methods for solving certain systems of linear equations

Summary This note is concerned with the following problem: Given a systemA·x=b of linear equations and knowing that certains of its subsystemsA ¹·x ¹=b ¹, ...,A ^m ·x ^m =b ^m can be solved uniquely what can be said about the regularity ofA and how to find the solutionx fromx ¹, ...,x ^m ? This question is of particular interest for establishing methods computing certain linear or quasilinear sequence transformations recursively [7, 13, 15].Work performed under NATO Research Grant 027-81