Сходимость жадных алгоритмов

• Автор: Лившиц, Евгений Давидович
• Шифр специальности: 01.01.01
• Научная степень: Докторская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 215 с.

Оглавление
Введение

1 Скорость сходимости чисто жадного и ортогонального жадного алгоритмов

1.1 Сходимость жадных алгоритмов

1.2 Реализуемость жадных алгоритмов для дискретных словарей

1.2.1 Вспомогательные леммы

1.2.2 Доказательство теорем 1.1 и 1.2 •

1.3 Скорость сходимости жадных алгоритмов и наилучшис тп-членные приближения

1.4 Оценка снизу на скорость сходимости чисто жадного алгоритма

1.4.1 Общие формулы

1.4.2 Конструкция

1.4.3 Подбор параметров
1.4.4 Дальнейшие оценки
1.4.5 Окончание доказательства теоремы 1.
1.5 Оценка снизу на скорость сходимости ортогонального жадного алгоритма
1.6 Интерполяционные классы
1.7 Оценки сверху на скорость сходимости чистого жадного алгоритма для интерполяционных классов
1.7.1 Численные неравенства
1.7.2 Основные определения и неравенства для ЧЖА
1.7.3 Множества Д(то)
1.7.4 Оценка произведений атЪт
1.7.5 Доказательство теоремы 1.
1.8 Нижние оценки для интерполяционных классов
2 Скорость сходимости жадных алгоритмов для словарей с малой когерентностью
2.1 Неравенства типа Лебега
2.1.1 Вспомогательные леммы
2.1.2 Вспомогательные обозначения

2.1.3 Основные леммы
2.1.4 Доказательство теоремы 2.
2.2 Словари с ограниченной совокупной когерентностью
3 Жадные разложения
3.1 Возвратный жадный алгоритм
3.2 Сходимость возвратного жадного алгоритма. Доказательство
теоремы 3.
3.3 Скорость сходимости возвратного жадного алгоритма
3.3.1 Оценка
3.3.2 Основная лемма
3.3.3 Доказательство теорем 3.3 и 3.
3.4 Жадные разложения с неотрицательными коэффициентами .
3.4.1 Основные определения
3.4.2 Сходимость ПСЖА
3.4.3 Связь между СЖА и ПСЖА. Необходимое условие сходимости ПСЖА
4 Жадные алгоритмы в банаховых пространствах
4.1 Введение
4.2 Пример расходимости А-ЖА в гладком банаховом пространстве
4.3 Сходимость Д-ЖА
4.4 Некоторые геометрические свойства пространства 1Р, р > 2 . .
4.5 Система Хаара и система функций пропорциональных индикаторам двоичных промежутков
4.6 Схема доказательства теоремы 4.
4.7 Вспомогательные леммы
4.8 Доказательство теоремы 4.
4.8.1 Приближение характеристическими функциями двоичных промежутков
4.8.2 Двоичные деревья
4.8.3 Окончание доказательства теоремы 4.
4.9 Доказательство теоремы 4.
4.10 Сходимость и скорость сходимости А-ЖА по системе Хаара .
4.11 Сходимость и скорость сходимости А-ЖА по системе 1Р . . .
Литература

Введение
Теория приближения относится к тем областям математики, которые тесно связаны с прикладными задачами естествознания и техники. Увеличение мощности вычислительных систем, происходившее в последние десятилетия, позволило приступить к решению новых более вычислительноемких задач. Одной из них является построение “индивидуального приближения” для заданной функции / из некоторого класса К. Приближение предлагается строить как элемент линейного подпространства L из заранее определенного (по К) семейства линейных подпространств С. При этом выбор L Е С зависит от /, что отличает эту задачу от классической задачи аппроксимации класса К, где приближающее подпространство L выбиралось единым для всех / € К. Другими словами, класс К приближается нелинейным объектом Ube£ -k- Такие приближения имеют также важное теоретическое значение. Как было показано P.C. Исмагиловым [9], К.И. Осколковым [17] и В.Е. Майоровым [16] этот нелинейный (индивидуальный) подход может давать преимущества в некоторых классических задачах. Изучение оценок снизу для этого метода приближения было начато Б.С. Кашиным [10].
Начиная с 80-х годов 20-го века, в рамках математической статистики и теории приближения стали интенсивно изучаться жадные алгоритмы, что, с одной стороны, дало теоретическое обоснование ряда методов вычислительной математики, а, с другой стороны, позволило получить конструктивные способы нахождения наилучших m-членных приближений. Ключевую роль в формировании теории жадных алгоритмов сыграли работы Дж. Фридмана, В. Стузла, С. Маллата, Ж. Жапга, П. Хьюбера, JI. Джоунса, А. Бэррона, Р. ДеВора, В.Н. Темлякова, С.В. Конягина, Д.Донохо и др. ([46], [64], [53], [54], [25], [37], [58], [34], [41]). В наши дни жадные алгоритмы успешно применяются в задачах распознавания образов, медицины, финансовой математики, обработки сигналов и ряде других областей ([42], [85], [70], [66], [65])-
Необходимо отметить, что со временем большая часть результатов по жадным алгоритмам начала формулироваться и доказываться на языке теории функций. Более того, идеология теории функций в значительной степени определила направлёния дальнейших исследований жадных алгоритмов.
Пусть X = (X, II • Л) — действительное банахово пространство. Множе-

С помощью определения (1.2.13) и (1.2.11) оценим
(f,9i) = (/,3i> +n(pdgi),gi) = (f,PrXai)> + 7 (-^(91), Pt, (91)) >
> A-min ^7(Д 2 ^»0 +7||^ьЫ1|2- (1-2.16)
Если .92 S D (£>' U T>") и ||Pl(S2)II > P + 9, to согласно (1.2.13), (1.2.9) и (1.2.10) имеем
1(7,92)1 < {f,92) +i(Pl(9i),92) Если 92 Е V (V U D") и ||Pl(92)|| < В + 9, то согласно (1.2.13), (1-2.7), (1.2.12) и (1.2.11)
1(7,.92)1 < || = |(/,РьЫ)|+7|(РьЫ,Р£Ы)| <
< sup{f,PL(g)) + 7l|Pb(9i)l|2(l -9) < А-ДВ - ^p. + jWPLia^f-

(1.2.18)
Объединяя (1.2.16), (1.2.17), (1.2.18) с определением (1.2.14), получаем справедливость (1.2.15). □
Для произвольного элемента / 6 Н и 6 > 0 обозначим
£>(/):= (<72 GP: | L . gev )
B(f,S) :={/'е Я: ||/' - /|| < <5}.
Лемма 1.3. Пусть заданы замкнутое подпространство Lc Н, codimL < 00 и / € L, / Ф 0. Тогда для любого е > 0 существуют / е L, конечное непустое множество Т>о С Р ы <50 > 0, такие что f Е B(f,e) и для любого f Е L П Р(/, д0), выполняется равенство
' V{f) = Во-
Доказательство. Определим с помощью леммы 1.2 / € L и <5 > 0. Тогда множество
Pi ■■= [92 Е V : 1(7,92)1 > sup |(7,9)| -5) (1.2.20)
I gev J
конечно. Рассмотрим открытый шар В
В := B(f, min(d/3, б - \f- /||)).