Convergence of multidimensional cascade algorithm

A necessary and sufficient condition on the spectrum of the restricted transition operator is given for the convergence in of the multidimensional cascade algorithm for any starting function whose shifts form a partition of unity. Received September 12, 1995 / Revised version received August 2, 1996     

Convergence of cascade algorithms in Sobolev spaces and integrals of wavelets

Summary. The cascade algorithm with mask a and dilation M generates a sequence by the iterative process from a starting function where M is a dilation matrix. A complete characterization is given for the strong convergence of cascade algorithms in Sobolev spaces for the case in which M is isotropic. The results on the convergence of cascade algorithms are used to deduce simple conditions for the computation of integrals of products of derivatives of refinable functions and wavelets. Received May 5, 1999 / Revised version received June 24, 1999 / Published online June 20, 2001     

General interpolation on the lattice h{\Bbb Z}^s: Compactly supported fundamental solutions

Summary. In this paper we combine an earlier method developed with K. Jetter on general cardinal interpolation with constructions of compactly supported solutions for cardinal interpolation to gain compactly supported fundamental solutions for the general interpolation problem. The general interpolation problem admits the interpolation of the functional and derivative values under very weak restrictions on the derivatives to be interpolated. In the univariate case, some known general constructions of compactly supported fundamental solutions for cardinal interpolation are discussed together with algorithms for their construction that make use of MAPLE. Another construction based on finite decomposition and reconstruction for spline spaces is also provided. Ideas used in the latter construction are lifted to provide a general construction of compactly supported fundamental solutions for cardinal interpolation in the multivariate case. Examples are provided, several in the context of some general interpolation problem to illustrate how easy is the transition from cardinal interpolation to general interpolation. Received May 11, 1993 / Revised version received August 16, 1994     

On the Gibbs phenomenon V: recovering exponential accuracy from collocation point values of a piecewise analytic function

Summary. This paper presents a method to recover exponential accuracy at all points (including at the discontinuities themselves), from the knowledge of an approximation to the interpolation polynomial (or trigonometrical polynomial). We show that if we are given the collocation point values (or a highly accurate approximation) at the Gauss or Gauss-Lobatto points, we can reconstruct an uniform exponentially convergent approximation to the function in any sub-interval of analyticity. The proof covers the cases of Fourier, Chebyshev, Legendre, and more general Gegenbauer collocation methods. A numerical example is also provided. Received July 17, 1994 / Revised version received December 12, 1994     

Asymptotic error expansion of wavelet approximations of smooth functions II

Summary. We generalize earlier results concerning an asymptotic error expansion of wavelet approximations. The properties of the monowavelets, which are the building blocks for the error expansion, are studied in more detail, and connections between spline wavelets and Euler and Bernoulli polynomials are pointed out. The expansion is used to compare the error for different wavelet families. We prove that the leading terms of the expansion only depend on the multiresolution subspaces and not on how the complementary subspaces are chosen. Consequently, for a fixed set of subspaces , the leading terms do not depend on the fact whether the wavelets are orthogonal or not. We also show that Daubechies' orthogonal wavelets need, in general, one level more than spline wavelets to obtain an approximation with a prescribed accuracy. These results are illustrated with numerical examples. Received May 3, 1993 / Revised version received January 31, 1994     

Look-ahead Levinson and Schur algorithms for non-Hermitian Toeplitz systems

Summary. We present generalizations of the nonsymmetric Levinson and Schur algorithms for non-Hermitian Toeplitz matrices with some singular or ill-conditioned leading principal submatrices. The underlying recurrences allow us to go from any pair of successive well-conditioned leading principal submatrices to any such pair of larger order. If the look-ahead step size between these pairs is bounded, our generalized Levinson and Schur recurrences require $ operations, and the Schur recurrences can be combined with recursive doubling so that an $ algorithm results. The overhead (in operations and storage) of look-ahead steps is very small. There are various options for applying these algorithms to solving linear systems with Toeplitz matrix. Received July 26, 1993     

Sur l'erreur d'approximation par éléments finis en utilisant la méthode des plaquettes splines

