聯合譜半徑:修订间差异
翻譯外文連結 |
(没有差异)
|
2020年1月28日 (二) 14:08的版本
此條目目前正依照其他维基百科上的内容进行翻译。 (2020年1月28日) |
聯合譜半徑(joint spectral radius)為一數學名詞,是將傳統上針對矩陣的谱半径表示法,擴展到針對矩陣集合表示法。近年來此表示法已應用在許多工程領域中,也是目前研究的熱門主題。
General description
The joint spectral radius of a set of matrices is the maximal asymptotic growth rate of products of matrices taken in that set. For a finite (or more generally compact) set of matrices the joint spectral radius is defined as follows:
It can be proved that the limit exists and that the quantity actually does not depend on the chosen matrix norm (this is true for any norm but particularly easy to see if the norm is 矩陣範數). The joint spectral radius was introduced in 1960 by 吉安-卡洛·羅塔 and 威廉·吉爾伯特·斯特朗,[1] two mathematicians from 麻省理工学院, but started attracting attention with the work of 英格丽·多贝西 and Lua错误:bad argument #1 to 'gsub' (string expected, got nil)。.[2] They showed that the joint spectral radius can be used to describe smoothness properties of certain 小波分析.[3] A wide number of applications have been proposed since then. It is known that the joint spectral radius quantity is NP困难 to compute or to approximate, even when the set consists of only two matrices with all nonzero entries of the two matrices which are constrained to be equal.[4] Moreover, the question "" is an 不可判定问题.[5] Nevertheless, in recent years much progress has been done on its understanding, and it appears that in practice the joint spectral radius can often be computed to satisfactory precision, and that it moreover can bring interesting insight in engineering and mathematical problems.
Computation
Approximation algorithms
In spite of the negative theoretical results on the joint spectral radius computability, methods have been proposed that perform well in practice. Algorithms are even known, which can reach an arbitrary accuracy in an a priori computable amount of time. These algorithms can be seen as trying to approximate the unit ball of a particular vector norm, called the extremal norm.[6] One generally distinguishes between two families of such algorithms: the first family, called polytope norm methods, construct the extremal norm by computing long trajectories of points.[7][8] An advantage of these methods is that in the favorable cases it can find the exact value of the joint spectral radius and provide a certificate that this is the exact value.
The second methods approximate the extremal norm with modern optimization techniques, like ellipsoid norm approximation,[9] 半正定规划,[10][11] Lua错误:bad argument #1 to 'gsub' (string expected, got nil)。,[12] Lua错误:bad argument #1 to 'gsub' (string expected, got nil)。.[13] The advantage of these methods is that they are easy to implement, and in practice, they provide in general the best bounds on the joint spectral radius.
The finiteness conjecture
Related to the computability of the joint spectral radius is the following conjecture:[14]
"For any finite set of matrices there is a product of matrices in this set such that
- "
In the above equation "" refers to the classical 谱半径 of the matrix
This conjecture, proposed in 1995, has been proved to be false in 2003,.[15] The counterexample provided in that reference uses advanced measure-theoretical ideas. Subsequently, many other counterexamples have been provided, including an elementary counterexample that uses simple combinatorial properties matrices [16] and a counterexample based on dynamical systems properties.[17] Recently an explicit counterexample has been proposed in.[18] Many questions related to this conjecture are still open, as for instance the question of knowing whether it holds for pairs of 邏輯矩陣.[19][20]
Applications
The joint spectral radius was introduced for its interpretation as a stability condition for discrete-time switching 动力系统s. Indeed, the system defined by the equations
is 李雅普诺夫稳定性 if and only if
The joint spectral radius became popular when 英格丽·多贝西 and Lua错误:bad argument #1 to 'gsub' (string expected, got nil)。 showed that it rules the continuity of certain wavelet functions. Since then, it has found many applications, ranging from number theory to information theory, Lua错误:bad argument #1 to 'gsub' (string expected, got nil)。s consensus, Lua错误:bad argument #1 to 'gsub' (string expected, got nil)。,...
Related notions
The joint spectral radius is the generalization of the 谱半径 of a matrix for a set of several matrices. However, much more quantities can be defined when considering a set of matrices: The joint spectral subradius characterizes the minimal rate of growth of products in the semigroup generated by . The p-radius characterizes the rate of growth of the average of the norms of the products in the semigroup. The Lyapunov exponent of the set of matrices characterizes the rate of growth of the geometric average.
參考資料
- ^ G. C. Rota and G. Strang. "A note on the joint spectral radius." Proceedings of the Netherlands Academy, 22:379–381, 1960. [1]
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ N. Barabanov. "Lyapunov indicators of discrete inclusions i–iii." Automation and Remote Control, 49:152–157, 283–287, 558–565, 1988.
- ^ V. Y. Protasov. "The joint spectral radius and invariant sets of linear operators." Fundamentalnaya i prikladnaya matematika, 2(1):205–231, 1996.
- ^ 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.
- ^ 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.
- ^ T. Ando and M.-H. Shih. "Simultaneous contractibility." SIAM Journal on Matrix Analysis and Applications, 19(2):487–498, 1998.
- ^ V. D. Blondel and Y. Nesterov. "Computationally efficient approximations of the joint spectral radius." SIAM Journal of Matrix Analysis, 27(1):256–272, 2005.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ V. Kozyakin Structure of Extremal Trajectories of Discrete Linear Systems and the Finiteness Conjecture, Automat. Remote Control, 68 (2007), no. 1, 174–209/
- ^ 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.
- ^ 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.
- ^ R. M. Jungers and V. D. Blondel. "On the finiteness property for rational matrices." Linear Algebra and its Applications, 428(10):2283–2295, 2008.
延伸閱讀
- Raphael M. Jungers. The joint spectral radius, Theory and applications. Springer. 2009. ISBN 978-3-540-95979-3.
- 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=
被忽略 (帮助)
- Antonio Cicone. PhD thesis. Spectral Properties of Families of Matrices. Part III (PDF). 2011.
- Jacques Theys. PhD thesis. Joint Spectral Radius: Theory and approximations. (PDF). 2005.[永久失效連結]