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

On the Problem of the Averaging of Solutions to the Laplace Operator in Domains with Narrow Slanting Channels

We consider the problem of the averaging of solutions to the Laplace operator in domains with narrow slanting channels of length O(ε^q), q = const > 0, and diameter a _ε = o(ε ^q), where ε is a small parameter. The number of channels is N _ε = O (ε ¹⁻ⁿ ), where n is the dimension of the space. We study the asymptotic behavior of solutions, obtain the limit problem, and estimate the closeness of the initial and limit problem.__________Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 10, Suzdal Conference-4, 2003.     

Error bounds for least squares approximation by polynomials

Let f ε Cⁿ⁺¹[−1, 1] and let H[f](x) be the nth degree weighted least squares polynomial approximation to f with respect to the orthonormal polynomials q_k associated with a distribution dα on [−1, 1]. It is shown that if q_n+1/q_n max(q_n+1(1)/q_n(1), −q_n+1(−1)/q_n(−1)), then f − H[f] f^{n + 1} · q_n+1/q_{n + 1}^{(n + 1)}, where · denotes the supremum norm. Furthermore, it is shown that in the case of Jacobi polynomials with distribution (1 − t)^α (1 + t)^β dt, α, β > −1, the condition on q_n+1/q_n is satisfied when either max(α,β) −1/2 or −1 < α = β < −1/2.     

On Parallel Complexity of Nonsmooth Convex Optimization

We consider the standard class of problems ƒ(x) → min, x B_n associated with convex continuous functions ƒ mapping the unit n-dimensional cube B_n into [0, 1]. It is known that the information complexity of the class with respect to the standard first-order oracle is, within an absolute constant factor, n ln (1/ε), ε < being the required accuracy (measured in terms of ƒ). The question we are interested in is how the complexity can be reduced if one is allowed to use K copies of the oracle in parallel rather than a single oracle. We demonstrate that the "K-oracle complexity" is at least O(1)(n/ln(2Kn))^1/3ln(1/ε).     

Variational analysis of a composite function: A formula for the lower second order epi-derivative

An exact formula is established for the lower second order epi-derivative of a function of the form g(F(x)), where F is a smooth map from one Banach space into another and g is a convex function (generally, not everywhere finite). Unconstrained minimization of such functions typically arise as an equivalent (in one or another sense) reduction form for many important classes of constrained optimization problems. The formula is further applied to study epi-differentiability of the max-function ƒ(x) = max{ƒ(q, x):q ε Q}.     

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.     

Best Approximations and Kolmogorov and Trigonometric Widths of the Classes <Emphasis Type="Italic">B</Emphasis><Stack><Subscript><Emphasis Type="Italic">p</Emphasis>,θ</Subscript><Superscript>Ω</Superscript></Stack> of Periodic Functions of Many Variables

We obtain estimates exact in order for the best approximations and Kolmogorov and trigonometric widths of the classes B _p,θ ^Ω of periodic functions of many variables in the space L ^q for certain values of the parameters p and q.__________Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 56, No. 11, pp. 1557–1568, November, 2004.     

Instability of Certain Nonlinear Stochastic Differential Equations

We prove existence and uniqueness of the solution X^ε_t of the SDE, X^ε_t = εB_t + ∫^t₀u^{q −1} _ε(s, X^ε_t) ds, where X^ε_t is a one-dimensional process and u_ε(t, x) the density of X^ε_t (ε > 0, q > 1). We show that the closure of (X^ε_t; 0 ≤ t ≤ 1) with respect to Hölder norm, when ε goes to 0, is a.s. equal to an explicit family of continuous functions. We obtain similar results, considering SDE′s where the drift coefficient is equal to ± sgn(x) u(t, x).     

Average case complexity of linear multivariate problems I. Theory

