Error estimates for Miller's algorithm

Summary A rigorous error analysis is given of both truncation and rounding errors in Miller's algorithm for three-term scalar recursions and 2×2 matrix-vector recursions. The error bounds are shown to be very realistic and this will be supported by examples. The results are generalized to recursions of higher order.     

Ein verallgemeinerter Jacobi-Perron-Algorithmus zur Reduktion linearer Differenzengleichungssysteme

This paper describes a generalized Jacobi-Perron-algorithm for the reduction of first order linear vector recursions. The method is applicable to a wide class of difference equations. As an example we consider Poincaré-Perron type vector recursions.

     

On Moments of Folded and Truncated Multivariate Normal Distributions

Recurrence relations for integrals that involve the density of multivariate normal distributions are developed. These recursions allow fast computation of the moments of folded and truncated multivariate normal distributions. Besides being numerically efficient, the proposed recursions also allow us to obtain explicit expressions of low-order moments of folded and truncated multivariate normal distributions. Supplementary material for this article is available online.     

Extension du filtre de Chandrasekhar au cas des modèles espace d'état périodiques

This Note extends the Chandrasekhar-type recursions due to Morf, Sidhu, and Kailath (1974) to the case of periodic time-varying state-space models. We show that the S-lagged increments of the one-step prediction error covariance satisfy certain recursions from which we derive some algorithms for linear least squares estimation for periodic state-space models. The proposed recursions have potential computational advantages over the Kalman Filter and, in particular, the periodic Riccati difference equation. To cite this article: A. Aknouche, F. Hamdi, C. R. Acad. Sci. Paris, Ser. I 346 (2008).     

Applying the Thorne-Kishino-Felsenstein model to sequence evolution on a star-shaped tree

Stochastic models that allow site substitutions, insertions, and deletions provide a useful framework for a statistical approach to DNA sequence evolution. Such a model, and recursions to calculate the probability of evolving two sequences, have been known for almost a decade. In this paper we show how the pairwise recursions can be generalised to a three-sequence tree, and more generally to an r-sequence star-shaped tree.     

Composition of recursions and nonlinear complexity of periodic binary sequences

We investigate further the new approach towards the classification of periodic binary sequences into nonlinear complexity classes that commenced in the paper by Petrides and Mykkeltveit (Proceedings of SETA’06 international conference on sequences and their applications, 2006). Nonlinear complexity was first introduced by Jansen (Investigations on nonlinear streamcipher systems: construction and evaluation methods, PhD thesis, 1989) and several attempts have since been made to make it of more practical cryptographic interest. In this direction, we will follow with this article. In particular we perform composition of the recursions found in the (2006) article which are related to nonlinear complexity, and prove some of its missing results. Studying the properties of the composition operation for a certain type of recursions is an alternative to study all possible recursions, as required for completing the above mentioned classification. A complete classification will allow, amongst other things, construction of statistical tests to assess the cryptographic strength of binary sequences used in stream ciphers.     

The Schur algorithm and its applications

The Schur algorithm and its time-domain counterpart, the fast Cholseky recursions, are some efficient signal processing algorithms which are well adapted to the study of inverse scattering problems. These algorithms use a layer stripping approach to reconstruct a lossless scattering medium described by symmetric two-component wave equations which model the interaction of right and left propagating waves. In this paper, the Schur and fast Chokesky recursions are presented and are used to study several inverse problems such as the reconstruction of nonuniform lossless transmission lines, the inverse problem for a layered acoustic medium, and the linear least-squares estimation of stationary stochastic processes. The inverse scattering problem for asymmetric two-component wave equations corresponding to lossy media is also examined and solved by using two coupled sets of Schur recursions. This procedure is then applied to the inverse problem for lossy transmission lines.The work of this author was supported by the Exxon Education FoundationThe work of this author was supported by the Air Force Office of Scientific Research under Grant AFOSR-82-0135A.     

Construction of new generalizations of Wynn’s epsilon and rho algorithm by solving finite difference equations in the transformation order

We construct new sequence transformations based on Wynn’s epsilon and rho algorithms. The recursions of the new algorithms include the recursions of Wynn’s epsilon and rho algorithm and of Osada’s generalized rho algorithm as special cases. We demonstrate the performance of our algorithms numerically by applying them to some linearly and logarithmically convergent sequences as well as some divergent series.

     

Stability of ZakianI MN recursions for linear delay differential equations

