A note on comparison theorems for nonnegative matrices

Summary In a recent paper, [4], Csordas and Varga have unified and extended earlier theorems, of Varga in [10] and Wonicki in [11], on the comparison of the asymptotic rates of convergence of two iteration matrices induced by two regular splittings. The main purpose of this note is to show a connection between the Csordas-Varga paper and a paper by Beauwens, [1], in which a comparison theorem is developed for the asymptotic rate of convergence of two nonnegative iteration matrices induced by two splittings which are not necessarily regular. Monotonic norms already used in [1] play an important role in our work here.Research supported in part by NSF grant number DMS-8400879     

Convergence of the shifted algorithm for unitary Hessenberg matrices

This paper shows that for unitary Hessenberg matrices the algorithm, with (an exceptional initial-value modification of) the Wilkinson shift, gives global convergence; moreover, the asymptotic rate of convergence is at least cubic, higher than that which can be shown to be quadratic only for Hermitian tridiagonal matrices, under no further assumption. A general mixed shift strategy with global convergence and cubic rates is also presented.

     

Langevin-Type Models I: Diffusions with Given Stationary Distributions and their Discretizations*

We describe algorithms for estimating a given measure known up to a constant of proportionality, based on a large class of diffusions (extending the Langevin model) for which is invariant. We show that under weak conditions one can choose from this class in such a way that the diffusions converge at exponential rate to , and one can even ensure that convergence is independent of the starting point of the algorithm. When convergence is less than exponential we show that it is often polynomial at verifiable rates. We then consider methods of discretizing the diffusion in time, and find methods which inherit the convergence rates of the continuous time process. These contrast with the behavior of the naive or Euler discretization, which can behave badly even in simple cases. Our results are described in detail in one dimension only, although extensions to higher dimensions are also briefly described.     

Asymptotisches Verhalten und Konvergenzbeschleunigung von Iterationsfolgen

Summary The effectivity of iterative numerical methods depends on the rate of convergence. In this note general procedures to accelerate the convergence of finite-dimensional stationary one-step-methods (fixed point methods) by extrapolation methods are studied. In this connection the investigation of the asymptotic behaviour of the sequences is fundamental. Differentiability and contractivity qualities supposed in the following an asymptotic expansion for such iterative sequences is proved. Neglecting the remainder the expansion fulfils a linear difference equation with constant coefficients. Wynn's -algorithm work off this expansion term by term, and the attainable acceleration can be exactly estimated. Skelboe's convergence statement is refuted. First test results demonstrate the advantage of acceleration methods.

     

Large deviations behavior of counting processes and their inverses

We show, under regularity conditions, that a counting process satisfies a large deviations principle in or the Gärtner-Ellis condition (convergence of the normalized logarithmic moment generating functions) if and only if its inverse process does. We show, again under regularity conditions, that embedded regenerative structure is sufficient for the counting process or its inverse process to have exponential asymptotics, and thus satisfy the Gärtner-Ellis condition. These results help characterize the small-tail asymptotic behavior of steady-state distributions in queueing models, e.g., the waiting time, workload and queue length.     

On the convergence of the exponential multiplier method for convex programming

In this paper, we analyze the exponential method of multipliers for convex constrained minimization problems, which operates like the usual Augmented Lagrangian method, except that it uses an exponential penalty function in place of the usual quadratic. We also analyze a dual counterpart, the entropy minimization algorithm, which operates like the proximal minimization algorithm, except that it uses a logarithmic/entropy proximal term in place of a quadratic. We strengthen substantially the available convergence results for these methods, and we derive the convergence rate of these methods when applied to linear programs.Research supported by the National Science Foundation under Grant DDM-8903385, and the Army Research Office under Grant DAAL03-86-K-0171.     

Asymptotic Approximation with a Sequence of Positive Linear Operators

The rate of pointwise convergence for a sequence of positive linear operators L_n approximating continuous functions on a finite interval is considered. The complete asymptotic expansion for the operators L_n as n tends to infinity is presented. It turns out that the central factorial numbers of first and second kind play an important role in the asymptotic expansion. The present work is an extension to that reported by Ivan and Raa.     

Convergence rates to the discrete travelling wave for relaxation schemes

This paper is concerned with the asymptotic convergence of numerical solutions toward discrete travelling waves for a class of relaxation numerical schemes, approximating the scalar conservation law. It is shown that if the initial perturbations possess some algebraic decay in space, then the numerical solutions converge to the discrete travelling wave at a corresponding algebraic rate in time, provided the sums of the initial perturbations for the -component equal zero. A polynomially weighted norm on the perturbation of the discrete travelling wave and a technical energy method are applied to obtain the asymptotic convergence rate.

     

Convergence of the unitary algorithm with a unimodular Wilkinson shift

In applying the algorithm to compute the eigenvalues of a unitary Hessenberg matrix, a projected Wilkinson shift of unit modulus is proposed and proved to give global convergence with (at least) a quadratic asymptotic rate for the iteration. Experimental testing demonstrates that the unimodular shift produces more efficient numerical convergence.

     

On the convergence of averages of mixing sequences