We study the average case complexity of linear multivariate problems, that is, the approximation of continuous linear operators on functions of d variables. The function spaces are equipped with Gaussian measures. We consider two classes of information. The first class Λ^std consists of function values, and the second class Λ^all consists of all continuous linear functionals. Tractability of a linear multivariate problem means that the average case complexity of computing an ε-approximation is O((1/)^p) with p independent of d. The smallest such p is called the exponent of the problem. Under mild assumptions, we prove that tractability in Λ^all is equivalent to tractability in Λ^std and that the difference of the exponents is at most 2. The proof of this result is not constructive. We provide a simple condition to check tractability in Λ^all. We also address the issue of how to construct optimal (or nearly optimal) sample points for linear multivariate problems. We use relations between average case and worst case settings. These relations reduce the study of the average case to the worst case for a different class of functions. In this way we show how optimal sample points from the worst case setting can be used in the average case. In Part II we shall apply the theoretical results to obtain optimal or almost optimal sample points, optimal algorithms, and average case complexity functions for linear multivariate problems equipped with the folded Wiener sheet measure. Of particular interest will be the multivariate function approximation problem.     

Complexity of fixed points, I

We study the complexity (minimal cost) of computing an s-approximation to a fixed point of a contractive function with the contractive factor q < 1. This is done for the relative error criterion in Part I and for the absolute error criterion in Part II, which is in progress. The complexity depends strongly on the dimension of the domain of functions. For the one-dimensional case we develop an optimal fixed point envelope (FPE) algorithm. The cost of the FPE algorithm with use of the relative error criterion is roughly , where c is the cost of one function evaluation. Thus, for fixed ε and q close to 1 the cost of the FPE algorithm is much smaller than the cost of the simple iteration algorithm, since the latter is roughly For the contractive functions of d variables, with d ≥ log(1/ε)/log(l/q) we show that it is impossible to essentially improve the efficiency of the simple iteration.     

Best Approximations of <Emphasis Type="Italic">q</Emphasis>-Ellipsoids in Spaces <Emphasis Type="Italic">S</Emphasis><Stack><Subscript>ϕ</Subscript><Superscript><Emphasis Type="Italic">p</Emphasis>,μ</Superscript></Stack>

We find exact values of the best approximations and basic widths of q-ellipsoids in the spaces S _ϕ ^p,μ for q > p > 0.__________Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 56, No. 10, pp. 1378 – 1383, October, 2004.     

L∞-upper bound of L2-projections onto splines at a geometric mesh

