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.     

A reduced-order finite difference extrapolation algorithm based on POD technique for the non-stationary Navier–Stokes equations

In this paper, a proper orthogonal decomposition (POD) technique is used to establish a reduced-order finite difference (FD) extrapolation algorithm with lower dimensions and sufficiently high accuracy for the non-stationary Navier–Stokes equations, and the error estimates between the reduced-order FD solutions and the classical FD solutions and the implementation for solving the reduced-order FD extrapolation algorithm are provided. Two numerical examples illustrate the fact that the results of numerical computation are consistent with theoretical conclusions. Moreover, it is shown that the reduced-order FD extrapolation algorithm based on POD method is feasible and efficient for solving the non-stationary Navier–Stokes equations.     

The Splitting Extrapolation Method for Multidimensional Problems

This note presents a splitting extrapolation process, which uses successively one-dimensional extrapolation procedure along only one variable with other variables kept fixed. This splitting technique is applied to the numerical cubature of multiple integrals, multidimensional integral equations and the difference method for solving the Poisson equation. For each case, the corresponding error estimates are given. They show the advantage of this method over the isotropic extrapolation along all the variables.     

数值解多维问题的外推与组合技术的若干新进展

本文综述近年来数值解多维问题的外推与组合技术的新进展，内容包括分裂外推及其在偏微分方程、多堆积分方程、多维数值积分中的应用；Ｃ．Ｚｅｎｇｅｒ的稀疏网格法与组合求解技术；以及解边界积分方程的组合方法，本文通过算例表明这些方法是非常有效的，是解多维问题的钥匙。     

Stability and accuracy of time-extrapolated ADI-FDTD methods for solving wave equations

Some recent work on the ADI-FDTD method for solving Maxwell's equations in 3-D have brought out the importance of extrapolation methods for the time stepping of wave equations. Such extrapolation methods have previously been used for the solution of ODEs. The present context (of wave equations) brings up two main questions which have not been addressed previously: (1) when will extrapolation in time of an unconditionally stable scheme for a wave equation again feature unconditional stability, and (2) how will the accuracy and computational efficiency depend on how frequently in time the extrapolations are carried out. We analyze these issues here.     

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.     

A multigrid compact finite difference method for solving the one‐dimensional nonlinear sine‐Gordon equation

The aim of this paper is to propose a multigrid method to obtain the numerical solution of the one‐dimensional nonlinear sine‐Gordon equation. The finite difference equations at all interior grid points form a large sparse linear system, which needs to be solved efficiently. The solution cost of this sparse linear system usually dominates the total cost of solving the discretized partial differential equation. The proposed method is based on applying a compact finite difference scheme of fourth‐order for discretizing the spatial derivative and the standard second‐order central finite difference method for the time derivative. The proposed method uses the Richardson extrapolation method in time variable. The obtained system has been solved by V‐cycle multigrid (VMG) method, where the VMG method is used for solving the large sparse linear systems. The numerical examples show the efficiency of this algorithm for solving the one‐dimensional sine‐Gordon equation. Copyright © 2014 John Wiley & Sons, Ltd.     

An extrapolation method for a class of boundary integral equations

Boundary value problems of the third kind are converted into boundary integral equations of the second kind with periodic logarithmic kernels by using Green's formulas. For solving the induced boundary integral equations, a Nyström scheme and its extrapolation method are derived for periodic Fredholm integral equations of the second kind with logarithmic singularity. Asymptotic expansions for the approximate solutions obtained by the Nyström scheme are developed to analyze the extrapolation method. Some computational aspects of the methods are considered, and two numerical examples are given to illustrate the acceleration of convergence.

     

A MULTI-PARAMETER SPLITTING EXTRAPOLATION AND A PARALLEL ALGORITHM FOR ELLIPTIC EIGENVALUE PROBLEM

1.IntroductionTheextrapolationmethodhasbecomeanimportanttechniquetoobtainmoreaccuratenumericalsolutionssinceitwasfirstestablishedbyruchardsonin1926.Theapplicationsofextrapolationmethodinthefinitdifferencecanbefoundin[14].In1983,Q.Lin,T.LhandS.Shen[8]intro…     

解椭圆边值问题的MGE方法

为了提高线性问题数值解的精度,Richardson在本世纪初期提出了一种新的处理方法——外推法.现在这种方法已经成为数值数学各个领域构造高效算法的一条重要途径. 外推法与有限差分法结合,得到了许多好的结果(见[2]).林群、黄鸿慈等又成功地将外推法与有限元法结合,使得线性元产生了高次元的效果.解微分方程边值问题     

