The Complexity of Indefinite Elliptic Problems with Noisy Data

We study the complexity of second-order indefinite elliptic problems −div(au) +bu=f(with homogeneous Dirichlet boundary conditions) over ad-dimensional domain Ω, the error being measured in theH¹(Ω)-norm. The problem elementsfbelong to the unit ball ofW^{r, p}, (Ω), wherep [2, ∞] andr>d/p. Information consists of (possibly adaptive) noisy evaluations off,a, orb(or their derivatives). 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/μ.     

Error bounds for multistep methods revisited

For linear multistep methods with constant stepsize we consider error bounds in terms of weightedL ₂-norms ofh ^px^(p) rather than ofh ^px^(p+1). The bounds apply to stiff systemsx'=Ax+f(t,x) where the spectrum ofA lies in a sector andf is of moderate size.     

Riesz potential and Sobolev embeddings on generalized Lebesgue and Sobolev spaces Lp(·) and Wk,p(·)

We study the Riesz potentials I_αf on the generalized Lebesgue spaces L^p(·)(?^d), where 0 < α < d and I_αf(x) ? ∫equation/tex2gif-inf-3.gif |f(y)| |x – y|^{α – d} dy. Under the assumptions that p locally satisfies |p(x) – p(x)| ≤ C/(– ln |x – y|) and is constant outside some large ball, we prove that I_α : L^p(·)(?^d) → L^p?(·)(?^d), where . If p is given only on a bounded domain Ω with Lipschitz boundary we show how to extend p to on ?^d such that there exists a bounded linear extension operator ? : W^1,p(·)(Ω) ? (?^d), while the bounds and the continuity condition of p are preserved. As an application of Riesz potentials we prove the optimal Sobolev embeddings W^k,p(·)(?^d) ?L^p*(·)(R^d) with and W^1,p(·)(Ω) ? L^p*(·)(Ω) for k = 1. We show compactness of the embeddings W^1,p(·)(Ω) ? L^q(·)(Ω), whenever q(x) ≤ p*(x) – ε for some ε > 0. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Two combinatorial properties of a class of simplicial polytopes

Letf(P _s ^d ) be the set of allf-vectors of simpliciald-polytopes. ForP a simplicial 2d-polytope let Σ(P) denote the boundary complex ofP. We show that for eachf ∈f(P _s ^d ) there is a simpliciald-polytopeP withf(P)=f such that the 11 02 simplicial diameter of Σ(P) is no more thanf ₀(P)−d+1 (one greater than the conjectured Hirsch bound) and thatP admits a subdivision into a simpliciald-ball with no new vertices that satisfies the Hirsch property. Further, we demonstrate that the number of bistellar operations required to obtain Σ(P) from the boundary of ad-simplex is minimum over the class of all simplicial polytopes with the samef-vector. This polytopeP will be the one constructed to prove the sufficiency of McMullen's conditions forf-vectors of simplicial polytopes.     

Nonresonance between the first two eigenvalues for a Steklov problem

In this paper, we study the solvability of the Steklov problem Δ_pu=|u|^p−2u in Ω, on ∂Ω, under assumptions on the asymptotic behaviour of the quotients f(x,s)/|s|^p−2s and pF(x,s)/|s|^p which extends the classical results with Dirichlet boundary conditions that for a.e. x∈∂Ω, the limits at the infinity of these quotients lie between the first two eigenvalues.     

Bounding the number of connected components of a real algebraic set

For every polynomial mapf=(f ₁,…,f _k): ℝ ⁿ →ℝ ^k , we consider the number of connected components of its zero set,B(Z _f) and two natural “measures of the complexity off,” that is the triple(n, k, d), d being equal to max(degree off _i), and thek-tuple (Δ₁,...,Δ₄), Δ _k being the Newton polyhedron off _i respectively. Our aim is to boundB(Z _f) by recursive functions of these measures of complexity. In particular, with respect to (n, k, d) we shall improve the well-known Milnor-Thom’s bound μ _d (n)=d(2d−1) ⁿ⁻¹. Considered as a polynomial ind, μ _d (n) has leading coefficient equal to 2 ⁿ⁻¹. We obtain a bound depending onn, d, andk such that ifn is sufficiently larger thank, then it improves μ _d (n) for everyd. In particular, it is asymptotically equal to 1/2(k+1)n ^k−1 dⁿ, ifk is fixed andn tends to infinity. The two bounds are obtained by a similar technique involving a slight modification of Milnor-Thom's argument, Smith's theory, and information about the sum of Betti numbers of complex complete intersections.     

