The Complexity of Two-Point Boundary-Value Problems with Analytic Data

Previous work on the complexity of elliptic boundary-value problems Lu = f assumed that class F of problem elements f was the unit ball of a Sobolev space. In this paper, we assume that F consists of analytic functions. To be specific, we consider the ϵ-complexity of a model two-point boundary-value problem −u″ + u = f in I = (−1, 1) with natural boundary conditions u′(−1) = u′(1) = 0, and the class F consists of analytic functions f bounded by 1 on a disk of radius ρ ≥ 1 centered at the origin. We find that if ρ > 1, then the ϵ-complexity is Θ(ln(ϵ⁻¹)) as ϵ → 0, and there is a finite element p-method (in the sense of Babuška) whose cost is optimal to within a constant factor. If ρ = 1, we find that the ϵ-complexity is Θ(ln²(ϵ⁻¹)) as ϵ → 0, and there is a finite element (h, p)-method whose cost is optimal to within a constant factor.     

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/μ.     

Coding into Ramsey sets

In [6] W. T. Gowers formulated and proved a Ramsey-type result which lies at the heart of his famous dichotomy for Banach spaces. He defines the notion of weakly Ramsey set of block sequences of an infinite dimensional Banach space and shows that every analytic set of block sequences is weakly Ramsey. We show here that Gowers’ result follows quite directly from the fact that all G_δ sets are weakly Ramsey, if the Banach space does not contain c₀, and from the fact that all F_σδ sets are weakly Ramsey, in the case of an arbitrary Banach space. We also show that every result obtained by the application of Gowers’ theorem to an analytic set can also be obtained by applying the Theorem to a F_σδ set (or to a G_δ set if the space does not contain c₀). This fact explains why the only known applications of this technique are based on very low-ranked Borel sets (open, closed, F_σ, or G_δ).     

Worst Case Complexity of Problems with Random Information Noise

We study the worst case complexity of solving problems for which information is partial and contaminated by random noise. It is well known that if information is exact then adaption does not help for solving linear problems, i.e., for approximating linear operators over convex and symmetric sets. On the other hand, randomization can sometimes help significantly. It turns out that for noisy information, adaption may lead to much better approximations than nonadaption, even for linear problems. This holds because, in the presence of noise, adaption is equivalent to randomization. We present sharp bounds on the worst case complexity of problems with random noise in terms of the randomized complexity with exact information. The results obtained are applied to thed-variate integration andL_∞-approximation of functions belonging to Hölder and Sobolev classes. Information is given by function evaluations with Gaussian noise of variance σ². For exact information, the two problems are intractable since the complexity is proportional to (1/ε)^qwhereqgrows linearly withd. For noisy information the situation is different. For integration, the ε-complexity is of order σ²/ε²as ε goes to zero. Hence the curse of dimensionality is broken due to random noise. for approximation, the complexity is of order σ²(1/ε)^q+2ln(1/ε), and the problem is intractable also with random noise.     

On the relation between rates of relaxation and convergence of wild sums for solutions of the Kac equation

In the case of Maxwellian molecules, the Wild summation formula gives an expression for the solution of the spatially homogeneous Boltzmann equation in terms of its initial data F as a sum . Here, is an average over n-fold iterated Wild convolutions of F. If M denotes the Maxwellian equilibrium corresponding to F, then it is of interest to determine bounds on the rate at which tends to zero. In the case of the Kac model, we prove that for every ε>0, if F has moments of every order and finite Fisher information, there is a constant C so that for all n, where Λ is the least negative eigenvalue for the linearized collision operator. We show that Λ is the best possible exponent by relating this estimate to a sharp estimate for the rate of relaxation of f(·,t) to M. A key role in the analysis is played by a decomposition of into a smooth part and a small part. This depends in an essential way on a probabilistic construction of McKean. It allows us to circumvent difficulties stemming from the fact that the evolution does not improve the qualitative regularity of the initial data.     

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

Two-Scale Convergence Method and Scattering Problems

In this paper, we deal with the steady-state acoustic wave equation in the space ℝ³ diffracted by an obstacle made by an inhomogeneous medium and located in a bounded domain. The inhomogeneity of the medium depends on a parameter ε > 0. If the solution u _ε converges to a solution u ₀ of the limit problem as ε → 0, as in the homogenization process, then we can use the two-scale convergence method to study the convergence of the gradient.__________Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 10, Suzdal Conference-4, 2003.     

