A note on contractivity in the numerical solution of initial value problems

This paper concerns the stability analysis of numerical methods for approximating the solutions to (stiff) initial value problems. Our analysis includes the case of (nonlinear) systems of differential equations that are essentially more general than the classical test equationU=U, with a complex constant.We explore the relation between two stability concepts, viz. the concepts of contractivity and weak contractivity.General Runge-Kutta methods, one-stage Rosenbrock methods and a notable rational Runge-Kutta method are analysed in some detail.     

On the Contractivity and Asymptotic Stability of Systems of Delay Differential Equations of Neutral Type

In this paper we investigate both the contractivity and the asymptotic stability of the solutions of linear systems of delay differential equations of neutral type (NDDEs) of the form y(t) = Ly(t) + M(t)y(t – (t)) + N(t)y(t – (t)). Asymptotic stability properties of numerical methods applied to NDDEs have been recently studied by numerous authors. In particular, most of the obtained results refer to the constant coefficient version of the previous system and are based on algebraic analysis of the associated characteristic polynomials. In this work, instead, we play on the contractivity properties of the solutions and determine sufficient conditions for the asymptotic stability of the zero solution by considering a suitable reformulation of the given system. Furthermore, a class of numerical methods preserving the above-mentioned stability properties is also presented.     

Monotonicity and boundedness in implicit Runge-Kutta methods

Summary This paper concerns the analysis of implicit Runge-Kutta methods for approximating the solutions to stiff initial value problems. The analysis includes the case of (nonlinear) systems of differential equations that are essentially more general than the classical test equationU=U (with a complex constant). The properties of monotonicity and boundedness of a method refer to specific moderate rates of growth of the approximations during the numerical calculations. This paper provides necessary conditions for these properties by using the important concept of algebraic stability (introduced by Burrage, Butcher and by Crouzeix). These properties will also be related to the concept of contractivity (B-stability) and to a weakened version of contractivity.     

Quadrature formulas with positive weights

Recent developments in the theory of stability or contractivity of numerical methods for solving ordinary differential equations (see for instance [4], [5], [8]) have renewed the interest for the study of quadrature formulas with positive weights. Nørsett-Wanner [8] and Burrage [2], [3] have given characterisation of such quadrature formulas of order 2m–2 or 2m–3. In this paper we extend these investigations to the case of formulas of order 2m–4 and then to the case where the order is 2m–7. Finally we use these results to characterise the algebraically stable methods out of a 12-parameter family of implicit Runge-Kutta methods of order 2m–4.     

On the Eigenvalues and Eigenfunctions of the Sturm--Liouville Operator with a Singular Potential

In this paper we consider the Sturm--Liouville operators generated by the differential expression -y+q(x)y and by Dirichlet boundary conditions on the closed interval [0,]. Here q(x) is a distribution of first order,, i.e., q(x)dx L ₂[0,]. Asymptotic formulas for the eigenvalues and eigenfunctions of such operators which depend on the smoothness degree of q(x) are obtained.     

Heat equation with degeneration in Holder and Slobodetskii spaces

We study initial-boundary value problems for the heat equation in which heat conductivity ²(x) may depend on the space variablex ⁺; the nonnegative function(x) is allowed to tend to infinity (respectively, zero) asx + (respectively,x +0). We prove that these problems are well posed and examine the smoothness of solutions. It is shown that criteria for smoothness of the solutions can be stated in terms of certain functionals, namely, the Hölder constant (for Hölder spaces) and the generalized Hölder constant (for Slobodetskii spaces).Translated fromMatematicheskie Zametki, Vol. 58, No. 2, pp. 189–203, August, 1995.     

Some propositions related to a dilation theorem of W. Benz

