Efficient computable error bounds for discontinuous Galerkin approximations of elliptic problems

We present guaranteed and computable both sided error bounds for the discontinuous Galerkin (DG) approximations of elliptic problems. These estimates are derived in the full DG-norm on purely functional grounds by the analysis of the respective differential problem, and thus, are applicable to any qualified DG approximation. Based on the triangle inequality, the underlying approach has the following steps for a given DG approximation: (1) computing a conforming approximation in the energy space using the Oswald interpolation operator, and (2) application of the existing functional a posteriori error estimates to the conforming approximation. Various numerical examples with varying difficulty in computing the error bounds, from simple problems of polynomial-type analytic solution to problems with analytic solution having sharp peaks, or problems with jumps in the coefficients of the partial differential equation operator, are presented which confirm the efficiency and the robustness of the estimates.     

A mollification method for ill-posed problems

Summary. A mollification method for a class of ill-posed problems is suggested. The idea of the method is very simple and natural: if the data are given inexactly then we try to find a sequence of ``mollification operators" which map the improper data into well-posedness classes of the problem (mollify the improper data). Within these mollified data our problem becomes well-posed. And when these facts are in hand we try to obtain error estimates and optimal or ``quasi-optimal" mollification parameters. The method is working not only for problems in Hilbert spaces, but also for problems in Banach spaces. Applications of the method to concrete problems, like numerical differentiation, parabolic equations backwards in time, the Cauchy problem for the Laplace equation, one- and multidimensional non-characteristic Cauchy problems for parabolic equations (in infinite or finite domains),... give us very sharp stability estimates of H\"older continuous type. In these cases the method is optimal in the sense that it gives the same order of H\"older continuous dependence on the data as for the regularized problems. Furthermore, the method may be implemented numerically using fast Fourier transforms. For the first time a uniform stability estimate of H\"older continuous type of the solution of the heat equation backwards in time in the space for all could be established by our mollification method. A new simple sharp pointwise estimate of H\"older type for the weak solution of a non-characteristic Cauchy problem for parabolic equations in a finite domain is established. Received June 25, 1993 / Revised version received February 18, 1994     

Convergence of linear multistep and one-leg methods for stiff nonlinear initial value problems

To prove convergence of numerical methods for stiff initial value problems, stability is needed but also estimates for the local errors which are not affected by stiffness. In this paper global error bounds are derived for one-leg and linear multistep methods applied to classes of arbitrarily stiff, nonlinear initial value problems. It will be shown that under suitable stability assumptions the multistep methods are convergent for stiff problems with the same order of convergence as for nonstiff problems, provided that the stepsize variation is sufficiently regular.     

Parameterized preconditioning for generalized saddle point problems arising from the Stokes equation

A parameterized preconditioning framework is proposed to improve the conditions of the generalized saddle point problems. Based on the eigenvalue estimates for the generalized saddle point matrices, a strategy to minimize the upper bounds of the spectral condition numbers of the matrices is given, and the explicit expression of the quasi-optimal preconditioning parameter is obtained. In numerical experiment, parameterized preconditioning techniques are applied to the generalized saddle point problems derived from the mixed finite element discretization of the stationary Stokes equation. Numerical results demonstrate that the involved preconditioning procedures are efficient.     

On resolvent conditions and stability estimates

As many numerical processes for time discretization of evolution equations can be formulated as analytic mappings of the generator, they can be represented in terms of the resolvent. To obtain stability estimates for time discretizations, one therefore would like to carry known estimates on the resolvent back to the time domain. For different types of bounds of the resolvent of a linear operator, bounds for the norm of the powers of the operator and for their sum are given. Under similar bounds for the resolvent of the generator, some new stability bounds for one-step and multistep discretizations of evolution equations are then obtained.     

Conditioning analysis of block incomplete factorizations and its application to elliptic equations

Summary. The paper deals with eigenvalue estimates for block incomplete factorization methods for symmetric matrices. First, some previous results on upper bounds for the maximum eigenvalue of preconditioned matrices are generalized to each eigenvalue. Second, upper bounds for the maximum eigenvalue of the preconditioned matrix are further estimated, which presents a substantial improvement of earlier results. Finally, the results are used to estimate bounds for every eigenvalue of the preconditioned matrices, in particular, for the maximum eigenvalue, when a modified block incomplete factorization is used to solve an elliptic equation with variable coefficients in two dimensions. The analysis yields a new upper bound of type for the condition number of the preconditioned matrix and shows clearly how the coefficients of the differential equation influence the positive constant . Received March 27, 1996 / Revised version received December 27, 1996     

