Cascadic multigrid methods combined with sixth order compact scheme for poisson equation

Based on the extrapolation theory and a sixth order compact difference scheme, new extrapolation interpolation operator and extrapolation cascadic multigrid methods for two dimensional Poisson equation are presented. The new extrapolation interpolation operator is used to provide a better initial value on refined grid. The convergence of the new methods are given. Numerical experiments are shown to illustrate that the new methods have higher accuracy and efficiency.     

L^2-ERROR OF EXTRAPOLATION CASCADIC MULTIGRID （EXCMG）

Based on an asymptotic expansion of finite element, an extrapolation cascadic multigrid method （EXCMG） is proposed, in which the new extrapolation and quadratic interpolation are used to provide a better initial value on refined grid. In the case of multiple grids, both superconvergence error in H^1-norm and the optimal error in l2-norm are analyzed. The numerical experiment shows the advantage of EXCMG in comparison with CMG.     

外推瀑布多网格法(EXCMG)——-大规模求解椭圆问题的新算法

基于有限元的渐近展开式,导出了新的外推公式,它们更精确地逼近密网上的有限元解(而不是微分方程的解).提出了新的外推瀑布型多网格法(EXCMG),采用新外推公式及其二次插值提供密网上的好初值.数值实验表明,新方法有很高的精度和效率.最后在PC机上求解了大规模二维椭圆问题.     

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.     

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.     

用数值积分的初参数法解波纹管

本文把波纹管的边值问题化为初值问题,根据B.B.Новожилов的环壳方程[8].用S.Gill方法[10],求出半圆弧波纹管的数值解.计算了在轴向力和内压作用下的变形和应力分布,其结果和钱伟长教授的一般解完全一致.本文提出的外推公式可以显著地提高离散化方法的计算精度.文后附有WANG 2200VS计算机上BASIC语言的源程序.     

On the internal stepsize of an extrapolation algorithm for IVP in ODE

We propose an extrapolation algorithm for initial value problems in ordinary differential equations. In the algorithm, an appropriately chosen stepsizeH is divided into smaller stepsizes by a sequence and a new stopping rule is proposed. The sequences applied to the algorithm are Romberg {2,4,8,16,32,...}, Bulirsch {2,4,6,8,16...} and Harmonic {2,4,6,8,10,12,...} types. The proposed algorithm is compared numerically with the algorithm introduced by Stoer. In view of the accuracy of numerical solutions, the relatively small number of calculations, the stability and reliability of the algorithm, we found that the algorithm with the Romberg sequence is the best.     

Estimation of 1-dimensional nonlinear stochastic differential equations based on higher-order partial differential equation numerical scheme and its application

A method based on higher-order partial differential equation (PDE) numerical scheme are proposed to obtain the transition cumulative distribution function (CDF) of the diffusion process (numerical differentiation of the transition CDF follows the transition probability density function (PDF)), where a transformation is applied to the Kolmogorov PDEs first, then a new type of PDEs with step function initial conditions and 0, 1 boundary conditions can be obtained. The new PDEs are solved by a fourth-order compact difference scheme and a compact difference scheme with extrapolation algorithm. After extrapolation, the compact difference scheme is extended to a scheme with sixth-order accuracy in space, where the convergence is proved. The results of the numerical tests show that the CDF approach based on the compact difference scheme to be more accurate than the other estimation methods considered; however, the CDF approach is not time-consuming. Moreover, the CDF approach is used to fit monthly data of the Federal funds rate between 1983 and 2000 by CKLS model.     

On Vortex Methods for Initial Boundary Value Problems

ＯｎＶｏｒｔｅｘＭｅｔｈｏｄｓｆｏｒＩｎｉｔｉａｌＢｏｕｎｄａｒｙＶａｌｕｅＰｒｏｂｌｅｍｓ￥ＺｈａｎｇＰｉｎｇｗｅｎ（张平文）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＰｅｋｉｎｇＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｉｎｇ，１００８７１）Ａｂｓｔｒ...     

Reciprocal polynomial extrapolation vs Richardson extrapolation for singular perturbed boundary problems

The reciprocal polynomial extrapolation was introduced in Amat et al. (J Comput Math 22(1):1?C10, 2004), where its accuracy and stability were studied and a linear scalar test problem was analyzed numerically. In the present work, a new step in the implementation of the reciprocal polynomial extrapolation, ensuring at least the same behavior as the Richardson extrapolation, is proposed. Looking at the reciprocal extrapolation as a Richardson extrapolation where the original data is nonlinearly modified, the improvements that we will obtain should be justified. Several theoretical analysis of the new extrapolation, including local error estimates and stability properties, are presented. A comparison between the two extrapolation techniques is performed for solving some boundary problems with perturbation controlled by a small parameter ?. Using two specific boundary problems, the error and the robustness of the new technique using centered divided differences in a uniform mesh are investigated numerically. They turn out to be better than those presented by the Richardson extrapolation. Finally, investigations on the accuracy when using a special non-uniform discretization mesh are presented. A numerical comparison with the Richardson extrapolation for this particular case, where we present some improvements, is also performed.     

Extrapolation applied to certain discretization methods solving the initial value problem for hyperbolic differential equations

