Development of the Levin-type algorithms for accelerating convergence of sequences

There are two aims of this paper. Firstly we shall introduce the determinantal representations of the new Levin-type algorithms and secondly we shall demonstrate further development of the Levin-type algorithms. We consider the use of the Levin-type algorithms to accelerate the convergence of scalar sequence and their effectiveness for approximating the solution of a given power series is illustrated. In process we shall demonstrate the convergence of each of the methods considered. The approximate solution of the super enhanced Levin algorithm and the efficient Levin algorithm are found to be substantially more accurate than the Cizek, Zamastil and Skala transformation and the iterated Aitken Δ²${\mathrm{\Delta }}^2$ algorithm.     

Fourier series and the δ process

We discuss the effect of a particular sequence acceleration method, the δ²${\delta }^2$ process, on the partial sums of Fourier series. We show that for a very general class of functions, this method fails on a dense set of points; not only does it not speed up convergence, it turns the sequence of partial sums into a sequence with multiple limit points.     

The banach algebra A and its properties

Beurling’s algebra is considered. A* arises quite naturally in problems of summability of the Fourier series at Lebesgue points, whereas Wiener’s algebra A of functions with absolutely convergent Fourier series arises when studying the norm convergence of linear means. Certainly, both algebras are used in some other areas. A* has many properties similar to those of A, but there are certain essential distinctions. A* is a regular Banach algebra, its space of maximal ideals coincides with[−π, π], and its dual space is indicated. Analogs of Herz’s and Wiener-Ditkin’s theorems hold. Quantitative parameters in an analog of the Beurling-Pollard theorem differ from those for A. Several inclusion results comparing the algebra A* with certain Banach spaces of smooth functions are given. Some special properties of the analogous space for Fourier transforms on the real axis are presented. The paper ends with a summary of some open problems.     

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.     

On a fast and accurate method for computing Fourier transforms

In this paper, a variable order method for the fast and accurate computation of the Fourier transform is presented. The increase in accuracy is achieved by applying corrections to the trapezoidal sum approximations obtained by the FFT method. It is shown that the additional computational work involved is of orderK(2m+2), wherem is a small integer andKn. Analytical expressions for the associated error is also given.     

The Segal Algebra {\bf S}_0({\Bbb R}^d) and Norm Summability of Fourier Series and Fourier Transforms

A general summability method, the so-called θ-summability is considered for multi-dimensional Fourier series. Equivalent conditions are derived for the uniform and L ₁-norm convergence of the θ-means σ _n ^θ f to the function f. If f is in a homogeneous Banach space, then the preceeding convergence holds in the norm of the space. In case θ is an element of Feichtinger’s Segal algebra , then these convergence results hold. Some new sufficient conditions are given for θ to be in . A long list of concrete special cases of the θ-summation is listed. The same results are also provided in the context of Fourier transforms, indicating how proofs have to be changed in this case. This research was supported by Lise Meitner fellowship No M733-N04 and the Hungarian Scientific Research Funds (OTKA) No T043769, T047128, T047132.     

On two methods for accelerating convergence of series

Summary The Euler-Knopp transformation and a recently considered transformation, effective for entire function of order 1, are applied to series involving completely monotonic coefficients. Some properties of the resulting series are analyzed; these include uniform convergence with respect to the index, a priori and a posteriori estimates of the remainder. For the latter transformation a compact recursive algorithm is established which enables one to make effective use of the transformation. To illustrate the effectiveness of the transformations three applications, with examples, are included.     

Extension of a theorem of Fejér to double Fourier-Stieltjes series

A theorem of Fejér states that if a periodic function F is of bounded variation on the closed interval [0, 2π], then the nth partial sum of its formally differentiated Fourier series divided by n converges to π^-1[F(x+0)-F(x-0)] at each point x. The generalization of this theorem for Fourier-Stieltjes series of (nonperiodic) functions of bounded variation is also well known. The aim of the present article is to extend these results to the (m, n)th rectangular partial sum of double Fourier or Fourier-Stieltjes series of a function F(x, y) of bounded variation over the closed square [0, 2π]×[0, 2π] in the sense of Hardy and Krause. As corollaries, we also obtain the following results:

On the stability of the J transformation

The stability of a large class of nonlinear sequence transformations is analyzed. Considered are variants of the J transformation [17]. Suitable variants of this transformation belong to the most successful extrapolation algorithms that are known [20]. Similar to recent results of Sidi, it is proved that the _p {J} transformations, the Weniger S transformation, the Levin transformation and a special case of the generalized Richardson extrapolation process of Sidi are S-stable. An efficient algorithm for the calculation of stability indices is presented. A numerical example demonstrates the validity of the approach. This revised version was published online in June 2006 with corrections to the Cover Date.     

Numerical treatment of a twisted tail using extrapolation methods

Highly oscillatory integral, called a twisted tail, is proposed as a challenge in The SIAM 100-digit challenge. A Study in High-Accuracy Numerical Computing, where Drik Laurie developed numerical algorithms based on the use of Aitken’s Δ²-method, complex integration and transformation to a Fourier integral. Another algorithm is developed by Walter Gautschi based on Longman’s method; Newton’s method for solving a nonlinear equation; Gaussian quadrature; and the epsilon algorithm of Wynn for accelerating the convergence of infinite series. In the present work, nonlinear transformations for improving the convergence of oscillatory integrals are applied to the integration of this wildly oscillating function. Specifically, the transformation and its companion the W algorithm, and the G transformation are all used in the analysis of the integral. A Fortran program is developed employing each of the methods, and accuracies of up to 15 correct digits are reached in double precision.     

