Full quadrature sums for pth powers of polynomials with Freud weights

In this paper, we provide a solution of the quadrature sum problem of R. Askey for a class of Freud weights. Let r> 0, b (− ∞, 2]. We establish a full quadrature sum estimate

1 p < ∞, for every polynomial P of degree at most n + rn^1/3, where W² is a Freud weight such as exp(−¦x¦), > 1, λ_jn are the Christoffel numbers, x_jn are the zeros of the orthonormal polynomials for the weight W², and C is independent of n and P. We also prove a generalisation, and that such an estimate is not possible for polynomials P of degree M = m(n) if m(n) = n + ξ_nn^1/3, where ξ_n → ∞ as n → ∞. Previous estimates could sum only over those x_jn with ¦x_jn¦ σx_1n, some fixed 0 < σ < 1.     

New interpolatory quadrature formulae with Chebyshev abscissae

We study interpolatory quadrature formulae, relative to the Legendre weight function on [−1,1], having as nodes the zeros of any one of the four Chebyshev polynomials of degree n plus one of the points 1 or −1. In particular, we derive explicit formulae for the weights and examine their positivity, we determine the precise degree of exactness, we obtain asymptotically optimal error bounds, and we examine the definiteness f these quadrature formulae. In addition, we establish their convergence for Riemann integrable functions on [−1, 1] as well as for functions having a monotonic singularity at −1 or 1.     

Estimates for the Remainders of Certain Quadrature Formulas

Estimates of the remainders of certain quadrature formulas are obtained, in particular, of quadrature formulas with nodes that are the zeros of Chebyshev polynomials of the first kind in classes of differentiable functions characterized by a generalized modulus of continuity.     

Generalized Logan’s Problem for Entire Functions of Exponential Type and Optimal Argument in Jackson’s Inequality in <Emphasis Type="Italic">L</Emphasis><Subscript>2</Subscript>(ℝ<Superscript>3</Superscript>)

We study Jackson's inequality between the best approximation of a function f ∈ L₂(R³) by entire functions of exponential spherical type and its generalized modulus of continuity. We prove Jackson's inequality with the exact constant and the optimal argument in the modulus of continuity. In particular, Jackson's inequality with the optimal parameters is obtained for classical modulus of continuity of order r and Thue-Morse modulus of continuity of order r ∈ N. These results are based on the solution of the generalized Logan problem for entire functions of exponential type. For it we construct a new quadrature formulas for entire functions of exponential type.     

On an optimal stopping problem of Gusein-Zade

We study the problem of selecting one of the r best of n rankable individuals arriving in random order, in which selection must be made with a stopping rule based only on the relative ranks of the successive arrivals. For each r up to r=25, we give the limiting (as n→∞) optimal risk (probability of not selecting one of the r best) and the limiting optimal proportion of individuals to let go by before being willing to stop. (The complete limiting form of the optimal stopping rule is presented for each r up to r=10, and for r=15, 20 and 25.) We show that, for large n and r, the optical risk is approximately (1−t^*)^r, where t^*≈0.2834 is obtained as the roof of a function which is the solution to a certain differential equation. The optimal stopping rule τ_r,n lets approximately t^*n arrivals go by and then stops ‘almost immediately’, in the sense that τ_r,n/n→t^* in probability as n→∞, r→∞     

Turán Quadrature Formulas and Christoffel Type Functions for the Chebyshev Polynomials of the Second Kind

An explicit representation for the Cotes numbers of Turán quadrature formulas based on the zeros of the Chebyshev polynomials of the second kind and its asymptotic behavior are given. The asymptotic formula for the corresponding Christoffel type functions is also provided. This revised version was published online in June 2006 with corrections to the Cover Date.     

Binary set functions and parity check matrices

We consider the possibility of extending to a family of sets a binary set function defined on a subfamily so that the extension is, in fact, uniquely determined. We place in this context the problem of finding the least integer n(r) such that every linear code of length n with n n(r), dimension n-r and minimum Hamming distance at least 4 has a parity check matrix composed entirely of odd weight columns and answer this problem by showing that n(r) = 5.2^{r − 4} + 1, r4. This result is applied to yield new constructions and bounds for unequal error protection codes with minimum distances 3 and 4.     

On-line construction of the upper envelope of triangles and surface patches in three dimensions

In this paper, we describe a randomized incremental algorithm for computing the upper envelope (i.e., the pointwise maximum) of a set of n triangles in three dimensions. This algorithm is an on-line algorithm. It is structure-sensitive: the expected cost of inserting the n-th triangle is O(log nΣ_r=1ⁿτ(r)/r²) and depends on the expected size τ(r) of an intermediate result for r triangles. Since τ(r) can be Θ(r²(r)) in the worst case, this cost is bounded in the worst case by O(n(n) log n). (The expected behaviour is analyzed by averaging over all possible orderings of the input.) The main new characteristics is the use of a two-level history graph. (The history graph is an auxiliary data structure maintained by randomized incremental algorithms.) Our algorithm is fairly simple and appears to be efficient in practice. It extends to surfaces and surface patches of fixed maximum algebraic degree.     