Summary The procedurediwiex presented in this paper provides an approximate solution to Cauchy's initial value problem for general hyperbolic systems of first order. The procedurecharex can be applied to the initial value problem for a hyperbolic system of quasi-linear differential equations. This second method is a kind of method of characteristics. It produces a solution for the whole domain of determinancy. Both procedures use extrapolation to the limit. Editor's Note. In this fascile, prepublication of algorithms from the Approximations series of the Handbook for Automatic Computation is continued. Algorithms are published in ALGOL 60 reference language as approved by the IFIP. Contributions in this series should be styled after the most recently published ones     

EXTRAPOLATION AND A-POSTERIORI ERROR ESTIMATORS OF PETROV-GALERKIN METHODS FOR NON-LINEAR VOLTERRA INTEGRO-DIFFERENTIAL EQUATIONS

1. IntroductionThe pmpme of tabs Paper is to show that the ~ardson edrapolation can be used toenhance the nUmerical solutions generated by a cab of Petrov-Gaierkin lhate element methodsfor the nonlinear VOlterra integrO-chrential equation (VIDE):where j = j(t,y): I x R --+ R and k = k(t,8,g): D x R - R (with D:= {(t,8): 0 S & S t ST}) denote given hmctions.Throughout tab paperl it will always be assumed that the problem (1.1) possesses a piquesolution y E C'(I), namely, the given hmc…     

A method of characteristics solving the initial-boundary value problem of a hyperbolic differential equation of second order

Summary The ALGOL-procedure¹ char2 presented in this paper can be applied to the initial or initial-boundary value problem of a quasilinear hyperbolic differential equation of second order. A method of characteristics is combined with extrapolation to the limit. Thus, the results are very accurate. The same accuracy can also be obtained if the initial values are only piecewise smooth.Editor's Note: In this fascile, prepublication of algorithms from the Approximation series of the Handbook for Automatic Computation is continued. Algorithms are published in ALGOL 60 reference language as approved by the IFIP. Contributions in this series should be styled after the most recently published ones     

Smoothing the extrapolated midpoint rule

Summary The extrapolated midpoint rule is a popular way to solve the initial value problem for a system of ordinary differential equations. As originally formulated by Gragg, the results are smoothed to remove the weak instability of the midpoint rule. It is shown that this smoothing is not necessary. A cheaper smoothing scheme is proposed. A way to exploit smoothing to increase the robustness of extrapolation codes is formulated.This work performed at Sandia National Laboratories supported by the US Department of Energy under contract number DE-AC04-76DP00789     

Extrapolation to the limit for numerical solutions of hyperbolic equations

Summary The application of extrapolation to the limit requires the existence of an asymptotic expansion in powers of the step size. In this paper one-and multi-step methods for the solution of hyperbolic systems of first order are considered. Conditions are formulated that ensure the asymptotic expansion. Methods of characteristics for quasilinear systems with two independent variables are included in this presentation. If a rectangular grid is used, also non-quasilinear systems are admissible. The main part of this paper deals with initial value problems. But it is shown that in some exceptional cases asymptotic expansions hold for initial-boundary problems, too.This paper is chiefly based on the author's doctoral thesis [7], written under the direction of Professor R. Bulirsch     

TIME-EXTRAPOLATION ALGORITHM （TEA） FOR LINEAR PARABOLIC PROBLEMS

The fast solutions of Crank-Nicolson scheme on quasi-uniform mesh for parabolic prob- lems are discussed. First, to decrease regularity requirements of solutions, some new error estimates are proved. Second, we analyze the two characteristics of parabolic discrete scheme, and find that the efficiency of Multigrid Method （MG） is greatly reduced. Nu- merical experiments compare the efficiency of Direct Conjugate Gradient Method （DCG） and Extrapolation Cascadic Multigrid Method （EXCMG）. Last, we propose a Time- Extrapolation Algorithm （TEA）, which takes a linear combination of previous several level solutions as good initial values to accelerate the rate of convergence. Some typical extrapolation formulas are compared numerically. And we find that under certain accuracy requirement, the CG iteration count for the 3-order and 7-level extrapolation formula is about 1/3 of that of DCG＇s. Since the TEA algorithm is independent of the space dimension, it is still valid for quasi-uniform meshes. As only the finest grid is needed, the proposed method is regarded very effective for nonlinear parabolic problems.     

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.     

Das Differenzenverfahren für singuläre Rand-Eigenwertaufgaben gewöhnlicher Differentialgleichungen

Summary The boundary value problem for a class of singular second order differential operators is defined. Using the standard three point discretisation for the differential equation and taking care of the limits involved in the boundary conditions in a natural way, finite difference approximations to the boundary value problems are defined and their convergence properties are investigated. The rate of convergence is given in terms of the data. It turns out that for problems of the first kind extrapolation is possible up to an arbitrary order after a suitable change of the independent variable, whereas for problems of the second kind neither theoretical nor numerical results indicate the possibility of extrapolation. Corresponding results hold for the eigenvalue problems. Some numerical examples show that the convergence rates given in the paper are best possible and demonstrate the effect of extrapolation.     

Extrapolation for Higher Orders of Convergence

A new extrapolation procedure which encompasses Aitken's 2 processand extends to higher orders of convergence is presented. Thenew extrapolation yields information as to whether an algorithmis converging or diverging as well as a new approximation tothe solution point. The new extrapolation technique is comparedwith existing higher order extrapolation techniques. The valueof the new extrapolation is demonstrated analytically and empirically.     

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.