Kuna spektra radiuso

En matematiko, la kuna spektra radiuso estas ĝeneraligo de la klasika nocio de spektra radiuso de kvadrata matrico, al aroj da kvadrataj matricoj.

La kuna spektra radiuso de aro da matricoj estas la maksimuma asimptota kreskada kurzo de produtoj de matricoj elektitaj el la aro. Por finia aro da matricoj $M=\{A_{1},\dots ,A_{m}\}\subset \mathbb {R} ^{n},$ la kuna spektra radiuso estas difinita kiel:

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

Eblas pruvi ke la limeso ekzistas kaj ke la kvanto reale ne dependas de la elektita matrica normo, sed ĉi tiu normo devas esti sub-multiplika.

La nocio estis prezentita en 1960 de Gian-Carlo Rota kaj Gilbert Strang, du matematikistoj de Masaĉuseca Instituto de Teknologio^[1], sed startis allogi atenton pro la laboro de Ingrid Daubechies kaj Jeffrey Lagarias. Ili montris ke la kuna spektra radiuso povas esti uzata por priskribi glatecajn propraĵojn de certaj ondosimilaĵaj funkcioj.^[2] Granda kvanto da aplikoj estis proponita post tiam. Estas sciate ke la kuna spektra radiusa kvanto estas NP-peza por komputi aŭ por aproksimi, eĉ se la aro M konsistas el nur du duumaj matricoj ^[3]. Ankaŭ, la demando ĉu ρ≤1, estas nedecidebla problemo ^[4]. Tamen, en lastatempaj jaroj granda progreso estas farita pri komprenado de ĝi, kaj ŝajnas ke en praktiko la kuna spektra radiuso povas ofte esti komputita kun kontentiga precizeco, kaj ke ĝi ankaŭ povas doni interesan studkapablon en inĝenieradaj kaj matematikaj problemoj.

Kalkulado

Malgraŭ la negativaj teoriaj rezultoj pri komputebleco de la kuna spektra radiuso, estas proponitaj manieroj, kiuj funkcias bone en praktiko. Estas eĉ sciataj algoritmoj, kiuj povas atingi ajnan precizecon en apriore komputebla kvanto da tempo. Ĉi tiuj algoritmoj povas vidiĝi kiel penantaj aproksimi la unu-globon de aparta vektora normo, nomata la ekstrema normo.^[5] Estas ĝenerale diferenco inter du familioj de tiaj algoritmoj: la unua familio, nomata hiperpluredraj normaj manieroj, konstruas la ekstreman normon per komputado de longaj trajektorioj de punktoj.^[6]^[7] Avantaĝo de ĉi tiuj manieroj estas tio, ke en la prefereblaj okazoj ili povas trovi la precizan valoron de la kuna spektra radiuso kaj provizi pruvon ke ĉi tio estas la preciza valoro.

La dua familio de manieroj aproksimas la ekstreman normon per modernaj optimumigaj teknikoj, simile al duondifinita programado^[8]^[9], sumo de kvadratoj^[10], konika programado^[11]. La avantaĝo de ĉi tiuj manieroj estas ke ili estas facilaj en realigo, kaj en praktiko, ili provizas ĝenerale la plej bonajn barojn por la kuna spektra radiuso.

La finiteca konjekto

Rilatanta al la komputebleco de la kuna spektra radiuso estas jena konjekto: ^[12]

"Por ĉiu finia aro da matricoj

M\subset \mathbb {R} ^{n\times n},

estas produto

A_{1}\dots A_{t}

de matricoj el ĉi tiu aro tia, ke

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

"

En la ekvacio pli supre " $\rho (A_{1}\dots A_{t})$ " estas la simpla spektra radiuso de la produto de matricoj $A_{1}\dots A_{t}$ .

Ĉi tiu konjekto, proponita en 1995, estis pruvita kiel malvera en 2003, ^[13] sed multaj demandoj rilatantaj al ĉi tiu konjekto estas ankoraŭ malfermitaj, kiel ekzemple la demando, ĉu ĝi veras por paroj da duumaj matricoj.^[14]^[15]

Aplikoj

La kuna spektra radiuso okazas en stabileca kondiĉo por diskreto-tempaj reŝaltantaj dinamikaj sistemoj. Ja, la sistemo difinita per la ekvacioj

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

estas stabila se ρ(M)<1.

