On multistep interval methods for solving the initial value problem

In this paper we shortly complete our previous considerations on interval versions of Adams multistep methods [M. Jankowska, A. Marciniak, Implicit interval multistep methods for solving the initial value problem, Comput. Meth. Sci. Technol. 8(1) (2002) 17–30; M. Jankowska, A. Marciniak, On explicit interval methods of Adams–Bashforth type, Comput. Meth. Sci. Technol. 8(2) (2002) 46–57; A. Marciniak, Implicit interval methods for solving the initial value problem, Numerical Algorithms 37 (2004) 241–251]. It appears that there exist two families of implicit interval methods of this kind. More considerations are dealt with two new kinds of interval multistep methods based on conventional well-known Nyström and Milne–Simpson methods. For these new interval methods we prove that the exact solution of the initial value problem belongs to the intervals obtained. Moreover, we present some estimations of the widths of interval solutions. Some conclusions bring this paper to the end.     

Interval methods of Adams-Bashforth type with variable step sizes

Numerical Algorithms - In a number of our previous papers, we have proposed interval versions of multistep methods (explicit and implicit), including interval predictor-corrector methods, in which...     

Variable stepsize implementation of multistep methods for y″=f(x,y,y′)

The Falkner method is a multistep scheme intended for the numerical solution of second-order initial value problems where the first derivative does appear explicitly. In this paper, we develop a procedure to obtain k-step Falkner methods (explicit and implicit) in their variable step-size versions, providing recurrence formulas to compute the coefficients efficiently. Considering a pair of explicit and implicit formulae, these may be implemented in predictor–corrector mode.     

Linearly Implicit Finite Element Methods for the Time-Dependent Joule Heating Problem

Completely discrete numerical methods for a nonlinear elliptic-parabolic system, the time-dependent Joule heating problem, are introduced and analyzed. The equations are discretized in space by a standard finite element method, and in time by combinations of rational implicit and explicit multistep schemes. The schemes are linearly implicit in the sense that they require, at each time level, the solution of linear systems of equations. Optimal order error estimates are proved under the assumption of sufficiently regular solutions. AMS subject classification (2000) 65M30, 65M15, 35K60     

Validated Infeasible Interior-Point Predictor–Corrector Methods for Linear Programming

Many problems arising in practical applications lead to linear programming problems. Hence, they are fundamentally tractable. Recent interior-point methods can exploit problem structure to solve such problems very efficiently. Infeasible interior-point predictor–corrector methods using floating-point arithmetic sometimes compute an approximate solution with duality gap less than a given tolerance even when the problem may not have a solution. We present an efficient verification method for solving linear programming problems which computes a guaranteed enclosure of the optimal solution and which verifies the existence of the solution within the computed interval.     

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     

预估-校正方法的绝对稳定性讨论

预估-校正方法,即PECE方法,常被用于求解常微分方程的初值问题.而一般文献中常只讨论了单个线性多步法公式的稳定性问题,很少涉及由一个显式公式和一个隐式公式组合而成的PECE方法的稳定性.本文应用根轨迹法和对分法讨论了常用的PECE方法的稳定性,求出了一些常用PECE方法的组合公式的绝对稳定区间和绝对稳定区域,并用数值...     

求解非线性刚性初值问题的隐显线性多步方法的误差分析

隐显线性多步方法由隐式线性多步方法和显式线性多步法组合而成.本文主要讨论求解满足单边Lipschitz条件的非线性刚性初值问题和一类奇异摄动初值问题的隐显线性多步方法的误差分析.最后,由数值例子验证了所获的理论结果的正确性及方法处理这两类问题的有效性.     

