Convergence of nonstationary cascade algorithms

Summary. A nonstationary multiresolution of is generated by a sequence of scaling functions We consider that is the solution of the nonstationary refinement equations where is finitely supported for each k and M is a dilation matrix. We study various forms of convergence in of the corresponding nonstationary cascade algorithm as k or n tends to It is assumed that there is a stationary refinement equation at with filter sequence h and that The results show that the convergence of the nonstationary cascade algorithm is determined by the spectral properties of the transition operator associated with h. Received September 19, 1997 / Revised version received May 22, 1998 / Published online August 19, 1999     

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     

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     

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     

Peano kernels and bounds for the error constants of Gaussian and related quadrature rules for Cauchy principal value integrals

Summary. We show that, if (), the error term of every modified positive interpolatory quadrature rule for Cauchy principal value integrals of the type , , fulfills uniformly for all , and hence it is of optimal order of magnitude in the classes (). Here, is a weight function with the property . We give explicit upper bounds for the Peano-type error constants of such rules. This improves and completes earlier results by Criscuolo and Mastroianni (Calcolo 22 (1985), 391–441 and Numer. Math. 54 (1989), 445–461) and Ioakimidis (Math. Comp. 44 (1985), 191–198). For the special case of the Gaussian rule, we show that the restriction can be dropped. The results are based on a new representation of the Peano kernels of these formulae via the Peano kernels of the underlying classical quadrature formulae. This representation may also be useful in connection with some different problems. Received November 21, 1994     

Polynomial evaluation and associated polynomials

We show a connection between the Clenshaw algorithm for evaluating a polynomial , expanded in terms of a system of orthogonal polynomials, and special linear combinations of associated polynomials. These results enable us to get the derivatives of analogously to the Horner algorithm for evaluating polynomials in monomial representations. Furthermore we show how a polynomial given in monomial (!) representation can be evaluated for using the Clenshaw algorithm without complex arithmetic. From this we get a connection between zeros of polynomials expanded in terms of Chebyshev polynomials and the corresponding polynomials in monomial representation with the same coefficients. Received January 2, 1995 / Revised version received April 9, 1997     

Interpolatory product quadratures for Cauchy principal value integrals with Freud weights

Summary. We prove convergence results and error estimates for interpolatory product quadrature formulas for Cauchy principal value integrals on the real line with Freud–type weight functions. The formulas are based on polynomial interpolation at the zeros of orthogonal polynomials associated with the weight function under consideration. As a by–product, we obtain new bounds for the derivative of the functions of the second kind for these weight functions. Received July 15, 1997 / Revised version received August 25, 1998     

Efficient numerical methods in non-uniform sampling theory

Summary. We present a new ``second generation" reconstruction algorithm for irregular sampling, i\@.e\@. for the problem of recovering a band-limited function from its non-uniformly sampled values. The efficient new method is a combination of the adaptive weights method which was developed by the two first named authors and the method of conjugate gradients for the solution of positive definite linear systems. The choice of "adaptive weights" can be seen as a simple but very efficient method of preconditioning. Further substantial acceleration is achieved by utilizing the Toeplitz-type structure of the system matrix. This new algorithm can handle problems of much larger dimension and condition number than have been accessible so far. Furthermore, if some gaps between samples are large, then the algorithm can still be used as a very efficient extrapolation method across the gaps. Received December 22, 1993     

Convergence of vectorial sequences. Applications

Summary. A transformation of vectorial sequences is given, analogous to the Shank's transform in the scalar case. This is possible because of the link with the Vector Pad\'e approximants defined for a power series, with vectorial coefficients. Algorithms, different from recursive computation of determinants, can be defined. Some numerical examples are given. Received December 17, 1993 / Revised version received June 25, 1993     

Polynomial interpolation of minimal degree

