Совместный спектральный радиус

В математике совместный спектральный радиус представляет собой обобщение классического понятия спектрального радиуса матрицы на наборы матриц. В последние годы это понятие нашло применение во многих областях техники и до сих пор является предметом активных исследований.

Общее описание [ править ]

Совместный спектральный радиус набора матриц — это максимальная асимптотическая скорость роста произведений матриц, взятых в этом наборе. Для конечного (или, вообще говоря, компактного) набора матриц ${\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}}\}}.\,

Можно доказать, что предел существует и что величина на самом деле не зависит от выбранной матричной нормы (это верно для любой нормы, но особенно легко убедиться, если норма субмультипликативна ). Совместный спектральный радиус был введен в 1960 году Джан-Карло Ротой и Гилбертом Стрэнгом . ^[1] двух математиков из Массачусетского технологического института , но начал привлекать внимание работами Ингрид Добеши и Джеффри Лагариаса . ^[2] Они показали, что совместный спектральный радиус может использоваться для описания свойств гладкости некоторых вейвлет-функций . ^[3] С тех пор было предложено большое количество приложений. Известно, что величину совместного спектрального радиуса NP-трудно вычислить или аппроксимировать, даже если набор ${\mathcal {M}}$ состоит только из двух матриц со всеми ненулевыми элементами двухматрицы, которые ограничены равными. ^[4] Более того, вопрос « $\rho \leq 1?$ «Это неразрешимая проблема . ^[5] Тем не менее, в последние годы был достигнут большой прогресс в его понимании, и оказывается, что на практике объединенный спектральный радиус часто можно вычислить с удовлетворительной точностью, и, кроме того, он может дать интересное понимание инженерных и математических проблем.

Расчет [ править ]

Алгоритмы аппроксимации [ править ]

Несмотря на отрицательные теоретические результаты по вычислению совместного спектрального радиуса, были предложены методы, которые хорошо работают на практике. Известны даже алгоритмы, которые могут достигать произвольной точности за априорно вычислимое время. Эти алгоритмы можно рассматривать как попытку аппроксимировать единичный шар определенной векторной нормы, называемой экстремальной нормой. ^[6] Обычно различают два семейства таких алгоритмов: первое семейство, называемое методами многогранной нормы , строит экстремальную норму путем вычисления длинных траекторий точек. ^[7]^[8] Преимущество этих методов состоит в том, что в благоприятных случаях можно найти точное значение совместного спектрального радиуса и предоставить сертификат того, что это точное значение.

Второе семейство методов аппроксимирует экстремальную норму с помощью современных методов оптимизации , таких как аппроксимация нормы эллипсоида, ^[9] полуопределенное программирование , ^[10]^[11] Сумма квадратов , ^[12] и коническое программирование . ^[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] Контрпример, приведенный в этой ссылке, использует передовые идеи теории меры. Впоследствии было предложено множество других контрпримеров, в том числе элементарный контрпример, в котором используются простые матрицы комбинаторных свойств. ^[16] и контрпример, основанный на свойствах динамических систем. ^[17] Недавно был предложен явный контрпример. ^[18] Многие вопросы, связанные с этой гипотезой, все еще остаются открытыми, например, вопрос о том, справедлива ли она для пар двоичных матриц . ^[19]^[20]

Приложения [ править ]

Совместный спектральный радиус был введен для его интерпретации как условия устойчивости динамических систем с дискретным временем переключения . Действительно, система, определяемая уравнениями

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

устойчив когда тогда и только тогда, $\rho ({\mathcal {M}})<1.$

Совместный спектральный радиус стал популярным, когда Ингрид Добеши и Джеффри Лагариас показали, что он определяет непрерывность некоторых вейвлет-функций. С тех пор она нашла множество применений, начиная от теории чисел и заканчивая теорией информации, автономных агентов консенсусом , комбинаторикой слов ...

Связанные понятия [ править ]

Совместный спектральный радиус — это обобщение спектрального радиуса матрицы для набора из нескольких матриц. Однако при рассмотрении набора матриц можно определить гораздо больше величин: совместный спектральный субрадиус характеризует минимальную скорость роста произведений в полугруппе, порожденной ${\mathcal {M}}$ . p -радиус характеризует скорость роста $L_{p}$ среднее от норм продуктов в полугруппе.Показатель Ляпунова набора матриц характеризует скорость роста среднего геометрического.

