A new mesh selection strategy for ODEs

In this paper a new mesh selection strategy, based on the conditioning properties of continuous problems, is presented. It turns out to be particularly efficient when approximating solutions of BVPs. The numerical methods used to test the reliability of the strategy are symmetric Linear Multistep Formulae (LMF) used as Boundary Value Methods (BVMs) since they provide a wide choice of methods of arbitrary high order and have similar stability properties to each other. In particular, we shall consider a subclass of such methods, called Top Order Methods (TOMs) (Amodio, 1996; Brugnano and Trigiante, 1995, 1996), to carry out the numerical results on some singular perturbation test problems.     

On the practical value of the notion ofBN-stability

The oldest concept of unconditional stability of numerical integration methods for ordinary differential systems is that ofA-stability. This concept is related to linear systems having constant coefficients and has been introduced by Dahlquist in 1963. More recently, since another contribution of Dahlquist in 1975, there has been much interest in unconditional stability properties of numerical integration methods when applied to non-linear dissipative systems (G-stability,BN-stability,A-contractivity). Various classes of implicit Runge-Kutta methods have already been shown to beBN-stable. However, contrary to the property ofA-stability, when implementing such a method for practical use this unconditional stability property may be lost. The present note clarifies this for a class of diagonally implicit methods and shows at the same time that Rosenbrock's method is notBN-stable.     

Stabile Mehrschichtverfahren für parabolische Evolutionsgleichungen

Summary The line method discussed in [19] is improved by considering several time slices. It is applied to parabolic initial-value problems, and with techniques similar to [16] it is proved that the root conditions of Dahlquist [5] and Widlund [17] are sufficient for stability. Stable methods up to order 6 are given and illustrated by numerical calculations.

Die Arbeit ist im wesentlichen die gekürzte Fassung des zweiten Teils meiner am Lehrstuhl von Prof. G. Hämmerlin angefertigten Dissertation [18]. Über den anderen Teil wurde bereits in [19] berichtet     

The numerical stability of the lattice algorithm for least squares linear prediction problems

The numerical stability of the lattice algorithm for least-squares linear prediction problems is analysed. The lattice algorithm is an orthogonalization method for solving such problems and as such is in principle to be preferred to normal equations approaches. By performing a first-order analysis of the method and comparing the results with perturbation bounds available for least-squares problems, it is argued that the lattice algorithm is stable and in fact comparable in accuracy to other known stable but less efficient methods for least-squares problems.Dedicated to Germund Dahlquist on the occasion of his 60th birthday.This work was partially supported by NSF Grant MCS-8003364 and contracts AFOSR 82-0210, ARO DAAG29-82-K-0082.     

Adams-Type Methods for the Numerical Solution of Stochastic Ordinary Differential Equations

The modelling of many real life phenomena for which either the parameter estimation is difficult, or which are subject to random noisy perturbations, is often carried out by using stochastic ordinary differential equations (SODEs). For this reason, in recent years much attention has been devoted to deriving numerical methods for approximating their solution. In particular, in this paper we consider the use of linear multistep formulae (LMF). Strong order convergence conditions up to order 1 are stated, for both commutative and non-commutative problems. The case of additive noise is further investigated, in order to obtain order improvements. The implementation of the methods is also considered, leading to a predictor-corrector approach. Some numerical tests on problems taken from the literature are also included.     

Thirty years of G-stability

The 1976 paper of G. Dahlquist, [13], has had a wide-ranging impact on our understanding of numerical methods for the solution of stiff differential equation systems. The present paper surveys some of the work of Dahlquist in this area. It also shows how this has led to contributions by other authors. In particular, the paper contains a review of non-linear stability for Runge–Kutta and general linear methods. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65L05, 65L06, 65L20     

On some questions arising in numerical realization of amplitude-phase methods

For computing rapidly oscillating solutions of certain second order differential equations a new version of amplitude-phase methods has recently been proposed in [11]. Error estimates were given to approximate solutions for large arguments in [15]. One of the most important points in these methods is the introduction of Prüfer transformation modified by auxiliary functions. Their appropriate choice makes the methods applicable and efficient. When implementing and applying the methods to practical problems, we face some further questions. In this paper we describe and try to answer them. Efficiency of the methods is confirmed by numerical experiments on concrete problems. This revised version was published online in June 2006 with corrections to the Cover Date.     

