The Price of Pessimism for Multidimensional Quadrature

We study multivariate integration in the worst case setting for weighted Korobov spaces of smooth periodic functions of d variables. We wish to reduce the initial error by a factor for functions from the unit ball of the weighted Korobov space. Tractability means that the minimal number of function samples needed to solve the problem is polynomial in ⁻¹ and d. Strong tractability means that we have only a polynomial dependence in ⁻¹. This problem has been recently studied for quasi-Monte Carlo quadrature rules and for quadrature rules with non-negative coefficients. In this paper we study arbitrary quadrature rules. We show that tractability and strong tractability in the worst case setting hold under the same assumptions on the weights of the Korobov space as for the restricted classes of quadrature rules. More precisely, let γ_j moderate the behavior of functions with respect to the jth variable in the weighted Korobov space. Then strong tractability holds iff ∑^∞_j=1 γ_j<∞, whereas tractability holds iff lim sup_d→∞ ∑^d_j=1 γ_j/ln d<∞. We obtain necessary conditions on tractability and strong tractability by showing that multivariate integration for the weighted Korobov space is no easier than multivariate integration for the corresponding weighted Sobolev space of smooth functions with boundary conditions. For the weighted Sobolev space we apply general results from E. Novak and H. Woźniakowski (J. Complexity17 (2001), 388–441) concerning decomposable kernels.     

Tractability of Multivariate Integration for Periodic Functions

We study multivariate integration in the worst case setting for weighted Korobov spaces of smooth periodic functions of d variables. We wish to reduce the initial error by a factor ε for functions from the unit ball of the weighted Korobov space. Tractability means that the minimal number of function samples needed to solve the problem is polynomial in ε⁻¹ and d. Strong tractability means that we have only a polynomial dependence in ε⁻¹. This problem has been recently studied for quasi-Monte Carlo quadrature rules and for quadrature rules with non-negative coefficients. In this paper we study arbitrary quadrature rules. We show that tractability and strong tractability in the worst case setting hold under the same assumptions on the weights of the Korobov space as for the restricted classes of quadrature rules. More precisely, let γ_j moderate the behavior of functions with respect to the jth variable in the weighted Korobov space. Then strong tractability holds iff ∑^∞_j=1 γ_j<∞, whereas tractability holds iff lim sup_d→∞ ∑^d_j=1 γ_j/ln d<∞. We obtain necessary conditions on tractability and strong tractability by showing that multivariate integration for the weighted Korobov space is no easier than multivariate integration for the corresponding weighted Sobolev space of smooth functions with boundary conditions. For the weighted Sobolev space we apply general results from E. Novak and H. Woźniakowski (J. Complexity17 (2001), 388–441) concerning decomposable kernels.     

Multivariate approximation in the worst case setting over reproducing kernel Hilbert spaces

We study the worst case setting for approximation of d variate functions from a general reproducing kernel Hilbert space with the error measured in the L_∞ norm. We mainly consider algorithms that use n arbitrary continuous linear functionals. We look for algorithms with the minimal worst case errors and for their rates of convergence as n goes to infinity. Algorithms using n function values will be analyzed in a forthcoming paper.We show that the L_∞ approximation problem in the worst case setting is related to the weighted L₂ approximation problem in the average case setting with respect to a zero-mean Gaussian stochastic process whose covariance function is the same as the reproducing kernel of the Hilbert space. This relation enables us to find optimal algorithms and their rates of convergence for the weighted Korobov space with an arbitrary smoothness parameter α>1, and for the weighted Sobolev space whose reproducing kernel corresponds to the Wiener sheet measure. The optimal convergence rates are n^-(α-1)/2 and n^-1/2, respectively.We also study tractability of L_∞ approximation for the absolute and normalized error criteria, i.e., how the minimal worst case errors depend on the number of variables, d, especially when d is arbitrarily large. We provide necessary and sufficient conditions on tractability of L_∞ approximation in terms of tractability conditions of the weighted L₂ approximation in the average case setting. In particular, tractability holds in weighted Korobov and Sobolev spaces only for weights tending sufficiently fast to zero and does not hold for the classical unweighted spaces.     

On numerical improvement of Gauss–Legendre quadrature rules

