The Complexity of Definite Elliptic Problems with Noisy Data

We study the complexity of 2mth order definite elliptic problemsLu=f(with homogeneous Dirichlet boundary conditions) over ad-dimensional domain Ω, error being measured in theH^m(Ω)-norm. The problem elementsfbelong to the unit ball ofW^r,p(Ω), wherep∈ [2, ∞] andr>d/p. Information consists of (possibly adaptive) noisy evaluations offor the coefficients ofL. The absolute error in each noisy evaluation is at most δ. We find that thenth minimal radius for this problem is proportional ton^−r/d+ δ, and that a noisy finite element method with quadrature (FEMQ), which uses only function values, and not derivatives, is a minimal error algorithm. This noisy FEMQ can be efficiently implemented using multigrid techniques. Using these results, we find tight bounds on the ?-complexity (minimal cost of calculating an ?-approximation) for this problem, said bounds depending on the costc(δ) of calculating a δ-noisy information value. As an example, if the cost of a δ-noisy evaluation isc(δ) = δ^−s(fors> 0), then the complexity is proportional to (1/?)^d/r+s.     

Where does smoothness count the most for Fredholm equations of the second kind with noisy information?

We study the complexity of Fredholm problems (I−T_k)u=f of the second kind on I^d=[0,1]^d, where T_k is an integral operator with kernel k. Previous work on the complexity of this problem has assumed either that we had complete information about k or that k and f had the same smoothness. In addition, most of this work has assumed that the information about k and f was exact. In this paper, we assume that k and f have different smoothness; more precisely, we assume that fW^r,p(I^d) with r>d/p and that kW^s,∞(I^2d) with s>0. In addition, we assume that our information about k and f is contaminated by noise. We find that the nth minimal error is Θ(n^−μ+δ), where μ=min{r/d,s/(2d)} and δ is a bound on the noise. We prove that a noisy modified finite element method has nearly minimal error. This algorithm can be efficiently implemented using multigrid techniques. We thus find tight bounds on the -complexity for this problem. These bounds depend on the cost c(δ) of calculating a δ-noisy information value. As an example, if the cost of a δ-noisy evaluation is proportional to δ^−t, then the -complexity is roughly (1/)^t+1/μ.     

On piecewise-polynomial approximation of functions with a bounded fractional derivative in an Lp-norm