Summary. Minimal degree interpolation spaces with respect to a finite set of points are subspaces of multivariate polynomials of least possible degree for which Lagrange interpolation with respect to the given points is uniquely solvable and degree reducing. This is a generalization of the concept of least interpolation introduced by de Boor and Ron. This paper investigates the behavior of Lagrange interpolation with respect to these spaces, giving a Newton interpolation method and a remainder formula for the error of interpolation. Moreover, a special minimal degree interpolation space will be introduced which is particularly beneficial from the numerical point of view. Received June 9, 1995 / Revised version received June 26, 1996     

On vector subdivision

In this paper we give a complete characterization of the convergence of stationary vector subdivision schemes and the regularity of the associated limit function. These results extend and complete our earlier work on vector subdivision and its use in the construction of multiwavelets. Received March 19, 1997; in final form November 13, 1997     

Calculation of the elliptic integrals of the first and second kinds with complex modulus

Summary. Numerical procedures for calculating the elliptic integrals of the first and the second kind with complex modulus and their analytic continuations are presented. The corresponding results for the elliptic integral of the third kind are given in Appendices. Received September 9, 1996 / Revised version received June 2, 1998     

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     

On the stability of the $L_2$ projection in fractional Sobolev spaces

Summary.   In this paper we prove the stability of the projection onto the finite element trial space of piecewise polynomial, in particular, piecewise linear basis functions in for . We formulate explicit and computable local mesh conditions to be satisfied which depend on the Sobolev index s. In conclusion we prove a stability condition needed in the numerical analysis of mixed and hybrid boundary element methods as well as in the construction of efficient preconditioners in adaptive boundary and finite element methods. Received October 14, 1999 / Revised version received March 24, 2000 / Published online October 16, 2000     

On a generalized $L_2$ projection and some related stability estimates in Sobolev spaces

Summary. In this paper we investigate a stability estimate needed in hybrid finite and boundary element methods, especially in hybrid coupled domain decomposition methods including mortar finite elements. This stability estimate is equivalent to the stability of a generalized projection in certain Sobolev spaces. Using piecewise linear trial spaces and appropriate piecewise constant test spaces, the stability of the generalized projection is proved assuming some mesh conditions locally. Received April 11, 2000 / Revised version received February 15, 2001 / Published online July 25, 2001     

On the optimal stability of bases of univariate functions

Summary. This paper is concerned with bases of finite dimensional spaces of univariate continuous functions which are optimally stable for evaluation. The only bases considered are those whose elements have no sign changes. Among these, an optimally stable basis is characterized under the assumption that the set of points where each basis function is nonzero is an interval. A uniqueness result and many examples of such optimally stable bases are also provided. Received May 26, 2000 / Published online August 17, 2001     

Convex interval interpolation using a three-term staircase algorithm

Motivated by earlier considerations of interval interpolation problems as well as a particular application to the reconstruction of railway bridges, we deal with the problem of univariate convexity preserving interval interpolation. To allow convex interpolation, the given data intervals have to be in (strictly) convex position. This property is checked by applying an abstract three-term staircase algorithm, which is presented in this paper. Additionally, the algorithm provides strictly convex ordinates belonging to the data intervals. Therefore, the known methods in convex Lagrange interpolation can be used to obtain interval interpolants. In particular, we refer to methods based on polynomial splines defined on grids with additional knots. Received September 22, 1997 / Revised version received May 26, 1998     

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     

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     

The Euler-Maclaurin expansion and finite-part integrals

In this paper we compare G(p), the Mellin transform (together with its analytic continuation), and , the related Hadamard finite-part integral of a function g(x), which decays exponentially at infinity and has specified singular behavior at the origin. Except when p is a nonpositive integer, these coincide. When p is a nonpositive integer, is well defined, but G(p) has a pole. We show that the terms in the Laurent expansion about this pole can be simply expressed in terms of the Hadamard finite-part integral of a related function. This circumstance is exploited to provide a conceptually uniform proof of the various generalizations of the Euler-Maclaurin expansion for the quadrature error functional. Received June 11, 1997 / Revised version received December 15, 1997