Résumé. On établit des majorations de l'erreur d'approximation par éléments finis à partir de données de Lagrange pour des fonctions appartenant à un espace de Sobolev d'ordre convenable, lorsque les degrés de liberté sont approchés à l'aide de la méthode des plaquettes splines introduite par A. Le Méhauté (cf. [13], [14], [15]). Les résultats obtenus s'appliquent notamment à la construction de surfaces de classe . Received May 29, 1995 / Revised version received August 20, 1995     

A class of bivariate orthogonal polynomials and cubature formula

Summary. The existence of Gaussian cubature for a given measure depends on whether the corresponding multivariate orthogonal polynomials have enough common zeros. We examine a class of orthogonal polynomials of two variables generated from that of one variable. Received February 9, 1993 / Revised version received January 18, 1994     

Zeros of the partial sums of $cos(z)$ and $sin(z)$ II

Summary.   We study here in detail the location of the real and complex zeros of the partial sums of and , which extends results of Szeg? (1924) and Kappert (1996). Received November 9, 2000 / Published online August 17, 2001     

On the zeros of the partial sums of \cos(z) and \sin(z)

Summary. Let denote the -th partial sum of the exponential function. Carpenter et al. (1991) [1] studied the exact rate of convergence of the zeros of the normalized partial sums to the so-called Szeg?-curve Here we apply parts of the results found by Carpenter et al. to the zeros of the normalized partial sums of and . Received August 11, 1995     

Asymptotics for the zeros and poles of normalized Pad\'{e} approximants to{\rm e}^{z}

Summary. With denoting the -th partial sum of ${\rm e}^{z}$, the exact rate of convergence of the zeros of the normalized partial sums, , to the Szeg\"o curve was recently studied by Carpenter et al. (1991), where is defined by Here, the above results are generalized to the convergence of the zeros and poles of certain sequences of normalized Pad\'{e} approximants to , where is the associated Pad\'{e} rational approximation to . Received February 2, 1994     

Approximation of conformal mappings of annular regions

Summary. In this paper we examine the convergence rates in an adaptive version of an orthonormalization method for approximating the conformal mapping of an annular region onto a circular annulus. In particular, we consider the case where has an analytic extension in compl() and, for this case, we determine optimal ray sequences of approximants that give the best possible geometric rate of uniform convergence. We also estimate the rate of uniform convergence in the case where the annular region has piecewise analytic boundary without cusps. In both cases we also give the corresponding rates for the approximations to the conformal module of . Received February 2, 1996     

Constructing cubature formulae by the method of reproducing kernel

Summary. We examine the method of reproducing kernel for constructing cubature formulae on the unit ball and on the triangle in light of the compact formulae of the reproducing kernels that are discovered recently. Several new cubature formulae are derived. Received April 15, 1998 / Revised version received November 24, 1998 / Published online January 27, 2000     

Computing orthogonal polynomials in Sobolev spaces

Summary. Numerical methods are considered for generating polynomials orthogonal with respect to an inner product of Sobolev type, i.e., one that involves derivatives up to some given order, each having its own (positive) measure associated with it. The principal objective is to compute the coefficients in the increasing-order recurrence relation that these polynomials satisfy by virtue of them forming a sequence of monic polynomials with degrees increasing by 1 from one member to the next. As a by-product of this computation, one gains access to the zeros of these polynomials via eigenvalues of an upper Hessenberg matrix formed by the coefficients generated. Two methods are developed: One is based on the modified moments of the constitutive measures and generalizes what for ordinary orthogonal polynomials is known as "modified Chebyshev algorithm". The other - a generalization of "Stieltjes's procedure" - expresses the desired coefficients in terms of a Sobolev inner product involving the orthogonal polynomials in question, whereby the inner product is evaluated by numerical quadrature and the polynomials involved are computed by means of the recurrence relation already generated up to that point. The numerical characteristics of these methods are illustrated in the case of Sobolev orthogonal polynomials of old as well as new types. Based on extensive numerical experimentation, a number of conjectures are formulated with regard to the location and interlacing properties of the respective zeros. Received July 13, 1994 / Revised version received September 26, 1994     

