The Optimal Discretization of Stochastic Differential Equations

We study pathwise approximation of scalar stochastic differential equations. The mean squared L₂-error and the expected number n of evaluations of the driving Brownian motion are used for the comparison of arbitrary methods. We introduce an adaptive discretization that reflects the local properties of every single trajectory. The corresponding error tends to zero like c·n^−1/2, where c is the average of the diffusion coefficient in space and time. Our method is justified by the matching lower bound for arbitrary methods that are based on n evaluations on the average. Hence the adaptive discretization is asymptotically optimal. The new method is very easy to implement, and about 7 additional arithmetical operations are needed per evaluation of the Brownian motion. Hereby we can determine the complexity of pathwise approximation of stochastic differential equations. We illustrate the power of our method already for moderate accuracies by means of a simulation experiment.     

有限元插值误差的下界估计

基于一维区域上的拟一致剖分,证明了线性元插值误差的最优下界估计.基于此并利用超收敛理论,我们得到了有限元离散误差的上、下界.     

A Posteriori Error Estimators of Gradient Recovery Type for Fem of a Model Optimal Control Problem

In this paper, we derive an a posteriori error estimator of gradient recovery type for a model optimal control problem. We show that the a posteriori error estimator is equivalent to the discretization error in a norm of energy type on general meshes. Furthermore, when the solution of the control problem is smooth and the meshes are uniform, it is shown to be asymptotically exact.     

A posteriori error estimates for mixed finite element approximations of parabolic problems

We derive residual based a posteriori error estimates for parabolic problems on mixed form solved using Raviart–Thomas–Nedelec finite elements in space and backward Euler in time. The error norm considered is the flux part of the energy, i.e. weighted L ²(Ω) norm integrated over time. In order to get an optimal order bound, an elementwise computable post-processed approximation of the scalar variable needs to be used. This is a common technique used for elliptic problems. The final bound consists of terms, capturing the spatial discretization error and the time discretization error and can be used to drive an adaptive algorithm.     

Optimal approximation of stochastic differential equations by adaptive step-size control

We study the pathwise (strong) approximation of scalar stochastic differential equations with respect to the global error in the -norm. For equations with additive noise we establish a sharp lower error bound in the class of arbitrary methods that use a fixed number of observations of the driving Brownian motion. As a consequence, higher order methods do not exist if the global error is analyzed. We introduce an adaptive step-size control for the Euler scheme which performs asymptotically optimally. In particular, the new method is more efficient than an equidistant discretization. This superiority is confirmed in simulation experiments for equations with additive noise, as well as for general scalar equations.

     

Generalized faber polynomials and an optimal error recovery algorithm

This paper deals with the problem of approximate evaluation of a certain class of analytic functions. The choice of this class is motivated by the problem of the summation of moment sequences. By assuming that the information about the function is given by its Taylor coefficients, we are able to establish a lower bound on the error of an arbitrary algorithm. We present also an algorithm whose error is asymptotically at most twice the lower bound, thereby showing that our estimate is asymptotically sharp.     

Minmax earliness–tardiness costs with unit processing time jobs

The problem addressed in this paper is defined by M parallel identical machines, N jobs with identical (unit) processing time, job-dependent weights, and a common due-date for all jobs. The objective is of a minmax type, i.e. we are interested in minimizing the cost of the worst scheduled job. In the case of a non-restrictive (i.e., sufficiently large) common due-date, the problem is shown to have a solution that is polynomial in the number of jobs. The solution in the case of a restrictive due-date remains polynomial in the number of jobs, but is exponential in the number of machines. We introduce a lower bound on the optimal cost and an efficient heuristic. We show that the worst case relative error of the heuristic is bounded by 2 and that this bound is tight. We also prove that the heuristic is asymptotically optimal under very general assumptions. Finally, we provide an extensive numerical study demonstrating that in most cases the heuristic performs extremely well.     

Efficient Verification Tools for Reduced Derivatives Computed by a First-Optimize-Then-Discretize Approach for Optimal Control Problems

We give an overview about several verification tools to study consistency between discrete optimization problem and discrete derivatives when using independent discretization schemes for state and adjoint systems within the context of optimal control problems. We present strategies that detect impreciseness within a considered quantity without any additional effort. They are therefore a suitable tool to control the grid refinement within a multilevel setting. More detailed tools are useful to verify the problem implementation and to analyze the quantities discretization error order. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Gradient recovery type a posteriori error estimate for finite element approximation on non-uniform meshes

