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

Содержание
1 О скорости сходимости слабых жадных алгоритмов с наг раметром. 16
1.1 О решениях одного дифференциально-разностного неравенства. . . ............................................. 16
1.2 Оценка сверху скорости сходимости слабого жадного алгоритма с параметром....................................... 22
2 О сходимости ПСЖА в квазинормированных пространствах. 29
2.1 Критерий сходимости ПСЖА.............................. 29
2.2 Геометрический критерий сходимости в евклидовом пространстве.................................................. 34
3 Сходимость ПСЖА в функциональных пространствах. 36
3.1 Аналог леммы Филиппова - Освальда для ПСЖА и сходимость ПСЖА почти всюду................................... 36
3.2 Сходимость ПСЖА в Ьр при 1 < р < оо............... 41
3.3 Сходимость ПСЖА в Ьр при 0 < р < 1................ 45
3.4 Доказательство теоремы о сходимости ПСЖА в Ьр, при
О < р < 1............................................. 49
3.5 Сходимость ПСЖА в Ьр для периодических функций. . . 57
3.6 Сходимость ПСЖА для тригонометрических полиномов. . 60
1
$
Введение.
Данная работа посвящена изучению различных методов жадных аппроксимаций и их применению к решению некоторых задач теории приближений.
В первой части мы рассмотрим чистую жадную аппроксимацию (далее ЧЖА). В литературе ЧЖА часто называется не аппроксимацией, а алгоритмом, но мы будем употреблять в дальнейшем слово "аппроксимация," следуя терминологии В. Н. Темлякова. Дадим необходимые определения. Пусть Я - гильбертово пространство со скалярным произведением (•,■). Подмножество элементов D С Н назовем словарем, если ||p|j = 1 для любого g £ D и при этом замыкание линейной оболочки D в Я совпадает с Я. Для / е Я обозначим g = g(f) е D - элемент из D, который максимизирует |(/,р)| (предполагаем, что такой элемент всегда существует). Если таких элементов более одного, то будем выбирать в качестве g произвольный. Определим
G(f) = Gif, D) = {},д)д- R(f) = Rif,d) = / - Gif).
Определим ЧЖА как метод построения последовательностей Gm(f) и Rm(f) следующим образом: Я0(/) = /, Go(f) = 0. Далее но индукции
Gtn(f) = Gm-1(f) + G(Rm-1(f))
Ят(/) = / - Gm(f) = RlRn-lV))-
На каждом шаге индукции G(Rm-\(f)) может, вообще говоря, быть выбран несколькими способами. Полученные последовательности Gm(f ) и Rm(f) будем называть реализацией ЧЖА.
2
По-видимому, история жадных алгоритмов началась с работы Е. Шмидта (см. [1|), результат которой может быть интерпретирован, как сходимость ЧЖА в частном случае. Потом была работа Б.С. Стечкина и С.Б. Стечкина (см [2]), в которой также была доказана сходимость ЧЖА для специального словаря. Но существованию термина "жадный алгоритм,"мы обязаны именно исследованиям, которые начались с 80-х годов.
Впервые ЧЖА появился в статистике в работе Дж. Фридмана и В. Стузла под именем "Projection pursuit regression,"а также в теории передачи сигнала в работе С. Маллата и Ж. Жанга под именем "Matching pursuit."(см. [3], [4))
Жадные аппроксимации активно изучались с середины 80-х годов XX века. Основную роль в становлении теории жадных аппроксимаций сыграли Дж. Фридман, В. Стузл, С. Маллат, Ж. Жанг, П. Хыобер, Л. Джоунс, А. Бэррон, Р. ДеВор, В.Н. Темляков, С.В. Конягин, Д. Допохо и др.
В 1987 году Л. Джонс доказал сходимость ЧЖА для произвольного словаря ( см. [5]). После этого стала актуальной проблема оценки качества приближения ЧЖА на и-ом шаге. Оказалось, что для всего пространства Н данная задача не имеет смысла. Это можно проиллюстрировать следующим примером. Пусть D - ортонормированный базис. Тогда для любого е > 0, для любого п, существует элемент / £ Я, II/H = 1, такой, что ||Ят(/)|| >1—6. Достаточно взять / так, чтобы п его наибольших коэффициентов Фурье по базису D не превосходили ft.
Традиционно задача о скорости сходимости ЧЖА рассматривается на специальном подмножестве гильбертова пространства А\(D). Опре-
3
делим для словаря Я класс элементов Л°(Д М) = {/ е Я : / = £ OkWfe, w* G Д |А| < оо £ |с*| < Л/}
fc€Л fceA
Пусть A\(D,M) - замыкание в Я множества А?(Я, М). Положим
Ai (Я) = Um>oAi(.D, М).
Для / 6 Ai (Я) обозначим
= min М. feAi(D,M)
В данных обозначениях сформулируем проблему оценки скорости сходимости ЧЖА следующим образом: оценить величину
f{m) = sup ||/m - Gm(f, £>)|| • |/|^(0)
в зависимости от т.
Данная задача активно изучалась разными математиками, начиная с середины 90-х годов прошлого века. В 1996г. Р.А.ДеВором и В.Н.Темляковым была получена оценка
||/ - Gm(f)\\ ^ ТП~*\/\а1(0)у
подробнее см. [6].
В 1999г. С.В.Конягин и В.Н.Темляков [7] улучшили предыдущий результат, получив оценку :
Il/-Gm(/)||<4W-Ö|/Ul(z)).
При решении задачи о скорости сходимости ЧЖА исследовались оценки не только сверху, но и снизу. В 1996г. Р.А.ДеВором и
В.Н.Темляковым в работе [6] построен пример словаря, приближаемого элемента и реализации ЧЖЛ, для которой
\\/- СМ)\\ > \Лмп)Ш-1
Дальнейшее улучшение оценки снизу было получено в [8], где построен пример, когда
\\/-Ст(Л\\>\Лы»т-°-27.
Потом Е.Д. Лившиц (см. [9] и [10]) еще два раза улучшал оценку снизу. На сегодняшний день наилучшим результатом в этом направлении является пример, когда
\\Г-Ст(т>\/\мо)т-°-19.
Естественным обобщением ЧЖА является слабая жадная аппроксимация с параметром /3 (далее СЖА). Так же как и ЧЖА она строится с помощью индуктивной проце,чуры.
Определим СЖА как метод построения последовательностей С?т(/) и Ятт:{/) следующим образом: Яо(/) = /> Со(Я = 0- Далее по индукции
от(/) = ст_,(/) + |ас(лт_1(/))
Яп(Л = / - <?*,(/)•
Легко видеть, что при /3=1 мы получим ЧЖА. Оказалось, что при /3 < 1, скорость сходимости СЖА лучше по порядку, чем скорость сходимости ЧЖА. В [11] доказано, что:
||/-Ст(/)||<т-^|/и1(в).
Таким образом, при /У —► 0 показатель порядка оценки скорости сходимости стремится к