An asymptotically exact stopping rule for the numerical computation of the Lyapunov spectrum

It is in general not possible to analytically compute the Lyapunov spectrum of a given dynamical system. This has been achieved for a few special cases only. Therefore, numerical algorithms have been devised for this task. However, one major drawback of these numerical algorithms is their lack of stopping rules. In this paper, an asymptotically exact stopping rule is proposed to alleviate this shortcoming while computing the Lyapunov spectrum of linear discrete-time random dynamical systems (i.e., linear systems with random parameters). The proposed stopping rule provides an estimate of the least number of iterations, for which the probability of incurring a prescribed error, in the numerical computation of the Lyapunov spectrum, is minimized. It exploits simple upper bounds on the Lyapunov exponents, along with some results from finite state Markov chains. The accuracy of the stopping rule, and the computational load, is proportional to the tightness of the bound. In fact, a series of increasingly tighter bounds are proposed, yielding an asymptotically exact stopping rule for the tightest one. It is demonstrated via an example, that the proposed stopping rule is applicable to nonlinear dynamics as well.