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.     

The method of successive extrapolated iterated defect correction and its application to second kind Fredholm's integral equations

We describe an application of the principle of Iterated Defect Correction (IDeC) on the quadrature methods for the numerical solution of Fredholm's integral equations of the second kind. We also derive an asymptotic expansion for the global error in the solution produced by the IDeC method. Applying Richardson extrapolation repeatedly on the IDeC method, we present the technique of Successive Extrapolated Iterated Defect Correction (SEIDeC) and the resulting asymptotic expansion for the global error. Numerical tests confirm the asymptotic results and demonstrate the power of the IDeC method as well as the superiority of our method SEIDeC.     

Geometrically adaptive grids for stiff Cauchy problems

A new method for automatic step size selection in the numerical integration of the Cauchy problem for ordinary differential equations is proposed. The method makes use of geometric characteristics (curvature and slope) of an integral curve. For grids generated by this method, a mesh refinement procedure is developed that makes it possible to apply the Richardson method and to obtain a posteriori asymptotically precise estimate for the error of the resulting solution (no such estimates are available for traditional step size selection algorithms). Accordingly, the proposed methods are more robust and accurate than previously known algorithms. They are especially efficient when applied to highly stiff problems, which is illustrated by numerical examples.     

Error analysis for a potential problem on locally refined grids

Summary. For the simulation of biomolecular systems in an aqueous solvent a continuum model is often used for the solvent. The accurate evaluation of the so-called solvation energy coming from the electrostatic interaction between the solute and the surrounding water molecules is the main issue in this paper. In these simulations, we deal with a potential problem with jumping coefficients and with a known boundary condition at infinity. One of the advanced ways to solve the problem is to use a multigrid method on locally refined grids around the solute molecule. In this paper, we focus on the error analysis of the numerical solution and the numerical solvation energy obtained on the locally refined grids. Based on a rigorous error analysis via a discrete approximation of the Greens function, we show how to construct the composite grid, to discretize the discontinuity of the diffusion coefficient and to interpolate the solutions at interfaces between the fine and coarse grids. The error analysis developed is confirmed by numerical experiments. Received June 25, 1998 / Revised version received July 14, 1999 / Published online June 8, 2000     

Asymptotic Error Expansion for the Nystrom Method of Nonlinear Volterra Integral Equation of the Second Kind