We construct an absolutely regular stationary random sequence which is an instantaneous bounded function of an aperiodic recurrent Markov chain with a countable state space, such that the large deviation principle fails for the arithmetic means of the sequence, while the exponential convergence holds. We also show that exponential convergence holds for the arithmetic means of a vector valued strictly stationary bounded -mixing sequence.     

Entropy and Convergence on Compact Groups

We investigate the behaviour of the entropy of convolutions of independent random variables on compact groups. We provide an explicit exponential bound on the rate of convergence of entropy to its maximum. Equivalently, this proves convergence of the density to uniformity, in the sense of Kullback–Leibler. We prove that this convergence lies strictly between uniform convergence of densities (as investigated by Shlosman and Major), and weak convergence (the sense of the classical Ito–Kawada theorem). In fact it lies between convergence in L ¹⁺ and convergence in L ¹.     

Different capacities of a digraph

Sperner product is the natural generalization of co-normal product to digraphs. For every class of digraphs closed under Sperner product, the cardinality of the largest subgraph from the given class, contained as an induced subgraph in the co-normal powers of a graphG, has an exponential growth. The corresponding asymptotic exponent is the capacity ofG with respect to said class of digraphs. We derive upper and lower bounds for these capacities for various classes of digraphs, and analyze the conditions under which they are tight.     

Asymptotic agreement of moments and higher order contraction in the Burgers equation

The purpose of this paper is to investigate the relation between the moments and the asymptotic behavior of solutions to the Burgers equation. The Burgers equation is a special nonlinear problem that turns into a linear one after the Cole-Hopf transformation. Our asymptotic analysis depends on this transformation. In this paper an asymptotic approximate solution is constructed, which is given by the inverse Cole-Hopf transformation of a summation of n heat kernels. The k-th order moments of the exact and the approximate solution are contracting with order in Lp-norm as t→∞. This asymptotics indicates that the convergence order is increased by a similarity scale whenever the order of controlled moments is increased by one. The theoretical asymptotic convergence orders are tested numerically.     

On the convergence of an algorithm for discreteL p approximation

Summary The convergence properties of an algorithm for discreteL _p approximation (1p<2) that has been considered by several authors are studied. In particular, it is shown that for 1<p<2 the method converges (with a suitably close starting value) to the best approximation at a geometric rate with asymptotic convergence constant 2-p. A similar result holds forp=1 if the best approximation is unique. However, in this case the convergence constant depends on the function to be approximated.     

Inexact Inverse Iteration for Generalized Eigenvalue Problems

In this paper, we study an inexact inverse iteration with inner-outer iterations for solving the generalized eigenvalu problem Ax = Bx, and analyze how the accuracy in the inner iterations affects the convergence of the outer iterations. By considering a special stopping criterion depending on a threshold parameter, we show that the outer iteration converges linearly with the inner threshold parameter as the convergence rate. We also discuss the total amount of work and asymptotic equivalence between this stopping criterion and a more standard one. Numerical examples are given to illustrate the theoretical results.     

L∞ convergence of interpolation and associated product integration for exponential weights

We investigate convergence in a weighted L_∞ norm of Hermite–Fejér, Hermite, and Grünwald interpolations at zeros of orthogonal polynomials with respect to exponential weights such as Freud, Erd s, and exponential weight on (−1,1). Convergence of product integration rules induced by the various approximation processes is deduced. We also give more precise weight conditions for convergence of interpolations with respect to above three types of weights, respectively.     

Stability of nonlinear regime-switching jump diffusion

Motivated by networked systems, stochastic control, optimization, and a wide variety of applications, this work is devoted to systems of switching jump diffusions. Treating such nonlinear systems, we focus on stability issues. One of the distinct features considered here is that the switching process depends on the jump diffusions. First asymptotic stability in the large is obtained. Then the study on exponential p$p$-stability is carried out. Connection between almost surely exponential stability and exponential p$p$-stability is exploited. Also presented are smooth-dependence on the initial data. Using the smooth-dependence, necessary conditions for exponential p$p$-stability are derived. Then criteria for asymptotic stability in distribution are provided. A couple of examples are given to illustrate our results.     

Estimating drift parameters in a fractional Ornstein Uhlenbeck process with periodic mean

We construct a least squares estimator for the drift parameters of a fractional Ornstein Uhlenbeck process with periodic mean function and long range dependence. For this estimator we prove consistency and asymptotic normality. In contrast to the classical fractional Ornstein Uhlenbeck process without periodic mean function the rate of convergence is slower depending on the Hurst parameter H, namely \(n^{1-H}\).     

Uniform approximation of solutions of nonlinear parabolic problems in perforated domains

We investigate the behavior of a remainder of an asymptotic expansion for solutions of a quasi-linear parabolic Cauchy-Dirichlet problem in a sequence of domains with fine-grained boundary. By using a modification of an asymptotic expansion and new pointwise estimates for a solution of a model problem, we prove the uniform convergence of the remainder to zero.__________Translated from Ukrainskyi Matematychnyi Zhurnal, Vol. 56, No. 9, pp. 1244–1258, September, 2004.