In this paper, we derive gradient recovery type a posteriori error estimate for the finite element approximation of elliptic equations. We show that a posteriori error estimate provide both upper and lower bounds for the discretization error on the non-uniform meshes. Moreover, it is proved that a posteriori error estimate is also asymptotically exact on the uniform meshes if the solution is smooth enough. The numerical results demonstrating the theoretical results are also presented in this paper.     

Subgridscale stabilization of time-dependent convection dominated diffusive transport

In [W.J. Layton, A connection between subgrid scale eddy viscosity and mixed methods, Appl. Math. Comput. 133 (2002) 147-157], a variationally consistent eddy viscosity discretization is given for the stationary convection diffusion equation. We further develop this discretization to include the time-dependent problem. We give comprehensive stability and error analysis of the semi-discrete case. We also state the stability and error results for the fully discrete algorithm with a Crank-Nicholson time discretization. The error bound is near optimal and independent of the diffusion coefficient, ?. Finally, we give guidance on optimal parameter selection for some common finite element spaces.     

A numerical method for hybrid optimal control based on dynamic programming

This contribution extends a numerical method for solving optimal control problems by dynamic programming to a class of hybrid dynamic systems with autonomous as well as controlled switching. The value function of the hybrid control system is calculated based on a full discretization of the state and input spaces. A bound for the error due to discretization is obtained from modeling the error as perturbation of the continuous dynamics and the cost terms. It is shown that the bound approaches zero and that the value function of the discretized variant converges to the value function of the original problem if the discretization parameters go to zero. The performance of a numerical scheme exploiting the discretized system is illustrated for two different examples treated previously in literature.     

A convergence analysis of hopscotch methods for fourth order parabolic equations

Summary Consider the ODE (ordinary differential equation) that arises from a semi-discretization (discretization of the spatial coordinates) of a first order system form of a fourth order parabolic PDE (partial differential equation). We analyse the stability of the finite difference methods for this fourth order parabolic PDE that arise if one applies the hopscotch idea to this ODE.Often the error propagation of these methods can be represented by a three terms matrix-vector recursion in which the matrices have a certain anti-hermitian structure. We find a (uniform) expression for the stability bound (or error propagation bound) of this recursion in terms of the norms of the matrices. This result yields conditions under which these methods are strongly asymptotically stable (i.e. the stability is uniform both with respect to the spatial and the time stepsizes (tending to 0) and the time level (tending to infinity)), also in case the PDE has (spatial) variable coefficients. A convergence theorem follows immediately.     

Quasi-norm a priori and a posteriori error estimates for the nonconforming approximation of p-Laplacian

Summary. In this paper, we derive quasi-norm a priori and a posteriori error estimates for the Crouzeix-Raviart type finite element approximation of the p-Laplacian. Sharper a priori upper error bounds are obtained. For instance, for sufficiently regular solutions we prove optimal a priori error bounds on the discretization error in an energy norm when . We also show that the new a posteriori error estimates provide improved upper and lower bounds on the discretization error. For sufficiently regular solutions, the a posteriori error estimates are further shown to be equivalent on the discretization error in a quasi-norm. Received January 25, 1999 / Revised version received June 5, 2000 Published online March 20, 2001     

Numerical analysis of a method for high Peclet number transport in porous media

A variationally consistent eddy viscosity discretization is presented in [W.J. Layton, A connection between subgrid scale eddy viscosity and mixed methods, Appl. Math. Comput. 133 (2002) 147-157] for the stationary convection diffusion problem. This discretization is extended to the evolutionary problem in [N. Heitmann, Subgridscale stabilization of time-dependent convection dominated diffusive transport, J. Math. Anal. Appl. 331 (2007) 38-50] with a near optimal error bound. In the following, we couple this discretization with the porous media problem. We present a comprehensive analysis of stability and error for the velocity field derived from the porous media problem. Next, using a backward Euler approximation for the time derivative we follow the inherited error in velocity through the coupling with the convection diffusion problem. The method is shown to be stable and the error near optimal and independent of the diffusion coefficient, ?.     

A fast interface solver for the biharmonic Dirichlet problem on polygonal domains