For an integer k 1 and a geometric mesh (qⁱ)_−∞^∞ with q ε (0, ∞), let M_i,k(x): = k[q^{i + k}](· − x)₊^{k − 1}, N_i,k(x): = (q^{i + k} − qⁱM_i,k(x)/k, and let A_k(q) be the Gram matrix (∝M_i,kN_j,k)_i,jεz. It is known that A_k(q)⁻¹_∞ is bounded independently of q. In this paper it is shown that A_k(q)⁻¹_∞ is strictly decreasing for q in [1, ∞). In particular, the sharp upper bound and lower bound for A_k (q)⁻¹ are obtained: for all q ε (0, ∞).     

Damped Oscillatory Integrals and the Boundedness Problem for Maximal Operators

Let S ⊂ ℝR ^{n +1} be a real-analytic hypersurface with surface measure dσ, and let ψ be a smooth nonnegative compactly supported cutoff function. Consider the surface measure dμ _q = ψ|Λ(X)|^q dσ, where Λ(X) is a damping factor determined by the matrices of the first and second fundamental forms of the surface. We show that its Fourier transform decays for large |ξ| as O (|ξ|^−(1/2+ε)), ε > 0, provided that q > 3/2. We also consider applications involving maximal operators associated with means of functions over hypersurfaces.__________Translated from Funktsional’nyi Analiz i Ego Prilozheniya, Vol. 39, No. 2, pp. 70–74, 2005Original Russian Text Copyright © by I. A. Ikromov     

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

Previous work on the ε-complexity of elliptic boundary-value problems Lu = f assumed that the class F of problem elements f was the unit ball of a Sobolev space. In a recent paper, we considered the case of a model two-point boundary-value problem, with F being a class of analytic functions. In this paper, we ask what happens if F is a class of piecewise analytic functions. We find that the complexity depends strongly on how much a priori information we have about the breakpoints. If the location of the breakpoints is known, then the ε-complexity is proportional to ln (ε⁻¹), and there is a finite element p-method (in the sense of Babu ka) whose cost is optimal to within a constant factor. If we know neither the location nor the number of breakpoints, then the problem is unsolvable for ε < √2. If we know only that there are b ≥ 2 breakpoints, but we de not know their location, then the ε-complexity is proportional to bε⁻¹, and a finite element h-method is nearly optimal. In short, knowing the location of the breakpoints is as good as knowing that the problem elements are analytic, whereas only knowing the number of breakpoints is no better than knowing that the problem elements have a bounded derivative in the L₂ sense.     

Asymptotic behavior of Solutions for Hénon systems with nearly critical exponent

We consider in this paper the problem

(0.1)

where Ω is the unit ball in centered at the origin, 0α<pN, β>0, N8, p>1, q_ε>1. Suppose q_ε→q>1 as ε→0⁺ and q_ε,q satisfy respectively

we investigate the asymptotic behavior of the ground state solutions (u_ε,v_ε) of (0.1) as ε→0⁺. We show that the ground state solutions concentrate at a point, which is located at the boundary. In addition, the ground state solution is non-radial provided that ε>0 is small.     

Product properties of Hilbert transforms

Let fεL^p(R), gεL^q(R) with 1<p<∞, 1<q<∞ and let Hf, Hg be their respective Hilbert transforms. We give a simple proof of the identity Hf · Hg − f · G = H(f · Hg + g · Hf) a.e. and of its inverse in the case (1/p) + (1/q) 1 which includes the cases already considered by Cossar and Tricomi. We next derive applications, especially to boundary values of analytic functions.     

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.     

The rate of convergence of q-Bernstein polynomials for

In the note, we obtain the estimates for the rate of convergence for a sequence of q-Bernstein polynomials {B_n,q(f)} for 0<q<1 by the modulus of continuity of f, and the estimates are sharp with respect to the order for Lipschitz continuous functions. We also get the exact orders of convergence for a family of functions , and the orders do not depend on α, unlike the classical case.     

Schur functions and the invariant polynomials characterizing U(n) tensor operators

We give a direct formulation of the invariant polynomials _μG_q⁽ⁿ⁾(, Δ_i,;, x_{i,i + 1},) characterizing U(n) tensor operators p, q, …, q, 0, …, 0 in terms of the symmetric functions S_λ known as Schur functions. To this end, we show after the change of variables Δ_i = γ_i − δ_i and x_{i, i + 1} = δ_i − δ_{i + 1} that_μG_q⁽ⁿ⁾(,Δ_i;, x_{i, i + 1},) becomes an integral linear combination of products of Schur functions S_α(, γ_i,) · S_β(, δ_i,) in the variables {γ₁,…, γ_n} and {δ₁,…, δ_n}, respectively. That is, we give a direct proof that _μG_q⁽ⁿ⁾(,Δ_i,;, x_{i, i + 1},) is a bisymmetric polynomial with integer coefficients in the variables {γ₁,…, γ_n} and {δ₁,…, δ_n}. By making further use of basic properties of Schur functions such as the Littlewood-Richardson rule, we prove several remarkable new symmetries for the yet more general bisymmetric polynomials _μ^mG_q⁽ⁿ⁾(γ₁,…, γ_n; δ₁,…, δ_m). These new symmetries enable us to give an explicit formula for both _μ^mG₁⁽ⁿ⁾(γ; δ) and ₁G₂⁽ⁿ⁾(γ; δ). In addition, we describe both algebraic and numerical integration methods for deriving general polynomial formulas for _μ^mG_q⁽ⁿ⁾(γ; δ).