Summary This paper begins with another proof of a theorem of W. Benz [2] concerning dilations in normed linear spaces. Our proof motivates several questions which are addressed thereafter. For instance it is shown that, ifI is an open interval in ,: I ⁿ , is continuously differentiable and there exista ₁,...,a _n I such that {(a ₁,...,(a _n )} is linearly independent, then {(t): t I} contains a Hamel basis for ⁿ over .     

Global optimization and stochastic differential equations

Let ⁿ be then-dimensional real Euclidean space,x=(x ₁,x ₂, ...,x _n)^{T n} , and letf: ⁿ R be a real-valued function. We consider the problem of finding the global minimizers off. A new method to compute numerically the global minimizers by following the paths of a system of stochastic differential equations is proposed. This method is motivated by quantum mechanics. Some numerical experience on a set of test problems is presented. The method compares favorably with other existing methods for global optimization.This research has been supported by the European Research Office of the US Army under Contract No. DAJA-37-81-C-0740.The third author gratefully acknowledges Prof. A. Rinnooy Kan for bringing to his attention Ref. 4.     

A variable dimension algorithm with the Dantzig-Wolfe decomposition for structured stationary point problems

Given a set ofR ⁿ and a functionf from intoR ⁿ we consider a problem of finding a pointx ^* in such that(x–x ^*) ^t f(x ^*)0 holds for every pointx in. This problem is called the stationary point problem and the pointx ^* is called a stationary point. We present a variable dimension algorithm for solving the stationary point problem with an affine functionf on a polytope defined by constraints of linear equations and inequalities. We propose a system of equations whose solution set contains a piecewise linear path connecting a trivial starting point in with a stationary point. The path can be followed by solving a series of linear programs which inherit the structure of constraints of. The linear programs are solved efficiently with the Dantzig-Wolfe decomposition method by exploiting fully the structure.Part of this research was carried out when the first author was supported by the Center for Economic Research, Tilburg University, The Netherlands and the third author was supported by the Alexander von Humboldt-Foundation, Federal Republic of Germany.     

Extremal Eigenvalues of the Laplacian in a Conformal Class of Metrics: The `Conformal Spectrum'

Let M be a compact connected manifold of dimension n endowed witha conformal class C ofRiemannian metrics of volume one. For any integer k 0, we consider the conformal invariant _k ^c (C) defined as the supremum of the k-th eigenvalue _k (g) of the Laplace–Beltrami operator _g , where g runs over C.First, we give a sharp universal lower bound for _k ^c (C) extending to all k a result obtained by Friedlander andNadirashvili for k = 1. Then, we show that the sequence \{ _k ^c (C)\}, that we call `conformal spectrum',is strictly increasing and satisfies, k 0, _k+1 ^c (C) ^n/2– _k ^c (C) ^n/2 n ^n/2 _n , where _n is the volume of the n-dimensionalstandard sphere.When M is an orientable surface of genus , we also considerthe supremum _k ^top()of _k (g) over theset of all the area one Riemannian metrics on M, and study thebehavior of _k ^top() in terms of .     

Existence and construction of Δ1-splines of class Ck on a three-directional mesh

Let ^* be the equilateral triangulation of the plane and let ₁ ^* be the equilateral triangle formed by four triangles of ^*. We study the space of piecewise polynomial functions in C ^k (R ²) with support ₁ ^*, having a sufficiently high degree n and which are invariant with respect to the group of symmetries of ₁ ^*. Such splines are called ₁ ^*-splines. We first compute the dimension of this space in function of n and k. Then, for any fixed k0, we prove the existence of ₁ ^*-splines of class C ^k and minimal degree, but these splines are not unique. Finally, we describe an algorithm computing the Bernstein–Bézier coefficients of these splines.     

Circle contractive linear multistep methods

Linear multistep methods satisfying a non-linear circle contractivity condition when the step-ratios are less than some 1+,>0, are shown to exist for any order. Methods with formulas of order 1 to 12 are given.     

On the relation between stability and contractivity

This paper concerns the rate of growth of numerical approximations obtained by one-step methods for solving linear stiff initial value problems. For some of these methods weak stability with respect to arbitrary norms is shown to be equivalent to contractivity. This kind of stability is also proved to entail a barrierp1 for the order of accuracyp within a broad class of methods, including general Runge-Kutta methods withm1 stages.Dedicated to Professor Germund Dahlquist on the occasion of his sixtieth birthday.     

Absolute monotonicity of polynomials occurring in the numerical solution of initial value problems

Summary This paper deals with polynomial approximations ø(x) to the exponential function exp(x) related to numerical procedures for solving initial value problems. Motivated by positivity and contractivity requirements imposed on these numerical procedures we study the smallest negative argument, denoted by –R(ø), at which ø is absolutely monotonic. For given integersp1,m1 we determine the maximum ofR(ø) when ø varies over the class of all polynomials of a degree m with (forx0).     

Solving sparse symmetric definite quadraticλ-matrix problems

This paper describes a method for computing all the eigenvalues in a user supplied interval [a,b], and their associated eigenvectors, of the symmetric definite quadratic-matrix problem (M ²+C+K)x=0, where the matrices ar sufficiently sparse that methods based on similarity transformations are inappropriate. Only the triangular factorization of onen ×n matrix need be computed.Research sponsored in part by the Mathematics Department, University of Linköping, Sweden, and the Applied Mathematical Sciences Research Program, Office of Energy Research, U.S. Department of Energy under contract W-7405-eng-26 with the Union Carbide Corporation.     

Maximal order for quadratures usingn evaluations

The problem is to find approximationsI (f; h) to the integralI(f; h)= ₀ ^h f. Such an approximation has local orderp ifI(f; h)–I (f; h)=O(h ^p ) ash0. Let(n) denote the maximal local order possible for a method usingn evaluations of a function or its derivatives. We show that (n)=2n+1 if the information used is Hermitian. This is conjectured to be true in general. The conjecture is established for all methods using three or fewer evaluations.This research was supported in part by the National Science Foundation under Grant MCS75-222-55 and the Office of Naval Research under Contract N00014-76-C-0370, NR 044-422. Numerical results reported in this paper were obtained through the computing facilities of the University of Maryland.     

Finite population corrections for ranked set sampling

Ranked set sampling (RSS) for estimating a population mean is studied when sampling is without replacement from a completely general finite populationx=(x ₁,x ₂,...,x _N ). Explicit expressions are obtained for the variance of the RSS estimator and for its precision relative to that of simple random sampling without replacement. The critical term in these expressions involves a quantity =(x–)(x–) where is anN × N matrix whose entries are functions of the population sizeN and the set-sizem, but where does not depend on the population valuesx. A computer program is given to calculate for arbitraryN andm. When the population follows a linear (resp., quadratic) trend, then is a polynomial inN of degree 2m+2 (resp., 2m+4). The coefficients of these polynomials are evaluated to yield explicit expressions for the variance and the relative precision of for these populations. Unlike the case of sampling from an infinite population, here the relative precision depends upon the number of replications of the set sizem.Prepared with partial support from the Statistical Analysis and Computing Branch. Environmental Statistics and Information Division, Office of Policy, Planning, and Evaluation, United States Environmental Protection Agency, Washington, DC under a Cooperative Agreement Number CR-821531. The contents have not been subjected to Agency review and therefore do not necessarily reflect the views of the Agency and no official endorsement should be inferred.     

On nonconvex perturbations of maximal monotone differential inclusions

The paper is concerned with the evolution inclusionxAx+F(t,x), whereA generates a contractive semigroup andF is a lower semicontinuous multifunction. Constructing a suitable directionally continuous selection fromF, we prove the existence of solutions on a closed domain and the connectedness of the set of trajectories.     

A decomposition for the exponential dispersion model generated by the invariant measure on the hyperboloid

For = ₀, ₁, ₂) andx=(x₀, x₁, x₂) in R³, define [,x] = ₀ x ₀ – ₁ x ₁ – ₂ x ₂,C = {x³:x ₀ > 0 and [x, x]>0},R(x)=([x, x]) ^1/2 forx inC andH ₁={xC: x₀>0,R(x)=1}. Define the measure onH ₁ such that if is inC and =R(), then exp (–[,x])(dx = ( exp )^–1. Therefore, is invariant under the action ofSO (1, 2), the connected component ofO(1, 2) containing the identity. We first prove that there exists a positive measure in ³ such that its Laplace transform is ( exp )^– if and only if >1. Finally, for 1 and inC, denotingP(,)(dx) = ( exp )^– exp (–[,x])(dx, we show that ifY ₀,...,Y _n aren+1 independent variables with densityP(,),j=0,...,n and ifS _k =X ₀ + ... +X _k andQ _k =R(S _k) –R(S _k–1) –R(Y _k),k=1,...,n, then then+1 statisticsD _n = [/,S _k ] –R _{k – 1} ),Q ₁,...,Q _n are independent random variables with the exponential () or gamma (1,1/) distribution.This research has been partially funded by NSERC Grant A8947.     

Nonparametric Estimation of a Conditional Quantile for α-Mixing Processes

Let (X_i,Y _i) be a set of observations form a stationary -mixing process and (x) be the conditional -th quantile of Y given X = x. Several authors considered nonparametric estimation of (x) in the i.i.d. setting. Assuming the smoothness of FF(x), we estimate it by local polynomial fitting and prove the asymptotic normality and the uniform convergence.