A note on unconditionally stable linear multistep methods

It has been shown by Dahlquist [3] that the trapezoidal formula has the smallest truncation error among all linear multistep methods with a certain stability property. It is the purpose of this note to show that a slightly different stability requirement permits methods of higher accuracy.The preparation of this paper was sponsored by the Swedish Technical Research Council.     

On the Convergence of LMF-type Methods for SODEs

In a previous paper [3], some numerical methods for stochastic ordinary differential equations (SODEs), based on Linear Multistep Formulae (LMF), were proposed. Nevertheless, a formal proof for the convergence of such methods is still lacking. We here provide such a proof, based on a matrix formulation of the discrete problem, which allows some more insight in the structure of LMF-type methods for SODEs.     

EFFICIENT SIXTH ORDER P-STABLE METHODS WITH MINIMAL LOCAL TRUNCATION ERROR FOR y"=f(x,y)

1. IntroductionWe consider a class of direct hybrid methods proposed in [11 for solving the second orderinitial value problemy" = f(t,y), y(0),y'(0) given (1.1)The basic method has the formandHere t. = nh and we define t.l.. = t. I aih, i = 1, 2 and n=0,1…     

Numerical detection of instability regions for delay models with delay-dependent parameters

In this paper we are interested in gaining local stability insights about the interior equilibria of delay models arising in biomathematics. The models share the property that the corresponding characteristic equations involve delay-dependent coefficients. The presence of such dependence requires the use of suitable criteria which usually makes the analytical work harder so that numerical techniques must be used. Most existing methods for studying stability switching of equilibria fail when applied to such a class of delay models. To this aim, an efficient criterion for stability switches was recently introduced in [E. Beretta, Y. Kuang, Geometric stability switch criteria in delay differential systems with delay dependent parameters, SIAM J. Math. Anal. 33 (2002) 1144–1165] and extended [E. Beretta, Y. Tang, Extension of a geometric stability switch criterion, Funkcial Ekvac 46(3) (2003) 337–361]. We describe how to numerically detect the instability regions of positive equilibria by using such a criterion, considering both discrete and distributed delay models.     

Parallel implementation of block boundary value methods for ODEs

The parallel solution of initial value problems for ODEs has been the subject of much research in the last thirty years, and different approaches to the problem have been devised. In this paper we examine the parallel methods derived by block boundary value methods (BVMs), recently introduced for approximating Hamiltonian problems. Here we restrict the analysis of the methods when applied to linear problems, since their nonlinear parallel implementation deserves further study. However, for linear problems, the methods can reach a high parallel efficiency.Some of these solvers can also be adapted for approximating continuous two-point boundary value problems. Numerical tests carried out on a distributed memory parallel computer are reported.     

Linearly implicit time discretization for free surface problems

Deeper investigation of time discretization for free surface problems is a widely neglected problem. Many existing approaches use an explicit decoupling which is only conditionally stable. Only few unconditionally stable methods are known, and known methods may suffer from too strong numerical dissipativity. They are also usually of first rder only [1, 9]. We are therefore looking for unconditionally stable, minimally dissipative methods of higher order. Linearly implicit Runge-Kutta (LIRK) methods are a class of one-step methods that require the solution of linear systems in each time step of a nonlinear system. They are well suited for discretized PDEs, e.g. parabolic problems [7]. They have been used successfully to solve the incompressible Navier-Stokes equations [5]. We suggest an adaption of these methods for free surface problems and compare different approximations to the Jacobian matrix needed for such methods. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Differentiable difference approximations for nonlinear initial-value problems.I

This paper deals with the approximation of nonlinear initial-value problems by difference methiods. in the Present part I The basic definitions and concepts are presented and equivalence theorems for stability and continuous convergenc are proved. Here, The differentiability condition (d) and the boundedness condition (Bp) are of fundamental siginificance. the latter is one of the equivalent characterizations of stability. The equivalence theorems for stability and continuous convergence include characterizations by means of locally uniform two-sided Lipschitz conditions and tow-sided discertization error estimates. At the end of part I a generalized of the concept of stable convergence of Dahlquist [2] and Torng [16] is proved to series of equivalent conditions convergence. in part II the above results will yields a series of equivalent conditions for the concepts of weak stability and conditions convergence of certain order. Moreover, further convergence concepts for semi-homogeneous methods will be studied, and hyperbolic and parawbolic example will be treated     

求解具有混合边界条件的拟线性扩散方程的有限元方法的误差估计问题

在M.F.Wheeler的[5]中,对一类拟线性抛物型方程的F.E.M,进行了颇为深入的理论分析。但是,[5]所考虑的方程,其高阶项的系数,尚有某种局限性,以致不能应用于一般的各向异性问题;对于混合边界的情形,也未加讨论。此外,[5]中所涉及的条件也是较强的,如要求解函数u(x,t)∈c~2(Ω×[0,T])等等。 本文对实践中常常遇到的具有第三混合边界条件的一类拟线性扩散问题的F.E.M,在较[5]为弱的条件下,进行了讨论,把有关拟线性问题的误差估计问题归结为某一线性椭圆边值问题F.E.M的误差估计问题。本文的结果是[1]的推广。     

The equivalence ofB-stability andA-stability

It is a well-known result of Dahlquist that the linear (A-stability) and non-linear (G-stability) stability concepts are equivalent for multistep methods in their one-leg formulation. We show to what extent this result also holds for Runge-Kutta methods. Dedicated to Germund Dahlquist on the occasion of his 60th birthday.     

Towards explicit methods for differential algebraic equations

Explicit methods have previously been proposed for parabolic PDEs and for stiff ODEs with widely separated time constants. We discuss ways in which Differential Algebraic Equations (DAEs) might be regularized so that they can be efficiently integrated by explicit methods. The effectiveness of this approach is illustrated for some simple index three problems. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65-L80, 34-04     

Parallelization Strategies for Rollout Algorithms

Rollout algorithms are innovative methods, recently proposed by Bertsekas et al. [3], for solving NP-hard combinatorial optimization problems. The main advantage of these approaches is related to their capability of magnifying the effectiveness of any given heuristic algorithm. However, one of the main limitations of rollout algorithms in solving large-scale problems is represented by their computational complexity. Innovative versions of rollout algorithms, aimed at reducing the computational complexity in sequential environments, have been proposed in our previous work [9]. In this paper, we show that a further reduction can be accomplished by using parallel technologies. Indeed, rollout algorithms have very appealing characteristics that make them suitable for efficient and effective implementations in parallel environments, thus extending their range of relevant practical applications.We propose two strategies for parallelizing rollout algorithms and we analyze their performance by considering a shared-memory paradigm. The computational experiments have been carried out on a SGI Origin 2000 with 8 processors, by considering two classical combinatorial optimization problems. The numerical results show that a good reduction of the execution time can be obtained by exploiting parallel computing systems.     

Expansions of the chromatic polynomial

The chromatic polynomial (or chromial) of a graph was first defined by Birkhoff in 1912, and gives the number of ways of properly colouring the vertices of the graph with any number of colours. A good survey of the basic facts about these polynomials may be found in the article by Read [3].It has recently been noticed that some classical problems of physics can be expressed in terms of chromials, and papers by Nagle [2], Baker [1], Temperley and Lieb [4], are concerned with methods of expanding the chromial for use in such problems. In this note we shall unify, simplify, and generalise their treatments, confining our attention to the theoretical basis of the methods.     

B-spline curve fitting with invasive weed optimization

B-spline curves and surfaces are generally used in computer aided design (CAD), data visualization, virtual reality, surface modeling and many other fields. Especially, data fitting with B-splines is a challenging problem in reverse engineering. In addition to this, B-splines are the most preferred approximating curve because they are very flexible and have powerful mathematical properties and, can represent a large variety of shapes efficiently [1]. The selection of the knots in B-spline approximation has an important and considerable effect on the behavior of the final approximation. Recently, in literature, there has been a considerable attention paid to employing algorithms inspired by natural processes or events to solve optimization problems such as genetic algorithms, simulated annealing, ant colony optimization and particle swarm optimization. Invasive weed optimization (IWO) is a novel optimization method inspired from ecological events and is a phenomenon used in agriculture. In this paper, optimal knots are selected for B-spline curve fitting through invasive weed optimization method. Test functions which are selected from the literature are used to measure performance. Results are compared with other approaches used in B-spline curve fitting such as Lasso, particle swarm optimization, the improved clustering algorithm, genetic algorithms and artificial immune system. The experimental results illustrate that results from IWO are generally better than results from other methods.