Among all integration rules with n points, it is well-known that n-point Gauss–Legendre quadrature rule∫₋₁¹f(x) dx∑_i=1ⁿw_if(x_i)has the highest possible precision degree and is analytically exact for polynomials of degree at most 2n−1, where nodes x_i are zeros of Legendre polynomial P_n(x), and w_i's are corresponding weights.In this paper we are going to estimate numerical values of nodes x_i and weights w_i so that the absolute error of introduced quadrature rule is less than a preassigned tolerance ε₀, say ε₀=10⁻⁸, for monomial functionsf(x)=x^j, j=0,1,…,2n+1.(Two monomials more than precision degree of Gauss–Legendre quadrature rules.) We also consider some conditions under which the new rules act, numerically, more accurate than the corresponding Gauss–Legendre rules. Some examples are given to show the numerical superiority of presented rules.     

Summability of Product Jacobi Expansions

Orthogonal expansions in product Jacobi polynomials with respect to the weight function W_α, β(x)=∏^d_j=1 (1−x_j)^α_j (1+x_j)^β_j on [−1, 1]^d are studied. For α_j, β_j>−1 and α_j+β_j−1, the Cesàro (C, δ) means of the product Jacobi expansion converge in the norm of L^p(W_{α, β}, [−1, 1]^d), 1p<∞, and C([−1, 1]^d) if

Full-size image

Moreover, for α_j, β_j−1/2, the (C, δ) means define a positive linear operator if and only if δ∑^d_i=1 (α_i+β_i)+3d−1.     

Weighted simultaneous Chebyshev approximation

In this paper we discuss the problem of weighted simultaneous Chebyshev approximation to functions f₁,…f_m ε C(X) (1 m ∞), i.e., we wish to minimize the expression {∑^m_{j = 1} λ_j¦f_j − q¦^p}^1/p∞, where λ_j > 0, ∑^m_{j = 1} λ_j = 1, p 1. For this problem we establish the main theorems of the Chebyshev theory, which include the theorems of existence, alternation, de La Vallée Poussin, uniqueness, strong uniqueness, as well as that of continuity of the best approximation operator, etc.     

Summability of orthogonal expansions of several variables

Summability of spherical h-harmonic expansions with respect to the weight function ∏_j=1^d |x_j|^2κ_j (κ_j0) on the unit sphere S^d−1 is studied. The main result characterizes the critical index of summability of the Cesàro (C,δ) means of the h-harmonic expansion; it is proved that the (C,δ) means of any continuous function converge uniformly in the norm of C(S^d−1) if and only if δ>(d−2)/2+∑_j=1^d κ_j−min_1jd κ_j. Moreover, it is shown that for each point not on the great circles defined by the intersection of the coordinate planes and S^d−1, the (C,δ) means of the h-harmonic expansion of a continuous function f converges pointwisely to f if δ>(d−2)/2. Similar results are established for the orthogonal expansions with respect to the weight functions ∏_j=1^d |x_j|^2κ_j(1−|x|²)^μ−1/2 on the unit ball B^d and ∏_j=1^d x_j^κ_j−1/2(1−|x|₁)^μ−1/2 on the simplex T^d. As a related result, the Cesàro summability of the generalized Gegenbauer expansions associated to the weight function |t|^2μ(1−t²)^λ−1/2 on [−1,1] is studied, which is of interest in itself.     

On the sequence of powers of a stochastic matrix with large exponent

We consider the class of primitive stochastic n×n matrices A, whose exponent is at least (n²−2n+2)/2+2. It is known that for such an A, the associated directed graph has cycles of just two different lengths, say k and j with k>j, and that there is an α between 0 and 1 such that the characteristic polynomial of A is λⁿ−αλ^n−j−(1−α)λ^n−k. In this paper, we prove that for any mn, if α1/2, then A^m+k−A^m_∞A^m−1w^T_∞, where 1 is the all-ones vector and w^T is the left-Perron vector for A, normalized so that w^T1=1. We also prove that if jn/2, n31 and , then A^m+j−A^m_∞A^m−1w^T_∞ for all sufficiently large m. Both of these results lead to lower bounds on the rate of convergence of the sequence A^m.     

Lattice-Nyström method for Fredholm integral equations of the second kind with convolution type kernels