On the numerical solution of loaded systems of ordinary differential equations with nonseparated multipoint and integral conditions

We propose a numerical method of solving systems of loaded linear nonautonomous ordinary differential equations with nonseparated multipoint and integral conditions. This method is based on the convolution of integral conditions to obtain local conditions. This approach allows one to reduce solving the original problem to solving a Cauchy problem for a system of ordinary differential equations and linear algebraic equations. Numerous computational experiments on several test problems with the formulas and schemes proposed for the numerical solution have been carried out. The results of the experiments show that the approach is reasonably efficient.     

Higher-order compact finite difference method for systems of reaction–diffusion equations

This paper is concerned with a compact finite difference method for solving systems of two-dimensional reaction–diffusion equations. This method has the accuracy of fourth-order in both space and time. The existence and uniqueness of the finite difference solution are investigated by the method of upper and lower solutions, without any monotone requirement on the nonlinear term. Three monotone iterative algorithms are provided for solving the resulting discrete system efficiently, and the sequences of iterations converge monotonically to a unique solution of the system. A theoretical comparison result for the various monotone sequences is given. The convergence of the finite difference solution to the continuous solution is proved, and Richardson extrapolation is used to achieve fourth-order accuracy in time. An application is given to an enzyme–substrate reaction–diffusion problem, and some numerical results are presented to demonstrate the high efficiency and advantages of this new approach.     

Extrapolated Magnus Methods

This paper describes the use of extrapolation with Magnus methods for the solution of a system of linear differential equations. The idea is a generalization of extrapolation with symmetric methods for the numerical solution of ODEs, where each extrapolation step increases the order of the method by 2.This revised version was published online in October 2005 with corrections to the Cover Date.     

Numerical solution of the heat equation by infinite-order ordinary differential equations

A numerical algorithm is given for solving a class of infinite-order differential equations previously discussed by the authors. These equations yield solutions to certain time-dependent boundary-value problems for the heat equation. An extrapolation process is given for increasing the speed of convergence of the sequence generated by the method. © 1992 John Wiley & Sons, Inc.     

Extrapolation Combined with Multigrid Method for Solving Finite Element Equations

An algorithm combining the MG method with two types of extrapolation is given for solving finite element equations with any initial triangulation. A high order approximation to the solution of PDEs can be obtained at the cost of order O(N) of computational work.     

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     

A numerical method for solving linear integral equations of the second kind on the non-rectangular domains based on the meshless method

The main purpose of this article is to describe a numerical scheme for solving two-dimensional linear Fredholm integral equations of the second kind on a non-rectangular domain. The method approximates the solution by the discrete collocation method based on radial basis functions (RBFs) constructed on a set of disordered data. The proposed method does not require any background mesh or cell structures, so it is meshless and consequently independent of the geometry of domain. This approach reduces the solution of the two-dimensional integral equation to the solution of a linear system of algebraic equations. The error analysis of the method is provided. The proposed scheme is also extended to linear mixed Volterra–Fredholm integral equations. Finally, some numerical examples are presented to illustrate the efficiency and accuracy of the new technique.     

Numerical solutions of index-1 differential algebraic equations can be computed in polynomial time

The cost of solving an initial value problem for index-1 differential algebraic equations to accuracy ɛ is polynomial in ln(1/ɛ). This cost is obtained for an algorithm based on the Taylor series method for solving differential algebraic equations developed by Pryce. This result extends a recent result by Corless for solutions of ordinary differential equations. The results of the standard theory of information-based complexity give exponential cost for solving ordinary differential equations, being based on a different model.     

三维热传导方程的紧交替方向差分格式

本文研究了三维热传导方程的紧交替方向隐式差分格式.利用算子方法导出了紧交替方向隐式差分格式,并利用Fourier分析方法证明了差分格式的收敛性和绝对稳定性,Richardson外推法外推一次得到具有O(T3+h6)阶精度的近似解.本文方法是对二维热传导方程问题的推广,同样适用于多维的情形.     

Numerical solution of fractional order differential equations by extrapolation

We present an extrapolation type algorithm for the numerical solution of fractional order differential equations. It is based on the new result that the sequence of approximate solutions of these equations, computed by means of a recently published algorithm by Diethelm [6], possesses an asymptotic expansion with respect to the stepsize. From this we conclude that the application of extrapolation is justified, and we obtain a very efficient differential equation solver with practically no additional numerical costs. This is also illustrated by a number of numerical examples. This revised version was published online in August 2006 with corrections to the Cover Date.