Совместный спектральный радиус матриц: приложения и методы вычисления. В.Ю.Протасов (МГУ) Геометрический смысл: Возьмём единичный шар в этой норме:

Геометрический смысл JSR

1960 Rota, Strang (теория нормированных алгебр) Барабанов, Козякин (динамическе системы с переключениями) 1991 Daubechies, Lagarias, Cohen, Heil, …. (теория всплесков) Micchelli, Prautzsch, Dyn, Dahmen, … (уточняющие схемы – теория приближений и дизайн кривых и поверхностей) Распределение случайных рядов (теория вероятностей), Асимптотика бинарной функции разбиения Эйлера (комбинаторика, теория чисел), Емкость кодов, оценка числа неперекрывающихся слов, теория графов,.... Приложения: Основные свойства

Всплески с компактным носителем : С.Малла, И.Мейер, И.Добеши, Ч.Чуи, А.Коэн, В.Дамен, и др. А.Хаар (1909), В.А. Котельников (1933), К.Э.Шеннон (1949),. I.Daubechies (1988) – всплески с компактным носителем.. Теория функций, теория приближений. Обработка сигналов. Диф. Уравнения (Вейвлет-Галёркин метод, и др.) Преимущества всплесков: Локализация (компактные носители), Быстрые алгоритмы вычисления коэффициентов, Характеризация функциональных пространств

Для построения системы всплесков с компактным носителем нужно решить масштабирующие уравнение (refinement equation) – разностное функциональное уравнение со сжатием аргумента. - последовательность комплексных коэффициентов. Это – обычное разностное уравнение, но с двоичным сжатием аргумента. Построение всплесков. Масштабирующие уравнения.

Примеры систем всплесков 1. Всплески Хаара (1909) Масштабирующее уравнение: Всплески Шеннона-Котельникова (1933, 1949) 4. Всплески Добеши (1988) Второй всплеск Добеши. Масштабирующее уравнение: Всплески Мейера (1986), Всплески Баттла-Лемарье (1987) Носитель некомпактен! Носитель некомпактен!

Если есть решение с компактным носителем, и Что известно о масштабирующих уравнениях ? Обратно, если, то есть решение с компактным носителем. Оно единственно с точностью о домножения на константу и сосредоточено на отрезке [0, N]. Но только в обобщённых функциях из 0N то Масштабирующая функция не бывает бесконечно-гладкой

Примеры 1. Тривиально: 01 Пример Пример Решение неустойчиво ! Малые изменения коэффициентов могут приводить к резким изменениям решения: Пример 4. Tо же с примером Примеры масштабирующих уравнений

Cavaretta, Dahmen and Micchelli (1991) Описание всех масштабирующих сплайнов с целыми узлами. Lawton, Lee and Sсhen (1995) Описание всех масштабирующих сплайнов. Для любого N существует конечное число масштабирующих сплайнов порядка N Berg and Plonka (2000), Hirn (2008) Cклассификация всех кусочно-гладких масштабирующих функций. Все кусочно-гладкие масштабирующие функции -- сплайны. Все они – линейные комбинации целых сдвигов B-сплайна.

Типичная масштабирующая функция и всплеск-функция Пример 5 03 показатель гладкости (показатель Гельдера) Непрерывна, но не дифференцируема Тем не менее, она дифференцируема почти всюду Локальная гладкость в точке x (максимальная гладкость) (минимальная гладкость) (изломы во всех двоично- рациональных точках) Фрактальная природа всплесков. Переменная локальная гладкость.

I.Daubechies, D.Lagarias, 1991 A.Cavaretta, W.Dahmen, C.Micchelli, 1991 C.Heil, D.Strang, 1994 Пример. Как определить, будет ли масштабирующая функция непрерывной ?

0N Максимальная локальная гладкость Минимальная локальная гладкость Гладкость почти всюду

Как вычислить или оценить JSR ? Сходимость к величине JSR при растущем к чрезвычайно медленная.

