'

Совместный спектральный радиус матриц: приложения и методы вычисления.

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

X Y


Слайд 16

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


Слайд 17

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


Слайд 18


Слайд 19

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


Слайд 20

N2r F(N2r)


Слайд 21

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


Слайд 22

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


Слайд 23

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


Слайд 24

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


Слайд 25

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


Слайд 26

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


Слайд 27

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


Слайд 28

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


Слайд 29

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


Слайд 30


Слайд 31

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)


Слайд 32

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


Слайд 33


Слайд 34

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


Слайд 35

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


Слайд 36

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


Слайд 37

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


Слайд 38

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


Слайд 39

Спасибо!


×

HTML:





Ссылка: