Asymptotic expansions of finite element solutions to Robin problems in H 3 and their application in extrapolation cascadic multigrid method

For the Poisson equation with Robin boundary conditions,by using a few techniques such as orthogonal expansion(M-type),separation of the main part and the finite element projection,we prove for the first time that the asymptotic error expansions of bilinear finite element have the accuracy of O(h3)for u∈H3.Based on the obtained asymptotic error expansions for linear finite elements,extrapolation cascadic multigrid method(EXCMG)can be used to solve Robin problems effectively.Furthermore,by virtue of Richardson not only the accuracy of the approximation is improved,but also a posteriori error estimation is obtained.Finally,some numerical experiments that confirm the theoretical analysis are presented.     

Richardson extrapolation in boundary value problems for differential equations with nonregular right-hand side

When the finite-difference method is used to solve initial- or boundary value problems with smooth data functions, the accuracy of the numerical results may be considerably improved by acceleration techniques like Richardson extrapolation. However, the success of such a technique is doubtful in cases were the right-hand side or the coefficients of the equation are not sufficiently smooth, because the validity of an asymptotic error expansion — which is the theoretical prerequisite for the convergence analysis of the Richardson extrapolation — is not a priori obvious. In this work we show that the Richardson extrapolation may be successfully applied to the finite-difference solutions of boundary value problems for ordinary second-order linear differential equations with a nonregular right-hand side. We present some numerical results confirming our conclusions.     

On improving the absolute stability of local extrapolation

Summary A widely used technique for improving the accuracy of solutions of initial value problems in ordinary differential equations is local extrapolation. It is well known, however, that when using methods appropriate for solving stiff systems of ODES, the stability of the method can be seriously degraded if local extrapolation is employed. This is due to the fact that performing local extrapolation on a low order method is equivalent to using a higher order formula and this high order formula may not be suitable for solving stiff systems. In the present paper a general approach is proposed whereby the correction term added on in the process of local extrapolation is in a sense a rational, rather than a polynomial, function. This approach allows high order formulae with bounded growth functions to be developed. As an example we derive anA-stable rational correction algorithm based on the trapezoidal rule. This new algorithm is found to be efficient when low accuracy is requested (say a relative accuracy of about 1%) and its performance is compared with that of the more familiar Richardson extrapolation method on a large set of stiff test problems.     

Application of Richardson extrapolation to the numerical solution of partial differential equations

Richardson extrapolation is a methodology for improving the order of accuracy of numerical solutions that involve the use of a discretization size h. By combining the results from numerical solutions using a sequence of related discretization sizes, the leading order error terms can be methodically removed, resulting in higher order accurate results. Richardson extrapolation is commonly used within the numerical approximation of partial differential equations to improve certain predictive quantities such as the drag or lift of an airfoil, once these quantities are calculated on a sequence of meshes, but it is not widely used to determine the numerical solution of partial differential equations. Within this article, Richardson extrapolation is applied directly to the solution algorithm used within existing numerical solvers of partial differential equations to increase the order of accuracy of the numerical result without referring to the details of the methodology or its implementation within the numerical code. Only the order of accuracy of the existing solver and certain interpolations required to pass information between the mesh levels are needed to improve the order of accuracy and the overall solution accuracy. Using the proposed methodology, Richardson extrapolation is used to increase the order of accuracy of numerical solutions of the linear heat and wave equations and of the nonlinear St. Venant equations in one‐dimension. © 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2009     

Enhancing finite difference approximations for double barrier options: mesh optimization and repeated Richardson extrapolation