On a conjecture of D. B. Hunter

We consider errors of positive quadrature formulas applied to Chebyshev polynomials. These errors play an important role in the error analysis for many function classes. Hunter conjectured that the supremum of all errors in Gaussian quadrature of Chebyshev polynomials equals the norm of the quadrature formula. We give examples, for which Hunter's conjecture does not hold. However, we prove that the conjecture is valid for all positive quadratures if the supremum is replaced by the limit superior. Considering a fixed positive quadrature formula and the sequence of all Chebyshev polynomials, we show that large errors are rare.     

Linear recurrence relations in the algebra of matrices and applications

We study here some linear recurrence relations in the algebra of square matrices. With the aid of the Cayley–Hamilton Theorem, we derive some explicit formulas for Aⁿ (nr) and e^tA for every r×r matrix A, in terms of the coefficients of its characteristic polynomial and matrices A^j, where 0jr−1.     

Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers

The Ramsey number r(H,K_n) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r(K_2,m,K_n)(m−1+o(1))(n/log n)² and r(C_2m,K_n)c(n/log n)^m/(m−1) for m fixed and n→∞. Also r(K_2,n,K_n)=Θ(n³/log² n) and .     

Optimale Approximation mit Nebenbedingungen an lineare Funktionale auf periodischen Funktionen

Summary In a general Hilbert space of periodic functions numerical approximations with equidistant nodes for any bounded linear functional are given which are of minimal error norm in the class of approximations being exact for certain trigonometric polynomials. In examples optimal quadrature formulas with such side conditions are considered.     

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     

Numerical Quadratures for Hadamard Hypersingular Integrals

In this paper,we develop Gaussian quadrature formulas for the Hadamard fi- nite part integrals.In our formulas,the classical orthogonal polynomials such as Legendre and Chebyshev polynomials are used to approximate the density function f(x)so that the Gaussian quadrature formulas have degree n-1.The error estimates of the formulas are obtained.It is found from the numerical examples that the convergence rate and the accu- racy of the approximation results are satisfactory.Moreover,the rate and the accuracy can be improved by choosing appropriate weight functions.     

一类广义Gauss型求积公式

基于被积函数在n次第一类和第二类Chebyshev多项式的零点处的差商,该本构造了两种Gauss型求积公式. 这些求积公式包含了某些已知结果作为特例.更重要的是这些新结果与Gauss-Turan求积公式有密切的联系.     

On a quadrature formula of Micchelli and Rivlin

Micchelli and Rivlin (1972) obtained a quadrature formula of highest algebraic degree of precision for the Fourier-Chebyshev coefficients A_n(f), which is based on the divided differences of f′ at the zeros of the Chebyshev polynomial T_n(x). We give here a simple approach to questions of this type, which applies to the coefficients in arbitrary orthogonal expansion of f. As an auxiliary result we obtain a new interpolation formula and a new representation of the Turán quadrature formula.     

Inertially arbitrary patterns

An n×n sign pattern matrix A is an inertially arbitrary pattern (IAP) if each non-negative triple (rst) with r+s+t=n is the inertia of a matrix with sign pattern A. This paper considers the n×n(n≥2) skew-symmetric sign pattern S_n with each upper off-diagonal entry positive, the (1,1) entry negative, the (nn) entry positive, and every other diagonal entry zero. We prove that S_n is an IAP.     

The zeros of Faber polynomials generated by an -star

It is shown that the zeros of the Faber polynomials generated by a regular -star are located on the -star. This proves a recent conjecture of J. Bartolomeo and M. He. The proof uses the connection between zeros of Faber polynomials and Chebyshev quadrature formulas.

     

Minimal enclosing parallelepiped in 3D

We investigate the problem of finding a minimal volume parallelepiped enclosing a given set of n three-dimensional points. We give two mathematical properties of these parallelepipeds, from which we derive two algorithms of theoretical complexity O(n⁶). Experiments show that in practice our quickest algorithm runs in O(n²) (at least for n10⁵). We also present our application in structural biology.     

Solving satisfiability in less than 2 steps

In this paper we describe and analyse an algorithm for solving the satisfiability problem. If E is a boolean formula in conjunctive normal form with n variables and r clauses, then we will show that this algorithm solves the satisfiability problem for formulas with at most k literals per clause in time O(|F|·_kⁿ), where _k is the greatest number satisfying _k = 2−1/_k^k−1 (in the case of 3-satisfiability ₃ = 1,6181).