La kuna spektra radiuso iĝis populara, kiam Ingrid Daubechies kaj Jeffrey Lagarias montris, ke ĝi regas la kontinuecon de certaj ondosimilaĵaj funkcioj. Post tio, ĝi ekhavis multajn aplikojn, en nombroteorio kaj informteorio, aŭtonomaj agentoj (interkonsento, ĝenerala interkonsento), kombinatoriko sur vortoj, ktp.

Rilatantaj nocioj

La kuna spektra radiuso estas la ĝeneraligo de la spektra radiuso de matrico por aro de kelkaj matricoj. Tamen, multaj pluaj kvantoj povas esti difinitaj pro konsidero de aro da matricoj: La kuna spektra subradiuso karakterizas la minimuman kurzon de kreskado de produtoj en la duongrupo generita per M.

La p-radiuso karakterizas la kurzon de kreskado de la L_p-averaĝo de la normoj de la produtoj en la duongrupo.

La lapunova eksponento de la aro da matricoj karakterizas la kurzon de kreskado de la geometria meznombro.

Referencoj

↑ G. C. Rota kaj G. Strang. "Noto pri la kuna spektra radiuso." Paperoj de nederlanda Akademio, 22:379–381, 1960
↑ I. Daubechies kaj J. C. Lagarias. "Du-skalaj diferencaj ekvacioj. ii. loka reguleco, malfiniaj produtoj de matricoj kaj fraktaloj." SIAM-revuo de Matematika Analizo, 23, p. 1031–1079, 1992.
↑ V. D. Blondel kaj J. N. Tsitsiklis. "La lapunova eksponento kaj kuna spektra radiuso de paroj de matricoj estas peza – kiam ne neebla – por komputi kaj por aproksimi." Matematiko de Regado, Signaloj, kaj Sistemoj, 10, p. 31–40, 1997.
↑ Vincent D. Blondel, John N. Tsitsiklis. "La limigiteco de ĉiuj produtoj de paro da matricoj estas nedecidebla." Sistemaj kaj Regadaj Leteroj, 41:2, p. 135-140, 2000.
↑ N. Barabanov. "Ljapunovaj nadloj de diskretaj inkluzivecoj i-iii." Aŭtomacio kaj Malproksima Regado, 49:152–157, 283–287, 558–565, 1988.
↑ V. Y. Protasov. "La kuna spektra radiuso kaj invariantaj aroj de linearaj operatoroj." Fundamentalnaja i prikladnaja matematika, 2(1):205–231, 1996.
↑ N. Guglielmi, F. Wirth, kaj M. Zennaro. "Kompleksaj hiperpluredraj ekstremaj rezultoj por familioj de matricoj." SIAM-revuo pri Matrica Analitiko kaj Aplikoj, 27(3):721–743, 2005.
↑ T. Ando kaj M.-H. Shih. "Samtempa punktigebleco." SIAM-revuo pri Matrica Analitiko kaj Aplikoj, 19(2):487–498, 1998.
↑ V. D. Blondel kaj Y. Nesterov. "Kompute kompetentaj proksimumadoj de la kuna spektra radiuso." SIAM-revuo de Matrica Analitiko, 27(1):256–272, 2005.
↑ P. Parrilo kaj A. Jadbabaie. "Proksimumado de la kuna spektra radiuso uzante sumon de kvadratoj." Lineara Algebro kaj ĝiaj Aplikoj, 428(10):2385–2402, 2008.
↑ V. Protasov, R. M. Jungers kaj V. D. Blondel. "Kunaj spektraj karakterizoj de matricoj: konika programada maniero." SIAM-revuo pri Matrica Analitiko kaj Aplikoj, 2008.
↑ J. C. Lagarias kaj Y. Wang. "La finiteca konjekto por la ĝeneraligita spektra radiuso de aro de matricoj." Lineara Algebro kaj ĝiaj Aplikoj, 214:17–42, 1995.
↑ T. Bousch kaj J. Mairesse. "Asimptota alta optimumigo por aktuala IFS, Tetriso-akumulaĵoj, kaj la finiteca konjekto." Revuo de la Matematika Usona Societo, 15(1):77–111, 2002.
↑ A. Cicone, N. Guglielmi, S. Serra Capizzano, kaj M. Zennaro. "Finiteca propraĵo de paroj de 2×2-signo-matricoj tra reelaj ekstremaj hiperpluredraj normoj." Lineara Algebro kaj ĝiaj Aplikoj, 2010.
↑ R. M. Jungers kaj V. D. Blondel. "Pri la finiteca propraĵo por racionalaj matricoj." Lineara Algebro kaj ĝiaj Aplikoj, 428(10):2283–2295, 2008.

