Multi-step methods are essentially one-step methods

Summary In this note the geometry of multi-step methods is studied using invariant manifold theory for maps, as familiar from dynamical systems theory. This permits to associate a one-step method to each multi-step method to which the former is not only equivalent asymptotically, but equal in each step if the one-step method is used to produce the initial data of the multi-step method.     

On the order of iterated defect correction

Summary In a recent article [2] Frank and Überhuber define and motivate the method of iterated defect correction for Runge-Kutta methods. They prove a theorem on the order of that method using the theory of asymptotic expansions.In this paper we give similar results using the theory of Butcher series (see [4]). Our proofs are purely algebraic. We don't restrict our considerations to Runge-Kutta methods, but we admit arbitrary linear one-step methods. At the same time we consider more general defect functions as in [2].     

On invariant closed curves for one-step methods

Summary We show that a one-step method as applied to a dynamical system with a hyperbolic periodic orbit, exhibits an invariant closed curve for sufficiently small step size. This invariant curve converges to the periodic orbit with the order of the method and it inherits the stability of the periodic orbit. The dynamics of the one-step method on the invariant curve can be described by the rotation number for which we derive an asymptotic expression. Our results complement those of [2, 3] where one-step methods were shown to create invariant curves if the dynamical system has a periodic orbit which is stable in either time direction or if the system undergoes a Hopf bifurcation.     

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.     

A one-step optimal homotopy analysis method for nonlinear differential equations

In this paper, a one-step optimal approach is proposed to improve the computational efficiency of the homotopy analysis method (HAM) for nonlinear problems. A generalized homotopy equation is first expressed by means of a unknown embedding function in Taylor series, whose coefficient is then determined one by one by minimizing the square residual error of the governing equation. Since at each order of approximation, only one algebraic equation with one unknown variable is solved, the computational efficiency is significantly improved, especially for high-order approximations. Some examples are used to illustrate the validity of this one-step optimal approach, which indicate that convergent series solution can be obtained by the optimal homotopy analysis method with much less CPU time. Using this one-step optimal approach, the homotopy analysis method might be applied to solve rather complicated differential equations with strong nonlinearity.     

Asymptotic bounds on the errors of one-step methods

Summary Bulirsch and Stoer have shown how to construct asymptotic upper and lower bounds on the true (global) errors resulting from the solution by extrapolation of the initial value problem for a system of ordinary differential equations. It is shown here how to do this for any one-step method endowed with an asymptotically correct local error estimator. The one-step method can be changed at every step.This work performed at Sandia National Laboratories supported by the U.S. Department of Energy under contract number DE-AC04-76DP00789     

Local error estimation for multistep collocation methods

Multistep collocation methods for initial value problems in ordinary differential equations are known to be a subclass of multistep Runge-Kutta methods and a generalisation of the well-known class of one-step collocation methods as well as of the one-leg methods of Dahlquist. In this paper we derive an error estimation method of embedded type for multistep collocation methods based on perturbed multistep collocation methods. This parallels and generalizes the results for one-step collocation methods by Nørsett and Wanner. Simple numerical experiments show that this error estimator agrees well with a theoretical error estimate which is a generalisation of an error estimate first derived by Dahlquist for one-leg methods.     

Convergence Analysis of Spatially Adaptive Rothe Methods

This paper is concerned with the convergence analysis of the horizontal method of lines for evolution equations of the parabolic type. Following a semidiscretization in time by \(S\) -stage one-step methods, the resulting elliptic stage equations per time step are solved with adaptive space discretization schemes. We investigate how the tolerances in each time step must be tuned in order to preserve the asymptotic temporal convergence order of the time stepping also in the presence of spatial discretization errors. In particular, we discuss the case of linearly implicit time integrators and adaptive wavelet discretizations in space. Using concepts from regularity theory for partial differential equations and from nonlinear approximation theory, we determine an upper bound for the degrees of freedom for the overall scheme that are needed to adaptively approximate the solution up to a prescribed tolerance.     

P_0函数非线性互补问题的一步非内点连续方法的收敛性

本文对于Ｐ０函数非线性互补问题提出了一个基于Ｋａｎｚｏｗ光滑函数的一步非内点连续方法,在适当的假设条件下,证明了方法的全局线性及局部二次收敛性．特别,在方法的全局线性收敛性的分析中,不需要假定非线性互补问题的函数的Ｊａｃｏｂｉ阵是Ｌｉｐｓｃｈｉｔｚ连续的．文献中为了得到非内点连续方法的全局线性收敛性,这一假定是被广泛使用的．本文提出的方法在每一次迭代只须解一个线性方程式组．     

General techniques for constructing variational integrators

The numerical analysis of variational integrators relies on variational error analysis, which relates the order of accuracy of a variational integrator with the order of approximation of the exact discrete Lagrangian by a computable discrete Lagrangian. The exact discrete Lagrangian can either be characterized variationally, or in terms of Jacobi’s solution of the Hamilton-Jacobi equation. These two characterizations lead to the Galerkin and shooting constructions for discrete Lagrangians, which depend on a choice of a numerical quadrature formula, together with either a finite-dimensional function space or a one-step method. We prove that the properties of the quadrature formula, finite-dimensional function space, and underlying one-step method determine the order of accuracy and momentum-conservation properties of the associated variational integrators. We also illustrate these systematic methods for constructing variational integrators with numerical examples.     

Order conditions for Rosenbrock type methods