On the Real Zeros of Positive Semidefinite Biquadratic Forms

For a positive semidefinite biquadratic forms F in (3, 3) variables, we prove that, if F has a finite number but at least 7 real zeros 𝒵(F), then it is not a sum of squares. We show also that if F has at least 11 zeros, then it has infinitely many real zeros and it is a sum of squares. It can be seen as the counterpart for biquadratic forms as the results of Choi, Lam, and Reznick for positive semidefinite ternary sextics.

We introduce and compute some of the numbers BB _{n, m} which are set to be equal to sup |𝒵(F)| where F ranges over all the positive semidefinite biquadratic forms F in (n, m) variables such that |𝒵(F)| < ∞.

We also recall some old constructions of positive semidefinite biquadratic forms which are not sums of squares and we give some new families of examples.     

Existence and uniqueness of mild solutions to a semilinear integrodifferential equation of fractional order

In this paper, we prove some existence and uniqueness of mild solutions for a semilinear integrodifferential equation of fractional order with nonlocal initial conditions in α-norm. We assume that the linear part generates a noncompact analytic semigroup. Our results cover the cases that the nonlinearity F takes values in different spaces such as X,X_α and X_β, where α≤β(0,1). Finally, some practical consequences are also obtained.     

Multifunctions of faces for conditional expectations of selectors and Jensen's inequality

Let (T, , P) be a probability space, a P-complete sub-δ-algebra of and X a Banach space. Let multifunction t → Γ(t), t T, have a (X)-measurable graph and closed convex subsets of X for values. If x(t) ε Γ(t) P-a.e. and y(·) ε E_p x(·), then y(t) ε Γ(t) P-a.e. Conversely, x(t) ε F(Γ(t), y(t)) P-a.e., where F(Γ(t), y(t)) is the face of point y(t) in Γ(t). If X = , then the same holds true if Γ(t) is Borel and convex, only. These results imply, in particular, extensions of Jensen's inequality for conditional expectations of random convex functions and provide a complete characterization of the cases when the equality holds in the extended Jensen inequality.     

Some dynamical properties of transcendental meromorphic functions

If a transcendental meromorphic function f with finitely many poles has a completely invariant domain U which is simply connected and satisfies some conditions, we prove F(f)=U. And for a transcendental meromorphic function f with the lower order μ<∞ and δ(∞,f)>0, we prove J(f) cannot be contained in any finite set of straight lines completely.     

A uniform bound for the deviation of empirical distribution functions

If X₁, …, X_n are independent R^d-valued random vectors with common distribution function F, and if F_n is the empirical distribution function for X₁, …, X_n, then, among other things, it is shown that P{sup_x F_n(x) ε} 2e²(2n)^de^−2nε2 for all nε² ≥ d². The inequality remains valid if the X_i are not identically distributed and F(x) is replaced by Σ_iP{X_i ≤ x}/n.     

The short range expansion