Accuracy of TSVD solutions computed from rank-revealing decompositions

Summary. Rank-revealing decompositions are favorable alternatives to the singular value decomposition (SVD) because they are faster to compute and easier to update. Although they do not yield all the information that the SVD does, they yield enough information to solve various problems because they provide accurate bases for the relevant subspaces. In this paper we consider rank-revealing decompositions in computing estimates of the truncated SVD (TSVD) solution to an overdetermined system of linear equations , where is numerically rank deficient. We derive analytical bounds which show how the accuracy of the solution is intimately connected to the quality of the subspaces. Received July 12, 1993 / Revised version received November 14, 1994     

Grid modification for the wave equation with attenuation

Summary. The wave equation with attenuation due to a linear friction is approximated by a new mixed finite element method which allows one to use different grids and basis functions at different times when necessary. This method enables one to track sharp moving wave fronts more efficiently and accurately. Error estimates with optimal convergent rates are established. Unconditional stability is also proved for this method. Received March 27, 1992/Revised version received May 21, 1993     

Schwarz alternating and iterative refinement methods for mixed formulations of elliptic problems,part II: Convergence theory

Summary In this paper we discuss bounds for the convergence rates of several domain decomposition algorithms to solve symmetric, indefinite linear systems arising from mixed finite element discretizations of elliptic problems. The algorithms include Schwarz methods and iterative refinement methods on locally refined grids. The implementation of Schwarz and iterative refinement algorithms have been discussed in part I. A discussion on the stability of mixed discretizations on locally refined grids is included and quantiative estimates for the convergence rates of some iterative refinement algorithms are also derived.Department of Mathematics, University of Wyoming, Laramie, WY 82071-3036. This work was supported in part by the National Science Foundation under Grant NSF-CCR-8903003, while the author was a graduate student at New York University, and in part by NSF Grant ASC 9003002, while the author was a Visiting, Assistant Researcher at UCLA.     

A posteriori estimates of inverse operators for initial value problems in linear ordinary differential equations

We present constructive a posteriori estimates of inverse operators for initial value problems in linear ordinary differential equations (ODEs) on a bounded interval. Here, “constructive” indicates that we can obtain bounds of the operator norm in which all constants are explicitly given or are represented in a numerically computable form. In general, it is difficult to estimate these inverse operators a priori. We, therefore, propose a technique for obtaining a posteriori estimates by using Galerkin approximation of inverse operators. This type of estimation will play an important role in the numerical verification of solutions for initial value problems in nonlinear ODEs as well as for parabolic initial boundary value problems.     

Finite element approximationof a nonlinear elliptic equation arising from bimaterial problemsin elastic-plastic mechanics

Summary. In [13], a nonlinear elliptic equation arising from elastic-plastic mechanics is studied. A well-posed weak formulation is established for the equation and some regularity results are further obtained for the solution of the boundary problem. In this work, the finite element approximation of this boundary problem is examined in the framework of [13]. Some error bounds for this approximation are initially established in an energy type quasi-norm, which naturally arises in degenerate problems of this type and proves very useful in deriving sharper error bounds for the finite element approximation of such problems. For sufficiently regular solutions optimal error bounds are then obtained for some fully degenerate cases in energy type norms. Received June 12, 1998 / Revised version received June 21, 1999 / Published online June 8, 2000     

Numerical solution of one-dimensional Burgers’ equation using reproducing kernel function

This paper presents a numerical method for one-dimensional Burgers’ equation by the Hopf–Cole transformation and a reproducing kernel function, abbreviated as RKF. The numerical solution is given as explicit integral expressions with the RKF at each time step, so that the computation is fully parallel. The stability and error estimates are derived. Numerical results for some test problems are presented and compared with the exact solutions. Some numerical results are also compared with the results obtained by other methods. The present method is easily implemented and effective.     

A second order backward difference method with variable steps for a parabolic problem

The numerical solution of a parabolic problem is studied. The equation is discretized in time by means of a second order two step backward difference method with variable time step. A stability result is proved by the energy method under certain restrictions on the ratios of successive time steps. Error estimates are derived and applications are given to homogenous equations with initial data of low regularity.     

The regularization method for an obstacle problem

Summary. We give a relatively complete analysis for the regularization method, which is usually used in solving non-differentiable minimization problems. The model problem considered in the paper is an obstacle problem. In addition to the usual convergence result and a-priori error estimates, we provide a-posteriori error estimates which are highly desired for practical implementation of the regularization method. Received March 22, 1993 / Revised version received October 11, 1993     