We consider Fredholm integral equations of the second kind of the form , where g and k are given functions from weighted Korobov spaces. These spaces are characterized by a smoothness parameter α>1 and weights γ₁≥γ₂≥. The weight γ_j moderates the behavior of the functions with respect to the jth variable. We approximate f  by the Nyström method using n rank-1 lattice points. The combination of convolution and lattice group structure means that the resulting linear system can be solved in O(nlogn) operations. We analyze the worst case error measured in sup norm for functions g in the unit ball and a class of functions k in weighted Korobov spaces. We show that the generating vector of the lattice rule can be constructed component-by-component to achieve the optimal rate of convergence O(n^-α/2+δ), δ>0, with the implied constant independent of the dimension d under an appropriate condition on the weights. This construction makes use of an error criterion similar to the worst case integration error in weighted Korobov spaces, and the computational cost is only O(nlognd) operations. We also study the notion of QMC-Nyström tractability: tractability means that the smallest n needed to reduce the worst case error (or normalized error) to is bounded polynomially in ^-1 and d; strong tractability means that the bound is independent of d. We prove that strong QMC-Nyström tractability in the absolute sense holds iff , and QMC-Nyström tractability holds in the absolute sense iff .     

On the spectral function of the Poisson–Voronoi cells

Denote by (t)=∑_n1e^−λ_nt, t>0, the spectral function related to the Dirichlet Laplacian for the typical cell of a standard Poisson–Voronoi tessellation in . We show that the expectation E(t), t>0, is a functional of the convex hull of a standard d-dimensional Brownian bridge. This enables us to study the asymptotic behaviour of E(t), when t→0⁺,+∞. In particular, we prove that the law of the first eigenvalue λ₁ of satisfies the asymptotic relation lnP{λ₁t}−2^dω_dj_(d−2)/2^d·t^−d/2 when t→0⁺, where ω_d and j_(d−2)/2 are respectively the Lebesgue measure of the unit ball in and the first zero of the Bessel function J_(d−2)/2.     

Cesàro Asymptotics for Orthogonal Polynomials on the Unit Circle and Classes of Measures

The convergence in L²( ) of the even approximants of the Wall continued fractions is extended to the Cesàro–Nevai class CN, which is defined as the class of probability measures σ with lim_n→∞ ∑ⁿ⁻¹_k=0 |a_k|=0, {a_n}_n0 being the Geronimus parameters of σ. We show that CN contains universal measures, that is, probability measures for which the sequence {|_n|² dσ}_n0 is dense in the set of all probability measures equipped with the weak-* topology. We also consider the “opposite” Szeg class which consists of measures with ∑^∞_n=0 (1−|a_n|²)^1/2<∞ and describe it in terms of Hessenberg matrices.     

A Singular Riesz Product in the Nevai Class and Inner Functions with the Schur Parameters in ∩p>2 l

There exist singular Riesz products dσ=∏^∞_κ=1 (1+Re(α_κζ^n_κ)) on the unit circle with the parameters (a_n)_n0 of orthogonal polynomials in L²(dσ) satisfying ∑^∞_n=0 |a_n|^p<+∞ for every p, p>2. The Schur parameters of the inner factor of the Cauchy integral ∫ (ζ−z)⁻¹ dσ(ζ), σ being such a Riesz product, belong to ∩_p>2 l^p.     

Asymptotic Behaviour of Best lp-Approximations from Affi ne Subspaces

In this paper we consider the problem of best approximation in ℓ_pⁿ, 1<p∞. If h_p, 1<p<∞, denotes the best ℓ_p-approximation of the element h ⁿ from a proper affine subspace K of ⁿ, hK, then lim_p→∞h_p=h_∞^*, where h_∞^* is a best uniform approximation of h from K, the so-called strict uniform approximation. Our aim is to prove that for all r there are α_j ⁿ, 1jr, such that

Full-size image

, with γ_p^{(r) n} and γ_p^(r)= (p^−r−1).     

On the Strong Law of Large Numbers and the Law of the Logarithm for Weighted Sums of Independent Random Variables with Multidimensional Indices

