What Is the Complexity of Solution-Restricted Operator Equations?

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.     

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.     

L ∞-error estimates of triangular mixed finite element methods for optimal control problems governed by semilinear elliptic equations

We look at L ^∞-error estimates for convex quadratic optimal control problems governed by nonlinear elliptic partial differential equations. In so doing, use is made of mixed finite element methods. The state and costate are approximated by the lowest order Raviart-Thomas mixed finite element spaces, and the control, by piecewise constant functions. L ^∞-error estimates of optimal order are derived for a mixed finite element approximation of a semilinear elliptic optimal control problem. Finally, numerical tests are presented which confirm our theoretical results.     

Error estimates for finite element approximations of nonlinear monotone elliptic problems with application to numerical homogenization

We consider a finite element method (FEM) with arbitrary polynomial degree for nonlinear monotone elliptic problems. Using a linear elliptic projection, we first give a new short proof of the optimal convergence rate of the FEM in the L² norm. We then derive optimal a priori error estimates in the H¹ and L² norm for a FEM with variational crimes due to numerical integration. As an application, we derive a priori error estimates for a numerical homogenization method applied to nonlinear monotone elliptic problems. © 2016 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 955–969, 2016     

Recognition of order-preserving maps

The following algorithmic problem is considered. Let P and Q be finite partially ordered sets. Given an unknown order-preserving map f: P→Q what is the minimum number of evaluations of f on elements of P which are needed to determine f completely in the worst case? Here the algorithms considered are ‘adaptive’, in the sense that the choice of the next element x of P for which f (x) is requested, can depend on the information gathered so far. Bounds are given for this minimum number. It is determined exactly in the case that P satisfies certain conditions.     

Analysis of Generalised Galerkin methods in the numerical solution of elliptic equations

The Petrov-Galerkin projection method is outlined for the solution of the linear elliptic equation Lu = f with homogeneous boundary conditions. By choosing appropriate finite dimensional trial and test spaces, the methods of weighted residuals, collocation, and H¹ Galerkin can be interpreted within the Petrov-Galerkin projection method framework. The important question of how best to choose the trial and test functions to suit a particular type of problem is then discussed. Objective criteria associated with the matrix which governs the Petrov-Galerkin numerical process are proposed.     

Finite element methods with numerical quadrature for elliptic problems with smooth interfaces

The purpose of this paper is to study the effect of the numerical quadrature on the finite element approximation to the exact solution of elliptic equations with discontinuous coefficients. Due to low global regularity of the solution, it seems difficult to achieve optimal order of convergence with classical finite element methods [Z. Chen, J. Zou, Finite element methods and their convergence for elliptic and parabolic interface problems, Numer. Math. 79 (1998) 175-202]. We derive error estimates in finite element method with quadrature for elliptic interface problems in a two-dimensional convex polygonal domain. Optimal order error estimates in L² and H¹ norms are shown to hold even if the regularity of the solution is low on the whole domain. Finally, numerical experiment for two dimensional test problem is presented in support of our theoretical findings.     