Robust a posteriori error estimators for a singularly perturbed reaction-diffusion equation

We derive robust a posteriori error estimators for a singularly perturbed reaction-diffusion equation. Here, robust means that the estimators yield global upper and local lower bounds on the error measured in the energy norm such that the ratio of the upper and lower bounds is bounded from below and from above by constants which do neither depend on any meshsize nor on the perturbation parameter. The estimators are based either on the evaluation of local residuals or on the solution of discrete local Dirichlet or Neumann problems. Received June 5, 1996     

Forward error analysis of Gaussian elimination

Summary Part I of this work deals with the forward error analysis of Gaussian elimination for general linear algebraic systems. The error analysis is based on a linearization method which determines first order approximations of the absolute errors exactly. Superposition and cancellation of error effects, structure and sparsity of the coefficient matrices are completely taken into account by this method. The most important results of the paper are new condition numbers and associated optimal component-wise error and residual estimates for the solutions of linear algebraic systems under data perturbations and perturbations by rounding erros in the arithmetic floating-point operations. The estimates do not use vector or matrix norms. The relative data and rounding condition numbers as well as the associated backward and residual stability constants are scaling-invariant. The condition numbers can be computed approximately from the input data, the intermediate results, and the solution of the linear system. Numerical examples show that by these means realistic bounds of the errors and the residuals of approximate solutions can be obtained. Using the forward error analysis, also typical results of backward error analysis are deduced. Stability theorems and a priori error estimates for special classes of linear systems are proved in Part II of this work.     

On the balancing principle for some problems of Numerical Analysis

We discuss a choice of weight in penalization methods. The motivation for the use of penalization in computational mathematics is to improve the conditioning of the numerical solution. One example of such improvement is a regularization, where a penalization substitutes an ill-posed problem for a well-posed one. In modern numerical methods for PDEs a penalization is used, for example, to enforce a continuity of an approximate solution on non-matching grids. A choice of penalty weight should provide a balance between error components related with convergence and stability, which are usually unknown. In this paper we propose and analyze a simple adaptive strategy for the choice of penalty weight which does not rely on a priori estimates of above mentioned components. It is shown that under natural assumptions the accuracy provided by our adaptive strategy is worse only by a constant factor than one could achieve in the case of known stability and convergence rates. Finally, we successfully apply our strategy for self-regularization of Volterra-type severely ill-posed problems, such as the sideways heat equation, and for the choice of a weight in interior penalty discontinuous approximation on non-matching grids. Numerical experiments on a series of model problems support theoretical results.     

A-priori error estimates of Galerkin backward differentiation methods in time-inhomogeneous parabolic problems

Summary Backward differentiation methods up to orderk=5 are applied to solve linear ordinary and partial (parabolic) differential equations where in the second case the space variables are discretized by Galerkin procedures. Using a mean square norm over all considered time levels a-priori error estimates are derived. The emphasis of the results lies on the fact that the obtained error bounds do not depend on a Lipschitz constant and the dimension of the basic system of ordinary differential equations even though this system is allowed to have time-varying coefficients. It is therefore possible to use the bounds to estimate the error of systems with arbitrary varying dimension as they arise in the finite element regression of parabolic problems.     

Robustness of multi-grid applied to anisotropic equations on convex domains and on domains with re-entrant corners

Summary We analyse multi-grid applied to anisotropic equations within the framework of smoothing and approximation-properties developed by Hack busch. For a model anisotropic equation on a square, we give an up-till-now missing proof of an estimate concerning the approximation property which is essential to show robustness. Furthermore, we show a corresponding estimate for a model anisotropic equation on an L-shaped domain. The existing estimates for the smoothing property are not suitable to prove robustness for either 2-cyclic Gauss-Seidel smoothers or for less regular problems such as our second model equation. For both cases, we give sharper estimates. By combination of our results concerning smoothing- and approximation-properties, robustness of W-cycle multi-grid applied to both our model equations will follow for a number of smoothers.     

Quasi-norm error bounds for the finite element approximation of a non-Newtonian flow

Summary. We consider the finite element approximation of a non-Newtonian flow, where the viscosity obeys a general law including the Carreau or power law. For sufficiently regular solutions we prove energy type error bounds for the velocity and pressure. These bounds improve on existing results in the literature. A key step in the analysis is to prove abstract error bounds initially in a quasi-norm, which naturally arises in degenerate problems of this type. Received May 25, 1993 / Revised version received January 11, 1994