聯合譜半徑

聯合譜半徑（joint spectral radius）為一數學名詞，是將傳統上針對矩陣的譜半徑表示法，擴展到矩陣集合的表示法。近年來此表示法已應用在許多工程領域中，也是目前研究的熱門主題。

概述

矩陣集合的聯合譜半徑是在集合中矩陣乘積的最大漸近成長率。針對有限集合（或是更廣義的緊湊集合） ${\mathcal {M}}=\{A_{1},\dots ,A_{m}\}\subset \mathbb {R} ^{n\times n},$ ，其聯合譜半徑定義如下：

\rho ({\mathcal {M}})=\lim _{k\to \infty }\max {\{\|A_{i_{1}}\cdots A_{i_{k}}\|^{1/k}:A_{i}\in {\mathcal {M}}\}}.\,

可以證明其極限存在，而且其數值不會隨所選擇的矩陣範數種類而改變（這對任何矩陣範數都成立，不過若矩陣範數有次可乘性sub-multiplicative，更容易證明）。聯合譜半徑的概念是在1960年由麻省理工學院的兩位數學家吉安-卡洛·羅塔及威廉·吉爾伯特·斯特朗發明^[1]，不過在英格麗·多貝西及傑佛瑞·拉加里亞斯（英語：Jeffrey Lagarias）的研究後，才開始受到注意^[2]，他們證明了聯合譜半徑可以用來描述特定小波函數的光滑性^[3]。之後就提出了許多相關的應用。目前已知聯合譜半徑的量值求值，不論是要計算或只是近似，在運算複雜度上都是NP困難，就算集合 ${\mathcal {M}}$ 中只有二個矩陣，其中所有非零元素都相同也是一樣^[4]。而且， $\rho \leq 1?$ 這個問題是不可判定問題^[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]：

「針對任何有限個的矩陣集合 ${\mathcal {M}}\subset \mathbb {R} ^{n\times n},$ ，存在一個矩陣乘積 $A_{1}\dots A_{t}$ 使得

\rho ({\mathcal {M}})=\rho (A_{1}\dots A_{t})^{1/t}.

」

上式中的「 $\rho (A_{1}\dots A_{t})$ 」是指矩陣 $A_{1}\dots A_{t}$ 在傳統意義下的譜半徑。

此猜想在1995年提出，在2003年證否^[15]。在參考資料中的反例用到了進階的量度理論（measure-theoretical）概念。之後，也找到了許多的反例，包括只用到簡單組合數學性質的矩陣^[16]以及另一個用到動態系統概念的反例^[17]。近來也提出了一顯式的反例^[18]。許多相關的問題還沒有證明，例如對於成對的邏輯矩陣，此猜想是否成立^[19]^[20]。

應用

聯合譜半徑的出現，是為了作為離散時間切換動力系統的穩定性條件。而以下方程定義的系統

x_{t+1}=A_{t}x_{t},\quad A_{t}\in {\mathcal {M}}\,\forall t

為李雅普諾夫穩定性若而唯若 $\rho ({\mathcal {M}})<1.$ 。

因為英格麗·多貝西及傑佛瑞·拉加里亞斯將聯合譜半徑應用在小波函數的連續性上，因此聯合譜半徑受到許多人的注意。之後的應用包括有數論、信息理論、自治代理（英語：autonomous agent）共識、字的組合數學（英語：combinatorics on words）等。

參考資料

^ 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 [2020-01-28]. （原始內容 (PDF)存檔於2012-03-31）.

Jacques Theys. PhD thesis. Joint Spectral Radius: Theory and approximations. (PDF). 2005 [2020-01-28]. （原始內容 (PDF)存檔於2007-06-13）.

[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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

聯合譜半徑

目次

概述

計算

近似演算法

有限性猜想

應用

相關的表示法

參考資料

延伸閱讀