Laurent-Padé approximants to four kinds of Chebyshev polynomial expansions. Part I. Maehly type approximants

Laurent Padé-Chebyshev rational approximants,A _m (z,z ⁻¹)/B _n (z, z ⁻¹), whose Laurent series expansions match that of a given functionf(z,z ⁻¹) up to as high a degree inz, z ⁻¹ as possible, were introduced for first kind Chebyshev polynomials by Clenshaw and Lord [2] and, using Laurent series, by Gragg and Johnson [4]. Further real and complex extensions, based mainly on trigonometric expansions, were discussed by Chisholm and Common [1]. All of these methods require knowledge of Chebyshev coefficients off up to degreem+n. Earlier, Maehly [5] introduced Padé approximants of the same form, which matched expansions betweenf(z,z ⁻¹)B _n (z, z ⁻¹)). The derivation was relatively simple but required knowledge of Chebyshev coefficients off up to degreem+2n. In the present paper, Padé-Chebyshev approximants are developed not only to first, but also to second, third and fourth kind Chebyshev polynomial series, based throughout on Laurent series representations of the Maehly type. The procedures for developing the Padé-Chebyshev coefficients are similar to that for a traditional Padé approximant based on power series [8] but with essential modifications. By equating series coefficients and combining equations appropriately, a linear system of equations is successfully developed into two sub-systems, one for determining the denominator coefficients only and one for explicitly defining the numerator coefficients in terms of the denominator coefficients. In all cases, a type (m, n) Padé-Chebyshev approximant, of degreem in the numerator andn in the denominator, is matched to the Chebyshev series up to terms of degreem+n, based on knowledge of the Chebyshev coefficients up to degreem+2n. Numerical tests are carried out on all four Padé-Chebyshev approximants, and results are outstanding, with some formidable improvements being achieved over partial sums of Laurent-Chebyshev series on a variety of functions. In part II of this paper [7] Padé-Chebyshev approximants of Clenshaw-Lord type will be developed for the four kinds of Chebyshev series and compared with those of the Maehly type.     

Chebyshev Solution of the Nearly-Singular One-Dimensional Helmholtz Equation and Related Singular Perturbation Equations: Multiple Scale Series and the Boundary Layer Rule-of-Thumb

The one-dimensional Helmholtz equation, ² u _xx –u=f(x), arises in many applications, often as a component of three-dimensional fluids codes. Unfortunately, it is difficult to solve for 1 because the homogeneous solutions are exp(±x/), which have boundary layers of thickness O(1/). By analyzing the asymptotic Chebyshev coefficients of exponentials, we rederive the Orszag–Israeli rule [16] that Chebyshev polynomials are needed to obtain an accuracy of 1% or better for the homogeneous solutions. (Interestingly, this is identical with the boundary layer rule-of-thumb in [5], which was derived for singular functions like tanh([x–1]/).) Two strategies for small are described. The first is the method of multiple scales, which is very general, and applies to variable coefficient differential equations, too. The second, when f(x) is a polynomial, is to compute an exact particular integral of the Helmholtz equation as a polynomial of the same degree in the form of a Chebyshev series by solving triangular pentadiagonal systems. This can be combined with the analytic homogeneous solutions to synthesize the general solution. However, the multiple scales method is more efficient than the Chebyshev algorithm when is very, very tiny.     

Laurent–Padé Approximants to Four Kinds of Chebyshev Polynomial Expansions. Part II: Clenshaw–Lord Type Approximants

Laurent–Padé (Chebyshev) rational approximants P _m (w,w ^–1)/Q _n (w,w ^–1) of Clenshaw–Lord type [2,1] are defined, such that the Laurent series of P _m /Q _n matches that of a given function f(w,w ^–1) up to terms of order w ^±(m+n), based only on knowledge of the Laurent series coefficients of f up to terms in w ^±(m+n). This contrasts with the Maehly-type approximants [4,5] defined and computed in part I of this paper [6], where the Laurent series of P _m matches that of Q _n f up to terms of order w ^±(m+n), but based on knowledge of the series coefficients of f up to terms in w ^±(m+2n). The Clenshaw–Lord method is here extended to be applicable to Chebyshev polynomials of the 1st, 2nd, 3rd and 4th kinds and corresponding rational approximants and Laurent series, and efficient systems of linear equations for the determination of the Padé–Chebyshev coefficients are obtained in each case. Using the Laurent approach of Gragg and Johnson [4], approximations are obtainable for all m0, n0. Numerical results are obtained for all four kinds of Chebyshev polynomials and Padé–Chebyshev approximants. Remarkably similar results of formidable accuracy are obtained by both Maehly-type and Clenshaw–Lord type methods, thus validating the use of either.     