Where Does Smoothness Count the Most for Two-Point Boundary-Value Problems?

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 L_p-sense, with r⩾−m and p∈[2, ∞], and that L has the usual divergence form Lv=∑_{0⩽i, j⩽m} (−1)ⁱ Dⁱ(a_i, j D^jv), with a_i, j being r_i, j-times continuously differentiable, where r_i, j⩾0. We first suppose that continuous linear information is available. Let r=min{r, min_{0⩽i, j⩽m} {r_i, 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 r_min=min{r, min_{0⩽i, j⩽m} {r_i, j}}. If r_min=0, the problem is unsolvable; for r_min>0, we find that the ε-complexity is proportional to (1/ε)^1/r_min, and we show that a modified FEM (which uses only function evaluations, and not derivatives) is optimal.     

Optimal recovery of linear functionals on sets of finite dimension

Suppose that X is a linear space and L ₁, …, L _n is a system of linearly independent functionals on P, where P ? X is a bounded set of dimension n + 1. Suppose that the linear functional L ₀ is defined in X. In this paper, we find an algorithm that recovers the functional L ₀ on the set P with the least error among all linear algorithms using the information L ₁ f, …, L _n f, f ∈ P.     

A priori error estimates for finite element methods with numerical quadrature for nonmonotone nonlinear elliptic problems

The effect of numerical quadrature in finite element methods for solving quasilinear elliptic problems of nonmonotone type is studied. Under similar assumption on the quadrature formula as for linear problems, optimal error estimates in the L ² and the H ¹ norms are proved. The numerical solution obtained from the finite element method with quadrature formula is shown to be unique for a sufficiently fine mesh. The analysis is valid for both simplicial and rectangular finite elements of arbitrary order. Numerical experiments corroborate the theoretical convergence rates.     

Optimal error estimates of mixed finite element methods for a fourth-order nonlinear elliptic problem

A mixed finite element method is developed for a nonlinear fourth-order elliptic problem. Optimal L² error estimates are proved by using a special interpolation operator on the standard tensor-product finite elements of order k?1. Then two iterative schemes are presented and proved to keep the same optimal error estimates. Three numerical examples are provided to support the theoretical analysis.     

A microscopic convexity theorem of level sets for solutions to elliptic equations

We study the microscopic level-set convexity theorem for elliptic equation Lu?=?f(x, u, Du), which generalize Korevaars?? result in (Korevaar, Commun Part Diff Eq 15(4):541?C556, 1990) by using different expression for the elementary symmetric functions of the principal curvatures of the level surface. We find out that the structure conditions on equation are as same as conditions in macroscopic level-set convexity results (see e.g. (Colesanti and Salani, Math Nachr 258:3?C15, 2003; Greco, Bound Value Prob 1?C15, 2006)). In a forthcoming paper, we use the same techniques to deal with Hessian type equations.     

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.     

Global minimization of multivariate polynomials using nonstandard methods

The purpose of this paper is to present two algorithms for global minimization of multivariate polynomials. For a multivariate real polynomial f, we provide an effective algorithm for deciding whether or not the infimum of f is finite. In the case of f having a finite infimum, the infimum of f can be accurately coded as (h; a, b), where h is a real polynomial in one variable, a and b is two rational numbers with a?<?b, and (h, a, b) stands for the only real root of h in the open interval ]a, b[. Moreover, another algorithm is provided to decide whether or not the infimum of f is attained when the infimum of f is finite. Our methods are called ??nonstandard??, because an infinitesimal element is introduced in our arguments.     

Cubic superconvergent finite volume element method for one-dimensional elliptic and parabolic equations

In this paper, a cubic superconvergent finite volume element method based on optimal stress points is presented for one-dimensional elliptic and parabolic equations. For elliptic problem, it is proved that the method has optimal third order accuracy with respect to H¹ norm and fourth order accuracy with respect to L² norm. We also obtain that the scheme has fourth order superconvergence for derivatives at optimal stress points. For parabolic problem, the scheme is given and error estimate is obtained with respect to L² norm. Finally, numerical examples are provided to show the effectiveness of the method.     

Radiation conditions and the exterior Dirichlet problem for a class of higher order elliptic equations

Denote by L a second order strongly elliptic operator in the Euclidian p-space $\text{R}$^p, and by P some real polynomial in one variable. First the wholespace-problem for the equation P(L)u = f is considered and asymptotic conditions are derived which yield an existence and uniqueness theorem. Then for the Dirichlet problem in some exterior domain G ? $\text{R}$^p a “Fredholm alternative theorem” is proved.     

Error estimates for finite volume element methods for general second‐order elliptic problems

We treat the finite volume element method (FVE) for solving general second order elliptic problems as a perturbation of the linear finite element method (FEM), and obtain the optimal H¹ error estimate, H¹ superconvergence and L^p (1 < p ≤ ∞) error estimates between the solution of the FVE and that of the FEM. In particular, the superconvergence result does not require any extra assumptions on the mesh except quasi‐uniform. Thus the error estimates of the FVE can be derived by the standard error estimates of the FEM. Moreover we consider the effects of numerical integration and prove that the use of barycenter quadrature rule does not decrease the convergence orders of the FVE. The results of this article reveal that the FVE is in close relationship with the FEM. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 693–708, 2003.     

K-homology and index theory on contact manifolds

This paper applies K-homology to solve the index problem for a class of hypoelliptic (but not elliptic) operators on contact manifolds. K-homology is the dual theory to K-theory. We explicitly calculate the K-cycle (i.e., the element in geometric K-homology) determined by any hypoelliptic Fredholm operator in the Heisenberg calculus. The index theorem of this paper precisely indicates how the analytic versus geometric K-homology setting provides an effective framework for extending formulas of Atiyah–Singer type to non-elliptic Fredholm operators.     

Finite element methods for elliptic optimal control problems with boundary observations

We study in this paper the finite element approximations to elliptic optimal control problems with boundary observations. The main feature of this kind of optimal control problems is that the observations or measurements are the outward normal derivatives of the state variable on the boundary, this reduces the regularity of solutions to the optimal control problems. We propose two kinds of finite element methods: the standard FEM and the mixed FEM, to efficiently approximate the underlying optimal control problems. For both cases we derive a priori error estimates for problems posed on polygonal domains. Some numerical experiments are carried out at the end of the paper to support our theoretical findings.