A priori bounds for semilinear equations and a new class of critical exponents for Lipschitz domains

A priori bounds for positive, very weak solutions of semilinear elliptic boundary value problems −Δu=f(x,u) on a bounded domain Ω⊂Rn with u=0 on ∂Ω are studied, where the nonlinearity 0?f(x,s) grows at most like sp. If Ω is a Lipschitz domain we exhibit two exponents p_* and p^*, which depend on the boundary behavior of the Green function and on the smallest interior opening angle of ∂Ω. We prove that for 1<p<p_* all positive very weak solutions are a priori bounded in L^∞. For p>p^* we construct a nonlinearity f(x,s)=a(x)sp together with a positive very weak solution which does not belong to L^∞. Finally we exhibit a class of domains for which p_*=p^*. For such domains we have found a true critical exponent for very weak solutions. In the case of smooth domains is an exponent which is well known from classical work of Brezis, Turner [H. Brezis, R.E.L. Turner, On a class of superlinear elliptic problems, Comm. Partial Differential Equations 2 (1977) 601-614] and from recent work of Quittner, Souplet [P. Quittner, Ph. Souplet, A priori estimates and existence for elliptic systems via bootstrap in weighted Lebesgue spaces, Arch. Ration. Mech. Anal. 174 (2004) 49-81].     

n-Widths,Faber Expansion,and Computation of Analytic Functions

LetBH^∞(Ω) be the space of analytic functionsfin the region Ω for which |f(z)| ≤ 1,z∈ Ω, and letKbe a compact subset of Ω. How can we compute the values of any functionf∈BH^∞(Ω) at an arbitrary pointz∈K? One of the approaches to this problem applies the results concerning then-widths and ϵ-entrophy of classBH^∞(Ω) in the metricC(K). In the case whenKhas a simply connected complement inC and Ω is a canonical neighbourhood ofK, the classical tools for approximation off∈BH^∞(Ω) inC(K) give the Faber series. This work is concerned with the following: the exact values of Kolmogorov and othern-widths of Hardy spacesH^p, then-widths and ϵ-entrophy of classBH^∞(Ω), the optimality of Faber approximations, and computing values of analytic functions with the help of Faber series.     

Explosive solutions of elliptic equations with absorption and nonlinear gradient term

Letf be a non-decreasing C¹-function such that andF(t)/f ² a(t)→ 0 ast → ∞, whereF(t)=∫ ₀ ^t f(s) ds anda ∈ (0, 2]. We prove the existence of positive large solutions to the equationΔu +q(x)|Δu| ^a =p(x)f(u) in a smooth bounded domain Ω ⊂R^N, provided thatp, q are non-negative continuous functions so that any zero ofp is surrounded by a surface strictly included in Ω on whichp is positive. Under additional hypotheses onp we deduce the existence of solutions if Ω is unbounded.     

A degenerate parabolic equation with a nonlocal source and an absorption term

This article deals with a class of nonlocal and degenerate quasilinear parabolic equation u _t = f(u)(Δu + a∫_Ω u(x, t)dx ? u) with homogeneous Dirichlet boundary conditions. The local existence of positive classical solutions is proved by using the method of regularization. The global existence of positive solutions and blow-up criteria are also obtained. Furthermore, it is shown that, under certain conditions, the solutions have global blow-up property. When f(s) = s ^p , 0 < p ≤ 1, the blow-up rate estimates are also obtained.     

Asymptotic expansion formula for Bernstein polynomials defined on a simplex

