Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Лившиц, Евгений Давидович
01.01.01
Докторская
2010
Москва
215 с.
Стоимость:
499 руб.
Оглавление
Введение
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)
1(7,.92)1 < |,92)| + 7|<РьЫ,92>| = |(/,РьЫ)|+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: |, 52)| = sup | (/, 9) 11, (1-2.19)
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- /||)).
Название работы | Автор | Дата защиты |
---|---|---|
Спектральная теория операторов, интегралы типа Коши и меры Кларка | Капустин, Владимир Владимирович | 2013 |
Оценка ряда Дирихле в полуполосе, показатели которого - нули произведения Вейерштрасса с нерегулярным поведением | Сергеева, Дина Ильдаровна | 2007 |
Дробные классы Соболева на бесконечномерных пространствах | Никитин, Егор Владимирович | 2013 |