Let (X, X ; ^d} be a field of independent identically distributed real random variables, 0 < p < 2, and {a _, ; ( , ) ^d × ^d, ≤ } a triangular array of real numbers, where ^d is the d-dimensional lattice. Under the minimal condition that sup _, |a _, | < ∞, we show that | |^{− 1/p} ∑ _≤ a _, X → 0 a.s. as | | → ∞ if and only if E(|X|^p(L|X|)^{d − 1}) < ∞ provided d ≥ 2. In the above, if 1 ≤ p < 2, the random variables are needed to be centered at the mean. By establishing a certain law of the logarithm, we show that the Law of the Iterated Logarithm fails for the weighted sums ∑ _≤ a _, X under the conditions that EX = 0, EX² < ∞, and E(X²(L|X|)^{d − 1}/L₂|X|) < ∞ for almost all bounded families {a _, ; ( , ) ^d × ^d, ≤ of numbers.     

Component-by-Component Construction of Good Lattice Rules with a Composite Number of Points

We develop algorithms to construct rank-1 lattice rules in weighted Korobov spaces of periodic functions and shifted rank-1 lattice rules in weighted Sobolev spaces of non-periodic functions. Analyses are given which show that the rules so constructed achieve strong QMC tractability error bounds. Unlike earlier analyses, there is no assumption that n, the number of quadrature points, be a prime number. However, we do assume that there is an upper bound on the number of distinct prime factors of n. The generating vectors and shifts characterizing the rules are constructed ‘component-by-component,’ that is, the (d+1)th components of the generating vectors and shifts are obtained using one-dimensional searches, with the previous d components kept unchanged.     

On Laurent series with multiply positive coefficients

We consider the class of doubly infinite sequences {a _k } _k ^∞ = −∞ whose truncated sequences {a _k } _n ^k = −n are 3-times positive in the sense of Pólya and Fekete for all n = 1, 2, ..., and a ₀ ≠ 0. We obtain a characterization of this class in terms of independent parameters. We also find an estimate of the growth order of the corresponding Laurent series ∑ _{k= −∞} ^∞ akz ^k .     

Lacunary Quadrature Formulae and Interpolation Singularity

Birkholl quadrature formulae (q.f.), which have algebraic degree of precision (ADP) greater than the number of values used, are studied. In particular, we construct a class of quadrature rules of ADP = 2n + 2r + 1 which are based on the information {ƒ^(j)(−1), ƒ^(j)(−1), j = 0, ..., r − 1 ; ƒ(x_i), ƒ^(2m)(x_i), i = 1, ..., n}, where m is a positive integer and r = m, or r = m − 1. It is shown that the corresponding Birkhoff interpolation problems of the same type are not regular at the quadrature nodes. This means that the constructed quadrature formulae are not of interpolatory type. Finally, for each In, we prove the existence of a quadrature formula based on the information {ƒ(x_i), ƒ^(2m)(x_i), i = 1, ..., 2m}, which has algebraic degree of precision 4m + 1.     

On the distributions of the form ∑i (δpi−δni)

We present some properties of the distributions T of the form ∑_i (δ_pi−δ_ni), with ∑_i d(p_i,n_i)<∞, which arise in the study of the 3-d Ginzburg–Landau problem; see Bourgain et al. (C. R. Acad. Sci. Paris, Ser. I 331 (2000) 119–124). We show that there always exists an irreducible representation of T. We also extend a result of Smets (C. R. Acad. Sci. Paris, Ser. I 334 (2002) 371–374) which says that T is a measure iff T can be written as a finite sum of dipoles.     

The Asymptotic Behavior of a Family of Sequences via Tauberian Theorems

We study the asymptotic behavior of a family of sequences defined by the following nonlinear induction relation c₀ = 1 and c_n ∑^k_{j = 1} r_jc_[n/mj] + ∑^k_{j = k + 1} r_jc_{[(n + 1)^1/mj] − 1} for n ≥ 1, where the r_j are real positive numbers and m_j are integers greater than or equal to 2. Depending on the fact that ∑^k_{j = 1} r_j is greater or lower than 1, we prove that c_n/n^α or c_n/(ln n)^α goes to some finite limit for some explicit α. Our study is based on Tauberian theorems and extends a result of Erdös et al.     

Completeness of Trigonometric System with Integer Indices {e; x }

Necessary and sufficient conditions are given which ensure the completeness of the trigonometric systems with integer indices; {e^inx; x }^∞_n=−∞ or {e^inx; x }^∞_n=1 in L^α(μ,  ), α1. If there exists a support Λ of the measure μ which is a wandering set, that is, Λ+2kπ, k=0, ±1, ±2, … are mutually disjoint for different k's, then the linear span of our trigonometric system {e^inx; x }^∞_n=−∞ is dense in L^α(μ,  ) α1. The converse statement is also true.