The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - When not impossible - To compute and to approximate

被引：203

作者：

Tsitsiklis, JN ^{[1
]}

Blondel, VD ^{[1
]}

机构：

[1] UNIV LIEGE, MATH INST, B-4000 LIEGE, BELGIUM

来源：

MATHEMATICS OF CONTROL SIGNALS AND SYSTEMS | 1997年 / 10卷 / 01期

关键词：

Lyapunov exponent; Lyapunov indicator; joint spectral radius; generalized spectral radius; discrete differential inclusion; computational complexity; NP-hard; algorithmic solvability;

D O I：

10.1007/BF01219774

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We analyze the computability and the complexity of various definitions of spectral radii for sets of matrices. We show that the joint and generalized spectral radii of two integer matrices are not approximable iu polynomial time, and that two related quantities-the lower spectral radius and the largest Lyapunov exponent-are not algorithmically approximable.

引用

页码：31 / 40

页数：10

共 35 条

[1] [Anonymous], LECT NOTES MATH
[2] ARNOLD L, 1991, LECT NOTES MATH, V1486
[3] BARABANOV NE, 1988, AVTOMAT TELEMEKH, V5, P17
[4] Barabanov Nikita E, 1988, AVTOM TELEMEH, V2, P40
[5] BOUNDED SEMIGROUPS OF MATRICES
BERGER, MA
WANG, Y
[J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 1992, 166 : 21 - 27
[6] BLONDEL VD, 1996, IN PRESS INFORMATION
[7] BLONDEL VD, 1997, COMPLEXITY STABILITY
[8] BOYD S, 1994, SIAM STUDIES APPL MA, V15
[9] CONSTRUCTIVE STABILITY AND ASYMPTOTIC STABILITY OF DYNAMICAL-SYSTEMS
BRAYTON, RK
TONG, CH
[J]. IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS, 1980, 27 (11): : 1121 - 1130
[10] Carey M., 1979, COMPUTER INTRACTABIL

← 1 2 3 4 →