We study the complexity of approximating the Stieltjes integral ∫ 1 0 f ( x ) dg ( x ) for functions f having r continuous derivatives and functions g whose s th derivative has bounded variation. Let r ( n ) denote the n th minimal error attainable by approximations using at most n evaluations of f and g , and let comp( ε ) denote the ε -complexity (the minimal cost of computing an ε -approximation). We show that r ( n )≍ n −min{ r , s +1} and that comp( ε )≍ ε −1/min{ r , s +1} . We also present an algorithm that computes an ε -approximation at nearly minimal cost.

We study the complexity of scalar 2mth order elliptic two-point boundary-value problems Lu=f, error being measured in the energy norm. Previous work on the complexity of these problems has generally assumed that we had partial information about the right-hand side f and complete information about the coefficients of L. In this paper, we study the complexity of such problems when, in addition to partial information about f, we have only partial information about the coefficients of L. More precisely, we suppose that f has r derivatives in the Lp-sense, with r⩾−m and p∈[2, ∞], and that L has the usual divergence form Lv=∑0⩽i, j⩽m (−1)i Di(ai, j Djv), with ai, j being ri, j-times continuously differentiable, where ri, j⩾0. We first suppose that continuous linear information is available. Let r=min{r, min0⩽i, j⩽m {ri, j−i}}. If r=−m, the problem is unsolvable; for r>−m, we find that the ε-complexity is proportional to (1/ε)1/(r+m), and we show that a finite element method (FEM) is optimal. We next suppose that only standard information (consisting of function and/or derivative evaluations) is available. Let rmin=min{r, min0⩽i, j⩽m {ri, j}}. If rmin=0, the problem is unsolvable; for rmin>0, we find that the ε-complexity is proportional to (1/ε)1/rmin, and we show that a modified FEM (which uses only function evaluations, and not derivatives) is optimal.

We study the complexity of second-order indefinite elliptic problems −div(a∇u) +bu=f(with homogeneous Dirichlet boundary conditions) over ad-dimensional domain Ω, the error being measured in theH1(Ω)-norm. The problem elementsfbelong to the unit ball ofWr, 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.

We study the complexity of 2mth order definite elliptic problemsLu=f(with homogeneous Dirichlet boundary conditions) over ad-dimensional domain Ω, error being measured in theHm(Ω)-norm. The problem elementsfbelong to the unit ball ofWr,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.

Let F be a class of functions defined on a d-dimensional domain. Our task is to compute Hm-norm ϵ-approximations to solutions of 2mth-order elliptic boundary-value problems Lu = f for a fixed L and for f ∈ F. We assume that the only information we can compute about f ∈ F is the value of a finite number of continuous linear functionals of f, each evaluation having cost c(d). Previous work has assumed that F was the unit ball of a Sobolev space Hr of fixed smoothness r, and it was found that the complexity of computing an ϵ-approximation was comp(ϵ, d) = Θ(c(d)(1/ϵ)d/(r+m)). Since the exponent of 1/ϵ depends on d, we see that the problem is intractable in 1/ϵ for any such F of fixed smoothness r. In this paper, we ask whether we can break intractability by letting F be the unit ball of a space of infinite smoothness. To be specific, we let F be the unit ball of a Hardy space of analytic functions defined over a complex d-dimensional ball of radius greater than one. We then show that the problem is tractable in 1/ϵ. More precisely, we prove that comp(ϵ, d) = Θ(c(d)(ln 1/ϵ)d), where the Θ-constant depends on d. Since for any p > 0, there is a function K (·) such that comp(ϵ, d) ≤ c(d) K (d)(1/ϵ)p for sufficiently small ϵ, we see that the problem is tractable, with (minimal) exponent 0. Furthermore, we show how to construct a finite element p-method (in the sense of Babuška) that can compute an ϵ-approximation with cost Θ(c(d)(ln 1/ϵ)d). Hence this finite element method is a nearly optimal complexity algorithm for d-dimensional elliptic problems with analytic data.

We study the worst case complexity of operator equations Lu = f where L: G → X is a bounded linear injection of normed linear spaces. Past work on the complexity of such problems has generally required the class F of problem elements f to be the unit ball of X. However, there are many problems for which this choice of F yields unsatisfactory results. Mixed elliptic—hyperbolic problems are one example. the difficulty being that our technical tools are nor strong enough to give good complexity bounds. Ill-posed problems are another example. because we know that the complexity of computing finite-error approximations is infinite if F is a ball in X. In this paper, we pursue another idea. Rather than directly restrict the class F of problem elements f, we will consider problems that are solution-restricted: i.e., we restrict the class U of solution elements u. In particular, we assume that U is the unit hall of a normed linear space W that is densely, continuously embedded in G. The main idea is that our problem can now be reduced to the standard approximation problem of approximating the embedding of W into G.This allows us to characterize optimal information and algorithms for our problem..We use this idea to study three problems: the Tricomi problem (a mixed hyperbolic— elliptic problem arising in the study of transonic flow), the inverse finite Laplace transform (an ill-posed problem arising. e.g.. in geomathematics), and the backwards heat equation. We determine the problem complexity and derive nearly optimal algorithms for each of these problems.

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 (ϵ−1), 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ϵ−1, 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 L2 sense.

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(ϵ−1)) 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 Θ(ln2(ϵ−1)) as ϵ → 0, and there is a finite element (h, p)-method whose cost is optimal to within a constant factor.