1.IntroductionConsiderthenonlinearVolterraintegraJequationofthesecondkindHere,u(x)isanunknownfunction,f(x)andK(x,t,u)aregivencontinuousfunctionsdefined,respectively,on[a,b1andD={(x,t,u):aSx5b,aSt5x)-oc相似文献   

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.     

Richardson-extrapolated sequential splitting and its application

During numerical time integration, the accuracy of the numerical solution obtained with a given step size often proves unsatisfactory. In this case one usually reduces the step size and repeats the computation, while the results obtained for the coarser grid are not used. However, we can also combine the two solutions and obtain a better result. This idea is based on the Richardson extrapolation, a general technique for increasing the order of an approximation method. This technique also allows us to estimate the absolute error of the underlying method. In this paper we apply Richardson extrapolation to the sequential splitting, and investigate the performance of the resulting scheme on several test examples.     

Repeated Richardson extrapolation applied to the two-dimensional Laplace equation using triangular and square grids

The focus of this work is to verify the efficiency of the Repeated Richardson Extrapolation (RRE) to reduce the discretization error in a triangular grid and to compare the result to the one obtained for a square grid for the two-dimensional Laplace equation. Two different geometries were employed: the first one, a unitary square domain, was discretized into a square or triangular grid; and the second, a half square triangle, was discretized into a triangular grid. The methodology employed used the following conditions: the finite volume method, uniform grids, second-order accurate approximations, several variables of interest, Dirichlet boundary conditions, grids with up to 16,777,216 nodes for the square domain and up to 2097,152 nodes for the half square triangle domain, multigrid method, double precision, up to eleven Richardson extrapolations for the first domain and up to ten Richardson extrapolations for the second domain. It was verified that (1) RRE is efficient in reducing the discretization error in a triangular grid, achieving an effective order of approximately 11 for all the variables of interest for the first geometry; (2) for the same number of nodes and with or without RRE, the discretization error is smaller in a square grid than in a triangular grid; and (3) the magnitude of the numerical error reduction depends on, among other factors, the variable of interest and the domain geometry.     

Adaptive sparse grid algorithms with applications to electromagnetic scattering under uncertainty

We discuss adaptive sparse grid algorithms for stochastic differential equations with a particular focus on applications to electromagnetic scattering by structures with holes of uncertain size, location, and quantity. Stochastic collocation (SC) methods are used in combination with an adaptive sparse grid approach based on nested Gauss-Patterson grids. As an error estimator we demonstrate how the nested structure allows an effective error estimation through Richardson extrapolation. This is shown to allow excellent error estimation and it also provides an efficient means by which to estimate the solution at the next level of the refinement. We introduce an adaptive approach for the computation of problems with discrete random variables and demonstrate its efficiency for scattering problems with a random number of holes. The results are compared with results based on Monte Carlo methods and with Stroud based integration, confirming the accuracy and efficiency of the proposed techniques.     

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     

One-leg variable-coefficient formulas for ordinary differential equations and local–global step size control

In this paper we discuss a class of numerical algorithms termed one-leg methods. This concept was introduced by Dahlquist in 1975 with the purpose of studying nonlinear stability properties of multistep methods for ordinary differential equations. Later, it was found out that these methods are themselves suitable for numerical integration because of good stability. Here, we investigate one-leg formulas on nonuniform grids. We prove that there exist zero-stable one-leg variable-coefficient methods at least up to order 11 and give examples of two-step methods of orders 2 and 3. In this paper we also develop local and global error estimation techniques for one-leg methods and implement them with the local–global step size selection suggested by Kulikov and Shindin in 1999. The goal of this error control is to obtain automatically numerical solutions for any reasonable accuracy set by the user. We show that the error control is more complicated in one-leg methods, especially when applied to stiff problems. Thus, we adapt our local–global step size selection strategy to one-leg methods.     

A high order finite difference method with Richardsonextrapolation for 3D convection diffusion equation

In this paper, we extend the Sun and Zhang’s [24] work on high order finite difference method, which is based on the Richardson extrapolation technique and an operator interpolation scheme for the one and two dimensional steady convection diffusion equations to the three dimensional case. Firstly, we employ a fourth order compact difference scheme to get the fourth order accurate solution on the fine and the coarse grids. Then, we use the Richardson extrapolation technique by combining the two approximate solutions to get a sixth order accurate solution on coarse grid. Finally, we apply an operator interpolation scheme to achieve the sixth order accurate solution on the fine grid. During this process, we use alternating direction implicit (ADI) method to solve the resulting linear systems. Numerical experiments are conducted to verify the accuracy and effectiveness of the present method.     

Using Richardson's method to construct high-order accurate adaptive grids

An algorithm is proposed to construct a sequence of evolutionary adaptive grids, each consisting of segments of uniform grids compatible with the Richardson extrapolation procedure. The necessary numerical accuracy is achieved by using Richardson's extrapolation method to increase the accuracy of the difference solution and by controlling the nonhomogeneity parameter on passing from one segment to the next. The numerical model used in the article is the diffusion-convection equation, whose solution contains large gradients. Numerical calculations show that the algorithm attains the prespecified accuracy on a nonuniform difference grid. Numerical examples support the universality of the proposed algorithm. High accuracy results can be obtained without changing the structure of the difference schemes approximating the original problem; only the grid spacing has to be changed. Translated from Chislennye Metody v Matematicheskoi Fizike, Moscow State University, pp. 22–36, 1998.     

Numerical analysis of a continuous Galerkin method for damped sine-Gordon equation

In this article, we discuss the numerical solution for the two-dimensional (2-D) damped sine-Gordon equation by using a space–time continuous Galerkin method. This method allows variable time steps and space mesh structures and its discrete scheme has good stability which are necessary for adaptive computations on unstructured grids. Meanwhile, it can easily get the higher-order accuracy in both space and time directions. The existence and uniqueness to the numerical solution are strictly proved and a priori error estimate in maximum-norm is given without any space–time grid conditions attached. Also, we prove that if the mesh in each time level is generated in a reasonable way, we can get the optimal order of convergence in both temporal and spatial variables. Finally, the convergence rates are presented and analyzed by some numerical experiments to illustrate the validity of the scheme.     

二维Volterra积分方程数值解的渐近展开及其外推

本文讨论了求解二维Ｖｏｌｔｅｒｒａ积分方程的Ｎｙｓｔｒｏｍ方法，得到了数值解的逐项渐近展开，从而可进行Ｒｉｃｈａｒｄｓｏｎ外推，提高数值解的精度。     

Maximum norm error bounds of ADI and compact ADI methods for solving parabolic equations

Alternating direction implicit (ADI) schemes are computationally efficient and widely utilized for numerical approximation of the multidimensional parabolic equations. By using the discrete energy method, it is shown that the ADI solution is unconditionally convergent with the convergence order of two in the maximum norm. Considering an asymptotic expansion of the difference solution, we obtain a fourth‐order, in both time and space, approximation by one Richardson extrapolation. Extension of our technique to the higher‐order compact ADI schemes also yields the maximum norm error estimate of the discrete solution. And by one extrapolation, we obtain a sixth order accurate approximation when the time step is proportional to the squares of the spatial size. An numerical example is presented to support our theoretical results. © 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2010     

Full collocation methods for some boundary integral equations

In this paper we propose a fully discretized version of the collocation method applied to integral equations of the first kind with logarithmic kernel. After a stability and convergence analysis is given, we prove the existence of an asymptotic expansion of the error, which justifies the use of Richardson extrapolation. We further show how these expansions can be translated to a new expansion of potentials calculated with the numerical solution of a boundary integral equation such as those treated before. Some numerical experiments, confirming our theoretical results, are given. This revised version was published online in August 2006 with corrections to the Cover Date.     

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 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.     

Anisotropic mesh adaptation for numerical solution of boundary value problems

We present an efficient mesh adaptation algorithm that can be successfully applied to numerical solutions of a wide range of 2D problems of physics and engineering described by partial differential equations. We are interested in the numerical solution of a general boundary value problem discretized on triangular grids. We formulate a necessary condition for properties of the triangulation on which the discretization error is below the prescribed tolerance and control this necessary condition by the interpolation error. For a sufficiently smooth function, we recall the strategy how to construct the mesh on which the interpolation error is below the prescribed tolerance. Solving the boundary value problem we apply this strategy to the smoothed approximate solution. The novelty of the method lies in the smoothing procedure that, followed by the anisotropic mesh adaptation (AMA) algorithm, leads to the significant improvement of numerical results. We apply AMA to the numerical solution of an elliptic equation where the exact solution is known and demonstrate practical aspects of the adaptation procedure: how to control the ratio between the longest and the shortest edge of the triangulation and how to control the transition of the coarsest part of the mesh to the finest one if the two length scales of all the triangles are clearly different. An example of the use of AMA for the physically relevant numerical simulation of a geometrically challenging industrial problem (inviscid transonic flow around NACA0012 profile) is presented. © 2004 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2004.