Raphael M. Jungers (2009). The joint spectral radius, Theory and applications – La kuna spektra radiuso, Teorio kaj aplikoj. Springer – Saltanto. ISBN 978-3-540-95979-3.
. Vincent D. Blondel, Michael Karow, Vladimir Protassov, kaj Fabian R. Wirth:Linear Algebra and its Applications: special issue on the joint spectral radius – Lineara Algebro kaj ĝiaj Aplikoj: speciala eldono pri la kuna spektra radiuso. Linear Algebra and its Applications – Lineara Algebro kaj ĝiaj Aplikoj 428 (10). Elsevier (2008).

[1] G. C. Rota kaj G. Strang. "Noto pri la kuna spektra radiuso." Paperoj de nederlanda Akademio, 22:379–381, 1960

[2] I. Daubechies kaj J. C. Lagarias. "Du-skalaj diferencaj ekvacioj. ii. loka reguleco, malfiniaj produtoj de matricoj kaj fraktaloj." SIAM-revuo de Matematika Analizo, 23, p. 1031–1079, 1992.

[3] V. D. Blondel kaj J. N. Tsitsiklis. "La lapunova eksponento kaj kuna spektra radiuso de paroj de matricoj estas peza – kiam ne neebla – por komputi kaj por aproksimi." Matematiko de Regado, Signaloj, kaj Sistemoj, 10, p. 31–40, 1997.

[4] Vincent D. Blondel, John N. Tsitsiklis. "La limigiteco de ĉiuj produtoj de paro da matricoj estas nedecidebla." Sistemaj kaj Regadaj Leteroj, 41:2, p. 135-140, 2000.

[5] N. Barabanov. "Ljapunovaj nadloj de diskretaj inkluzivecoj i-iii." Aŭtomacio kaj Malproksima Regado, 49:152–157, 283–287, 558–565, 1988.

[6] V. Y. Protasov. "La kuna spektra radiuso kaj invariantaj aroj de linearaj operatoroj." Fundamentalnaja i prikladnaja matematika, 2(1):205–231, 1996.

[7] N. Guglielmi, F. Wirth, kaj M. Zennaro. "Kompleksaj hiperpluredraj ekstremaj rezultoj por familioj de matricoj." SIAM-revuo pri Matrica Analitiko kaj Aplikoj, 27(3):721–743, 2005.

[8] T. Ando kaj M.-H. Shih. "Samtempa punktigebleco." SIAM-revuo pri Matrica Analitiko kaj Aplikoj, 19(2):487–498, 1998.

[9] V. D. Blondel kaj Y. Nesterov. "Kompute kompetentaj proksimumadoj de la kuna spektra radiuso." SIAM-revuo de Matrica Analitiko, 27(1):256–272, 2005.

[10] P. Parrilo kaj A. Jadbabaie. "Proksimumado de la kuna spektra radiuso uzante sumon de kvadratoj." Lineara Algebro kaj ĝiaj Aplikoj, 428(10):2385–2402, 2008.

[11] V. Protasov, R. M. Jungers kaj V. D. Blondel. "Kunaj spektraj karakterizoj de matricoj: konika programada maniero." SIAM-revuo pri Matrica Analitiko kaj Aplikoj, 2008.

[12] J. C. Lagarias kaj Y. Wang. "La finiteca konjekto por la ĝeneraligita spektra radiuso de aro de matricoj." Lineara Algebro kaj ĝiaj Aplikoj, 214:17–42, 1995.

[13] T. Bousch kaj J. Mairesse. "Asimptota alta optimumigo por aktuala IFS, Tetriso-akumulaĵoj, kaj la finiteca konjekto." Revuo de la Matematika Usona Societo, 15(1):77–111, 2002.

[14] A. Cicone, N. Guglielmi, S. Serra Capizzano, kaj M. Zennaro. "Finiteca propraĵo de paroj de 2×2-signo-matricoj tra reelaj ekstremaj hiperpluredraj normoj." Lineara Algebro kaj ĝiaj Aplikoj, 2010.

[15] R. M. Jungers kaj V. D. Blondel. "Pri la finiteca propraĵo por racionalaj matricoj." Lineara Algebro kaj ĝiaj Aplikoj, 428(10):2283–2295, 2008.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]