We study the error in approximating functions with a bounded (r + α)th derivative in an L_p-norm. Here r is a nonnegative integer, α ε [0, 1), and ƒ^{(r + α)} is the classical fractional derivative, i.e., ƒ^{(r + α)}(y) = ∝₀¹, ^α d(ƒ^(r)(t)). We prove that, for any such function ƒ, there exists a piecewise-polynomial of degree s that interpolates ƒ at n equally spaced points and that approximates ƒ with an error (in sup-norm) ƒ^{(r + α)}_p O(n^{−(r+α−1/p}). We also prove that no algorithm based on n function and/or derivative values of ƒ has the error equal ƒ^{(r + α)}_p O(n^{−(r+α−1/p}) for any ƒ. This implies the optimality of piecewise-polynomial interpolation. These two results generalize well-known results on approximating functions with bounded rth derivative (α = 0). We stress that the piecewise-polynomial approximation does not depend on α nor on p. It does not depend on the exact value of r as well; what matters is an upper bound s on r, s r. Hence, even without knowing the actual regularity (r, α, and p) of ƒ, we can approximate the function ƒ with an error equal (modulo a constant) to the minimal worst case error when the regularity were known.     

Minimum asymptotic error of algorithms for solving ODE

We deal with algorithms for solving systems z′(x) = f(x, z(x)), x ε [0, c], z(0) = η where f has r continuous bounded derivatives in [0, c) × ^s. We consider algorithms whose sole dependence on f is through the values of n linear continuous functionals at f. We show that if these functionals are defined by partial derivatives off then, roughly speaking, the error of an algorithm (for a fixed f) cannot converge to zero faster than n^−r as n → +∞. This minimal error is achieved by the Taylor algorithm. If arbitrary linear continuous functionals are allowed, then the error cannot converge to zero faster than n^−(r+1) as n → +∞. This minimal error is achieved by the Taylor-integral algorithm which uses integrals of f.     

Sharp inequalities for convolution-type operators

Let μ be a probability measure on [− a, a], a > 0, and let x₀ε[− a, a], f ε Cⁿ([−2a, 2a]), n 0 even. Using moment methods we derive best upper bounds to ¦∫_−a^a ([f(x₀ + y) + f(x₀ − y)]/2) μ(dy) − f(x₀)¦, leading to sharp inequalities that are attainable and involve the second modulus of continuity of f⁽ⁿ⁾ or an upper bound of it.     

Remarks on some zero-sum problems

Let Z denote the ring of integers and for a prime p and positive integers r and d, let f_r(P, d) denote the smallest positive integer such that given any sequence of f_r(p, d) elements in (Z/pZ(^d, there exists a subsequence of (rp) elements whose sum is zero in (Z/pZ(^d. That f₁(p, 1) = 2p − 1, is a classical result due to Erdős, Ginzburg and Ziv. Whereas the determination of the exact value of f₁(p, 2) has resisted the attacks of many well known mathematicians, we shall see that exact values of f_r(p, 1) for r ≥ 1 can be easily obtained from the above mentioned theorem of Erdős, Ginzburg and Ziv and those of f_r(p, 2) for r ≥ 2 can be established by the existing techniques developed by Alon, Dubiner and Rónyai in connection with obtaining good upper bounds for f₁(p, 2). We shall also take this opportunity to describe some of the early results in the introduction.     

Values of the Euler Function in Various Sequences

Let ϕ(n) and λ(n) denote the Euler and Carmichael functions, respectively. In this paper, we investigate the equation ϕ(n)^r = λ(n)^s, where r ≥ s ≥ 1 are fixed positive integers. We also study those positive integers n, not equal to a prime or twice a prime, such that ϕ(n) = p − 1 holds with some prime p, as well as those positive integers n such that the equation ϕ(n) = f(m) holds with some integer m, where f is a fixed polynomial with integer coefficients and degree degf > 1.     

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).     

The vertex-cover polynomial of a graph

In this paper we define the vertex-cover polynomial Ψ(G,τ) for a graph G. The coefficient of τ^r in this polynomial is the number of vertex covers V′ of G with |V′|=r. We develop a method to calculate Ψ(G,τ). Motivated by a problem in biological systematics, we also consider the mappings f from {1, 2,…,m} into the vertex set V(G) of a graph G, subject to f⁻¹(x)f⁻¹(y)≠ for every edge xy in G. Let F(G,m) be the number of such mappings f. We show that F(G,m) can be determined from Ψ(G,τ).     

On an infinite series of Abel occurring in the theory of interpolation

The purpose of this paper is to show that for a certain class of functions f which are analytic in the complex plane possibly minus (−∞, −1], the Abel series f(0) + Σ_{n = 1}^∞ f⁽ⁿ⁾(nβ) z(z − nβ)^{n − 1}/n! is convergent for all β>0. Its sum is an entire function of exponential type and can be evaluated in terms of f. Furthermore, it is shown that the Abel series of f for small β>0 approximates f uniformly in half-planes of the form Re(z) − 1 + δ, δ>0. At the end of the paper some special cases are discussed.     

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.     

Kolmogorov Width of Classes of Smooth Functions on the Sphere

Let ^d−1{(x₁,…,x_d) ^d:x²₁+···+x²_d=1} be the unit sphere of the d-dimensional Euclidean space ^d. For r>0, we denote by B^r_p (1p∞) the class of functions f on ^d−1 representable in the formwhere dσ(y) denotes the usual Lebesgue measure on ^d−1, and P^λ_k(t) is the ultraspherical polynomial.For 1p,q∞, the Kolmogorov N-width of B^r_p in L^q( ^d−1) is given bythe left-most infimum being taken over all N-dimensional subspaces X_N of L^q( ^d−1).The main result in this paper is that for r2(d−1)²,where A_NB_N means that there exists a positive constant C, independent of N, such that C⁻¹A_NB_NCA_N.This extends the well-known Kashin theorem on the asymptotic order of the Kolmogorov widths of the Sobolev class of the periodic functions.     

On the structure of biharmonic functions satisfying the clamped plate conditions on a right angle

Let u(r,θ) be biharmonic and bounded in the circular sector ¦θ¦ < π/4, 0 < r < ρ (ρ > 1) and vanish together with δu/δθ when ¦θ¦ = π/4. We consider the transform û(p,θ) = ∝₀¹r^{p − 1}u(r,θ)dr. We show that for any fixed θ₀ u(p,θ₀) is meromorphic with no real poles and cannot be entire unless u(r, θ₀) ≡ 0. It follows then from a theorem of Doetsch that u(r, θ₀) either vanishes identically or oscillates as r → 0.     

Minimax estimation of the mean of spherically symmetric distributions under general quadratic loss

For X one observation on a p-dimensional (p ≥ 4) spherically symmetric (s.s.) distribution about θ, minimax estimators whose risks dominate the risk of X (the best invariant procedure) are found with respect to general quadratic loss, L(δ, θ) = (δ − θ)′ D(δ − θ) where D is a known p × p positive definite matrix. For C a p × p known positive definite matrix, conditions are given under which estimators of the form δ_a,r,C,D(X) = (I − (ar(|X|²)) D^−1/2CD^1/2 |X|⁻²)X are minimax with smaller risk than X. For the problem of estimating the mean when n observations X₁, X₂, …, X_n are taken on a p-dimensional s.s. distribution about θ, any spherically symmetric translation invariant estimator, δ(X₁, X₂, …, X_n), with have a s.s. distribution about θ. Among the estimators which have these properties are best invariant estimators, sample means and maximum likelihood estimators. Moreover, under certain conditions, improved robust estimators can be found.     

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.     

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.     

Sur l'approximation de fonctions intégrables sur [0, 1] par des polynômes de Bernstein modifies

We study here a new kind of modified Bernstein polynomial operators on L¹(0, 1) introduced by J. L. Durrmeyer in [4]. We define for f integrable on [0, 1] the modified Bernstein polynomial M_n f: M_nf(x) = (n + 1) ∑ⁿ_{k = o}P_nk(x)∝¹₀ P_nk(t) f(t) dt. If the derivative d^r f/dx^r with r 0 is continuous on [0, 1], d^r/dx^rM_n f converge uniformly on [0,1] and sup_xε[0,1] ¦M_n f(x) − f(x)¦ 2ω_f(1/trn) if ω_f is the modulus of continuity of f. If f is in Sobolev space W_l,p(0, 1) with l 0, p 1, M_n f converge to f in w^l,p(0, 1).     

Jackson's theorem for compact connected Lie groups

We prove that for f ε E = C(G) or L^p(G), 1 p < ∞, where G is any compact connected Lie group, and for n 1, there is a trigonometric polynomial t_n on G of degree n so that f − t_nE C_rω_r(n⁻¹,f). Here ω_r(t, f) denotes the rth modulus of continuity of f. Using this and sharp estimates of the Lebesgue constants recently obtained by Giulini and Travaglini, we obtain “best possible” criteria for the norm convergence of the Fourier series of f.     

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.     

Asymptotic expansions in the conditional central limit theorem

Let X_n, n , be i.i.d. with mean 0, variance 1, and E(¦X_n¦^r) < ∞ for some r 3. Assume that Cramér's condition is fulfilled. We prove that the conditional probabilities P(1/√n Σ_{i = 1}ⁿ X_i t¦B) can be approximated by a modified Edgeworth expansion up to order o(1/n^{(r − 2)/2)}), if the distances of the set B from the σ-fields σ(X₁, …, X_n) are of order O(1/n^{(r − 2)/2)}(lg n)^β), where β < −(r − 2)/2 for r and β < −r/2 for r . An example shows that if we replace β < −(r − 2)/2 by β = −(r − 2)/2 for r (β < −r/2 by β = −r/2 for r ) we can only obtain the approximation order O(1/n^{(r − 2)/2)}) for r (O(lg lgn/n^{(r − 2)/2)}) for r ).