In this paper we give a complete expansion formula for Bernstein polynomials defined on ans-dimensional simplex. This expansion for a smooth functionf represents the Bernstein polynomialB _n (f) as a combination of derivatives off plus an error term of orderO(n^–s ).Communicated by Wolfgang Dahmen.     

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.     

Error estimates for a class of quadrature formulae

The problem considered is that of estimating the error of a class of quadrature formulae for _–1 ¹ w _r (x)f(x)dx, (w _r (x) being a positive weight-function), where only values off(x) in (–1,1) and off(x) and its derivatives at the end-points of the interval are considered.     

Quadratic spline interpolation on uniform meshes

The interpolation problem at uniform mesh points of a quadratic splines(x _i)=f _i,i=0, 1,...,N ands(x ₀)=f₀ is considered. It is known that s–f=O(h ³) and s–f=O(h ²), whereh is the step size, and that these orders cannot be improved. Contrary to recently published results we prove that superconvergence cannot occur for any particular point independent off other than mesh points wheres=f by assumption. Best error bounds for some compound formulae approximatingf _i andf _i ⁽³⁾ are also derived.     

On maximal (k,t)-sets

Summary This investigation was originally motivated by the problem of determining the maximum number of points in finiten-dimensional projective spacePG(n, s) based on the Galois fieldGF(s) of orders=p ^h (wherep andh are positive integers andp is the prime characteristic of the field), such that not of these chosen points are linearly dependent. A set ofk distinct points inPG(n, s), not linearly dependent, is called a (k, t)-set fork ₁ >k. The maximum value ofk is denoted bym _t (n+1, s). The purpose of this paper is to find new upper bounds for some values ofn, s andt. These bounds are of importance in the experimental design and information theory problems.     

Existence of positive solution for some class of nonlinear fractional differential equations

In this paper, we investigate the multiple and infinitely solvability of positive solutions for nonlinear fractional differential equation Du(t)=t^νf(u), 0<t<1, where D=t^−βδD_β^γ−δ,δ, β>0, γ?0, 0<δ<1, ν>−β(γ+1). Our main work is to deal with limit case of f(s)/s as s→0 or s→∞ and Φ(s)/s, Ψ(s)/s as s→0 or s→∞, where Φ(s), Ψ(s) are functions connected with function f. In J. Math. Appl. 252 (2000) 804-812, we consider the existence of a positive solution for the particular case of Eq. (1.1), i.e., the Riemann-Liouville type (β=1, γ=0) nonlinear fractional differential equation, using the super-lower solutions method. Here, we devote to the existence of positive solution and multi-positive solutions for Eq. (1.1) by means of the fixed point theorems for the cone.     

Simultaneous approximation of periodic continuous functions and their derivatives

LetR _n(f; x) be a trigonometric polynomial of ordern satisfying Eqs. (1.1) and (1.2). The object of this note is to obtain sufficient conditions in order that thepth derivative ofR _n(f, x) converges uniformly tof ^(p)(x) on the real line. The sufficient conditions turns out to bef ^(p)(x) ∈ Lipα, α>0 with the restrictions of Eq. (1.3). The author acknowledges financial support for this work from the University of Alberta, Post Doctoral Fellowship 1966–67. The author is extremely grateful to the referee for pointing out some valuable results and suggestions.     

Near-circularity of the error curve in complex Chebyshev approximation

Let f(z) be analytic on the unit disk, and let p^*(z) be the best (Chebyshev) polynomial approximation to f(z) on the disk of degree at most n. It is observed that in typical problems the “error curve,” the image of the unit circle under (f − p^*)(z), often approximates to a startling degree a perfect circle with winding number n + 1. This phenomenon is approached by consideration of related problems whose error curves are exactly circular, making use of a classical theorem of Carathéodory and Fejér. This leads to a technique for calculating approximations in one step that are roughly as close to best as the best approximation error curve is close to circular, and hence to strong theorems on near-circularity as the radius of the domain shrinks to 0 or as n increases to ∞. As a computational example, very tight bounds are given for approximation of e^z on the unit disk. The generality of the near-circularity phenomenon (more general domains, rational approximation) is discussed.