Constrained near-minimax approximation by weighted expansion and interpolation using Chebyshev polynomials of the second,third, and fourth kinds

Well known results on near-minimax approximation using Chebyshev polynomials of the first kind are here extended to Chebyshev polynomials of the second, third, and fourth kinds. Specifically, polynomial approximations of degreen weighted by (1–x ²)^1/2, (1+x)^1/2 or (1–x)^1/2 are obtained as partial sums of weighted expansions in Chebyshev polynomials of the second, third, or fourth kinds, respectively, to a functionf continuous on [–1, 1] and constrained to vanish, respectively, at ±1, –1 or +1. In each case a formula for the norm of the resulting projection is determined and shown to be asymptotic to 4^–2logn +A +o(1), and this provides in each case and explicit bound on the relative closeness of a minimax approximation. The constantA that occurs for the second kind polynomial is markedly smaller, by about 0.27, than that for the third and fourth kind, while the latterA is identical to that for the first kind, where the projection norm is the classical Lebesgue constant _n . The results on the third and fourth kind polynomials are shown to relate very closely to previous work of P.V. Galkin and of L. Brutman.Analogous approximations are also obtained by interpolation at zeros of second, third, or fourth kind polynomials of degreen+1, and the norms of resulting projections are obtained explicitly. These are all observed to be asymptotic to 2^–1logn +B +o(1), and so near-minimax approximations are again obtained. The norms for first, third, and fourth kind projections appear to be converging to each other. However, for the second kind projection, we prove that the constantB is smaller by a quantity asymptotic to 2^–1log2, based on a conjecture about the point of attainment of the supremum defining the projection norm, and we demonstrate that the projection itself is remarkably close to a minimal (weighted) interpolation projection.All four kinds of Chebyshev polynomials possess a weighted minimax property, and, in consequence, all the eight approximations discussed here coincide with minimax approximations when the functionf is a suitably weighted polynomial of degreen+1.     

Polynomials of Binomial Type and Renewal Sequences

We study polynomials of binomial type that have an exponential generating function of the form { 1 ? f(u)^?x}. They have a close connection with renewal sequences. The asymptotic behavior as n ? ∞ is studied.     

New degree bounds for polynomial threshold functions

A real multivariate polynomial p(x ₁, …, x _n ) is said to sign-represent a Boolean function f: {0,1} ⁿ →{−1,1} if the sign of p(x) equals f(x) for all inputs x∈{0,1} ⁿ . We give new upper and lower bounds on the degree of polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs.     

A counterexample in copositive approximation