Applications of interval arithmetic in solving polynomial equations by Wu''''s elimination method

Wu's elimination method is an important method for solving multivariate poly- nomial equations.In this paper,we apply interval arithmetic to Wu's method and convert the problem of solving polynomial equations into that of solving interval polynomial equa- tions.Parallel results such as zero-decomposition theorem are obtained for interval poly- nomial equations.The advantages of the new approach are two-folds:First,the problem of the numerical instability arisen from floating-point arithmetic is largely overcome.Second, the low efficiency of the algorithm caused by large intermediate coefficients introduced by exact compaction is dramatically improved.Some examples are provided to illustrate the effectiveness of the proposed algorithm.     

Safe bounds in linear and mixed-integer linear programming

Current mixed-integer linear programming solvers are based on linear programming routines that use floating-point arithmetic. Occasionally, this leads to wrong solutions, even for problems where all coefficients and all solution components are small integers. An example is given where many state-of-the-art MILP solvers fail. It is then shown how, using directed rounding and interval arithmetic, cheap pre- and postprocessing of the linear programs arising in a branch-and-cut framework can guarantee that no solution is lost, at least for mixed-integer programs in which all variables can be bounded rigorously by bounds of reasonable size. Mathematics Subject Classification (2000):primary 90C11, secondary 65G20     

Modified Implicit–Explicit BDF Methods for Nonlinear Parabolic Equations

Implicit–explicit multistep methods for nonlinear parabolic equations were recently analyzed. If the implicit scheme is one of the backward differentiation formulae (BDF) of order up to six, then the corresponding implicit–explicit method of the same order is stable provided the stability constant is less than a specific scheme-dependent constant. Based on BDF, implicit methods are constructed such that the corresponding implicit–explicit scheme of the same order exhibits improved stability properties.     

Two-Stage Stochastic Runge-Kutta Methods for Stochastic Differential Equations

In this paper we discuss two-stage diagonally implicit stochastic Runge-Kutta methods with strong order 1.0 for strong solutions of Stratonovich stochastic differential equations. Five stochastic Runge-Kutta methods are presented in this paper. They are an explicit method with a large MS-stability region, a semi-implicit method with minimum principal error coefficients, a semi-implicit method with a large MS-stability region, an implicit method with minimum principal error coefficients and another implicit method. We also consider composite stochastic Runge-Kutta methods which are the combination of semi-implicit Runge-Kutta methods and implicit Runge-Kutta methods. Two composite methods are presented in this paper. Numerical results are reported to compare the convergence properties and stability properties of these stochastic Runge-Kutta methods.     

Convergence of multistep discretizations of DAEs

Standard ODE methods such as linear multistep methods encounter difficulties when applied to differential-algebraic equations (DAEs) of index greater than 1. In particular, previous results for index 2 DAEs have practically ruled out the use of all explicit methods and of implicit multistep methods other than backward difference formulas (BDFs) because of stability considerations. In this paper we embed known results for semi-explicit index 1 and 2 DAEs in a more comprehensive theory based on compound multistep and one-leg discretizations. This explains and characterizes the necessary requirements that a method must fulfill in order to be applicable to semi-explicit DAEs. Thus we conclude that the most useful discretizations are those that avoid discretization of the constraint. A freer use of e.g. explicit methods for the non-stiff differential part of the DAE is then possible.Dedicated to Germund Dahlquist on the occasion of his 70th birthdayThis author thanks the Centro de Estadística y Software Matemático de la Universidad Simón Bolivar (CESMa) for permitting her free use of its research facilities.Partial support by the Swedish Research Council for Engineering Sciences TFR under contract no. 222/91-405.     

A Validated Real Function Calculus

We present a framework for validated numerical computations with real functions. The framework is based on a formalisation of abstract data types for basic floating-point arithmetic, interval arithmetic and function models based on Banach algebra. As a concrete instantiation, we develop an elementary smooth function calculus approximated by sparse polynomial models. We demonstrate formal verification applied to validated calculus by a formalisation of basic arithmetic operations in a theorem prover. The ultimate aim is to develop a formalism powerful enough for reachability analysis of nonlinear hybrid systems.     

Intrinsic Compiler Support for Interval Arithmetic

Interval arithmetic provides an efficient method for monitoring errors in numerical computations and for solving problems that cannot be efficiently solved with floating-point arithmetic. To support interval arithmetic, several software tools have been developed including interval arithmetic libraries, extended scientific programming languages, and interval-enhanced compilers. The main disadvantage of these software tools is their speed, since interval operations are implemented using function calls. In this paper, compiler support for interval arithmetic is investigated. In particular, the performance benefits of having the compiler inline interval operations to eliminate function call overhead is researched. Interval operations are inlined with the GNU gcc compiler and the performance of interval arithmetic is evaluated on a superscalar architecture. To implement interval operations with compiler support, the compiler produces sequences of instructions that use existing floating point hardware. Simulation results show that the compiler implementation of interval arithmetic is approximately 4 to 5 times faster than a functionally equivalent interval arithmetic software implementation with function call overhead and approximately 1.2 to 1.5 times slower than a dedicated interval arithmetic hardware implementation.     

Numerical techniques for finding equilibrium in von Neumann’s model

Numerical methods for finding an equilibrium position in von Neumann’s multisector economy model are proposed. They can be implemented using computers with floating-point arithmetic. The proposed methods are based on reducing the problem to solving the corresponding matrix games.     

A direct variable step block multistep method for solving general third-order ODEs

This paper discusses a direct three-point implicit block multistep method for direct solution of the general third-order initial value problems of ordinary differential equations using variable step size. The method is based on a pair of explicit and implicit of Adams type formulas which are implemented in PE(CE) ^t mode and in order to avoid calculating divided difference and integration coefficients all the coefficients are stored in the code. The method approximates the numerical solution at three equally spaced points simultaneously. The Gauss Seidel approach is used for the implementation of the proposed method. The local truncation error of the proposed scheme is studied. Numerical examples are given to illustrate the efficiency of the method.     

一类带有差分扰动项的显式线性多步法的讨论

一、方法的形成 求解常微分程初值问题 y′=f(x,y),y(a)= y_0,x∈[a b).(1.0)一般形式的显式k阶线性多步法表成(见[3]):     

解Stiff常微分方程组初值问题的线性隐式方法

对于Stiff常微分方程组初值问题的数值解,人们为了保证数值解过程误差传播的有界性,经常使用的方法之一是隐式的线性多步法.而在解由隐式线性多步法所产生的非线性方程组时,总是采用Newton-Raphson迭代方法.为此就要给出适当的预估式和计算     

Precise evaluation of a polynomial at a point given in staggered correction format

The problem of the evaluation in floating-point arithmetic of a polynomial with floating-point coefficients at a point which is a finite sum of floating-point numbers is studied. The solution is obtained as an infinite convergent series of floating-point numbers. The algorithm requires a precise scalar product, but this can always be implemented by software in a high-level language without assembly language routines as we indicate. A convergence result is proved under a very weak restriction on the size of the degree of the polynomial in terms of the unit roundoff u; roughly speaking, the degree should not be larger than the square root of (1 + u)(2u). Even in the particular case when the point at which to evaluate the polynomial reduces to one floating-point number, we find a new simplified algorithm among the whole family that the preceding convergence result allows.

This problem occurs, among others, in the convergence of the Newton method to some real root of the given polynomial p. If we simply use the Horner scheme to evaluate the polynomial p in a neighbourhood of the root, in some cases the evaluation will contain no correct digits and will prevent us from getting convergence even to machine accuracy. The convergence of iterative methods, among which the Newton method, with added perturbations was the central theme of my talk given at the ICCAM'92. The second part will appear in a forthcoming paper. These added perturbations can represent for example forward or backward errors occurring in finite-precision computations.

The problem discussed here appears in validating some hypotheses of these general convergence results (see the forthcoming paper).