We show that the performances of the finite difference method for double barrier option pricing can be strongly enhanced by applying both a repeated Richardson extrapolation technique and a mesh optimization procedure. In particular, first we construct a space mesh that is uniform and aligned with the discontinuity points of the solution being sought. This is accomplished by means of a suitable transformation of coordinates, which involves some parameters that are implicitly defined and whose existence and uniqueness is theoretically established. Then, a finite difference scheme employing repeated Richardson extrapolation in both space and time is developed. The overall approach exhibits high efficacy: barrier option prices can be computed with accuracy close to the machine precision in less than one second. The numerical simulations also reveal that the improvement over existing methods is due to the combination of the mesh optimization and the repeated Richardson extrapolation.

     

Self-qualification of finite element analysis results by polynomial extrapolation

Evaluations of finite element model discretization error using other finite element analysis results exhibit high promise and erratic fidelity. This paper provides data from carefully controlled experiments which demonstrate the possibility of highly-accurate qualification predictions and suggest sources of failure in the past. The paper reviews the polynomial extrapolation theory, describes a procedure for adapting the general theory to a particular analysis, and illustrates application of the new approach to problems involving distributed loadings on beams.Predictions of accuracy for the beam agree to up to twelve digits with exact measures of error. This success recommends high-precision finite element analysis and suggests that finite element analysis accuracy may be only weakly sensitive to the initial selection of mesh parameters.     

Highly accurate numerical solutions with repeated Richardson extrapolation for 2D laplace equation

A theoretical basis is presented for the repeated Richardson extrapolation (RRE) to reduce and estimate the discretization error of numerical solutions for heat conduction. An example application is described for the 2D Laplace equation using the finite difference method, a domain discretized with uniform grids, second-order accurate approximations, several variables of interest, Dirichlet boundary conditions, grids with up to 8,193 × 8,193 nodes, a multigrid method, single, double and quadruple precisions and up to twelve Richardson extrapolations. It was found that: (1) RRE significantly reduces the discretization error (for example, from 2.25E-07 to 3.19E-32 with nine extrapolations and a 1,025 × 1,025 grid, yielding an order of accuracy of 19.1); (2) the Richardson error estimator works for numerical results obtained with RRE; (3) a higher reduction of the discretization error with RRE is achieved by using higher calculation precision, a larger number of extrapolations, a larger number of grids and correct error orders; and (4) to obtain a given value error, much less CPU time and RAM memory are required for the solution with RRE than without it.     

Local theory of extrapolation methods

In this paper we discuss the theory of one-step extrapolation methods applied both to ordinary differential equations and to index 1 semi-explicit differential-algebraic systems. The theoretical background of this numerical technique is the asymptotic global error expansion of numerical solutions obtained from general one-step methods. It was discovered independently by Henrici, Gragg and Stetter in 1962, 1964 and 1965, respectively. This expansion is also used in most global error estimation strategies as well. However, the asymptotic expansion of the global error of one-step methods is difficult to observe in practice. Therefore we give another substantiation of extrapolation technique that is based on the usual local error expansion in a Taylor series. We show that the Richardson extrapolation can be utilized successfully to explain how extrapolation methods perform. Additionally, we prove that the Aitken-Neville algorithm works for any one-step method of an arbitrary order s, under suitable smoothness.     

Error and extrapolation of a compact LOD method for parabolic differential equations

This paper is concerned with a compact locally one-dimensional (LOD) finite difference method for solving two-dimensional nonhomogeneous parabolic differential equations. An explicit error estimate for the finite difference solution is given in the discrete infinity norm. It is shown that the method has the accuracy of the second-order in time and the fourth-order in space with respect to the discrete infinity norm. A Richardson extrapolation algorithm is developed to make the final computed solution fourth-order accurate in both time and space when the time step equals the spatial mesh size. Numerical results demonstrate the accuracy and the high efficiency of the extrapolation algorithm.     

On the extrapolation of Galerkin methods for parabolic problems

Summary The use of Richardson extrapolation in conjunction with several discrete-time Galerkin methods for the approximate solution of parabolic initialboundary value problems is investigated. It is shown that the extrapolation of certain two- and three-level Galerkin approximations which arep ^th order correct in time yields an improvement ofp orders of accuracy in time per extrapolation, wherep=1, 2. Both linear and quasilinear problems are considered.This research was supported in part by NSF Grant GP-36561.     