The present paper gives a converse result by showing that there exists a functionf ∈C _[−1,1], which satisfies that sgn(x)f(x) ≥ 0 forx ∈ [−1, 1], such that {fx75-1} whereE _n ⁽⁰⁾ (f, 1) is the best approximation of degreen tof by polynomials which are copositive with it, that is, polynomialsP withP(x(f(x) ≥ 0 for allx ∈ [−1, 1],E _n(f) is the ordinary best polynomial approximation off of degreen.     

Estimates for the first and second derivatives of the Stieltjes polynomials

Let w_λ(x)(1−x²)^λ−1/2 and P_n^(λ) be the ultraspherical polynomials with respect to w_λ(x). Then we denote E_n+1^(λ) the Stieltjes polynomials with respect to w_λ(x) satisfyingIn this paper, we give estimates for the first and second derivatives of the Stieltjes polynomials E_n+1^(λ) and the product E_n+1^(λ)P_n^(λ) by obtaining the asymptotic differential relations. Moreover, using these differential relations we estimate the second derivatives of E_n+1^(λ)(x) and E_n+1^(λ)(x)P_n^(λ)(x) at the zeros of E_n+1^(λ)(x) and the product E_n+1^(λ)(x)P_n^(λ)(x), respectively.     

Coincidence of Least Uniform Deviations of Functions from Polynomials and Rational Fractions

For a given nonincreasing vanishing sequence {a _n } _{n = 0} of nonnegative real numbers, we find necessary and sufficient conditions for a sequence {n _k } _{k = 0} to have the property that for this sequence there exists a function f continuous on the interval [0,1] and satisfying the condition that , k = 0,1,2,..., where E _n (f) and R _n,m (f) are the best uniform approximations to the function f by polynomials whose degree does not exceed n and by rational functions of the form r _n,m (x) = p _n (x)/q _m (x), respectively.     

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.     

On Generalized Hermite–Fejér Interpolation of Lagrange Type on the Chebyshev Nodes

For fC[−1, 1], let H_m, n(f, x) denote the (0, 1, …,anbsp;m) Hermite–Fejér (HF) interpolation polynomial of f based on the Chebyshev nodes. That is, H_m, n(f, x) is the polynomial of least degree which interpolates f(x) and has its first m derivatives vanish at each of the zeros of the nth Chebyshev polynomial of the first kind. In this paper a precise pointwise estimate for the approximation error |H_2m, n(f, x)−f(x)| is developed, and an equiconvergence result for Lagrange and (0, 1, …, 2m) HF interpolation on the Chebyshev nodes is obtained. This equiconvergence result is then used to show that a rational interpolatory process, obtained by combining the divergent Lagrange and (0, 1, …, 2m) HF interpolation methods on the Chebyshev nodes, is convergent for all fC[−1, 1].     

A method of constructing Krall's polynomials

We propose a method of constructing orthogonal polynomials P_n(x) (Krall's polynomials) that are eigenfunctions of higher-order differential operators. Using this method we show that recurrence coefficients of Krall's polynomials P_n(x) are rational functions of n. Let P_n^(a,b;M)(x) be polynomials obtained from the Jacobi polynomials P_n^(a,b)(x) by the following procedure. We add an arbitrary concentrated mass M at the endpoint of the orthogonality interval with respect to the weight function of the ordinary Jacobi polynomials. We find necessary conditions for the parameters a,b in order for the polynomials P_n^(a,b;M)(x) to obey a higher-order differential equation. The main result of the paper is the following. Let a be a positive integer and b⩾−1/2 an arbitrary real parameter. Then the polynomials P_n^(a,b;M)(x) are Krall's polynomials satisfying a differential equation of order 2a+4.     

On the error terms for representation numbers of quadratic forms

Let f be a primitive positive integral binary quadratic form of discriminant −D, and r _f (n) the number of representations of n by f up to automorphisms of f. We first improve the error term E(x) of $ \sum\limits_{n \leqq x} {r_f (n)^\beta } $ \sum\limits_{n \leqq x} {r_f (n)^\beta } for any positive integer β. Next, we give an estimate of ∫₁ ^T |E(x)|² x ^−3/2 dx when β = 1.     

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.     

On the asymptotic behavior of the bestL ∞-approximation by polynomials

LetE _n (f) denote the sup-norm-distance (with respect to the interval [?1, 1]) betweenf and the set of real polynomials of degree not exceedingn. For functions likee ^x , cosx, etc., the order ofE _n (f) asn→∞ is well known. A typical result is $$2^{n - 1} n!E_{n - 1} (e^x ) = 1 + 1/4n + O(n^{ - 2} ).$$ It is shown in this paper that 2 ^n?1 n!E _n?1(e ^x ) possesses a complete asymptotic expansion. This result is contained in the more general result that for a wide class of entire functions (containing, for example, exp(cx), coscx, and the Bessel functionsJ _k (x)) the quantity $$2^{n - 1} n!E_{n - 1} \left( f \right)/f^{(n)} \left( 0 \right)$$ possesses a complete asymptotic expansion (providedn is always even (resp. always odd) iff is even (resp. odd)).     

Linear Differential Equations with Variable Coefficients in Regular and Some Singular Cases

In this paper the asymptotic properties as t → + ∞ for a single linear differential equation of the form x⁽ⁿ⁾ + a₁ (t)x^(n?1)+…. + a_n(t)x = 0, where the coefficients aj (z) are supposed to be of the power order of growth, are considered. The results obtained in the previous publications of the author were related to the so called regular case when a complete set of roots {λ,(t)}, j = 1, 2, …, n of the characteristic polynomial yⁿ + a₁ (t)y^n?1 + … + a_n(t) possesses the property of asymptotic separability. One of the main restrictions of the regular case consists of the demand that the roots of the set {λ,(t)} have not to be equivalent in pairs for t → + ∞. In this paper we consider the some more general case when the set of characteristic roots possesses the property of asymptotic independence which includes the case when the roots may be equivdent in pairs. But some restrictions on the asymptotic behaviour of their differences λ_i(t)→ λ_j(t) are preserved. This case demands more complicated technique of investigation. For this purpose the so called asymptotic spaces were introduced. The theory of asymptotic spaces is used for formal solution of an operator equation of the form x = A(x) and has the analogous meaning as the classical theory of solving this equation in Band spaces. For the considered differential equation, the main asymptotic terms of a fundamental system of solution is given in a simple explicit form and the asymptotic fundamental system is represented in the form of asymptotic Emits for several iterate sequences.     

q-Bernstein polynomials and their iterates

Let B_n( f,q;x), n=1,2,… be q-Bernstein polynomials of a function f : [0,1]→C. The polynomials B_n( f,1;x) are classical Bernstein polynomials. For q≠1 the properties of q-Bernstein polynomials differ essentially from those in the classical case. This paper deals with approximating properties of q-Bernstein polynomials in the case q>1 with respect to both n and q. Some estimates on the rate of convergence are given. In particular, it is proved that for a function f analytic in {z: |z|<q+} the rate of convergence of {B_n( f,q;x)} to f(x) in the norm of C[0,1] has the order q⁻ⁿ (versus 1/n for the classical Bernstein polynomials). Also iterates of q-Bernstein polynomials {B_n^j_n( f,q;x)}, where both n→∞ and j_n→∞, are studied. It is shown that for q(0,1) the asymptotic behavior of such iterates is quite different from the classical case. In particular, the limit does not depend on the rate of j_n→∞.     

New Coins from Old, Smoothly

Given a (known) function f:[0,1]→(0,1), we consider the problem of simulating a coin with probability of heads f(p) by tossing a coin with unknown heads probability p, as well as a fair coin, N times each, where N may be random. The work of Keane and O’Brien (ACM Trans. Model. Comput. Simul. 4(2):213–219, 1994) implies that such a simulation scheme with the probability ℙ _p (N<∞) equal to 1 exists if and only if f is continuous. Nacu and Peres (Ann. Appl. Probab. 15(1A):93–115, 2005) proved that f is real analytic in an open set S⊂(0,1) if and only if such a simulation scheme exists with the probability ℙ _p (N>n) decaying exponentially in n for every p∈S. We prove that for α>0 noninteger, f is in the space C ^α [0,1] if and only if a simulation scheme as above exists with ℙ _p (N>n)≤C(Δ _n (p)) ^α , where \varDelta _n(x):=max{?{x(1-x)/n},1/n}\varDelta _{n}(x):=\max\{\sqrt{x(1-x)/n},1/n\}. The key to the proof is a new result in approximation theory: Let B⁺_n\mathcal{B}^{+}_{n} be the cone of univariate polynomials with nonnegative Bernstein coefficients of degree n. We show that a function f:[0,1]→(0,1) is in C ^α [0,1] if and only if f has a series representation ?_n=1^￥F_n\sum_{n=1}^{\infty}F_{n} with F_n ? B⁺_nF_{n}\in \mathcal{B}^{+}_{n} and ∑ _k>n F _k (x)≤C(Δ _n (x)) ^α for all x∈[0,1] and n≥1. We also provide a counterexample to a theorem stated without proof by Lorentz (Math. Ann. 151:239–251, 1963), who claimed that if some j_n ? B⁺_n\varphi_{n}\in\mathcal{B}^{+}_{n} satisfy |f(x)−φ _n (x)|≤C(Δ _n (x)) ^α for all x∈[0,1] and n≥1, then f∈C ^α [0,1].     

Asymptotic analysis of the Hermite polynomials from their differential–difference equation

We analyze the Hermite polynomials H _n (x) and their zeros asymptotically, as n → ∞ We obtain asymptotic approximations from the differential–difference equation which they satisfy, using the ray method. We give numerical examples showing the accuracy of our formulas.     

Stirling polynomials

An investigation is made of the polynomials f_k(n) = S(n + k, n) and g_k(n) = (?1)^ks(n, n ? k), where S and s denote the Stirling numbers of the second and first kind, respectively. The main result gives a combinatorial interpretation of the coefficients of the polynomial (1 ? x)^2k+1Σ_n=0^∞f_k(n)xⁿ analogous to the well-known combinatorial interpretation of the Eulerian numbers in terms of descents of permutations.     

On the neutrix composition of the distributions x −s ln m |x| and x r

Let F be a distribution and let f be a locally summable function. The distribution F(f) is defined as the neutrix limit of the sequence {F _n (f)}, where F _n (x) = F(x) * δ _n (x) and {δ _n (x)} is a certain sequence of infinitely differentiable functions converging to the Dirac delta-function δ(x). The composition of the distributions x ^?s ln ^m |x| and x ^r is proved to exist and be equal to r ^m x ^?rs ln ^m |x| for r, s, m = 2, 3….     

On the sets of branch points of mappings more general than quasiregular

It is shown that if a point x ₀ ∊ ℝ ⁿ , n ≥ 3, is an essential isolated singularity of an open discrete Q-mapping f : D → [`(\mathbb R<sup>n</sup>)] \overline {\mathbb {R}^n} , B <sub>f</sub> is the set of branch points of f in D; and a point z <sub>0</sub> ∊ [`(\mathbb Rⁿ)] \overline {\mathbb {R}^n} is an asymptotic limit of f at the point x ₀; then, for any neighborhood U containing the point x ₀; the point z ₀ ∊ [`(f( B<sub>f</sub> ?U ))] \overline {f\left( {B_f \cap U} \right)} provided that the function Q has either a finite mean oscillation at the point x <sub>0</sub> or a logarithmic singularity whose order does not exceed n − 1: Moreover, for n ≥ 2; under the indicated conditions imposed on the function Q; every point of the set [`(\mathbb Rⁿ)] \overline {\mathbb {R}^n} \ f(D) is an asymptotic limit of f at the point x ₀. For n ≥ 3, the following relation is true: [`(\mathbbR<sup>n</sup> )] \f( D ) ì [`(f B_f )] \overline {\mathbb{R}^n } \backslash f\left( D \right) \subset \overline {f\,B_f } . In addition, if ￥ ? f( D ) \infty \notin f\left( D \right) , then the set f B _f is infinite and x₀ ? [`(B_f )] x_0 \in \overline {B_f } .