Cubature over the sphere in Sobolev spaces of arbitrary order

This paper studies numerical integration (or cubature) over the unit sphere for functions in arbitrary Sobolev spaces H^s(S²), s>1. We discuss sequences of cubature rules, where (i) the rule Q_m(n) uses m(n) points and is assumed to integrate exactly all (spherical) polynomials of degree ≤n and (ii) the sequence (Q_m(n)) satisfies a certain local regularity property. This local regularity property is automatically satisfied if each Q_m(n) has positive weights. It is shown that for functions in the unit ball of the Sobolev space H^s(S²), s>1, the worst-case cubature error has the order of convergence O(n^-s), a result previously known only for the particular case . The crucial step in the extension to general s>1 is a novel representation of , where P_ℓ is the Legendre polynomial of degree ℓ, in which the dominant term is a polynomial of degree n, which is therefore integrated exactly by the rule Q_m(n). The order of convergence O(n^-s) is optimal for sequences (Q_m(n)) of cubature rules with properties (i) and (ii) if Q_m(n) uses m(n)=O(n²) points.     

A lower bound for the worst-case cubature error on spheres of arbitrary dimension

This paper is concerned with numerical integration on the unit sphere S^r of dimension r≥2 in the Euclidean space ℝ^r+1. We consider the worst-case cubature error, denoted by E(Q_m;H^s(S^r)), of an arbitrary m-point cubature rule Q_m for functions in the unit ball of the Sobolev space H^s(S^r), where s>, and show that The positive constant c_s,r in the estimate depends only on the sphere dimension r≥2 and the index s of the Sobolev space H^s(S^r). This result was previously only known for r=2, in which case the estimate is order optimal. The method of proof is constructive: we construct for each Q_m a `bad' function f_m, that is, a function which vanishes in all nodes of the cubature rule and for which Our proof uses a packing of the sphere S^r with spherical caps, as well as an interpolation result between Sobolev spaces of different indices.     

On the construction of multi-dimensional embedded cubature formulae

Summary In order to compute an integralI[f], one needs at least two cubature formulaeQ _j ,j{1, 2}. |Q ₁[f]–Q ₂[f]| can be used as an error estimate for the less precise cubature formula. In order to reduce the amount of work, one can try to reuse some of the function evaluations needed forQ ₁, inQ ₂. The easiest way to construct embedded cubature formulae is: start with a high degree formulaQ ₁, drop (at least) one knot and calculate the weights such that the new formulaQ ₂ is exact for as much monomials as possible. We describe how such embedded formulae with positive weights can be found. The disadvantage of such embedded cubature formulae is that there is in general a large difference in the degree of exactness of the two formulae. In this paper we will explain how the high degree formula can be chosen to obtain an embedded pair of cubature formulae of degrees 2m+1/2m–1. The method works for all regions ⁿ ,n2. We will also show the influence of structure on the cubature formulae.     

Boundary effects on convergence rates for Tikhonov regularization

We consider the Tikhonov regularizer f_λ of a smooth function f ε H^2m[0, 1], defined as the solution (see [1]) to We prove that if f^(j)(0) = f^(j)(1) = 0, J = m, …, k < 2m − 1, then ¦f − f_λ¦_j² Rλ^{(2k − 2j + 3)/2m}, J = 0, …, m. A detailed analysis is given of the effect of the boundary on convergence rates.     

The <Emphasis Type="Italic">s</Emphasis>-energy of spherical designs on <Emphasis Type="Italic">S</Emphasis><Superscript>2</Superscript>

This paper investigates the s-energy of (finite and infinite) well separated sequences of spherical designs on the unit sphere S ². A spherical n-design is a point set on S ² that gives rise to an equal weight cubature rule which is exact for all spherical polynomials of degree ≤n. The s-energy E _s (X) of a point set of m distinct points is the sum of the potential for all pairs of distinct points . A sequence Ξ = {X _m } of point sets X _m ⊂S ², where X _m has the cardinality card(X _m )=m, is well separated if for each pair of distinct points , where the constant λ is independent of m and X _m . For all s>0, we derive upper bounds in terms of orders of n and m(n) of the s-energy E _s (X _m(n)) for well separated sequences Ξ = {X _m(n)} of spherical n-designs X _m(n) with card(X _m(n))=m(n).      

A lower bound on the independence number of arbitrary hypergraphs

We present a lower bound on the independence number of arbitrary hypergraphs in terms of the degree vectors. The degree vector of a vertex v is given by d(v) = (d₁(v), d₂(v), …) where d_m(v) is the number of edges of size m containing v. We define a function f with the property that any hypergraph H = (V, E) satisfies α(H) ≥ Σ_v∈V f(d(v)). This lower bound is sharp when H is a match, and it generalizes known bounds of Caro/Wei and Caro/Tuza for ordinary graphs and uniform hypergraphs. Furthermore, an algorithm for computing independent sets of size as guaranteed by the lower bound is given. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 213–221, 1999     

On the square root of a positive B( )-valued function

Let (Ω, , μ) be a measure space, a separable Banach space, and ^* the space of all bounded conjugate linear functionals on . Let f be a weak^* summable positive B( ^*)-valued function defined on Ω. The existence of a separable Hilbert space , a weakly measurable B( )-valued function Q satisfying the relation Q^*(ω)Q(ω) = f(ω) is proved. This result is used to define the Hilbert space L_2,f of square integrable operator-valued functions with respect to f. It is shown that for B⁺( ^*)-valued measures, the concepts of weak^*, weak, and strong countable additivity are all the same. Connections with stochastic processes are explained.     

The number of K m,m -free graphs

A graph is called H-free if it contains no copy of H. Denote by f _n (H) the number of (labeled) H-free graphs on n vertices. Erdős conjectured that f _n (H) ≤ 2^{(1+o(1))ex(n,H)}. This was first shown to be true for cliques; then, Erdős, Frankl, and R?dl proved it for all graphs H with χ(H)≥3. For most bipartite H, the question is still wide open, and even the correct order of magnitude of log₂ f _n (H) is not known. We prove that f _n (K _m,m ) ≤ 2 ^O (n ^2−1/m ) for every m, extending the result of Kleitman and Winston and answering a question of Erdős. This bound is asymptotically sharp for m∈{2,3}, and possibly for all other values of m, for which the order of ex(n,K _m,m ) is conjectured to be Θ(n ^2−1/m ). Our method also yields a bound on the number of K _m,m -free graphs with fixed order and size, extending the result of Füredi. Using this bound, we prove a relaxed version of a conjecture due to Haxell, Kohayakawa, and Łuczak and show that almost all K _3,3-free graphs of order n have more than 1/20·ex(n,K _3,3) edges.     

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 Error Expansion for some Gauss–Turán Quadratures and <Emphasis Type="Italic">L</Emphasis><Superscript>1</Superscript>-Estimates of the Remainder Term

Our aim in this paper is to obtain error expansions in the Gauss–Turán quadrature formula ∫₋₁¹f(t)w(t) dt=∑_ν=1ⁿ∑_i=0^2sA_i,νf⁽ⁱ⁾(τ_ν)+R_n,s(f), in the case when f is an analytic function in some region of the complex plane containing the interval [−1,1] in its interior. Using a representation of the remainder term R_n,s(f) in the form of contour integral over confocal ellipses, we obtain R_n,1(f) for the four Chebyshev weights and R_n,2(f) for the Chebyshev weight of the first kind. Also, we get a few new L¹-estimates of the remainder term, which are stronger than the previous ones. Some numerical results, illustrations and comparisons are also given. AMS subject classification (2000) 41A55, 65D30, 65D32.Received January 2004. Accepted October 2004. Communicated by Lothar Reichel.M. M. Spalević: This work was supported in part by the Serbian Ministry of Science and Environmental Protection (Project: Applied Orthogonal Systems, Constructive Approximation and Numerical Methods, grant number 2002).     

Signed 2-independence in graphs

A function f : V→{−1,1} defined on the vertices of a graph G=(V,E) is a signed 2-independence function if the sum of its function values over any closed neighbourhood is at most one. That is, for every vV, f(N[v])1, where N[v] consists of v and every vertex adjacent to v. The weight of a signed 2-independence function is f(V)=∑f(v), over all vertices vV. The signed 2-independence number of a graph G, denoted α_s²(G), equals the maximum weight of a signed 2-independence function of G. In this paper, we establish upper bounds for α_s²(G) in terms of the order and size of the graph, and we characterize the graphs attaining these bounds. For a tree T, upper and lower bounds for α_s²(T) are established and the extremal graphs characterized. It is shown that α_s²(G) can be arbitrarily large negative even for a cubic graph G.     

On the Growth of Positive Definite Double Sequences Which Are not Moment Sequences

For every a > 1, there is a function f : N²₀ → R, which is positive semidefinite but not a moment sequence, such that |f(m, n)| ≥ m+ n^a(m+n) for all (m, n). The constant 1 is the best possible.     

A recursive algorithm for the infinity-norm fixed point problem

We present the PFix algorithm for the fixed point problem f(x)=x on a nonempty domain [a,b], where d1, , and f is a Lipschitz continuous function with respect to the infinity norm, with constant q1. The computed approximation satisfies the residual criterion , where >0. In general, the algorithm requires no more than ∑_i=1^dsⁱ function component evaluations, where s≡max(1,log₂(||b−a||_∞/))+1. This upper bound has order as →0. For the domain [0,1]^d with <0.5 we prove a stronger result, i.e., an upper bound on the number of function component evaluations is , where r≡log₂(1/). This bound approaches as r→∞ (→0) and as d→∞. We show that when q<1 the algorithm can also compute an approximation satisfying the absolute criterion , where x^* is the unique fixed point of f. The complexity in this case resembles the complexity of the residual criterion problem, but with tolerance (1−q) instead of . We show that when q>1 the absolute criterion problem has infinite worst-case complexity when information consists of function evaluations. Finally, we report several numerical tests in which the actual number of evaluations is usually much smaller than the upper complexity bound.     

A recurrence property of smooth functions

LetP andQ be real polynomials of degreesd ande, respectively, andf a periodic function. It is shown that, iff iss times differentiable atQ(0), wheres≧7de ³ log 14e ³, then for every ɛ>0 the diophantine inequality ≧FF5C;P(x)f(Q(x)) -P(0)f(Q(0)) -y≧ εx≠0, has a solution. This settles in particular a question raised by Furstenberg and Weiss [6].     

Exponential bounds of mean error for the kernel estimates of regression functions

Let (X, Y), (X₁, Y₁), …, (X_n, Y_n) be i.d.d. R^r × R-valued random vectors with E|Y| < ∞, and let Q_n(x) be a kernel estimate of the regression function Q(x) = E(Y|X = x). In this paper, we establish an exponential bound of the mean deviation between Q_n(x) and Q(x) given the training sample Zⁿ = (X₁, Y₁, …, X_n, Y_n), under conditions as weak as possible.     

On the Rate of Almost Everywhere Convergence of Certain Classical Integral Means

The main purpose of this article is to establish nearly optimal results concerning the rate of almost everywhere convergence of the Gauss–Weierstrass, Abel–Poisson, and Bochner–Riesz means of the one-dimensional Fourier integral. A typical result for these means is the following: If the function f belongs to the Besov spaceB^s_{p, p}, 1<p<∞, 0<s<1, thenT_mtf (x)−f(x)=o_x(t^s) a.e. ast→0+.     

Nonradial Large Solutions of Sublinear Elliptic Equations

We show that the equation Δu = p(x)f(u) has a positive solution on R ^N , N ≥ 3, satisfying <artwork name="GAPA31011ei1"> <artwork name="GAPA31011ei2"> if and only if <artwork name="GAPA31011ei3"> when ψ(r) = min{p(x): |x| = r}. The nondecreasing continuous function f satisfies f(0) = 0, f (s) > 0 for s > 0, and sup _{s ≥ 1} f(s)/s<∞, and the nonnegative continuous function p is required to be asymptotically radial. This extends previous results which required the function p to be constant or radial.     

A Remark on the Sobolev Regularity of Classical Solutions to Uniformly Parabolic Equations

We prove that C^2+α,1+α/2 (Q?) solutions of problem (1.6) below are in a subspace H_c^m+2(Q) of H^{m+2,(m+2)/2(Q)} for all m ∈ ?, if f and the coefficients are in H_c^m(Q)∪C^α,α/2 (Q?). We apply this result to obtain global existence of Sobolev solutions to the quasilinear problem (1.26) below.     

Entire functions that share a polynomial with their derivatives

Let f be a nonconstant entire function, k and q be positive integers satisfying k>q, and let Q be a polynomial of degree q. This paper studies the uniqueness problem on entire functions that share a polynomial with their derivatives and proves that if the polynomial Q is shared by f and f^′ CM, and if f^(k)(z)−Q(z)=0 whenever f(z)−Q(z)=0, then f≡f^′. We give two examples to show that the hypothesis k>q is necessary.     

Accurate estimates of deviations of spline approximations to classes of differentiable functions

We derive the approximation on [0, 1] of functionsf(x) by interpolating spline-functions s_r(f; x) of degree 2r+1 and defect r+1 (r=1, 2,...). Exact estimates for ¦f(x)–s_r(f; x) ¦ and f(x)–s_r(f; x)|_c on the class W^mH for m=1, r=1, 2, ..., and m=2, 3, r=1 for the case of convex (t),are derived.Translated from Matematicheskie Zametki, Vol. 9, No. 5, pp. 483–494, May, 1971.