Nyström methods and extrapolation for solving Steklov eigensolutions and its application in elasticity

Based on potential theory, Steklov eigensolutions of elastic problems can be converted into eigenvalue problems of boundary integral equations (BIEs). The kernels of these BIEs are characterized by logarithmic and Hilbert singularities. In this article, the Nyström methods are presented for obtaining eigensolutions (λ⁽ⁱ⁾,u⁽ⁱ⁾), which have to deal with the two kinds of singularities simultaneously. The solutions possess high accuracy orders O(h³) and an asymptotic error expansion with odd powers. Using h³ ‐Richardson extrapolation algorithms, we can greatly improve the accuracy orders to O(h⁵). Furthermore, a generalized Fourier series is constructed by the eigensolutions, and then solving the elasticity displacement and traction problems involves just calculating the coefficients of the series. A class of elasticity problems with boundary Γ is solved with high convergence rate O(h⁵). The efficiency is illustrated by a numerical example. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2012     

Extrapolation for the Approximations to the Solution of a Boundary Integral Equation on Polygonal Domains

In this paper, we consider a boundary integral equation of second kind rising from potential theory. The equation may be solved numerically by Galerkin's method using piecewise constant functions. Because of the singularities produced by the corners, we have to grade the mesh near the corner. In general, Chandler obtained the order 2 superconvergence of the iterated Galerkin solution in the uniform norm. It is proved in this paper that the Richardson extrapolation increases the accuracy from order 2 to order 4.     

Raising the order of geometric numerical integrators by composition and extrapolation

We analyse composition and polynomial extrapolation as procedures to raise the order of a geometric integrator for solving numerically differential equations. Methods up to order sixteen are constructed starting with basic symmetric schemes of order six and eight. If these are geometric integrators, then the new methods obtained by extrapolation preserve the geometric properties up to a higher order than the order of the method itself. We show that, for a number of problems, this is a very efficient procedure to obtain high accuracy. The relative performance of the different algorithms is examined on several numerical experiments. AMS subject classification 17B66, 34A50, 65L05     

The extrapolation of numerical eigenvalues by finite elements for differential operators

This paper discusses the extrapolation of numerical eigenvalues by finite elements for differential operators and obtains the following new results: (a) By extending a theorem of eigenvalue error estimate, which was established by Osborn, a new expansion of eigenvalue error is obtained. Many achievements, which are about the asymptotic expansions of finite element methods of differential operator eigenvalue problems, are brought into the framework of functional analysis. (b) The Richardson extrapolation of nonconforming finite elements for multiple eigenvalues and splitting extrapolation of finite elements based on domain decomposition of non-selfadjoint differential operators for multiple eigenvalues are achieved. In addition, numerical examples are provided to support the theoretical analysis.     

On richardson extrapolation for finite difference methods on regular grids

Summary Difference solutions of partial differential equations can in certain cases be expanded by even powers of a discretization parameterh. If we haven solutions corresponding to different mesh widthsh ₁,...,h _n we can improve the accuracy by Richardson extrapolation and get a solution of order 2n, yet only on the intersection of all grids used, i.e. normally on the coarsest grid. To interpolate this high order solution with the same accuracy in points not belonging to all grids, we need 2n points in an interval of length (2n–1)h ₁.This drawback can be avoided by combining such an interpolation with the extrapolation byh. In this case the approximation depends only on grid points in an interval of length 3/2h ₁. The length of this interval is independent of the desired order.By combining this approach with the method of Kreiss, boundary conditions on curved boundaries can be discretized with a high order even on coarse grids.This paper is based on a lecture held at the 5th Sanmarinian University Session of the International Academy of Sciences San Marino, at San Marino, 1988-08-27-1988-09-05     