Line search termination criteria for collinear scaling algorithms for minimizing a class of convex functions

Summary. Many successful quasi-Newton methods for optimization are based on positive definite local quadratic approximations to the objective function that interpolate the values of the gradient at the current and new iterates. Line search termination criteria used in such quasi-Newton methods usually possess two important properties. First, they guarantee the existence of such a local quadratic approximation. Second, under suitable conditions, they allow one to prove that the limit of the component of the gradient in the normalized search direction is zero. This is usually an intermediate result in proving convergence. Collinear scaling algorithms proposed initially by Davidon in 1980 are natural extensions of quasi-Newton methods in the sense that they are based on normal conic local approximations that extend positive definite local quadratic approximations, and that they interpolate values of both the gradient and the function at the current and new iterates. Line search termination criteria that guarantee the existence of such a normal conic local approximation, which also allow one to prove that the component of the gradient in the normalized search direction tends to zero, are not known. In this paper, we propose such line search termination criteria for an important special case where the function being minimized belongs to a certain class of convex functions. Received February 1, 1997 / Revised version received September 8, 1997     

A look-ahead Bareiss algorithm for general Toeplitz matrices

Summary. The Bareiss algorithm is one of the classical fast solvers for systems of linear equations with Toeplitz coefficient matrices. The method takes advantage of the special structure, and it computes the solution of a Toeplitz system of order~ with only~ arithmetic operations, instead of~ operations. However, the original Bareiss algorithm requires that all leading principal submatrices be nonsingular, and the algorithm is numerically unstable if singular or ill-conditioned submatrices occur. In this paper, an extension of the Bareiss algorithm to general Toeplitz systems is presented. Using look-ahead techniques, the proposed algorithm can skip over arbitrary blocks of singular or ill-conditioned submatrices, and at the same time, it still fully exploits the Toeplitz structure. Implementation details and operations counts are given, and numerical experiments are reported. We also discuss special versions of the proposed look-ahead Bareiss algorithm for Hermitian indefinite Toeplitz systems and banded Toeplitz systems. Received August 27, 1993 / Revised version received March 1994     

Smooth macro-elements based on Clough-Tocher triangle splits

Summary. Macro-elements of smoothness on Clough-Tocher triangle splits are constructed for all . These new elements are improvements on elements constructed in [11] in that (disproving a conjecture made there) certain unneeded degrees of freedom have been removed. Numerical experiments on Hermite interpolation with the new elements are included. Received September 6, 2000 / Revised version received November 15, 2000 / Published online July 25, 2001     

Fast integral wavelet transform on a dense set of the time-scale domain

Summary. The objective of this paper is to introduce a fast algorithm for computing the integral wavelet transform (IWT) on a dense set of points in the time-scale domain. By applying the duality principle and using a compactly supported spline-wavelet as the analyzing wavelet, this fast integral wavelet transform (FIWT) is realized by applying only FIR (moving average) operations, and can be implemented in parallel. Since this computational procedure is based on a local optimal-order spline interpolation scheme and the FIR filters are exact, the IWT values so obtained are guaranteed to have zero moments up to the order of the cardinal spline functions. The semi-orthogonal (s.o.) spline-wavelets used here cannot be replaced by any other biorthogonal wavelet (spline or otherwise) which is not s.o., since the duality principle must be applied to some subspace of the multiresolution analysis under consideration. In contrast with the existing procedures based on direct numerical integration or an FFT-based multi-voice per octave scheme, the computational complexity of our FIWT algorithm does not increase with the increasing number of values of the scale parameter. Received March 3, 1994     

Divergenzverhalten mehrdimensionaler Shannonscher Abtastreihen

The behaviour of multidimensional Shannon sampling series for continuous functions is examined. A continuous function g ₁∈C ₀ [0,1]² with support in the rectangle [0,1] × [0,?] is indicated in the paper for which the two dimensional Shannon sampling series diverge almost everywhere in the rectangle [0,1] × [?,1]. This shows that the localization principle for Shannon sampling series cannot hold in two dimensions and in higher dimensions. The result solves a problem formulated by P.L. Butzer. Received: 21 December 1995 / Revised version: 5 October 1996