联合谱半径

联合谱半径(joint spectral radius)为一数学名词,是将传统上针对矩阵谱半径表示法,扩展到矩阵集合的表示法。近年来此表示法已应用在许多工程领域中,也是目前研究的热门主题。

概述

矩阵集合的联合谱半径是在集合中矩阵乘积的最大渐近成长率。针对有限集合(或是更广义的紧凑集合) ,其联合谱半径定义如下:

 

可以证明其极限存在,而且其数值不会随所选择的矩阵范数种类而改变(这对任何矩阵范数都成立,不过若矩阵范数有次可乘性sub-multiplicative,更容易证明)。联合谱半径的概念是在1960年由麻省理工学院的两位数学家吉安-卡洛·罗塔威廉·吉尔伯特·斯特朗发明[1],不过在英格丽·多贝西杰佛瑞·拉加里亚斯英语Jeffrey Lagarias的研究后,才开始受到注意[2],他们证明了联合谱半径可以用来描述特定小波函数的光滑性[3]。之后就提出了许多相关的应用。目前已知联合谱半径的量值求值,不论是要计算或只是近似,在运算复杂度上都是NP困难,就算集合 中只有二个矩阵,其中所有非零元素都相同也是一样[4]。而且,  这个问题是不可判定问题[5]。不过,近年来已对此问题有多一些的了解,似乎在实务上,可以计算联合谱半径到令人满意的精度,而且对于一些工程及数学问题,可以有一些有趣的洞察。

计算

近似算法

虽然在联合谱半径的可计算性理论上有一些负面的结果,不过已有提出一些在实务上可以良好运作的方法。目前已找到算法,可以达到任意的精度,所需要的时间也是事先可以计算得知。这类的算法可以视为是近似向量范数(称为极值范数extremal norm)中的单位球[6]。一般会将算法分为两类:第一类是多义范数法(polytope norm method),透过计算点的长轨迹来建构极值范数[7][8],此方法的好处是在最理想的情形下,此方法可以找到联合谱半径的精确值,而且可以证明这个值就是正确值。

第二种方式是用“近代最佳化技巧”(modern optimization techniques)来近似极值范数,例如椭圆范数近似(ellipsoid norm approximation)[9]半正定规划[10][11]多项式平方和英语Polynomial SOS[12]圆锥规划英语Conic optimization[13]。这些方法的好处是容易实现,而且实务上此方式所产生的联合谱半径,一般来说是在最理想的范围内。

有限性猜想

有关联合谱半径的可计算性,存在以下的猜想[14]

“针对任何有限个的矩阵集合 ,存在一个矩阵乘积 使得

 

上式中的“ ”是指矩阵 在传统意义下的谱半径

此猜想在1995年提出,在2003年证否[15]。在参考资料中的反例用到了进阶的量度理论(measure-theoretical)概念。之后,也找到了许多的反例,包括只用到简单组合数学性质的矩阵[16]以及另一个用到动态系统概念的反例[17]。近来也提出了一显式的反例[18]。许多相关的问题还没有证明,例如对于成对的逻辑矩阵,此猜想是否成立[19][20]

应用

联合谱半径的出现,是为了作为离散时间切换动力系统的稳定性条件。而以下方程定义的系统

 

李雅普诺夫稳定性若而唯若 

因为英格丽·多贝西及杰佛瑞·拉加里亚斯将联合谱半径应用在小波函数的连续性上,因此联合谱半径受到许多人的注意。之后的应用包括有数论、信息理论、自治代理英语autonomous agent共识、字的组合数学英语combinatorics on words等。

相关的表示法

联合谱半径是将一个矩阵的谱半径扩展到矩阵集合。不过也有其他可以适用于多个矩阵的量化表示法:

  • 联合谱次幅(joint spectral subradius)表示由 产生的半群最小成长速率乘积。
  • p-半径(p-radius)表示此半群内乘积范数之 平均的成长速率。
  • 矩阵集合的李亚普诺夫指数(Lyapunov exponent)表示其几何平均的成长速率。