How to Recover the Convergent Rate for Richardson Extrapolation on Bounded Domains

We are interested in solving elliptic problems on bounded convex domains by higher order methods using the Richardson extrapolation. The theoretical basis for the application of the Richardson extrapolation is the asymptotic error expansion with a remainder of higher order. Such an expansion has been derived by the method of finite difference, where, in the neighborhood of the boundary one must reject the elementary difference analogs and adopt complex ones. This plight can be changed if we turn to the method of finite elements, where no additional boundary approximation is needed but an easy triangulation is chosen, i.e. the higher order boundary approximation is replaced by a chosen triangulation. Specifically, a global error expansion with a remainder of fourth order can be derived by the linear finite element discretization over a chosen triangulation, which is obtained by decomposing the domain first and then subdividing each subdomain almost uniformly. A fourth order method can thus be constructed by the simplest linear finite element approximation over the chosen triangulation using the Richardson extrapolation.     

Superconvergence analysis and extrapolation of quasi-Wilson nonconforming finite element method for nonlinear Sobolev equations

Quasi-Wilson nonconforming finite element approximation for a class of nonlinear Sobolev equa-tions is discussed on rectangular meshes. We first prove that this element has two special characters by novel approaches. One is that (▽h ( u-Ihu )1, ▽hvh) h may be estimated as order O ( h2 ) when u ∈ H3 (Ω), where Ihu denotes the bilinear interpolation of u , vh is a polynomial belongs to quasi-Wilson finite element space and ▽h denotes the piecewise defined gradient operator, h is the mesh size tending to zero. The other is that the consistency error of this element is of order O ( h2 ) /O ( h3 ) in broken H 1-norm, which is one/two order higher than its interpolation error when u ∈ H3 (Ω) /H4 (Ω). Then we derive the optimal order error estimate and su- perclose property via mean-value method and the known high accuracy result of bilinear element. Furthermore, we deduce the global superconvergence through interpolation post processing technique. At last, an extrapola- tion result of order O ( h3 ), two order higher than traditional error estimate, is obtained by constructing a new suitable extrapolation scheme.     

Recursive algorithms for vector extrapolation methods

In this work we devise three classes of recursion relations that can be used for implementing some extrapolation methods for vector sequences. One class of recursion relations can be used to implement methods like the modified minimal polynomial extrapolation and the topological epsilon algorithm, another allows implementation of methods like minimal polynomial and reduced rank extrapolation, while the remaining class can be employed in the implementation of the vector E-algorithm. Operation counts and storage requirements for these methods are also discussed, and some related techniques for special applications are also presented. Included are methods for the rapid evaluation of the vector E-algorithm.     

Finite Element Eigenvalue Computation on Domains with Reentrant Corners Using Richardson Extrapolation

In the presence of reentrant corners or changing boundary conditions, standard finite element schemes have only a reduced order of accuracy even at interior nodal points. This pollution effect can be completely described in terms of asymptotic expansions of the error with respect to certain fractional powers of the mesh size. Hence, eliminating the leading pollution terms by Richardson extrapolation may locally increase the accuracy of the scheme. It is shown here that this approach also gives improved approximations for eigenvalues and eigenfunctions which are globally defined quantities.     

An algorithm using the finite volume element method and its splitting extrapolation

This paper is to present a new efficient algorithm by using the finite volume element method and its splitting extrapolation. This method combines the local conservation property of the finite volume element method and the advantages of splitting extrapolation, such as a high order of accuracy, a high degree of parallelism, less computational complexity and more flexibility than a Richardson extrapolation. Because the splitting extrapolation formulas only require us to solve a set of smaller discrete subproblems on different coarser grids in parallel instead of on the globally fine grid, a large scale multidimensional problem is turned into a set of smaller discrete subproblems. Additionally, this method is efficient for solving interface problems if we regard the interfaces of the problems as the interfaces of the initial domain decomposition.