An inequality relating the order,maximum degree,diameter and connectivity of a strongly connected digraph

We prove that if there is a strongly connected digraph of ordern, maximum degreed, diameterk and connectivityc, thennc d ^k–d /d–1+d+1. It improves the previous known results, and it, in fact, is the best possible for several interesting cases. A similar result for arc connectivity is also established.This project is supported by the National Natural Science Foundation of China.     

On the Positivity of the Fundamental Polynomials for Generalized Hermite–Fejér Interpolation on the Chebyshev Nodes

It is shown that the fundamental polynomials for (0, 1, …, 2m+1) Hermite–Fejér interpolation on the zeros of the Chebyshev polynomials of the first kind are non-negative for −1x1, thereby generalising a well-known property of the original Hermite–Fejér interpolation method. As an application of the result, Korovkin's 10theorem on monotone operators is used to present a new proof that the (0, 1, …, 2m+1) Hermite–Fejér interpolation polynomials offC[−1, 1], based onnChebyshev nodes, converge uniformly tofasn→∞.     

Laurent–Padé Approximants to Four Kinds of Chebyshev Polynomial Expansions. Part I. Maehly Type Approximants

Laurent Padé–Chebyshev rational approximants, A _m (z,z ^–1)/B _n (z,z ^–1), whose Laurent series expansions match that of a given function f(z,z ^–1) up to as high a degree in z,z ^–1 as possible, were introduced for first kind Chebyshev polynomials by Clenshaw and Lord [2] and, using Laurent series, by Gragg and Johnson [4]. Further real and complex extensions, based mainly on trigonometric expansions, were discussed by Chisholm and Common [1]. All of these methods require knowledge of Chebyshev coefficients of f up to degree m+n. Earlier, Maehly [5] introduced Padé approximants of the same form, which matched expansions between f(z,z ^–1)B _n (z,z ^–1) and A _m (z,z ^–1). The derivation was relatively simple but required knowledge of Chebyshev coefficients of f up to degree m+2n. In the present paper, Padé–Chebyshev approximants are developed not only to first, but also to second, third and fourth kind Chebyshev polynomial series, based throughout on Laurent series representations of the Maehly type. The procedures for developing the Padé–Chebyshev coefficients are similar to that for a traditional Padé approximant based on power series [8] but with essential modifications. By equating series coefficients and combining equations appropriately, a linear system of equations is successfully developed into two sub-systems, one for determining the denominator coefficients only and one for explicitly defining the numerator coefficients in terms of the denominator coefficients. In all cases, a type (m,n) Padé–Chebyshev approximant, of degree m in the numerator and n in the denominator, is matched to the Chebyshev series up to terms of degree m+n, based on knowledge of the Chebyshev coefficients up to degree m+2n. Numerical tests are carried out on all four Padé–Chebyshev approximants, and results are outstanding, with some formidable improvements being achieved over partial sums of Laurent–Chebyshev series on a variety of functions. In part II of this paper [7] Padé–Chebyshev approximants of Clenshaw–Lord type will be developed for the four kinds of Chebyshev series and compared with those of the Maehly type.     

Rational approximations for the cosine function; P-acceptability and order

Properties of order stars corresponding to rational approximations for cos z are derived and are used to prove that the order of accuracy of a P-acceptable approximantR _nm(z ²), with numerator of degreen and denominator of degreem, cannot exceed 2m. It is shown that if the poles ofR _nm(z ²) are restricted to pure-imaginary values ofz the maximum attainable order is 2n+2, whatever the value ofm1. A study of rational approximations for the cosine function produced by symmetric one-step collocation methods, applied to the differential equationy ⁿ =–² y, provides the answer to a question posed by Kramarz [BIT 20 (1980) 215–222]; there are no P-stable methods of that type.     

Inequalities for the interpolation points in Chebyshev approximation by polynomials

