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

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

Общее описание

Совместный спектральный радиус набора матриц - это максимальная асимптотическая скорость роста произведений матриц, взятых из этого набора. Для конечного (или, в более общем смысле, компактного) набора матриц ${\displaystyle {\mathcal {M}}=\{A_{1},\dots ,A_{m}\}\subset \mathbb {R} ^{n\times n},}$ совместный спектральный радиус определяется следующим образом:

${\displaystyle \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-жесткий вычислить или приблизить, даже если набор ${\displaystyle {\mathcal {M}}}$ состоит только из двух матриц со всеми ненулевыми элементами двух матриц, которые должны быть равны.^[4] Более того, вопрос "${\displaystyle \rho \leq 1?}$" является неразрешимая проблема.^[5] Тем не менее, в последние годы был достигнут значительный прогресс в ее понимании, и кажется, что на практике совместный спектральный радиус часто может быть вычислен с удовлетворительной точностью, и, кроме того, это может принести интересное понимание инженерных и математических проблем.

Вычисление

Алгоритмы аппроксимации

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

Второе семейство методов аппроксимирует экстремальную норму с помощью современные методы оптимизации, например, аппроксимация нормы эллипсоида,^[9] полуопределенное программирование,^[10][11] Сумма площадей,^[12] и коническое программирование.^[13] Преимущество этих методов состоит в том, что их легко реализовать, и на практике они в целом обеспечивают наилучшие оценки совместного спектрального радиуса.

Гипотеза конечности

С вычислимостью совместного спектрального радиуса связана следующая гипотеза:^[14]

"Для любого конечного набора матриц ${\displaystyle {\mathcal {M}}\subset \mathbb {R} ^{n\times n},}$ есть продукт ${\displaystyle A_{1}\dots A_{t}}$ матриц из этого множества таких, что

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

В приведенном выше уравнении "${\displaystyle \rho (A_{1}\dots A_{t})}$"относится к классическим спектральный радиус матрицы ${\displaystyle A_{1}\dots A_{t}.}$

Эта гипотеза, выдвинутая в 1995 году, оказалась ложной в 2003 году.^[15] Контрпример, приведенный в этой ссылке, использует передовые теоретико-меры. Впоследствии было предоставлено множество других контрпримеров, включая элементарный контрпример, который использует простые комбинаторные матрицы свойств. ^[16] и контрпример, основанный на свойствах динамических систем.^[17] Недавно явный контрпример был предложен в.^[18] Многие вопросы, связанные с этой гипотезой, все еще остаются открытыми, например, вопрос о том, верна ли она для пар двоичные матрицы.^[19][20]

Приложения

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

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

является стабильный если и только если ${\displaystyle \rho ({\mathcal {M}})<1.}$

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

Связанные понятия

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

Рекомендации

1. Г. К. Рота и Г. Стрэнг. «Замечание о совместном спектральном радиусе». Слушания Нидерландской академии, 22: 379–381, 1960. [1]
2. Винсент Д. Блондель. Рождение совместного спектрального радиуса: интервью с Гилбертом Стренгом. Линейная алгебра и ее приложения, 428: 10, стр. 2261–2264, 2008.
3. И. Добеши и Дж. К. Лагариас. «Двухмасштабные разностные уравнения. II. Локальная регулярность, бесконечные произведения матриц и фракталов». SIAM Journal of Mathematical Analysis, 23, pp. 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. Протасов В.Ю. «Совместный спектральный радиус и инвариантные множества линейных операторов». Фундаментальная и прикладная математика, 2 (1): 205–231, 1996.
8. Н. Гульельми, Ф. Вирт и М. Зеннаро. "Комплексные результаты об экстремальности многогранников для семейств матриц". Журнал SIAM по матричному анализу и приложениям, 27 (3): 721–743, 2005.
9. Винсент Д. Блондель, Юрий Нестеров и Жак Тейс, О точности аппроксимации эллипсоидной нормой совместного спектрального радиуса, Линейная алгебра и ее приложения, 394: 1, стр. 91–107, 2005.
10. Т. Андо и М.-Х. Ши. «Одновременная сократимость». Журнал СИАМ по матричному анализу и приложениям, 19 (2): 487–498, 1998.
11. Блондель В.Д., Нестеров Ю.В. «Вычислительно эффективные приближения совместного спектрального радиуса». SIAM Журнал матричного анализа, 27 (1): 256–272, 2005.
12. П. Паррило и А. Джадбабайе. «Аппроксимация совместного спектрального радиуса с помощью суммы квадратов». Линейная алгебра и ее приложения, 428 (10): 2385–2402, 2008.
13. В. Протасов, Р. М. Юнгерс, В. Д. Блондель. «Совместные спектральные характеристики матриц: подход конического программирования». Журнал SIAM по матричному анализу и приложениям, 2008 г.
14. J. C. Lagarias и Y. Wang. «Гипотеза конечности для обобщенного спектрального радиуса набора матриц». Линейная алгебра и ее приложения, 214: 17–42, 1995.
15. T. Bousch и J. Mairesse. «Оптимизация асимптотической высоты для актуальных IFS, куч тетриса и гипотезы конечности». Журнал Американского математического общества, 15 (1): 77–111, 2002.
16. Блондель В. Д., Дж. Тейс и А. А. Владимиров, Элементарный контрпример к гипотезе конечности, SIAM Journal on Matrix Analysis, 24: 4, стр. 963–970, 2003.
17. Козякин В. Структура экстремальных траекторий дискретных линейных систем и гипотеза конечности, Автомат. Дистанционное управление, 68 (2007), вып. 1, 174–209 /
18. Кевин Г. Харе, Ян Д. Моррис, Никита Сидоров, Жак Тейс. Явный контрпример к гипотезе о конечности Лагариаса – Ванга, Успехи в математике, 226, стр. 4667-4701, 2011.
19. А. Чиконе, Н. Гульельми, С. Серра Капиццано и М. Зеннаро. «Свойство конечности пар знаковых матриц 2 × 2 через нормы вещественных экстремальных многогранников». Линейная алгебра и ее приложения, 2010.
20. Р. М. Юнгерс и В. Д. Блондель. «О свойстве конечности рациональных матриц». Линейная алгебра и ее приложения, 428 (10): 2283–2295, 2008.

дальнейшее чтение

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

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

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

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