A summability method for the arithmetic Fourier transform

The Arithmetic Fourier Transform (AFT) is an algorithm for the computation of Fourier coefficients, which is suitable for parallel processing and in which there are no multiplications by complex exponentials. This is accomplished by the use of the Möbius function and Möbius inversion. However, the algorithm does require the evaluation of the function at an array of irregularly spaced points. In the case that the function has been sampled at regularly spaced points, interpolation is used at the intermediate points of the array. Generally theAFT is most effective when used to calculate the Fourier cosine coefficients of an even function.In this paper a summability method is used to derive a modification of theAFT algorithm. The proof of the modification is quite independent of theAFT itself and involves a summation by primes. One advantage of the new algorithm is that with a suitable sampling scheme low order Fourier coefficients may be calculated without interpolation.     

On convergence of Fourier series of Besicovitch almost periodic functions

The paper deals with convergence of the Fourier series of q-Besicovitch almost periodic functions of the form $$ f(t)\sim \mathop{\sum}\limits_{m=1}^{\infty }{a_m}{{\mathrm{e}}^{{-\mathrm{i}{\uplambda_m}t}}}, $$ where {λm} is a Dirichlet sequence, that is, a strictly increasing sequence of nonnegative numbers tending to infinity. In particular, we show that, for 1 < q < ∞, the Fourier series of f(t) converges in norm to the function f(t) itself with usual order, which is analogous to the convergence in norm of the Fourier series of a function on [0, 2π]. A version of the Carleson–Hunt theorem is also investigated.     

The limit of the spectral radius of block Toeplitz matrices with nonnegative entries

A bi-infinite sequence ...,t _–2,t _–1,t ₀,t ₁,t ₂,... of nonnegativep×p matrices defines a sequence of block Toeplitz matricesT _n =(t _ik ),n=1,2,...,, wheret _ik =t _k–i ,i,k=1,...,n. Under certain irreducibility assumptions, we show that the limit of the spectral radius ofT _n , asn tends to infinity, is given by inf{()[0,]}, where () is the spectral radius of _jz t _j ^j .Supported by SFB 343 Diskrete Strukturen in der Mathematik, Universität Bielefeld     

<Emphasis Type="Italic">q</Emphasis>-Fibonacci Polynomials and the Rogers-Ramanujan Identities

We derive some formulas for the Carlitz q-Fibonacci polynomials F_n(t) which reduce to the finite version of the Rogers-Ramanujan identities obtained by I. Schur for t = 1. Our starting point is a representation of the q-Fibonacci polynomials as the weight of certain lattice paths in contained in a strip along the x-axis. We give an elementary combinatorial proof by using only the principle of inclusion-exclusion and some standard facts from q-analysis.     

Locally constant dyadic derivatives

We show that in order for a Walsh series to be locally constant it is necessary for certain blocks of that series to sum to zero. As a consequence, we show that a functionf with a somewhat sparse Walsh—Fourier series is necessarily a Walsh polynomial if its strong dyadic derivative is constant on an interval. In particular, if a Rademacher seriesR is strongly dyadically differentiable and if that derivative is constant on any open subset of [0, 1], thenR is a Rademacher polynomial.     

Cyclicity of bicyclic operators and completeness of translates

We study cyclicity of operators on a separable Banach space which admit a bicyclic vector such that the norms of its images under the iterates of the operator satisfy certain growth conditions. A simple consequence of our main result is that a bicyclic unitary operator on a Banach space with separable dual is cyclic. Our results also imply that if is the shift operator acting on the weighted space of sequences , if the weight ω satisfies some regularity conditions and ω(n) = 1 for nonnegative n, then S is cyclic if . On the other hand one can see that S is not cyclic if the series diverges. We show that the question of Herrero whether either S or S* is cyclic on admits a positive answer when the series is convergent. We also prove completeness results for translates in certain Banach spaces of functions on .     

Convergence of an operator series

The paper gives a necessary and sufficient condition on the spectrum of a bounded linear operator on Banach space for the convergence of the series ₀ T(I-T ²) ⁿ . Some properties of the sum are investigated.     

A parallel algorithm for the eigenvalues and eigenvectors of a general complex matrix

Summary A new parallel Jacobi-like algorithm is developed for computing the eigenvalues of a general complex matrix. Most parallel methods for this problem typically display only linear convergence, Sequential norm-reducing algorithms also exist and they display quadratic convergence in most cases. The new algorithm is a parallel form of the norm-reducing algorithm due to Eberlein. It is proven that the asymptotic convergence rate of this algorithm is quadratic. Numerical experiments are presented which demonstrate the quadratic convergence of the algorithm and certain situations where the convergence is slow are also identified. The algorithm promises to be very competitive on a variety of parallel architectures. In particular, the algorithm can be implemented usingn ²/4 processors, takingO(n log² n) time for random matrices.This research was supported by the Office of Naval Research under Contract N00014-86-k-0610 and by the U.S. Army Research Office under Contract DAAL 03-86-K-0112. A portion of this research was carried out while the author was visiting RIACS, Nasa Ames Research Center     

Fourier Series with Linear Splines on an Interval

We construct orthonormal bases of linear splines on a finite interval [a, b] and then we study the Fourier series associated to these orthonormal bases. For continuous functions defined on [a, b], we prove that the associated Fourier series converges pointwisely on (a, b) and also uniformly on [a, b], if it convergences pointwisely at a and b.