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 one-step collocation methods with higher derivatives

On the basis of symmetric E-methods with higher derivatives having the convergence order four, six, or eight, implicit extrapolation schemes are constructed for the numerical solution of ordinary differential equations. The combined step size and order control used in these schemes implements an automatic global error control in the extrapolation E-methods, which makes it possible to solve differential problems in automatic mode up to the accuracy specified by the user (without taking into account round-off errors). The theory of adjoint and symmetric methods presented in this paper is an extension of the results that are well known for the conventional Runge-Kutta schemes to methods involving higher derivatives. Since the implicit extrapolation based on multi-stage Runge-Kutta methods can be very time consuming, special emphasis is made on the efficiency of calculations. All the theoretical conclusions of this paper are confirmed by the numerical results obtained for test problems.     

Global error estimation for index-1 and -2 DAEs

In this paper, we consider the extension of three classical ODE estimation techniques (Richardson extrapolation, Zadunaisky's technique and solving for the correction) to DAEs. Their convergence analysis is carried out for semi-explicit index-1 DAEs solved by a wide set of Runge-Kutta methods. Experimentation of the estimation techniques with RADAU5 is also presented: their behaviour for index-1 and -2 problems, and for variable step size integration is investigated. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

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.     

Modelling and analysis of the non-iterative coupling process for co-simulation

Concerning non-iterative co-simulation, stepwise extrapolation of coupling signals is required to solve an overall system of interconnected subsystems. Each extrapolation is some kind of estimation and is directly associated with an estimation error. The introduced disturbance depends significantly on the macro-step size, i.e. the coupling step size, and influences the entire system behaviour. In addition, for synchronization purposes, sampling of the coupling signals can cause aliasing. Instead of analysing the coupling effects in the time domain, as it is commonly practised, we concentrate on a model-based approach to gain more insight into the coupling process. In this work, we consider commonly used polynomial extrapolation techniques and analyse them in the frequency domain. Based on this system-oriented point of view of the coupling process, a relation between the coupling signals and the macro-step size is available. In accordance to the dynamics of the interconnected subsystems, the model-based relation is used to select the most critical parameter, i.e. the macro-step size. Besides a ‘rule of thumb’ for meaningful step-size selection, a co-simulation benchmark example describing a two degree of freedom (2-DOF) mechanical system is used to demonstrate the advantages of modelling and the efficiency of the proposed method.     

Asynchronous method for the coupled simulation of mechatronic systems

A new method for coupled simulation of mechatronic systems based on a comparison of the actual time step of the simulation tools and the utilization of inter– and extrapolation methods will be presented in this contribution. Since the method does not use constant synchronization time points, the problem of setting the appropriate macro step size is avoided. The example of a drill driver model is used to compare the results of the proposed method with those obtained by a conventional approach. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Propagation of initial rounding error in Romberg-like quadrature

We examine a Romberg-like quadrature in which the number of subintervals taken grows only linearly, not exponentially. Such a scheme is known to be numerically unstable. We show, however, that this instability is only mild, and we obtain a bound on the size of the error, caused by extrapolation of the initial trapezoidal sums. A similar formula is obtained for the standard deviation of the error when a statistical model is used. Numerical examples show that the bound is not too pessimistic. Quantitatively, not more than two-fifths of a digit of accuracy get lost per extrapolation step, and this economical choice of points can thus be used practically.     

Extrapolation and Adaptivity in Software for Automatic Numerical Integration on a Cube

Asymptotic expansions related to the integration of well-behaved functions on simplices and cubes have been known for several decades. Extensions of these results to classes of vertex and line singularities are also known. The nature of these expansions justifies extrapolation using the ε-algorithm of Wynn. In principle this requires a uniform subdivision of the region. This was implemented in QUADPACK for finite intervals and in TRIEX for triangles about 15 years ago. In this paper its incorporation in CUBPACK, a software package for automatic integration over a collection of cubes and simplices, is described and some results are reported. We also report on a special subdivision strategy that offers an alternative approach for higher-dimensional problems.     

Unconditionally Optimal Error Analysis of the Second-Order BDF Finite Element Method for the Kuramoto-Tsuzuki Equation

This paper aims to study a second-order semi-implicit BDF finite element scheme for the Kuramoto-Tsuzuki equations in two dimensional and three dimensional spaces. The proposed scheme is stable and the nonlinear term is linearized by the extrapolation technique. Moreover, we prove that the error estimate in $L^2$-norm is unconditionally optimal which means that there has not any restriction on the time step and the mesh size. Finally, numerical results are displayed to illustrate our theoretical analysis.     

The efficiency of extrapolation methods for numerical integration

A study of various methods based on polynomial extrapolation for the automatic evaluation of definite integrals in one dimension confirms that Bulirsch and Stoer's choice is the optimum general-purpose procedure. This is then compared with the Gauss-Legendre and Clenshaw-Curtis schemes, and the possible advantages of rational extrapolation are also investigated.     

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.     

Blockwise acceleration of alternating least squares for canonical tensor decomposition

The canonical polyadic (CP) decomposition of tensors is one of the most important tensor decompositions. While the well-known alternating least squares (ALS) algorithm is often considered the workhorse algorithm for computing the CP decomposition, it is known to suffer from slow convergence in many cases and various algorithms have been proposed to accelerate it. In this article, we propose a new accelerated ALS algorithm that accelerates ALS in a blockwise manner using a simple momentum-based extrapolation technique and a random perturbation technique. Specifically, our algorithm updates one factor matrix (i.e., block) at a time, as in ALS, with each update consisting of a minimization step that directly reduces the reconstruction error, an extrapolation step that moves the factor matrix along the previous update direction, and a random perturbation step for breaking convergence bottlenecks. Our extrapolation strategy takes a simpler form than the state-of-the-art extrapolation strategies and is easier to implement. Our algorithm has negligible computational overheads relative to ALS and is simple to apply. Empirically, our proposed algorithm shows strong performance as compared to the state-of-the-art acceleration techniques on both simulated and real tensors.     

Automatic selection of the initial step size for an ODE solver

The choice of initial step size is critical for the reliable numerical solution of the initial value problem for a system of ordinary differential equations. Automatic selection of this step size may lead to a more robust and efficient integration than its provision by a user, and is always more convenient. It is especially important for the reliability of an ODE solver used as a module in a larger software package.Previous approaches to making the selection are combined with some new ideas to produce an effective scheme for the automatic choice of the initial step size. Numerical results illustrate the roles played by the individual phases of the algorithm and show that the whole algorithm is both robust and efficient.     

A study of Rosenbrock-type methods of high order

Summary This paper deals with the solution of nonlinear stiff ordinary differential equations. The methods derived here are of Rosenbrock-type. This has the advantage that they areA-stable (or stiffly stable) and nevertheless do not require the solution of nonlinear systems of equations. We derive methods of orders 5 and 6 which require one evaluation of the Jacobian and oneLU decomposition per step. We have written programs for these methods which use Richardson extrapolation for the step size control and give numerical results.     

Application of the largest Lyapunov exponent and non-linear fractal extrapolation algorithm to short-term load forecasting

Precise short-term load forecasting (STLF) plays a key role in unit commitment, maintenance and economic dispatch problems. Employing a subjective and arbitrary predictive step size is one of the most important factors causing the low forecasting accuracy. To solve this problem, the largest Lyapunov exponent is adopted to estimate the maximal predictive step size so that the step size in the forecasting is no more than this maximal one. In addition, in this paper a seldom used forecasting model, which is based on the non-linear fractal extrapolation (NLFE) algorithm, is considered to develop the accuracy of predictions. The suitability and superiority of the two solutions are illustrated through an application to real load forecasting using New South Wales electricity load data from the Australian National Electricity Market. Meanwhile, three forecasting models: the gray model, the seasonal autoregressive integrated moving average approach and the support vector machine method, which received high approval in STLF, are selected to compare with the NLFE algorithm. Comparison results also show that the NLFE model is outstanding, effective, practical and feasible.     

An extrapolation method with step size control for nonlinear Volterra integral equations

Summary In [6] it has been shown that the midpoint rule applied to second kind volterra integral equations possesses an asymptotic expansion in even powers of the stepsizeh. In this paper we describe an extrapolation method based on the midpoint rule, together with a mechanism of step size control.     

Solving the order reduction phenomenon in variable step size quasi-consistent Nordsieck methods

The phenomenon is studied of reducing the order of convergence by one in some classes of variable step size Nordsieck formulas as applied to the solution of the initial value problem for a first-order ordinary differential equation. This phenomenon is caused by the fact that the convergence of fixed step size Nordsieck methods requires weaker quasi-consistency than classical Runge-Kutta formulas, which require consistency up to a certain order. In other words, quasi-consistent Nordsieck methods on fixed step size meshes have a higher order of convergence than on variable step size ones. This fact creates certain difficulties in the automatic error control of these methods. It is shown how quasi-consistent methods can be modified so that the high order of convergence is preserved on variable step size meshes. The regular techniques proposed can be applied to any quasi-consistent Nordsieck methods. Specifically, it is shown how this technique performs for Nordsieck methods based on the multistep Adams-Moulton formulas, which are the most popular quasi-consistent methods. The theoretical conclusions of this paper are confirmed by the numerical results obtained for a test problem with a known solution.     

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.     

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