×

zbMATH — the first resource for mathematics

Lower and upper bounds for the largest Lyapunov exponent of matrices. (English) Zbl 1281.65154
Summary: We introduce a new approach to evaluate the largest Lyapunov exponent of a family of nonnegative matrices. The method is based on using special positive homogeneous functionals on \(\mathbb R_+^d\), which gives iterative lower and upper bounds for the Lyapunov exponent. They improve previously known bounds and converge to the real value. The rate of convergence is estimated and the efficiency of the algorithm is demonstrated on several problems from applications (in functional analysis, combinatorics, and language theory) and on numerical examples with randomly generated matrices. The method computes the Lyapunov exponent with a prescribed accuracy in relatively high dimensions (up to 60). We generalize this approach to all matrices, not necessarily nonnegative, derive a new universal upper bound for the Lyapunov exponent, and show that a potential similar lower bound does not exist in general.

MSC:
65P99 Numerical problems in dynamical systems
37M25 Computational methods for ergodic theory (approximation of invariant measures, computation of Lyapunov exponents, entropy, etc.)
37D25 Nonuniformly hyperbolic systems (Lyapunov exponents, Pesin theory, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Beyn, W.-J.; Lust, A., A hybrid method for computing Lyapunov exponents, Numer. Math., 113, 357-375, (2009) · Zbl 1178.37117
[2] Blondel, V. D.; Cassaigne, J.; Jungers, R. M., On the number of \(\alpha\)-power-free words for \(2 < \alpha \leqslant 7 / 3\), Theoret. Comput. Sci., 410, 2823-2833, (2009) · Zbl 1173.68046
[3] Blondel, V. D.; Tsitsiklis, J. N., Approximating the spectral radius of sets of matrices in the MAX-algebra is NP-hard, IEEE Trans. Automat. Control, 45, 9, 1762-1765, (2000) · Zbl 0990.93073
[4] Boyd, S.; Vandenberghe, L., Semidefinite programming, SIAM Rev., 38, 49-95, (1996) · Zbl 0845.65023
[5] Cicone, A.; Guglielmi, N.; Serra Capizzano, S.; Zennaro, M., Finiteness property of pairs of \(2 \times 2\) sign-matrices via real extremal polytope norms, Linear Algebra Appl., 432, 796-816, (2009) · Zbl 1186.15006
[6] Derrida, B.; Mecheri, K.; Pichard, J. L., Lyapounov exponents of products of random matrices: weak disorder expansion. application to localisation, J. Phys., 48, 733-740, (1987)
[7] Dieci, L.; van Vleck, E. S., Lyapunov spectral intervals: theory and computation, SIAM J. Math. Anal., 40, 516-542, (2002) · Zbl 1021.65067
[8] Dieci, L.; van Vleck, E. S., Perturbation theory for approximation of Lyapunov exponents by qr methods, J. Dynam. Differential Equations, 18, 815-840, (2006) · Zbl 1166.34319
[9] Fekete, M., Uber die verteilung der wurzeln bei gewissen algebraischen gleichungen mit. ganzzahligen koeffizienten, Math. Z., 17, 228-249, (1923) · JFM 49.0047.01
[10] S. Finch, Z.-Q. Bai, and P. Sebah, Typical dispersion and generalized lyapunov exponent, 2008, arxiv preprint: http://arxiv.org/abs/0803.2611.
[11] Furstenberg, H.; Kesten, H., Products of random matrices, Ann. Math. Statist., 31, 457-469, (1960) · Zbl 0137.35501
[12] Gerencser, L.; Michaletzky, G.; Orlovits, Z., Stability of block-triangular stationary random matrices, Systems and Control Lett., 57, 8, 620-625, (2008) · Zbl 1140.93492
[13] Gharavi, R.; Anantharam, V., An upper bound for the largest Lyapunov exponent of a Markovian product of nonnegative matrices, Theoret. Comput. Sci., 332, 543-557, (2005) · Zbl 1066.60066
[14] Gol’dsheid, I. Ya. G.; Margulis, G. A., Lyapunov indices of a product of random matrices, Russian Math. Surveys, 44, 11-71, (1989) · Zbl 0705.60012
[15] Guglielmi, N.; Wirth, F.; Zennaro, M., Complex polytope extremality results for families of matrices, SIAM J. Matrix Anal. Appl., 27, 3, 721-743, (2005) · Zbl 1099.15023
[16] Hennion, H., Limit theorems for products of positive random matrices, Ann. Probab., 25, 1545-1587, (1997) · Zbl 0903.60027
[17] D. Hong, Lyapunov exponents: when the top joins the bottom, Technical Report RR-4198, INRIA, 2001.
[18] Ishitani, H., A central limit theorem for the subadditive process and its application to products of random matrices, Publ. Res. Inst. Math. Sci. Kyoto University, 12, 565-575, (1977) · Zbl 0364.60048
[19] Jungers, R. M., The joint spectral radius, theory and applications, (Lecture Notes in Control and Inform. Sci., vol. 385, (2009), Springer-Verlag Berlin)
[20] Jungers, R. M., On asymptotic properties of matrix semigroups with an invariant cone, Linear Algebra Appl., 437, 1205-1214, (2012) · Zbl 1258.15015
[21] Jungers, R. M.; Protasov, V. Yu.; Blondel, V. D., Overlap-free words and spectra of matrices, Theoret. Comput. Sci., 410, 3670-3684, (2009), Preprint: http://arxiv.org/abs/0709.1794 · Zbl 1171.68035
[22] Key, E. S., Lower bounds for the maximal Lyapunov exponent, J. Theoret. Probab., 3, 477-488, (1990) · Zbl 0704.60011
[23] Kozyakin, V. S., Algebraic unsolvability of problem of absolute stability of desynchronized systems, Autom. Remote Control, 51, 6, 754-759, (1990) · Zbl 0737.93056
[24] Deutsch, J. M.; Paladin, G., Product of random matrices in a microcanonical ensemble, Phys. Rev. Lett., 62, 695-699, (1989)
[25] Mainieri, R., Cycle expansion for the Lyapunov exponent of a product of random matrices, Chaos, 2, 91-97, (1992) · Zbl 1055.82518
[26] J. Nielsen, Lyapunov Exponents for Products of Random Matrices, 1997. <http://citeseer.ist.psu.edu/438423.html>.
[27] Oseledets, V. I., A multiplicative ergodic theorem. Lyapunov characteristic numbers for dynamical systems, Trans. Moscow Math. Soc., 19, 197-231, (1968) · Zbl 0236.93034
[28] Peres, Y., Domains of the analytic continuation for the top Lyapunov exponent, Ann. lInst. H. Poincaré, 28, 131-148, (1992) · Zbl 0794.58023
[29] Pollicott, M., Maximal Lyapunov exponent for random matrix productss, Invent. Math., 181, 209-226, (2010) · Zbl 1196.37032
[30] Protasov, V. Yu., Asymptotic behaviour of the partition function, Sb. Math., 191, 3-4, 381-414, (2000)
[31] Protasov, V. Yu., On the regularity of de Rham curves, Izv. Math., 68, 3, 567-606, (2004) · Zbl 1119.28006
[32] Protasov, V. Yu., Invariant functionals of random matrices, Funct. Anal. Appl., 44, 230-233, (2010) · Zbl 1271.15024
[33] Protasov, V. Yu., Invariant functions for the Lyapunov exponents of random matrices, Sb. Math., 202, 101-126, (2011) · Zbl 1239.60004
[34] Protasov, V. Yu.; Jungers, R. M.; Blondel, V. D., Joint spectral characteristics of matrices: a conic programming approach, SIAM J. Matrix Anal. Appl., 31, 4, 2146-2162, (2010) · Zbl 1203.65093
[35] Protasov, V. Yu.; Voynov, A. S., Sets of nonnegative matrices without positive products, Linear Algebra Appl., 437, 749-765, (2012) · Zbl 1245.15033
[36] Watkins, W. C., Limit theorems for products of random matrices: a comparison of two points of view, Contemp. Math., 50, 5-29, (1986)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.