Long sequences of linear delay differential equations (DDEs) frequently occur in the design of control systems with delays using iterative-numerical methods, such as the method of inequalities. ZakianI _MN recursions for DDEs are suitable for solving this class of problems, since they are reliable and provide results to the desired accuracy, economically even if the systems are stiff. This paper investigates the numerical stability property of theI _MN recursions with respect to Barwell's concept ofP-stability. The result shows that the recursions using full gradeI _MN approximants areP-stable if, and only if,N−2≤M≤N−1.     

Finding efficient recursions for risk aggregation by computer algebra

We derive recursions for the probability distribution of random sums by computer algebra. Unlike the well-known Panjer-type recursions, they are of finite order and thus allow for computation in linear time. This efficiency is bought by the assumption that the probability generating function of the claim size be algebraic. The probability generating function of the claim number is supposed to be from the rather general class of D$D$-finite functions.     

Two-boundary lattice paths and parking functions

We describe an involution on a set of sequences associated with lattice paths with north or east steps constrained to lie between two arbitrary boundaries. This involution yields recursions (from which determinantal formulas can be derived) for the number and area enumerator of such paths. An analogous involution can be defined for parking functions with arbitrary lower and upper bounds. From this involution, we obtained determinantal formulas for the number and sum enumerator of such parking functions. For parking functions, there is an alternate combinatorial inclusion–exclusion approach. The recursions also yield Appell relations. In certain special cases, these Appell relations can be converted into rational or algebraic generating functions.     

Approximations to -, di- and tri-logarithms

We propose hypergeometric constructions of simultaneous approximations to polylogarithms. These approximations suit for computing the values of polylogarithms and satisfy 4-term Apéry-like (polynomial) recursions.     

A programming technique for recursive procedures

A programming technique is described for ALGOL-like recursive procedures in which parameters and local variables are replaced by variables global to the recursive procedure and declared in a surrounding non-recursive procedure. The stack and time required for execution of a variety of recursive procedures has been determined in the languages ALGOL 60, CORAL 66 and ALGOL 68 both when programmed using this technique and when using parameters. Detailed results are presented for the Ackermann function and for tree manipulation.The global technique gives considerable savings in stack for all recursions investigated. For call-dominated recursions the technique speeds up the execution time in ALGOL 60 and CORAL 66 by about 25%. In ALGOL 68 the parameterless recursive procedure must be declared in the closed-clause which forms the particular-program rather than in a surrounding procedure in order to achieve a similar improvement in execution time.     

Recursive relations for block Hankel and Toeplitz systems part II: Dual recursions

The recursive relations given in Part I of this report can be interpreted as recursions for the denominators of matrix Padé approximants. In this part we shall give dual relations for the corresponding numerators and residuals.     

The kernel method and systems of functional equations with several conditions

We generalize the kernel method to equation systems in which the number of unknowns is allowed to exceed the number of equations. With this generalization, we derive the generating functions for several kinds of sequences and generating trees whose recursions are dependent on the parity of the indices.     

灯笼图的可定向嵌入亏格分布

本文主要利用联树法研究了图的亏格多项式,得到了一类新图(灯笼图)的嵌入亏格分布.证明了灯笼图和偶梯图的亏格分布具有相同的递推关系,从而得到了灯笼图的嵌入亏格分布的精确解.     

Cybernetic causality: A unitary theory of causal recursion in natural and social systems

The phenomena connected with non-linear difference and differential equations are approached from a unifying point of view, offered by the general concept of causal recursion (Sections 1 and 2). After a short discussion of nilpotent causal recursions (Section 3), the properties of full causal recursions near or steadily developing states are considered in detail (Section 4). In the general case of causal recursion, a theorem based on a differential-geometric argument is proved concerning the convergence of trajectories, and an exhaustive classification of systems having causal recursion is obtained (Section 5). It gives, among some other things, a mathematical foundation to the concept of a self-steering system (as distinguished from that of a self-regulating system), applied in recent sociocybernetic analyses.     

Exact bounds on epsilon processes

In this paper we show that the lengths of the approximating processes in epsilon substitution method are calculable by ordinal recursions in an optimal way.     

Regular variation of order 1 nonlinear AR-ARCH models

We prove both geometric ergodicity and regular variation of the stationary distribution for a class of nonlinear stochastic recursions that includes nonlinear AR-ARCH models of order 1. The Lyapounov exponent for the model, the index of regular variation and the spectral measure for the regular variation all are characterized by a simple two-state Markov chain.     

Rota’s umbral calculus and recursions

Umbral Calculus can provide exact solutions to a wide range of linear recursions. We summarize the relevant theory and give a variety of examples from combinatorics in one, two and three variables.Dedicated to the Memory of Gian-Carlo Rota