We wish to solve an ill-posed problem whose solution operator S is a measurable unbounded linear transformation of a Banach space into a Hilbert space. Let ε > 0. It is known that the e-complexity of this problem is infinite in the worst case setting. Suppose we turn to an average case or probabilistic setting, the domain of S being equipped with a zero-mean Gaussian measure μ. It is known that the problem has finite ε-complexity iff S ϵ L2(μ), and optimal information and algorithms are essentially the same as if S were bounded. We show that any such unbounded operator S belongs to L2(μ). Hence, the ε-complexity of any such illposed problem is finite in the average case and probabilistic settings.

Traditionally, we measure the quality of an approximation to the solution of a linear operator equation by its error. However, the worst case error is sometimes an unsatisfactory measure of uncertainty, especially for ill-posed problems. In this paper, we propose that the residual be used instead of the error as our measure of uncertainty. We describe optimal information and ask to what extent linear algorithms can be optimal. These results are applied to the ill-posed problem of inverting a finite Laplace transform. In particular, we find that there are instances where there are no finite-residual linear algorithms for this problem, although the problem is convergent; i.e., there are nonlinear algorithms whose residual tends to zero.

This paper deals with optimal algorithms for the approximate solution of a problem of optimal control. The control problem in question is the minimization of a quadratic energy functional, which is equivalent to the solution of a mildly nonlinear two-point second-order elliptic boundary-value problem. The only restriction on the algorithms considered is that they can use only a finite amount of information about the problem element f appearing in the definition of the energy functional. An algorithm having error ϵ is said to be optimal if its cost is minimal among all algorithms that solve the problem to within ϵ. We first suppose that the information available about f consists of a finite set of linear functionals of f, that is, we allow arbitrary linear information. We then show that there is a finite element method (whose degree depends on the smoothness of f) which is an optimal algorithm for the optimal control problem. Note that this finite element method requires the evaluation of the inner products of f with finite element basis functions. These inner products are not usually available in practice; often, only “standard information” is available (meaning that we can evaluate f at a finite set of points). So, we next consider the case where the only information that is available is standard information. We then find that there is a “finite element method with quadrature” which is an optimal algorithm among all algorithms using this standard information. Moreover, we find that standard information is weaker than inner-product information. The asymptotic penalty for using standard information instead of inner-product information is unbounded as ϵ tends to 0.

We are interested in the approximate solution of elliptic partial differential equations (PDE). Our goal is to compute an ϵ-approximation with minimal cost. In previous work, we have obtained tight complexity bounds for this problem in the worst case setting, and found conditions that are necessary and sufficient for the finite element method (FEM) to be an almost optimal complexity algorithm. Since these bounds show that elliptic PDE are intractable in the worst case setting, it is natural to seek another setting in which PDE are tractable. With this in mind, we look at the average case setting. For a large class of measures (which includes Wiener measure as a special case), we give tight bounds on the average case complexity of PDE. Moreover, we show that the FEM with properly chosen parameters is an almost optimal complexity algorithm in the average case.

A problem is said to be ill-posed if the solution of the problem does not depend continuously on the input data. In this survey paper, we consider two different information-based settings for the optimal computation of approximate solution of ill-posed linear problems, namely the worst case and average case settings. These settings are studied for two different error criteria, namely, the absolute error and the residual error criteria. The main result for the absolute-error criterion is that algorithms having finite error exist for a given setting if and only if the solution operator is bounded in that setting. In the worst case setting with an absolute error criterion, this means that there is no algorithm for solving ill-posed problems having finite error. In the average case setting with an absolute error criterion, this means that algorithms having finite error exist if and only if the solution operator is "bounded on the average." Furthermore, when this holds, we exhibit optimal information of cardinality n, finding that the nth minimal average error goes to zero as n → ∞. The main result for the residual error criterion is that the problem may be formally reduced to the approximation problem. Hence, finite-error algorithms always exist. We exhibit optimal information of cardinality n. In the worst case setting, we give a necessary and sufficient condition for the nth minimal error to go to zero as n → ∞; in the average case setting, this always occurs. We use these results to determine the ε-complexity of ill-posed problems. The ε-complexity is infinite for anyε > 0 in the worst case setting with the absolute criterion. However, in the average case setting with either error criterion and the worst case setting with the residual error criterion, we determine necessary and sufficient conditions for the ε-complexity to be finite for all ε > 0; moreover, we find algorithms yielding ε-approximations with almost-minimal cost.

The problem is to find approximataons l,(f,h) to the integral l(f,h) = fohf The approximation as said to have "local order" p if l(f,h) -l~(f,h) = O(h p) as h ~ 0 Methods are considered for computing such approximations which use "information" about f For fixed information, methods having maximal order are sought The main result is that the maximal order of any method using fixed mformauon as equal to the "order of the information," as defined by Wo~nlakowski This result is used to show that the maximal order for any method using the information {ftJ~(x,)'O _~j <_ r -1, 1 _< * _< k} is 2k[r/2] + I