Summary. In this paper we propose and analyze an efficient discretization scheme for the boundary reduction of the biharmonic Dirichlet problem on convex polygonal domains. We show that the biharmonic Dirichlet problem can be reduced to the solution of a harmonic Dirichlet problem and of an equation with a Poincaré-Steklov operator acting between subspaces of the trace spaces. We then propose a mixed FE discretization (by linear elements) of this equation which admits efficient preconditioning and matrix compression resulting in the complexity . Here is the number of degrees of freedom on the underlying boundary, is an error reduction factor, or for rectangular or polygonal boundaries, respectively. As a consequence an asymptotically optimal iterative interface solver for boundary reductions of the biharmonic Dirichlet problem on convex polygonal domains is derived. A numerical example confirms the theory. Received September 1, 1995 / Revised version received February 12, 1996     

An Adaptive Newton Algorithm for Optimal Control Problems with Application to Optimal Electrode Design

In this work, we present an adaptive Newton-type method to solve nonlinear constrained optimization problems, in which the constraint is a system of partial differential equations discretized by the finite element method. The adaptive strategy is based on a goal-oriented a posteriori error estimation for the discretization and for the iteration error. The iteration error stems from an inexact solution of the nonlinear system of first-order optimality conditions by the Newton-type method. This strategy allows one to balance the two errors and to derive effective stopping criteria for the Newton iterations. The algorithm proceeds with the search of the optimal point on coarse grids, which are refined only if the discretization error becomes dominant. Using computable error indicators, the mesh is refined locally leading to a highly efficient solution process. The performance of the algorithm is shown with several examples and in particular with an application in the neurosciences: the optimal electrode design for the study of neuronal networks.     

TWO-GRID DISCRETIZATION SCHEMES OF THE NONCONFORMING FEM FOR EIGENVALUE PROBLEMS

This paper extends the two-grid discretization scheme of the conforming finite elements proposed by Xu and Zhou （Math. Comput., 70 （2001）, pp.17-25） to the nonconforming finite elements for eigenvalue problems. In particular, two two-grid discretization schemes based on Rayleigh quotient technique are proposed. By using these new schemes, the solution of an eigenvalue problem on a fine mesh is reduced to that on a much coarser mesh together with the solution of a linear algebraic system on the fine mesh. The resulting solution still maintains an asymptotically optimal accuracy. Comparing with the two-grid discretization scheme of the conforming finite elements, the main advantages of our new schemes are twofold when the mesh size is small enough. First, the lower bounds of the exact eigenvalues in our two-grid discretization schemes can be obtained. Second, the first eigenvalue given by the new schemes has much better accuracy than that obtained by solving the eigenvalue problems on the fine mesh directly.     

Third order convergent time discretization for parabolic optimal control problems with control constraints

We consider a priori error analysis for a discretization of a linear quadratic parabolic optimal control problem with box constraints on the time-dependent control variable. For such problems one can show that a time-discrete solution with second order convergence can be obtained by a first order discontinuous Galerkin time discretization for the state variable and either the variational discretization approach or a post-processing strategy for the control variable. Here, by combining the two approaches for the control variable, we demonstrate that almost third order convergence with respect to the size of the time steps can be achieved.     

Adaptive Wavelet Schwarz Methods for the Navier-Stokes Equation

In this article, we are concerned with domain decomposition methods for the stationary incompressible Navier-Stokes equation. We construct an adaptive additive Schwarz method based on discretization by means of a divergence-free wavelet frame. We prove that the method is convergent and asymptotically optimal with respect to the degrees of freedom involved.     

Fault-Tolerant Geometric Spanners

We present two new results about vertex and edge fault-tolerant spanners in Euclidean spaces. We describe the first construction of vertex and edge fault-tolerant spanners having optimal bounds for maximum degree and total cost. We present a greedy algorithm that for any t > 1 and any non-negative integer k, constructs a k-fault-tolerant t-spanner in which every vertex is of degree O(k) and whose total cost is O(k²) times the cost of the minimum spanning tree; these bounds are asymptotically optimal. Our next contribution is an efficient algorithm for constructing good fault-tolerant spanners. We present a new, sufficient condition for a graph to be a k-fault-tolerant spanner. Using this condition, we design an efficient algorithm that finds fault-tolerant spanners with asymptotically optimal bound for the maximum degree and almost optimal bound for the total cost.