Summary Based on the theory of Butcher series this paper developes the order conditions for Rosenbrock methods and its extensions to Runge-Kutta methods with exact Jacobian dependent coefficients. As an application a third order modified Rosenbrock method with local error estimate is constructed and tested on some examples.     

部分线性回归模型变窗宽一步局部M-估计

讨论了部分线性回归模型的变窗宽一步局部M-估计.用一步局部M-估计给出未知函数的估计,用平均方法给出参数估计.进一步通过两个引理证明一步M-估计的渐近正态性.所提出的方法继承了局部多项式的优点并且克服了最小二乘法缺乏稳健性的缺点.     

Explicit One-Step P-Stable Methods for Second Order Periodic Initial Value Problems

In this paper, we present an explicit one-step method for solving periodic initial value problems of second order ordinary differential equations. The method is P-stable, and of first algebraic order and high phase-lag order. To improve the algebraic order, we give a composition second order scheme with the proposed method and its adjoint. We report some numerical results to illustrate the efficiency of our methods.     

高阶单步A-稳定指数拟合法

In this paper,the necessary and sutlicient conditions for general one-step methoos to be exponentially fitted at q0∈C are given, A class of multtderivative hybrid one-step methods of order at least s 1 is constructed with s 1 parameters,where s is the order of derivative. The necessary and sufficient conditions for these methods to be A-stable and exponentially fitted is proved, Furthermore,a class of A-stable 2 parameters hybrid one-step methods of order at least 8 are constructed,which use 4th order derivative,These methods are exponentially fitted at q0 if and only its fitted function f(q) satisfies f(q0)= 0, Finally,an A-stable exponentlally fitted method of order 8 is obtained.     

High-order splitting schemes for semilinear evolution equations

We first derive necessary and sufficient stiff order conditions, up to order four, for exponential splitting schemes applied to semilinear evolution equations. The main idea is to identify the local splitting error as a sum of quadrature errors. The order conditions of the quadrature rules then yield the stiff order conditions in an explicit fashion, similarly to that of Runge–Kutta schemes. Furthermore, the derived stiff conditions coincide with the classical non-stiff conditions. Secondly, we propose an abstract convergence analysis, where the linear part of the vector field is assumed to generate a group or a semigroup and the nonlinear part is assumed to be smooth and to satisfy a set of compatibility requirements. Concrete applications include nonlinear wave equations and diffusion-reaction processes. The convergence analysis also extends to the case where the nonlinear flows in the exponential splitting scheme are approximated by a sufficiently accurate one-step method.     

Positive definiteness in the numerical solution of Riccati differential equations

Summary. In this work we address the issue of integrating symmetric Riccati and Lyapunov matrix differential equations. In many cases -- typical in applications -- the solutions are positive definite matrices. Our goal is to study when and how this property is maintained for a numerically computed solution. There are two classes of solution methods: direct and indirect algorithms. The first class consists of the schemes resulting from direct discretization of the equations. The second class consists of algorithms which recover the solution by exploiting some special formulae that these solutions are known to satisfy. We show first that using a direct algorithm -- a one-step scheme or a strictly stable multistep scheme (explicit or implicit) -- limits the order of the numerical method to one if we want to guarantee that the computed solution stays positive definite. Then we show two ways to obtain positive definite higher order approximations by using indirect algorithms. The first is to apply a symplectic integrator to an associated Hamiltonian system. The other uses stepwise linearization. Received April 21, 1993     

Nonlinear Implicit One-Step Schemes for Solving Initial Value Problems for Ordinary Differential Equation with Steep Gradients

A general theory for nonlinear implicit one-step schemes for solving initial value problems for ordinary differential equations is presented in this paper. The general expansion of "symmetric" implicit one-step schemes having second-order is derived and stability and convergence are studied. As examples, some geometric schemes are given. Based on previous work of the first author on a generalization of means, a fourth-order nonlinear implicit one-step scheme is presented for solving equations with steep gradients. Also, a hybrid method based on the GMS and a fourth-order linear scheme is discussed. Some numerical results are given.     

Rooted tree analysis of Runge–Kutta methods with exact treatment of linear terms

We investigate a class of time discretization schemes called “ETD Runge–Kutta methods,” where the linear terms of an ordinary differential equation are treated exactly, while the other terms are numerically integrated by a one-step method. These schemes, proposed by previous authors, can be regarded as modified Runge–Kutta methods whose coefficients are matrices instead of scalars. From this viewpoint, we reexamine the notion of consistency, convergence and order to provide a mathematical foundation for new methods. Applying the rooted tree analysis, expansion theorems of both the strict and numerical solutions are proved, and two types of order conditions are defined. Several classes of formulas with up to four stages that satisfy the conditions are constructed, and it is shown that the power series of matrices, employed as their coefficients, can be determined using the order conditions.     

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.     

An elementary algebraic representation of polynomial spline interpolants for equidistant lattices and its condition

Summary A customary representation formula for periodic spline interpolants contains redundance which, however, can be eliminated by a transcendent method. We use an elementary indentity for the generalized Euler-Frobenius-polynomials, which seems to be unknown until now, in order to derive the theory by purely algebraic arguments. The general cardinal spline interpolation theory can be obtained from the periodic case by a simple approach to the limit. Our representation has minimum condition for odd/even degree if the interpolation points are the lattice (mid-)points. We evaluate the corresponding condition numbers and give an asymptotic representation for them.