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.     

An Extrapolation Method for BEM

This paper gives an asymptotic expansion of the error on the mesh point for Galerkin approximation of integral equations of the first kind. The extrapolation formula and some numerical results are given.     

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.     

Methods for parallel integration of stiff systems of odes

This paper presents a class of parallel numerical integration methods for stiff systems of ordinary differential equations which can be partitioned into loosely coupled sub-systems. The formulas are called decoupled backward differentiation formulas, and they are derived from the classical formulas by restricting the implicit part to the diagnonal sub-system. With one or several sub-systems allocated to each processor, information only has to be exchanged after completion of a step but not during the solution of the nonlinear algebraic equations.The main emphasis is on the formula of order 1, the decoupled implicit Euler formula. It is proved that this formula even for a wide range of multirate formulations has an asymptotic global error expansion permitting extrapolation. Besides, sufficient conditions for absolute stability are presented.     

Numerical methods and asymptotic error expansions for the Emden-Fowler equations

In the present paper we analyse a numerical method for computing the solution of some boundary-value problems for the Emden-Fowler equations. The differential equations are discretized by a finite-difference method and we derive asymptotic expansions for the discretization error. Based on these asymptotic expansions, we use an extrapolation algorithm to accelerate the convergence of the numerical method.     

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.     

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.     

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.     

Asymptotic expansion of stochastic flows

Summary We study the asymptotic expansion in small time of the solution of a stochastic differential equation. We obtain a universal and explicit formula in terms of Lie brackets and iterated stochastic Stratonovich integrals. This formula contains the results of Doss [6], Sussmann [15], Fliess and Normand-Cyrot [7], Krener and Lobry [10], Yamato [17] and Kunita [11] in the nilpotent case, and extends to general diffusions the representation given by Ben Arous [3] for invariant diffusions on a Lie group. The main tool is an asymptotic expansion for deterministic ordinary differential equations, given by Strichartz [14].     

Asymptotic Initial-Value Method for Singularly-Perturbed Boundary-Value Problems for Second-Order Ordinary Differential Equations

A computational method is presented to solve a class of nonturning-point singularly-perturbed two-point boundary-value problems for second-order ordinary differential equations with a small parameter multiplying the highest derivative, subject to Dirichlet-type boundary conditions. In this method, first we construct a zeroth order asymptotic expansion for the solution of the given boundary-value problem. Then, this problem is integrated to get an equivalent initial-value problem for first-order ordinary differential equations. This initial-value problem is solved by either a classical method or a fitted operator method after approximating some of the terms in the differential equations by using the zeroth order asymptotic expansion. This method is effective and easy to implement. An error estimate is derived for the numerical solution. Examples are given to illustrate the method.     

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.     

Approximation of an Eigenvalue Problem Associated with the Stokes Problem by the Stream Function-Vorticity-Pressure Method

By means of eigenvalue error expansion and integral expansion techniques, we propose and analyze the stream function-vorticity-pressure method for the eigenvalue problem associated with the Stokes equations on the unit square. We obtain an optimal order of convergence for eigenvalues and eigenfuctions. Furthermore, for the bilinear finite element space, we derive asymptotic expansions of the eigenvalue error, an efficient extrapolation and an a posteriori error estimate for the eigenvalue. Finally, numerical experiments are reported. The first author was supported by China Postdoctoral Sciences Foundation.     

Linearly implicit extrapolation methods for differential-algebraic systems

Summary We consider the numerical solution of implicit differential equations in which the solution derivative appears multiplied by a solution-dependent singular matrix. We study extrapolation methods based on two linearly implicit Euler discretizations. Their error behaviour is explained by perturbed asymptotic expansions.     

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相似文献   

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

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

Asymptotic error expansion for the Nyström method for nonlinear Fredholm integral equations of the second kind

In this paper the asymptotic error expansion for the Nyström method for one-dimensional nonlinear Fredholm integral equations of the second kind is considered. We show that the Nyström solution admits an error expansion in powers of the step-sizeh. Thus Richardson's extrapolation can be performed on the solution, and this will greatly increase the accuracy of the numerical solution.The project has been supported by the National Natural Science Foundation of China.     

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…     

Multi-parameter extrapolation methods for boundary integral equations

Multi-parameter extrapolation was first introduced by Zhou et al. for solving partial differential equations with finite element methods in 1994. The method is based on a domain decomposition and independent discretization of the subdomains resulting in a multi-parameter error expansion. This permits a generalized extrapolation technique. The algorithm is naturally parallel since the main computational work is spent in solving independent linear systems. Here the method is extended to the case of boundary integral equations on polygonal domains, where singularities require graded meshes. A complete analysis is given, based on weighted norm techniques. Several numerical experiments demonstrate the mathematical features and practical usefulness of the method. This revised version was published online in June 2006 with corrections to the Cover Date.     

Automatic step size and order control in implicit one-step extrapolation methods

A theory is presented for implicit one-step extrapolation methods for ordinary differential equations. The computational schemes used in such methods are based on the implicit Runge-Kutta methods. An efficient implementation of implicit extrapolation is based on the combined step size and order control. The emphasis is placed on calculating and controlling the global error of the numerical solution. The aim is to achieve the user-prescribed accuracy in an automatic mode (ignoring round-off errors). All the theoretical conclusions of this paper are supported by the numerical results obtained for test problems.