Слабые жадные аппроксимации

• Автор: Сильниченко, Александр Владимирович
• Шифр специальности: 01.01.01
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 67 с.

Содержание

1 О скорости сходимости слабых жадных алгоритмов с параметром.

1.1 О решениях одного дифференциально-разностного неравенства. . . ,

1.2 Оценка сверху скорости сходимости слабого жадного алгоритма с параметром

2 О сходимости ПСЖА в квазинормированных пространствах.

2.1 Критерий сходимости ПСЖА

2.2 Геометрический критерий сходимости в евклидовом пространстве

3 Сходимость ПСЖА в функциональных пространствах.

3.1 Аналог леммы Филиппова - Освальда для ПСЖА и сходимость ПСЖА почти всюду

3.2 Сходимость ПСЖА в Ьр при 1 ^ р < оо

3.3 Сходимость ПСЖА в Ьр при 0 < р <

3.4 Доказательство теоремы о сходимости ПСЖА в Ьр, при
О < р <
3.5 Сходимость ПСЖА в Ьр для периодических функций. . .
3.6 Сходимость ПСЖА для тригонометрических полиномов. .

Введение.
Данная работа посвящена изучению различных методов жадных аппроксимаций и их применению к решению некоторых задач теории приближений.
В первой части мы рассмотрим чистую жадную аппроксимацию (далее ЧЖА). В литературе ЧЖА часто называется не аппроксимацией, а алгоритмом, но мы будем употреблять в дальнейшем слово "аппроксимация, "следуя терминологии В. Н. Темлякова. Дадим необходимые определения. Пусть Я — гильбертово пространство со скалярным произведением (•, •). Подмножество элементов D С Я назовем словарем, если ||g|| = 1 для любого g £ D и при этом замыкание линейной оболочки D в Я совпадает с Я. Для / £ Я обозначим g — g(f) £ D - элемент из D, который максимизирует |(/, р)| (предполагаем, что такой элемент всегда существует). Если таких элементов более одного, то будем выбирать в качестве g произвольный. Определим
G(f) = G{f, D) = if, g)g; Rif) = Rif, d) = f - Gif).
Определим ЧЖА как метод построения последовательностей Gm{f) и Rmif ) следующим образом: Яо(/) = /, б?о(/) = 0. Далее по индукции
G,nif) = Gm-iif) + G{Rm-i{f))
Rmif) =f- Gmif) = RiRm-xif)).
На каждом шаге индукции GiRm-iif)) может, вообще говоря, быть выбран несколькими способами. Полученные последовательности Gmif) и Rmif) будем называть реализацией ЧЖА.

По-видимому, история жадных алгоритмов началась с работы Е. Шмидта (см. [1]), результат которой может быть интерпретирован, как сходимость ЧЖА в частном случае. Потом была работа Б.С. Стечкина и С.Б. Стечкина (см [2]), в которой также была доказана сходимость ЧЖА для специального словаря. Но существованию термина "жадный алгоритм,"мы обязаны именно исследованиям, которые начались с 80-х годов.
Впервые ЧЖА появился в статистике в работе Дж. Фридмана и В. Стузла под именем "Projection pursuit regression,"а также в теории передачи сигнала в работе С. Маллата и Ж. Жанга под именем "Matching pursuit."(см. [3], [4])
Жадные аппроксимации активно изучались с середины 80-х годов XX века. Основную роль в становлении теории жадных аппроксимаций сыграли Дж. Фридман, В. Стузл, С. Маллат, Ж. Жанг, П. Хьюбер, Л. Джоунс, А. Бэррон, Р. ДеВор, В.Н. Темляков, С.В. Конягин, Д. Донохо и др.
В 1987 году J1. Джонс доказал сходимость ЧЖА для произвольного словаря ( см. [5j). После этого стала актуальной проблема оценки качества приближения ЧЖА на n-ом шаге. Оказалось, что для всего пространства Н данная задача не имеет смысла. Это можно проиллюстрировать следующим примером. Пусть D - ортонормированный базис. Тогда для любого е > 0, для любого та, существует элемент / £ Н, ||/|| = 1, такой, что ||АД(/)|| > 1 — е. Достаточно взять / так, чтобы та его наибольших коэффициентов Фурье по базису D не превосходили А Традиционно задача о скорости сходимости ЧЖА рассматривается на специальном подмножестве гильбертова пространства A(D). Опре-

которого верна ог^енка
1Ы1 ^

2.2 Геометрический критерий сходимости в евклидовом пространстве.
Как видно из предыдущего параграфа, формулировка критерия сходимости ПСЖА в общем случае громоздка, что затрудняет интуитивное понимание критерия и его проверку в большинстве случаев. Поэтому естественной задачей является получение критерия сходимости ПСЖА в более привычных терминах для некоторых частных случаев пространств. Этой задаче посвящен текущий параграф.
Пусть Н - гильбертово пространство. Точку ф е Н, будем называть пределом в слабом смысле для последовательности {<рп}, если для любого д е Н выполнено: (д,<рп) —> (д, ф) при п —> оо. Пусть В -множество точек ф, для которых существует подпоследовательность {фк}, 4>к & Упк, щ —» оо (к —> оо), ||^|| ^ 1, слабо сходящаяся к ф. Пусть А - замыкание выпуклой оболочки множества В.
Теорема 2.2.1 ПСЖА по системе {У„} сходится для любой последовательности ап —> 0 тогда и только тогда, когда внутренность множества А не пуста.
Доказательству теоремы предпошлем лемму.
Лемма 2.2.1 ПСЖА по системе {VI-} сходится для любой последова-тыъности {аД, а& —+■ 0 при к —■> оо, для любого / € Н тогда и только