AN ASYMPTOTICALLY EXACT STOPPING RULE FOR THE NUMERICAL COMPUTATION OF THE LYAPUNOV SPECTRUM

It is in general not possible to analytically compute the Lyapunov spe ctrum of a given dynamical system. This has been achieved for a few sp ecial cases only. Therefore, numerical algorithms have been devised fo r this task. However, one major drawback of these numerical algorithms is their lack of stopping rules. In this paper, an asymptotically exa ct stopping rule is proposed to alleviate this shortcoming while compu ting the Lyapunov spectrum of linear discrete-time random dynamical sy stems (i.e., linear systems with random parameters). The proposed stop ping rule provides an estimate of the least number of iterations, for which the probability of incurring a prescribed error, in the numerica l computation of the Lyapunov spectrum, is minimized. It exploits simp le upper bounds on the Lyapunov exponents, along with some results fro m finite state Markov chains. The accuracy of the stopping rule, and t he computational load, is proportional to the tightness of the bound. In fact, a series of increasingly tighter bounds are proposed, yieldin g an asymptotically exact stopping rule for the tightest one. It is de monstrated via an example, that the proposed stopping rule is applicab le to nonlinear dynamics as well. Copyright (C) 1996 Elsevier Science Ltd