查看“︁聯合譜半徑”︁的源代码

{{Expert|time=2020-01-31T15:58:33+00:00}}
'''聯合譜半徑'''（joint spectral radius）為一數學名詞，是將傳統上針對[[矩陣]]的[[谱半径]]表示法，擴展到矩陣[[集合 (數學)|集合]]的表示法。近年來此表示法已應用在許多工程領域中，也是目前研究的熱門主題。

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

: <math>\rho (\mathcal M)= \lim_{k \to
\infty}\max{\{ \|A_{i_1}\cdots A_{i_k}\|^{1/k}:A_i\in\mathcal M\}}. \, </math>

可以證明其極限存在，而且其數值不會隨所選擇的[[矩陣範數]]種類而改變（這對任何矩陣範數都成立，不過若矩陣範數有次可乘性sub-multiplicative，更容易證明）。聯合譜半徑的概念是在1960年由[[麻省理工学院]]的兩位數學家[[吉安-卡洛·羅塔]]及[[威廉·吉爾伯特·斯特朗]]發明<ref>G. C. Rota and G. Strang. "A note on the joint spectral radius." Proceedings of the Netherlands Academy, 22:379–381, 1960. [https://books.google.com/books?id=x7zKLGu3g9IC&lpg=RA1-PA40&ots=rxuCbvNTxI&dq=a%20note%20on%20the%20joint%20spectral%20radius%20rota%20strang&lr&pg=PA74#v=onepage&q&f=false]</ref>，不過在[[英格丽·多贝西]]及{{link-en|傑佛瑞·拉加里亞斯|Jeffrey Lagarias}}的研究後，才開始受到注意<ref>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.</ref>，他們證明了聯合譜半徑可以用來描述特定[[小波分析|小波函數]]的光滑性<ref>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.</ref>。之後就提出了許多相關的應用。目前已知聯合譜半徑的量值求值，不論是要計算或只是近似，在運算複雜度上都是[[NP困难]]，就算集合<math>\mathcal M</math>中只有二個矩陣，其中所有非零元素都相同也是一樣<ref>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.</ref>。而且，<math>\rho\leq 1 ?</math> 這個問題是[[不可判定问题]]<ref>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&ndash;140, 2000.</ref>。不過，近年來已對此問題有多一些的瞭解，似乎在實務上，可以計算聯合譜半徑到令人滿意的精度，而且對於一些工程及數學問題，可以有一些有趣的洞察。

==計算==
===近似演算法===
雖然在聯合譜半徑的可計算性理論上有一些負面的結果，不過已有提出一些在實務上可以良好運作的方法。目前已找到演算法，可以達到任意的精度，所需要的時間也是事先可以計算得知。這類的演算法可以視為是近似向量範數（稱為極值範數extremal norm）中的單位球<ref>N. Barabanov. "Lyapunov indicators of discrete inclusions i&ndash;iii." Automation and Remote Control, 49:152–157, 283–287, 558–565, 1988.</ref>。一般會將演算法分為兩類：第一類是多義範數法（polytope norm method），透過計算點的長軌跡來建構極值範數<ref>V. Y. Protasov. "The joint spectral radius and invariant sets of linear operators." Fundamentalnaya i prikladnaya matematika, 2(1):205–231, 1996.</ref><ref>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.</ref>，此方法的好處是在最理想的情形下，此方法可以找到聯合譜半徑的精確值，而且可以證明這個值就是正確值。

第二種方式是用「近代最佳化技巧」（modern optimization techniques）來近似極值範數，例如橢圓範數近似（ellipsoid norm approximation）<ref>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.</ref>、[[半正定规划]]<ref>T. Ando and M.-H. Shih. "Simultaneous contractibility." SIAM Journal on Matrix Analysis and Applications, 19(2):487–498, 1998.</ref><ref>V. D. Blondel and Y. Nesterov. "Computationally efficient approximations of the joint spectral radius." SIAM Journal of Matrix Analysis, 27(1):256–272, 2005.</ref>、{{link-en|多項式平方和|Polynomial SOS}}<ref>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.</ref>、{{link-en|圓錐最佳化|Conic optimization|圓錐規劃}}<ref>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.</ref>。這些方法的好處是容易實現，而且實務上此方式所產生的聯合譜半徑，一般來說是在最理想的範圍內。

===有限性猜想===
有關聯合譜半徑的可計算性，存在以下的猜想<ref>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.</ref>：

「針對任何有限個的矩陣集合<math>\mathcal M \subset \mathbb R^{n \times n},</math>，存在一個矩陣乘積<math> A_1\dots A_t</math>使得 
:<math>\rho(\mathcal M) = \rho(A_1 \dots A_t)^{1/t}.</math>」
上式中的「<math> \rho(A_1 \dots A_t)</math>」是指矩陣<math>A_1 \dots A_t</math>在傳統意義下的[[谱半径]]。

此猜想在1995年提出，在2003年證否<ref>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.</ref>。在參考資料中的反例用到了進階的量度理論（measure-theoretical）概念。之後，也找到了許多的反例，包括只用到簡單組合數學性質的矩陣<ref>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.</ref>以及另一個用到動態系統概念的反例<ref>V. Kozyakin
Structure of Extremal Trajectories of Discrete Linear Systems and the Finiteness Conjecture, Automat. Remote Control, 68 (2007), no. 1, 174–209/</ref>。近來也提出了一顯式的反例<ref>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.</ref>。許多相關的問題還沒有證明，例如對於成對的[[邏輯矩陣]]，此猜想是否成立<ref>A. Cicone, N. Guglielmi, S. Serra Capizzano, and M. Zennaro. "Finiteness property of pairs of
2&nbsp;×&nbsp;2 sign-matrices via real extremal polytope norms." Linear Algebra and its Applications, 2010.</ref><ref>R. M. Jungers and V. D. Blondel. "On the finiteness property for rational matrices." Linear Algebra and its Applications, 428(10):2283–2295, 2008.</ref>。

==應用==
聯合譜半徑的出現，是為了作為離散時間切換[[动力系统]]的穩定性條件。而以下方程定義的系統
:<math>x_{t+1}=A_tx_{t}, \quad A_t\in \mathcal M \, \forall t</math>
為[[李雅普诺夫稳定性]]若而唯若<math>\rho(\mathcal M)<1.</math>。

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

==相關的表示法==
聯合譜半徑是將一個矩陣的[[谱半径]]擴展到矩陣集合。不過也有其他可以適用於多個矩陣的量化表示法：

*聯合譜次幅（joint spectral subradius）表示由<math>\mathcal M</math>產生的半群最小成長速率乘積。  
*p-半徑（p-radius）表示此半群內乘積範數之<math>L_p</math>平均的成長速率。
*矩陣集合的[[李亞普諾夫指數]]（Lyapunov exponent）表示其幾何平均的成長速率。

== 參考資料 ==
{{Reflist}}

== 延伸閱讀 ==
*{{cite book
 | author = Raphael M. Jungers
 | year = 2009
 | title = The joint spectral radius, Theory and applications
 | publisher = Springer
 | isbn = 978-3-540-95979-3
}}

*{{cite book
 |editor1=Vincent D. Blondel |editor2=Michael Karow |editor3=Vladimir Protassov |editor4=Fabian R. Wirth | year = 2008
 | journal = Linear Algebra and its Applications
 | title = Linear Algebra and its Applications: special issue on the joint spectral radius
 | publisher = Elsevier
 | volume = 428
 | issue = 10
}}

*{{cite web
 |url=http://www.math.msu.edu/~cicone/papers/AntonioCiconeThesis.pdf
 |title=PhD thesis. Spectral Properties of Families of Matrices. Part III
 |author=Antonio Cicone
 |year=2011
 |accessdate=2020-01-28
 |archive-date=2012-03-31
 |archive-url=https://web.archive.org/web/20120331045840/http://www.math.msu.edu/~cicone/papers/AntonioCiconeThesis.pdf
 |dead-url=yes
 }}

*{{cite web
 |url    = http://www.inma.ucl.ac.be/~blondel/05thesetheys.pdf
 |title    = PhD thesis. Joint Spectral Radius: Theory and approximations.
 |author    = Jacques Theys
 |year    = 2005
 |accessdate    = 2020-01-28
 |archive-date    = 2007-06-13
 |archive-url    = https://web.archive.org/web/20070613182835/http://www.inma.ucl.ac.be/~blondel/05thesetheys.pdf
 |dead-url    = yes
 }}

<!--- Categories --->
[[Category:控制理论]]
[[Category:線性代數]]