Ссылки [ править ]

^ GC Рота и Г. Стрэнг. «Заметка о совместном спектральном радиусе». Труды Нидерландской академии, 22: 379–381, 1960. [1]
^ Винсент Д. Блондель. Рождение совместного спектрального радиуса: интервью с Гилбертом Стрэнгом. Линейная алгебра и ее приложения, 428:10, стр. 2261–2264, 2008.
^ И. Добеши и Ж. К. Лагариас. «Двухмасштабные разностные уравнения. ii. Локальная регулярность, бесконечные произведения матриц и фракталов». SIAM Journal of Mathematical Analysis, 23, стр. 1031–1079, 1992.
^ Ю. Н. Цициклис и В. Д. Блондель. «Показатели Ляпунова пар матриц, поправка». Математика управления, сигналов и систем , 10, с. 381, 1997.
^ Винсент Д. Блондель, Джон Н. Цициклис. «Ограниченность всех произведений пары матриц неразрешима». Системы и контрольные письма, 41:2, стр. 135–140, 2000.
^ Н. Барабанов. «Ляпуновские индикаторы дискретных включений i–iii». Автоматизация и дистанционное управление, 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.
^ Н. Гульельми, Ф. Вирт и М. Зеннаро. «Результаты экстремальности комплексных многогранников для семейств матриц». Журнал SIAM по матричному анализу и приложениям, 27 (3): 721–743, 2005.
^ Винсент Д. Блондель, Юрий Нестеров и Жак Тейс, О точности аппроксимации эллипсоидной нормы совместного спектрального радиуса, Линейная алгебра и ее приложения, 394:1, стр. 91–107, 2005.
^ Т. Андо и М.-Х. Ши. «Одновременная сокращаемость». Журнал SIAM по матричному анализу и приложениям, 19 (2): 487–498, 1998.
^ В.Д. Блондель и Ю. Нестеров. «Вычислительно эффективные аппроксимации совместного спектрального радиуса». SIAM Journal of Matrix Analysis, 27(1):256–272, 2005.
^ П. Паррило и А. Джадбабайе. «Аппроксимация совместного спектрального радиуса с использованием суммы квадратов». Линейная алгебра и ее приложения, 428(10):2385–2402, 2008.
^ В. Протасов, Р. М. Юнгерс и В. Д. Блондель. «Совместные спектральные характеристики матриц: подход конического программирования». Журнал SIAM по матричному анализу и приложениям, 2008.
^ Дж. К. Лагариас и Ю. Ван. «Гипотеза о конечности обобщенного спектрального радиуса набора матриц». Линейная алгебра и ее приложения, 214:17–42, 1995.
^ Т. Буш и Ж. Мэресс. «Асимптотическая оптимизация высоты для актуальных IFS, куч тетриса и гипотезы конечности». Журнал Американского математического общества, 15 (1): 77–111, 2002.
^ В.Д. Блондель, Дж. Тейс и А.А. Владимиров, Элементарный контрпример к гипотезе конечности, SIAM Journal on Matrix Analysis, 24:4, стр. 963–970, 2003.
^ В. КозякинСтруктура экстремальных траекторий дискретных линейных систем и гипотеза конечности, Автомат. Дистанционное управление, 68 (2007), вып. 1, 174–209/
^ Кевин Г. Хэйр, Ян Д. Моррис, Никита Сидоров, Жак Тейс. Явный контрпример к гипотезе конечности Лагариаса – Ванга, Advances in Mathematics , 226, стр. 4667-4701, 2011.
^ А. Чиконе, Н. Гульельми, С. Серра Капиццано и М. Зеннаро. «Свойство конечности парЗнаковые матрицы 2 × 2 с помощью норм вещественных экстремальных многогранников». Линейная алгебра и ее приложения, 2010.
^ Р. М. Юнгерс и В. Д. Блондель. «О свойстве конечности рациональных матриц». Линейная алгебра и ее приложения, 428(10):2283–2295, 2008.

Дальнейшее чтение [ править ]

Рафаэль М. Юнгерс (2009). Совместный спектральный радиус, Теория и приложения . Спрингер. ISBN 978-3-540-95979-3 .

Винсент Д. Блондель; Майкл Кароу; Владимир Протасов; Фабиан Р. Вирт, ред. (2008). «Линейная алгебра и ее приложения: специальный выпуск о совместном спектральном радиусе». Линейная алгебра и ее приложения . 428 (10). Эльзевир.