Let V_i be short range potential and λ_i(ε) analytic functions. We show that the Hamiltonians H_ε = −Δ + ε⁻²∑_{i = l}ⁿλ_i(ε)V_i((· − x_i)/ε converge in the strong resolvent sense to the point interactions as ε → 0, and if V_i have compact support then the eigenvalues and resonances of H_ε, which remains bounded as ε → 0, are analytic in ε in a complex neighborhood of zero. We compute in closed form the eigenvalues and resonances of H_ε to the first order in ε.     

Automorphism groups of certain simple 2-(q,3,λ) designs constructed from finite fields

Let F be a finite field of characteristic not 2, and SF a subset with three elements. Consider the collection

S={S·a+b | a,bF, a≠0}.

Then (F,S) is a simple 2-design and the parameter λ of (F,S) is 1, 2, 3 or 6. We find in this paper the full automorphism group of (F,S). Namely, if we put U={r | {0,1,r}S} and K the subfield of F generated by U, then the automorphisms of (F,S) are the maps of the form xg(α(x))+b, xF, where bF, α : F→F is a field automorphism fixing U, and g is a linear transformation of F considered as a vector space over K.     

CONVEX CONCENTRATION INEQUALITIES FOR CONTINUOUS GAS AND STOCHASTIC DOMINATION

In this article, we consider the continuous gas in a bounded domain ∧ of R^＋ or R^d described by a Gibbsian probability measure μη∧ associated with a pair interaction φ, the inverse temperature β, the activity z 〉 0, and the boundary condition η. Define F ∫ωf（s）wA（ds）. Applying the generalized Ito＇s formula for forward-backward martingales （see Klein et M. [5]）, we obtain convex concentration inequalities for F with respect to the Gibbs measure μη∧. On the other hand, by FKG inequality on the Poisson space, we also give a new simple argument for the stochastic domination for the Gibbs measure.     

Équations du type Monge-Ampère sur les variétés Riemanniennes compactes, I

Let (V_n, g) be a C^∞ compact Riemannian manifold. For a suitable function on V_n, let us consider the change of metric: g′ = g + Hess(), and the function, as a ratio of two determinants, M() = ¦g′¦ ¦g¦⁻¹. Using the method of continuity, we first solve in C^∞ the problem: Log M() = λ + ƒ, λ > 0, ƒ ε C^∞. Then, under weak hypothesis on F, we solve the general equation: Log M() = F(P, ), F in C^∞(V_n × ¦α, β¦), using a method of iteration. Our study gives rise to an interesting a priori estimate on ¦¦, which does not occur in the complex case. This estimate should enable us to solve the equation above when λ 0, providing we can overcome difficulties related to the invertibility of the linearised operator. This open question will be treated in our next article.     

Strong and weak convergence theorems for asymptotically nonexpansive mappings

Suppose K is a nonempty closed convex nonexpansive retract of a real uniformly convex Banach space E with P as a nonexpansive retraction. Let T :K→E be an asymptotically nonexpansive nonself-map with sequence {k_n}_n1[1,∞), limk_n=1, F(T):={xK: Tx=x}≠. Suppose {x_n}_n1 is generated iteratively by

where {α_n}_n1(0,1) is such that ε<1−α_n<1−ε for some ε>0. It is proved that (I−T) is demiclosed at 0. Moreover, if ∑_n1(k_n²−1)<∞ and T is completely continuous, strong convergence of {x_n} to some x^*F(T) is proved. If T is not assumed to be completely continuous but E also has a Fréchet differentiable norm, then weak convergence of {x_n} to some x^*F(T) is obtained.     

W(R)-splines

In [3] Golomb describes, for 1 < p < ∞, the H^r,p(R)-extremal extension F_* of a function ƒ:E → R (i.e., the H^r,p-spline with knots in E) and studies the cone H_*E^r,p of all such splines. We study the problem of determining when F_* is in W^r,p ≡ H^r,p ∩ L^p. If F_* ε W^r,p, then F_* is called a W^r,p-spline, and we denote by W_*E^r,p the cone of all such splines. If E is quasiuniform, then F_* ε W^r,p if and only if {ƒ(t_i)}_tiεE ε l^p. The cone W_*E^r,p with E quasiuniform is shown to be homeomorphic to l^p. Similarly, H_*E^r,p is homeomorphic to h^r,p. Approximation properties of the W^r,p-splines are studied and error bounds in terms of the mesh size ¦ E ¦ are calculated. Restricting ourselves to the case p = 2 and to quasiuniform partitions E, the second integral relation is proved and better error bounds in terms of ¦ E ¦ are derived.     

Voronovskaya-type formulas and saturation of convergence for q-Bernstein polynomials for

In the paper, we discuss Voronovskaya-type theorem and saturation of convergence for q-Bernstein polynomials for arbitrary fixed q, 0<q<1. We give explicit formulas of Voronovskaya-type for the q-Bernstein polynomials for 0<q<1. If , we show that the rate of convergence for the q-Bernstein polynomials is o(qⁿ) if and only ifWe also prove that if f is convex on [0,1] or analytic on (-ε,1+ε) for some ε>0, then the rate of convergence for the q-Bernstein polynomials is o(qⁿ) if and only if f is linear.     

On spectra of some linear elliptic differential operators

In the study of boundary-value problems, we often need information on the spectra of the corresponding differential operators. In this paper, we discuss the location of spectra of linear elliptic differential operators in ℝⁿ, n ∈ ℕ.Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 9, Suzdal Conference-3, 2003.