Letf andg be approximated in the Chebyshev sense by polynomials of degree n and n–1, respectively. It is shown that if the sum and difference of the normalized (n+1)-st derivatives off andg do not change sign, then the interpolation points ofg separate those off. A corollary is that the zeros of the Chebyshev polynomialT _n separate the interpolation points off iff ⁽ⁿ⁺¹⁾ does not change sign. The sharpness of this result is demonstrated.     

Polynomials of minimalL α-deviation, α>0

Let _n–1 be the linear space of algebraic polynomials of degreen–1. We prove that the extremal problem

A Jacobi spectral Galerkin method for the integrated forms of fourth‐order elliptic differential equations

This article analyzes the solution of the integrated forms of fourth‐order elliptic differential equations on a rectilinear domain using a spectral Galerkin method. The spatial approximation is based on Jacobi polynomials P (x), with α, β ∈ (?1, ∞) and n the polynomial degree. For α = β, one recovers the ultraspherical polynomials (symmetric Jacobi polynomials) and for α = β = ?½, α = β = 0, the Chebyshev of the first and second kinds and Legendre polynomials respectively; and for the nonsymmetric Jacobi polynomials, the two important special cases α = ?β = ±½ (Chebyshev polynomials of the third and fourth kinds) are also recovered. The two‐dimensional version of the approximations is obtained by tensor products of the one‐dimensional bases. The various matrix systems resulting from these discretizations are carefully investigated, especially their condition number. An algebraic preconditioning yields a condition number of O(N), N being the polynomial degree of approximation, which is an improvement with respect to the well‐known condition number O(N⁸) of spectral methods for biharmonic elliptic operators. The numerical complexity of the solver is proportional to N^d+1 for a d‐dimensional problem. This operational count is the best one can achieve with a spectral method. The numerical results illustrate the theory and constitute a convincing argument for the feasibility of the method. © 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2009     

Error bounds for a near-minimax approximation

It is known that a near minimax polynomial approximation tof C [–1, 1] is provided by a finite carrier projectionM _n fromC[–1, 1] onto the subspace of all polynomials of degree n, such thatM _nf is a weighted least squares approximation off on the set consisting of the extreme points of the Chebyshev polynomialT _{2n + 1}. In this paper, upper bounds for the error f–M _n f are given in terms of divided differences.     

Discretization of Volterra integral equations of the first kind (II)

Summary In the present paper integral equations of the first kind associated with strictly monotone Volterra integral operators are solved by projecting the exact solution of such an equation into the spaceS _m ^(–1) (Z _N ) of piecewise polynomials of degreem0, possessing jump discontinuities on the setZ _N of knots. Since the majority of direct one-step methods (including the higher-order block methods) result from particular discretizations of the moment integrals occuring in the above projection method we obtain a unified convergence analysis for these methods; in addition, the above approach yields the tools to deal with the question of the connection between the location of the collocation points used to determine the projection inS _m ^(–1) (Z _N ) and the order of convergence of the method.This research was supported by the National Research Council of Canada (Grant No. A-4805)     

Representation of Reproducing Kernels and the Lebesgue Constants on the Ball

For the weight function (1−x²)^μ−1/2 on the unit ball, a closed formula of the reproducing kernel is modified to include the case −1/2<μ<0. The new formula is used to study the orthogonal projection of the weighted L² space onto the space of polynomials of degree at most n, and it is proved that the uniform norm of the projection operator has the growth rate of n^(d−1)/2 for μ<0, which is the smallest possible growth rate among all projections, while the rate for μ0 is n^μ+(d−1)/2.     

Near-best multivariate approximation by Fourier series, Chebyshev series and Chebyshev interpolation

A set of results concerning goodness of approximation and convergence in norm is given for L_∞ and L₁ approximation of multivariate functions on hypercubes. Firstly the trigonometric polynomial formed by taking a partial sum of a multivariate Fourier series and the algebraic polynomials formed either by taking a partial sum of a multivariate Chebyshev series of the first kind or by interpolating at a tensor product of Chebyshev polynomial zeros are all shown to be near-best L_∞ approximations. Secondly the trigonometric and algebraic polynomials formed by taking, respectively, a partial sum of a multivariate Fourier series and a partial sum of a multivariate Chebyshev series of the second kind are both shown to be hear-best L₁ approximations. In all the cases considered, the relative distance of a near-best approximation from a corresponding best approximation is shown to be at most of the order of Π log n_j, where n_j (j = 1, 2,…, N) are the respective degrees of approximation in the N individual variables. Moreover, convergence in the relevant norm is established for all the sequences of near-best approximations under consideration, subject to appropriate restrictions on the function space.     

