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

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

偏微分方程的区间小波自适应精细积分法

利用插值小波理论构造了拟Shannon区间小波,并结合外推法给出了一种求解非线性常微分方程组的时间步长自适应精细积分法,在此基础上构造了求解非线性偏微分方程的区间小波自适应精细积分法（AIWPIM）．数值结果表明,该方法在计算精度上优于将小波和四阶Runge-Kutta法组合得到的偏微分方程的数值求解方法,而计算量则相差不大．该文方法通过Burgers方程给出,但适用于一般情形．     

A comparative study of ADI splitting methods for parabolic equations in two space dimensions

The main purpose of the paper is a numerical comparison of three integration methods for semi-discrete parabolic partial differential equations in two space variables. Linear as well as nonlinear,equations are considered. The integration methods are the well-known ADI method of Peaceman and Rachford, a global extrapolation scheme of the classical ADI method to order four and a fourth order, four-step ADI splitting method.     

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.     

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.     

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

A general theory is presented for explicit one-step extrapolation methods for ordinary differential equations. The emphasis is placed on the efficient use of extrapolation processes of this type in practice. The choice of the optimal step size and the order at each grid point is made in the automatic mode with the minimum computational work per step being the guiding principle. This principle makes it possible to find a numerical solution in the minimal time. The efficiency of the automatic step size and order control is demonstrated using test problems for which the well-known GBS method was used.     

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.     

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.     

一阶导数的五点数值微分公式及外推算法

通过对四次Lagrange插值多项式求导推导出一阶导数的五点数值微分公式,其截断误差为O(h~4).利用Richardson外推原理得到该公式的外推算法,K次外推后,中间节点的数值精度提高到O(h~(2(k+2))),其它节点的精度提高到O(h~(k+4)).     

Recursive interpolation,extrapolation and projection

The recursive projection algorithm derived in a previous paper is related to several well-known methods of numerical analysis such as the conjugate gradient method, Rosen's method and Henrici's. It is connected with the general interpolation problem, with extrapolation methods, with orthogonal projection on a subspace and with Fourier expansions. Several other connections and applications 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.     

Global Error Estimation and Extrapolated Multistep Methods For Index 1 Differential-Algebraic Systems

In recent papers the technique for a local and global error estimation and the local-global step size control were presented to solve both ordinary differential equations and semi-explicit index 1 differential-algebraic systems by multistep methods with any reasonable accuracy attained automatically. Now those results are extended to the concept of multistep extrapolation, and the paper demonstrates with numerical examples how such methods work in practice. Especially, we develop an efficient technique to calculate higher derivatives of a numerical solution with Hermite interpolating polynomials. The necessary theory is also provided. AMS subject classification (2000) 65L06, 65L70, 65L80     

Squared polynomial extrapolation methods with cycling: an application to the positron emission tomography problem

Roland and Varadhan (Appl. Numer. Math., 55:215–226, 2005) presented a new idea called “squaring” to improve the convergence of Lemaréchal’s scheme for solving nonlinear fixed-point problems. Varadhan and Roland (Squared extrapolation methods: A new class of simple and efficient numerical schemes for accelerating the convergence of the EM algorithm, Department of Biostatistics Working Paper. Johns Hopkins University, , 2004) noted that Lemaréchal’s scheme can be viewed as a member of the class of polynomial extrapolation methods with cycling that uses two fixed-point iterations per cycle. Here we combine these two ideas, cycled extrapolation and squaring, and construct a new class of methods, called squared polynomial methods (SQUAREM), for accelerating the convergence of fixed-point iterations. Our main goal is to evaluate whether the squaring device is effective in improving the rate of convergence of cycled extrapolation methods that use more than two fixed-point iterations per cycle. We study the behavior of the new schemes on an image reconstruction problem for positron emission tomography (PET) using simulated data. Our numerical experiments show the effectiveness of first- and higher-order squared polynomial extrapolation methods in accelerating image reconstruction, and also their relative superiority compared to the classical, “unsquared” vector polynomial methods.     

Extrapolation of the Stochastic Theta Numerical Method for Stochastic Differential Equations

ABSTRACT

The stochastic theta method is a family of implicit Euler methods for approximating solutions to Itô stochastic differential equations. It is proved that the weak error for the stochastic theta numerical method is of the correct form to apply Richardson extrapolation. Several computational examples illustrate the improvement in accuracy of the approximations when applying extrapolation.     

An approach to the Gummel map by vector extrapolation methods

The numerical approximation of nonlinear partial differential equations requires the computation of large nonlinear systems, that are typically solved by iterative schemes. At each step of the iterative process, a large and sparse linear system has to be solved, and the amount of time elapsed per step grows with the dimensions of the problem. As a consequence, the convergence rate may become very slow, requiring massive cpu-time to compute the solution. In all such cases, it is important to improve the rate of convergence of the iterative scheme. This can be achieved, for instance, by vector extrapolation methods. In this work, we apply some vector extrapolation methods to the electronic device simulation to improve the rate of convergence of the family of Gummel decoupling algorithms. Furthermore, a different approach to the topological ε-algorithm is proposed and preliminary results are presented.     

菲波纳奇数列在常微分方程外推方法中的应用

§1.引言 Deuflhard在关于常微分方程外推方法的综合报告[1]中认为“在早期的论文中,外推表依可用于无限排列(按两个下标)的想法加以分析:在数列?的Toeplitz条件     

A preconditioned and extrapolation-accelerated GMRES method for PageRank

In this paper, we propose and analyze GMRES-type methods for the PageRank computation. However, GMRES may converge very slowly or sometimes even diverge or break down when the damping factor is close to 1 and the dimension of the search subspace is low. We propose two strategies: preconditioning and vector extrapolation accelerating, to improve the convergence rate of the GMRES method. Theoretical analysis demonstrate the efficiency of the proposed strategies and numerical experiments show that the performance of the proposed methods is very much better than that of the traditional methods for PageRank problems.     

基于超收敛和外推方法的一类新的瀑布型多重网格方法

本文运用有限元超收敛理论和外推技巧提出了一类求解椭圆型方程的新的瀑布型多重网格方法(ACMG).数值结果表明新方法具有超收敛性.     

DECUHR: an algorithm for automatic integration of singular functions over a hyperrectangular region

We describe an automatic cubature algorithm for functions that have a singularity on the surface of the integration region. The algorithm combines an adaptive subdivision strategy with extrapolation. The extrapolation uses a non-uniform subdivision that can be directly incorporated into the subdivision strategy used for the adaptive algorithm. The algorithm is designed to integrate a vector function over ann-dimensional rectangular region and a FORTRAN implementation is included.Supported by the Norwegian Research Council for Science and the Humanities.