参考资料

  1. ^ G. C. Rota and G. Strang. "A note on the joint spectral radius." Proceedings of the Netherlands Academy, 22:379–381, 1960. [1]
  2. ^ Vincent D. Blondel. The birth of the joint spectral radius: an interview with Gilbert Strang. Linear Algebra and its Applications, 428:10, pp. 2261–2264, 2008.
  3. ^ I. Daubechies and J. C. Lagarias. "Two-scale difference equations. ii. local regularity, infinite products of matrices and fractals." SIAM Journal of Mathematical Analysis, 23, pp. 1031–1079, 1992.
  4. ^ J. N. Tsitsiklis and V. D. Blondel. "Lyapunov Exponents of Pairs of Matrices, a Correction." |Mathematics of Control, Signals, and Systems, 10, p. 381, 1997.
  5. ^ Vincent D. Blondel, John N. Tsitsiklis. "The boundedness of all products of a pair of matrices is undecidable." Systems and Control Letters, 41:2, pp. 135–140, 2000.
  6. ^ N. Barabanov. "Lyapunov indicators of discrete inclusions i–iii." Automation and Remote Control, 49:152–157, 283–287, 558–565, 1988.
  7. ^ V. Y. Protasov. "The joint spectral radius and invariant sets of linear operators." Fundamentalnaya i prikladnaya matematika, 2(1):205–231, 1996.
  8. ^ N. Guglielmi, F. Wirth, and M. Zennaro. "Complex polytope extremality results for families of matrices." SIAM Journal on Matrix Analysis and Applications, 27(3):721–743, 2005.
  9. ^ Vincent D. Blondel, Yurii Nesterov and Jacques Theys, On the accuracy of the ellipsoid norm approximation of the joint spectral radius, Linear Algebra and its Applications, 394:1, pp. 91–107, 2005.
  10. ^ T. Ando and M.-H. Shih. "Simultaneous contractibility." SIAM Journal on Matrix Analysis and Applications, 19(2):487–498, 1998.
  11. ^ V. D. Blondel and Y. Nesterov. "Computationally efficient approximations of the joint spectral radius." SIAM Journal of Matrix Analysis, 27(1):256–272, 2005.
  12. ^ P. Parrilo and A. Jadbabaie. "Approximation of the joint spectral radius using sum of squares." Linear Algebra and its Applications, 428(10):2385–2402, 2008.
  13. ^ V. Protasov, R. M. Jungers, and V. D. Blondel. "Joint spectral characteristics of matrices: a conic programming approach." SIAM Journal on Matrix Analysis and Applications, 2008.
  14. ^ J. C. Lagarias and Y. Wang. "The finiteness conjecture for the generalized spectral radius of a set of matrices." Linear Algebra and its Applications, 214:17–42, 1995.
  15. ^ T. Bousch and J. Mairesse. "Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture." Journal of the American Mathematical Society, 15(1):77–111, 2002.
  16. ^ V. D. Blondel, J. Theys and A. A. Vladimirov, An elementary counterexample to the finiteness conjecture, SIAM Journal on Matrix Analysis, 24:4, pp. 963–970, 2003.
  17. ^ V. Kozyakin Structure of Extremal Trajectories of Discrete Linear Systems and the Finiteness Conjecture, Automat. Remote Control, 68 (2007), no. 1, 174–209/
  18. ^ Kevin G. Hare, Ian D. Morris, Nikita Sidorov, Jacques Theys. An explicit counterexample to the Lagarias–Wang finiteness conjecture, Advances in Mathematics, 226, pp. 4667-4701, 2011.
  19. ^ A. Cicone, N. Guglielmi, S. Serra Capizzano, and M. Zennaro. "Finiteness property of pairs of 2 × 2 sign-matrices via real extremal polytope norms." Linear Algebra and its Applications, 2010.
  20. ^ R. M. Jungers and V. D. Blondel. "On the finiteness property for rational matrices." Linear Algebra and its Applications, 428(10):2283–2295, 2008.

延伸阅读

  • Vincent D. Blondel; Michael Karow; Vladimir Protassov; Fabian R. Wirth (编). Linear Algebra and its Applications: special issue on the joint spectral radius 428. Elsevier. 2008.  |journal=被忽略 (帮助); |issue=被忽略 (帮助)