The Minimality Properties of Chebyshev Polynomials and Their Lacunary Series

By considering four kinds of Chebyshev polynomials, an extended set of (real) results are given for Chebyshev polynomial minimality in suitably weighted Hölder norms on [–1,1], as well as (L ) minimax properties, and best L ₁ sufficiency requirements based on Chebyshev interpolation. Finally we establish best L _p , L and L ₁ approximation by partial sums of lacunary Chebyshev series of the form _i=0 a ⁱ _b ⁱ(x) where _n (x) is a Chebyshev polynomial and b is an odd integer 3. A complete set of proofs is provided.     

A local inverse for nonlinear mappings

A mapping :R ⁿ R ^m , nm, with Jacobian of full column-rank, has a local inverse that is analogous to the Moore–Penrose inverse of linear mappings.     

Cauchy, Ferrers-Jackson and Chebyshev polynomials and identities for the powers of elements of some conjugate recurrence sequences

In this paper some decompositions of Cauchy polynomials, Ferrers-Jackson polynomials and polynomials of the form x ²ⁿ + y ²ⁿ , n ∈ ℕ, are studied. These decompositions are used to generate the identities for powers of Fibonacci and Lucas numbers as well as for powers of the so called conjugate recurrence sequences. Also, some new identities for Chebyshev polynomials of the first kind are presented here.     

On multiresolution analysis of multiplicityd

In this paper we study some basic properties of multiresolution analysis of multiplicityd in several variables and discuss some examples related to the spaces of cardinal splines with respect to the unidiagonal or the crisscross partition of the plane. Furthermore, in analogy with [8], we show that if the scaling functions are compactly supported, then it is possible to find compactly supported mother wavelets _l ,l=1,...,2 ⁿ d–d, in such a way that the family {2 ^jn/2 _l (2 ^j x–v)} is a semiorthogonal basis ofL ² ( ⁿ ).     

On real and complex-valued bivariate Chebyshev polynomials

In the real uniform approximation of the function x^myⁿ by the space of bivariate polynomials of total degree m + n − 1 on the unit square, the product of monic univariate Chebyshev polynomials yields an optimal error. We exploit the fundamental Noether's theorem of algebraic curves theory to give necessary and sufficient conditions for unicity and to describe the set of optimal errors in case of nonuniqueness. Then, we extend these results to the complex approximation on biellipses. It turns out that the product of Chebyshev polynomials also provides an optimal error and that the same kind of uniqueness conditions prevail in the complex case. Yet, when nonuniqueness occurs, the characterization of the set of optimal errors presents peculiarities, compared to the real problem.     

A set of orthogonal polynomials induced by a given orthogonal polynomial

Summary Given an integern 1, and the orthogonal polynomials _n (·; d) of degreen relative to some positive measured, the polynomial system induced by _n is the system of orthogonal polynomials corresponding to the modified measure . Our interest here is in the problem of determining the coefficients in the three-term recurrence relation for the polynomials from the recursion coefficients of the orthogonal polynomials belonging to the measured. A stable computational algorithm is proposed, which uses a sequence ofQR steps with shifts. For all four Chebyshev measuresd, the desired coefficients can be obtained analytically in closed form. For Chebyshev measures of the first two kinds this was shown by Al-Salam, Allaway and Askey, who used sieved orthogonal polynomials, and by Van Assche and Magnus via polynomial transformations. Here, analogous results are obtained by elementary methods for Chebyshev measures of the third and fourth kinds. (The same methods are also applicable to the other two Chebyshev measures.) Interlacing properties involving the zeros of _n and those of are studied for Gegenbauer measures, as well as the orthogonality—or lack thereof—of the polynomial sequence .Work supported in part by the National Science Foundation under grant DMS-9023403.Dedicated to the memory of Alexander M. Ostrowski on the occasion of the 100th anniversary of his birth.