Антонио Чиконе (2011). «Кандидатская диссертация. Спектральные свойства семейств матриц. Часть III» (PDF) .

Жак Тейс (2005). «Докторская диссертация. Совместный спектральный радиус: теория и приближения» (PDF) . Архивировано из оригинала (PDF) 13 июня 2007 г.

[1] GC Рота и Г. Стрэнг. «Заметка о совместном спектральном радиусе». Труды Нидерландской академии, 22: 379–381, 1960. [1]

[2] Винсент Д. Блондель. Рождение совместного спектрального радиуса: интервью с Гилбертом Стрэнгом. Линейная алгебра и ее приложения, 428:10, стр. 2261–2264, 2008.

[3] И. Добеши и Ж. К. Лагариас. «Двухмасштабные разностные уравнения. ii. Локальная регулярность, бесконечные произведения матриц и фракталов». SIAM Journal of Mathematical Analysis, 23, стр. 1031–1079, 1992.

[4] Ю. Н. Цициклис и В. Д. Блондель. «Показатели Ляпунова пар матриц, поправка». Математика управления, сигналов и систем , 10, с. 381, 1997.

[5] Винсент Д. Блондель, Джон Н. Цициклис. «Ограниченность всех произведений пары матриц неразрешима». Системы и контрольные письма, 41:2, стр. 135–140, 2000.

[6] Н. Барабанов. «Ляпуновские индикаторы дискретных включений i–iii». Автоматизация и дистанционное управление, 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] Н. Гульельми, Ф. Вирт и М. Зеннаро. «Результаты экстремальности комплексных многогранников для семейств матриц». Журнал SIAM по матричному анализу и приложениям, 27 (3): 721–743, 2005.

[9] Винсент Д. Блондель, Юрий Нестеров и Жак Тейс, О точности аппроксимации эллипсоидной нормы совместного спектрального радиуса, Линейная алгебра и ее приложения, 394:1, стр. 91–107, 2005.

[10] Т. Андо и М.-Х. Ши. «Одновременная сокращаемость». Журнал SIAM по матричному анализу и приложениям, 19 (2): 487–498, 1998.

[11] В.Д. Блондель и Ю. Нестеров. «Вычислительно эффективные аппроксимации совместного спектрального радиуса». SIAM Journal of Matrix Analysis, 27(1):256–272, 2005.

[12] П. Паррило и А. Джадбабайе. «Аппроксимация совместного спектрального радиуса с использованием суммы квадратов». Линейная алгебра и ее приложения, 428(10):2385–2402, 2008.

[13] В. Протасов, Р. М. Юнгерс и В. Д. Блондель. «Совместные спектральные характеристики матриц: подход конического программирования». Журнал SIAM по матричному анализу и приложениям, 2008.

[14] Дж. К. Лагариас и Ю. Ван. «Гипотеза о конечности обобщенного спектрального радиуса набора матриц». Линейная алгебра и ее приложения, 214:17–42, 1995.

[15] Т. Буш и Ж. Мэресс. «Асимптотическая оптимизация высоты для актуальных IFS, куч тетриса и гипотезы конечности». Журнал Американского математического общества, 15 (1): 77–111, 2002.

[16] В.Д. Блондель, Дж. Тейс и А.А. Владимиров, Элементарный контрпример к гипотезе конечности, SIAM Journal on Matrix Analysis, 24:4, стр. 963–970, 2003.

[17] В. КозякинСтруктура экстремальных траекторий дискретных линейных систем и гипотеза конечности, Автомат. Дистанционное управление, 68 (2007), вып. 1, 174–209/

[18] Кевин Г. Хэйр, Ян Д. Моррис, Никита Сидоров, Жак Тейс. Явный контрпример к гипотезе конечности Лагариаса – Ванга, Advances in Mathematics , 226, стр. 4667-4701, 2011.

[19] А. Чиконе, Н. Гульельми, С. Серра Капиццано и М. Зеннаро. «Свойство конечности парЗнаковые матрицы 2 × 2 с помощью норм вещественных экстремальных многогранников». Линейная алгебра и ее приложения, 2010.

[20] Р. М. Юнгерс и В. Д. Блондель. «О свойстве конечности рациональных матриц». Линейная алгебра и ее приложения, 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]