Blondel, Tsitsiclis ( ). Задача приближённого вычисления JSR для рациональных матриц NP-сложна. Задача определения: верно ли, что JSR строго меньше 1 (для рациональных неотрицательных матриц) алгоритмически неразрешима, начиная с размерноти d = 47. Не существует алгоритма, полиномиального по размерности d и по точности для приближения JSR с относительной погрешностью Отрицательные результаты о сложности задачи вычисления JSR:

Инвариантные нормы Теорема 2 (A.Дранишников, С.Конягин, В.Протасов, 1996) Теорема 1 (Н. Барабанов, 1988) Независимо был установлен двойственный факт:

X Y

Послеитераций получим нужное приближение Общее число операций Для d=2 число операций: При требуетсяопераций. При d > 2 непонятно как практически реализовывать Для d =2 алгоритм был запрограммирован И.Шейпаком в Алгоритм приближения инвариантной нормы многогранниками

Оценка JSR с помощью тензорных произведений матриц Протасов (1997), Zhow (1998), Blondel, Nesterov (2005) Определен в 1995 независимо: Y.Wang (p = 1), R.Q.Jia (для всех p)

Идея доказательства. p-инвариантные нормы. N F(N)

N 2r F(N 2r )

Алгоритм вычисления JSR поиском лучшей нормы в определенном семействе норм. Идея: мы не можем найти инвариантную норму. Тогда приблизим её с помощью норм из определеннго конечномерного класса. (стандартный трюк в теории приближений) (V.Protasov, R.Jungers, and V.Blondel, 2010) (V.Blondel, Yu.Nesterov, J.Theys, 2005) Рассмотрим сначала случай неотрицательных матриц

Случай произвольных матриц Эффективно решается методом внутренней точки. ЛП-задачи – частный случай.

Доказать больше иногда легче. Джордж Пойа «Математика и правдоподобные рассуждения» (1954) Если не получается хорошо приблизить JSR, можно попробовать … вычислить его точно. Если не получается что-то доказать, можно попробовать доказать больше.

Понятие экстремальной нормы

Как построить экстремальную норму ?

Будем строить единичный шар экстремальной нормы в качестве многогранника M. Оказывается, что такая норма существует для большинства семейств матриц. Наблюдение 1. Для приводимого семейства задача вычисления JSR сводится к Нескольким аналогичным задачам в меньших размерностях. Таким образом, предполагаем, что семейство неприводимо. Наблюдение 2. Если произведение П максимальное, то его максимальный собственный вектор v должен быть крайней точкой множества M. Если M – многогранник, то v -- его вершина. Итак, максимальные собственные векторы произведения П и всех его циклических перестановок -- вершины M. Наблюдение 3. Критерий остановки:

Каждый раз проверяем, будет ли новая точка принадлежать выпуклой оболочке предыдущих точек (ЛП задача). Алгоритм завершается, когда не появилось ни одной новой вершины. Инвариантный многогранник M – выпуклая оболочка всех точек, построенных алгоритмом Мертвые ветви ….. Алгоритм точного вычисления JSR (Н.Гуглиелми, В.Протасов, 2011)

Для каждой очередной вершины применяем критерий остановки: …..

Пример 1. Задача о плотности единиц в ромбе Паскаля: (S.Finch, P.Sebah, and Z.-Q.Bai, 2008) На самом деле, (алгоритм работает несколько секунд)

L.Euler (1728), A.Tanturri (1918), K.Mahler (1940), N.de Bruijn (1948) L.Carlitz (1965), D.Knuth (1966), R.Churchhouse (1969), B.Reznick (1990)

Для размерности 50 программа работает 5 минут, для размерности около 20 минут Пример. При d = 5 :

Функция разбиения Эйлера для троичного разложения:

Пример 3. Асимптотика числа слов двоичного алфавита без перекрытий. Задача сводится к вычислению JSR и LSR двух 20x20-матриц. Программа работает 8 минут

Вычисление JSR для случайных пар матриц

Вычисление JSR и LSR для случайных пар булевских матриц размерности d = 100.

Условия конечной сходимости алгоритма максимальноедоминирующее

Спасибо !