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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16 X Y

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

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

19

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

21 N 2r F(N 2r )

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

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

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

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

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

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

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

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

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

31

32 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)

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

34

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

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

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

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

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

40 Спасибо !