Тексты на английском
<<  The Levittowners Айпад 5 2012  >>
В.Ю.Протасов (МГУ)
В.Ю.Протасов (МГУ)
Совместный спектральный радиус (JSR)
Совместный спектральный радиус (JSR)
Геометрический смысл JSR
Геометрический смысл JSR
Приложения:
Приложения:
.
.
Построение всплесков
Построение всплесков
Примеры систем всплесков
Примеры систем всплесков
Но
Но
Примеры масштабирующих уравнений
Примеры масштабирующих уравнений
“ Типичная ” масштабирующая функция и всплеск-функция
“ Типичная ” масштабирующая функция и всплеск-функция
Как определить, будет ли масштабирующая функция непрерывной
Как определить, будет ли масштабирующая функция непрерывной
Как вычислить или оценить JSR
Как вычислить или оценить JSR
Инвариантные нормы
Инвариантные нормы
Все существующие методы вычисления JSR основаны на приближении
Все существующие методы вычисления JSR основаны на приближении
Отрицательные результаты о сложности задачи вычисления JSR:
Отрицательные результаты о сложности задачи вычисления JSR:
Sometimes easier to prove more George Polya «Mathematics and Plausible
Sometimes easier to prove more George Polya «Mathematics and Plausible
Метод точного вычисления совместного спектрального радиуса (N
Метод точного вычисления совместного спектрального радиуса (N
Понятие экстремальной нормы
Понятие экстремальной нормы
Будем строить единичный шар экстремальной нормы в качестве
Будем строить единичный шар экстремальной нормы в качестве
Алгоритм точного вычисления JSR (N
Алгоритм точного вычисления JSR (N
Пример 1. Задача о плотности единиц в ромбе Паскаля: (S
Пример 1. Задача о плотности единиц в ромбе Паскаля: (S
The Joint spectral radius
The Joint spectral radius
L.Euler (1728), A.Tanturri (1918), K.Mahler (1940), N.de Bruijn (1948)
L.Euler (1728), A.Tanturri (1918), K.Mahler (1940), N.de Bruijn (1948)
Пример
Пример
The Joint spectral radius
The Joint spectral radius
Функция разбиения Эйлера для троичного разложения:
Функция разбиения Эйлера для троичного разложения:
Пример 3. Асимптотика числа слов двоичного алфавита без перекрытий
Пример 3. Асимптотика числа слов двоичного алфавита без перекрытий
Вычисление JSR для случайных пар матриц
Вычисление JSR для случайных пар матриц
Вычисление JSR и LSR для случайных пар булевских матриц размерности d
Вычисление JSR и LSR для случайных пар булевских матриц размерности d
Доминирующее
Доминирующее
Спасибо
Спасибо

Презентация: «The Joint spectral radius». Автор: Name. Файл: «The Joint spectral radius.pps». Размер zip-архива: 654 КБ.

The Joint spectral radius

содержание презентации «The Joint spectral radius.pps»
СлайдТекст
1 В.Ю.Протасов (МГУ)

В.Ю.Протасов (МГУ)

Вычисление совместных спектральных характеристик линейных операторов

(1960) Joint spectral radius, Rota, Strang

(1960) Lyapunov exponent, Furstenberg, Kesten, (1968) Oseledec

(1995) p-radius, Lau, Wang

(1995) Lower spectral radius, Gurvits

The Joint spectral radius (JSR)

J.C.Rota, G.Strang (1960) -- Normed algebras

Molchanov , Pyatnicky, Opoytsev, Barabanov, V.Kozyakin,…(1988) Linear switching systems

Micchelli, Prautzch, Dahmen, Levin, Dyn, …… (1989) Subdivision algorithms

I.Daubechies, J.Lagarias (1991) Wavelets

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

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

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

Возьмём единичный шар в этой норме:

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

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

4 Приложения:

Приложения:

Основные свойства

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

5 .

.

.

.

I.Daubechies (1988) – всплески с компактным носителем.

Преимущества всплесков: Локализация (компактные носители), Быстрые алгоритмы вычисления коэффициентов, Характеризация функциональных пространств

Всплески с компактным носителем (compactly-supported wavelets)

Обработка сигналов

Теория функций, теория приближений

Диф. Уравнения (Вейвлет-Галёркин метод, и др.)

А.Хаар (1909), В.А. Котельников (1933), К.Э.Шеннон (1949),.

1980-90: С.Малла, И.Мейер, И.Добеши, Ч.Чуи, А.Коэн, В.Дамен, и др.

6 Построение всплесков

Построение всплесков

Масштабирующие уравнения.

Это – обычное разностное уравнение, но с двоичным сжатием аргумента.

Для построения системы всплесков с компактным носителем нужно решить масштабирующие уравнение (refinement equation) – разностное функциональное уравнение со сжатием аргумента.

- Последовательность комплексных коэффициентов.

7 Примеры систем всплесков

Примеры систем всплесков

1. Всплески Хаара (1909)

2. Всплески Шеннона-Котельникова (1933, 1949)

Носитель некомпактен!

3. Всплески Мейера (1986), Всплески Баттла-Лемарье (1987) Носитель некомпактен!

4. Всплески Добеши (1988)

Масштабирующее уравнение:

1

1

0

1

0

1

Второй всплеск Добеши. Масштабирующее уравнение:

3

3

0

0

8 Но

Но

, то есть решение с компактным носителем. Оно единственно

С точностью о домножения на константу и сосредоточено на отрезке [0, N].

Только в обобщённых функциях из

Масштабирующая функция не бывает бесконечно-гладкой

Что известно о масштабирующих уравнениях ?

Если есть решение с компактным носителем, и

То

Обратно, если

0

N

9 Примеры масштабирующих уравнений

Примеры масштабирующих уравнений

Примеры 1.

Тривиально:

0

1

Пример 2.

0

2

Пример 3.

0

3

Решение неустойчиво ! Малые изменения коэффициентов могут приводить к резким изменениям решения:

Пример 4.

Tо же с примером

10 “ Типичная ” масштабирующая функция и всплеск-функция

“ Типичная ” масштабирующая функция и всплеск-функция

(Максимальная гладкость)

(Минимальная гладкость)

(Изломы во всех двоично- рациональных точках)

показатель гладкости (показатель Гельдера)

Фрактальная природа всплесков. Переменная локальная гладкость.

Пример 5

0

3

Тем не менее, она дифференцируема почти всюду

Непрерывна, но не дифференцируема

Локальная гладкость в точке x

11 Как определить, будет ли масштабирующая функция непрерывной

Как определить, будет ли масштабирующая функция непрерывной

I.Daubechies, D.Lagarias, 1991

A.Cavaretta, W.Dahmen, C.Micchelli, 1991

C.Heil, D.Strang, 1994

Пример.

12 Как вычислить или оценить JSR

Как вычислить или оценить JSR

Сходимость к величине JSR при растущем к очень медленная.

13 Инвариантные нормы

Инвариантные нормы

Теорема 1 (Н. Барабанов, 1988)

Независимо был установлен ‘’двойственный’’ факт:

Теорема 2 (A.Дранишников, С.Конягин, В.Протасов, 1996)

14 Все существующие методы вычисления JSR основаны на приближении

Все существующие методы вычисления JSR основаны на приближении

инвариантного тела (многогранниками, эллипсоидами, и т.д.)

Kronecker lifting method (приближение инвариантной нормы тензорными произведениями) , protasov (1997), zhow (1998), blondel, nesterov (2005)

Все методы – для невысоких размерностей (до 5, реже – до 10)

Точность невысока. Относительная погрешность – от 2 до 20 %

Branch-and-bound method («разумный перебор») daubechies, lagarias (1991), grippenberg (1996), hechler, mossner, reif (2009)

Ellipsoidal norms, Ando, Shih (1998), Blondel, Nesterov, Theys (2004)

Sum-of-squares method (приближение инвариантной нормы суммами квадратов полиномов), parrilo, jadbabai (2008)

Conic programming approach, Protasov, Jungers, Blondel (2010)

15 Отрицательные результаты о сложности задачи вычисления JSR:

Отрицательные результаты о сложности задачи вычисления JSR:

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

16 Sometimes easier to prove more George Polya «Mathematics and Plausible

Sometimes easier to prove more George Polya «Mathematics and Plausible

Reasoning» (1954)

When trying to prove something, often a good strategy is to try to prove more.

(Если не получается что-то доказать, можно попробовать доказать больше).

Если не получается хорошо приблизить JSR, можно попробовать …

Вычислить его точно.

17 Метод точного вычисления совместного спектрального радиуса (N

Метод точного вычисления совместного спектрального радиуса (N

Guglielmi, V.Protasov, 2013).

Применим к любым размерностям (эффективен на практике в размерностях до 20, для неотрицательных матриц – до 100)

Сводит задачу вычисления JSR к поиску корня некоторого полинома

Позволил решить ряд открытых проблем теории чисел и комбинаторики

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

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

19 Будем строить единичный шар экстремальной нормы в качестве

Будем строить единичный шар экстремальной нормы в качестве

многогранника M . Оказывается, что такая норма существует для большинства семейств матриц.

Наблюдение 1. Для приводимого семейства задача вычисления JSR сводится к Нескольким аналогичным задачам в меньших размерностях. Таким образом, предполагаем, что семейство неприводимо.

Наблюдение 2. Если произведение П максимальное, то его максимальный собственный вектор v должен быть крайней точкой множества M. Если M – многогранник, то v -- его вершина.

Итак, максимальные собственные векторы произведения П и всех его циклических перестановок -- вершины M.

Наблюдение 3. Критерий остановки:

20 Алгоритм точного вычисления JSR (N

Алгоритм точного вычисления JSR (N

Guglielmi, V.Protasov, 2011)

Алгоритм точного вычисления JSR (N.Guglielmi, V.Protasov, 2011)

Каждый раз проверяем, будет ли новая точка принадлежать выпуклой оболочке предыдущих точек (ЛП задача). Алгоритм завершается, когда не появилось ни одной новой вершины.

Инвариантный многогранник M – выпуклая оболочка всех точек, построенных алгоритмом

‘’Мертвые’’ ветви

…..

21 Пример 1. Задача о плотности единиц в ромбе Паскаля: (S

Пример 1. Задача о плотности единиц в ромбе Паскаля: (S

Finch, P.Sebah, and Z.-Q.Bai, 2008)

На самом деле,

(Алгоритм работает несколько секунд)

22 The Joint spectral radius
23 L.Euler (1728), A.Tanturri (1918), K.Mahler (1940), N.de Bruijn (1948)

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)

24 Пример

Пример

При d = 5 :

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

25 The Joint spectral radius
26 Функция разбиения Эйлера для троичного разложения:

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

27 Пример 3. Асимптотика числа слов двоичного алфавита без перекрытий

Пример 3. Асимптотика числа слов двоичного алфавита без перекрытий

Задача сводится к вычислению JSR и LSR двух 20x20-матриц.

Программа работает 8 минут

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

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

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

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

= 100.

30 Доминирующее

Доминирующее

Максимальное

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

31 Спасибо

Спасибо

«The Joint spectral radius»
http://900igr.net/prezentacija/anglijskij-jazyk/the-joint-spectral-radius-128400.html
cсылка на страницу

Тексты на английском

46 презентаций о текстах на английском
Урок

Английский язык

29 тем
Слайды