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

Данная работа посвящена изучению различных методов жадных аппроксимаций и их применению к решению некоторых задач теории приближений.

В первой части мы рассмотрим чистую жадную аппроксимацию (далее ЧЖА). В литературе ЧЖА часто называется не аппроксимацией, а алгоритмом, но мы будем употреблять в дальнейшем слово «аппроксимация, «следуя терминологии В. Н. Темлякова. Дадим необходимые определения. Пусть H — гильбертово пространство со скалярным произведением (•,•). Подмножество элементов D С H назовем словарем, если || <71| = 1 для любого g € D и при этом замыкание линейной оболочки D в H совпадает с Н. Для /? H обозначим g = g (f) Е D — элемент из D, который максимизирует |(/, (предполагаем, что такой элемент всегда существует). Если таких элементов более одного, то будем выбирать в качестве g произвольный. Определим.

G (f) = G (f, D) = (/, д) дR (f) = Д (/, d) = f — G (f).

Определим ЧЖА как метод построения последовательностей Gm (f) и Rm (f) следующим образом: Ro (f) = /, GoCf) = 0- Далее по индукции.

Gm (/) = Gmi (/) + C?(JRm-i (/)).

Rmif) =fGm (f) = R (Rm-l (f)).

На каждом шаге индукции Gr (i?mi (/)) может, вообще говоря, быть выбран несколькими способами. Полученные последовательности Gm (f) и Rm (f) будем называть реализацией ЧЖА.

Первая глава диссертации посвящена улучшению оценки сверху скорости сходимости СЖА. В параграфе 1.1 рассматривается вспомогательная задача, результаты исследования которой будут использованы в дальнейшем для оценки скорости сходимости ЧЖА сверху.

Пусть на промежутке [0, +оо] функция / неотрицательна, дифференцируема в каждой точке и на (1, +оо) удовлетворяет дифференциально-разностному неравенству af'(x) + bf (x — 1) ^ f (x) — f (x — 1).

Требуется найти все пары параметров уравнения (о, Ь) при которых все решения неравенства ограничены на [0, +оо]. Будет доказано следующее утверждение.

Лемма 1 Пусть неотрицательная функция f на промежутке [0, +оо) дифференцируема и удовлетворяет неравенству: af{x) + bf (x — 1) ^ f (x) — f (x — 1). (1).

Тогда, если пара чисел (а, Ъ) принадлежит одному из следующих множеств: ili = j (a,&): Ь > ае°~2, а е (0, fi2=j (a, 6): b > 1 — а, а > ij, то функция f ограничена на [0, +оо).

Применяя лемму 1, во втором параграфе первой главы мы получим оценку на скорость сходимости СЖА. Будет доказана следующая теорема:

Теорема 1 Для любого словаря D и любого элемента / € А (D) верна оценка:

II/ - Gm (/, D)|| < CfAl{D)m-*fci, где 7 — корень уравнения h (x) = 0 на отрезке [1,1.5], где — параметр СЖА.

Теорема 1 дает улучшение верхней оценки скорости сходимости СЖА. В случае ЧЖА — показатель порядка оценки скорости сходимости равен 0.182. Показатель порядка предыдущей оценки скорости сходимости был равен 0.177. Теперь разница показателей степени в оценках сверху и снизу для ЧЖА составляет менее 0.008. В случае? —" 0 показатель порядка оценки скорости сходимости равен 0.27, что на 0.02 лучше, имевшейся до этого оценки Темлякова, равной 0.25.

Таким образом, оценка скорости сходимости ЧЖА улучшена, а в случае СЖА наглядно продемонстрировано улучшение скорости сходимости при уменьшении параметра ?.

Вторая и третья главы будут посвящены исследованию систем представлений с помощью жадных аппроксимаций. Начнем с необходимых определений.

Линейное пространство X назовем квазинормированным, если выполнены следующие условия:

1)УхеХ ||ж|| ^ 0|| и ||s|| = 0 ^ х = 0,.

2) /х е X, Va е R ||ш-|| = а \х\,.

3) Уж, у е Х\х + у\ < С (|М| + |М|), где С — абсолютная константа.

Заметим, что нормированное пространство является частным случаем квазинормированного с константой С — 1. Одним из наиболее распространенных примеров квазинормированного пространства, не являющегося нормированным, является Ьр с квазинормой ||/|| = (/ /(х)рс1х)1^р при 0 < р < 1.

Введем понятие системы представления. Система элементов называется системой представления в X, если для любого элемента / 6 оо.

X существует набор чисел {ап}^=0 такой, что / = X) ап^РпВ отличие п—0 от базиса, набор коэффициентов {ап} может быть не единственным.

Жадные аппроксимации, рассмотренные выше, не удобны при изучении систем представлений. Ряд, полученный с помощью СЖА, не является рядом по системе элементов словаря, так как при приближении с помощью СЖА элементы, используемые на различных шагах, могут повторяться. Для преодоления описанной проблемы введем новый метод жадной аппроксимации, которую будем называть порядкосохраняющей слабой жадной аппроксимацией (в дальнейшем ПСЖА).

Пусть 14 — последовательность линейных подпространств из X, {а^} - набор положительных чисел.

Определим ПСЖА для любого элемента / € X с помощью следующей индуктивной процедуры. Пусть /0(/) = 0, г0(/) = /, /с0(/) = 0. Если определены /"(/), гп (/) и &-п (/), то выберем кп+х (/) > кп (/) и элемент Ч>кп+1 е Ькп+1 так, чтобы.

IМ/) — <^п+1|| ^ М ||г&bdquo-(/) — <И| + Оп. к>кп, 1р? Ук.

Далее положим /п+х (/) = /п (/) + (ркп+1 и гп+х (/) = / - /"+!(/).

Данную процедуру мы называем «жадной» так как, аналогично клас сическим жадным аппроксимациям, мы на каждом шаге стремимся максимально уменьшить норму остатка. 11 Слабость «выражена в наличии констант призванных решить проблему существования точной нижней грани в определении ПСЖА. Термин «порядкосохраняю-щая» связан с тем, что ПСЖА на каждом шаге выбирает элементы только из подпространств с номерами, большими, чем уже использованные. Т. е результат приближения можно рассматривать как ряд по системе элементов из заданных подпространств, где некоторые элементы могут быть нулевыми. Легко заметить, что при таком определении сходимость ПСЖА по системе одномерных подпространств {Уп}, натянутых на соответствующие элементы срп, является достаточным условием для того, чтобы система была системой представлений в X.

В работе Терехина (см. [14]) система представления определяется как система подпространств {14}, 14 С X, если для любого элемента / существует последовательность элементов (р^ е 14, такая, что оо = Фк' Последнее определение является обобщением классического к=1 определения системы представления. Для того, чтобы в этом убедиться, достаточно положить 14 =< <рк >¦ Так как ПСЖА определена для системы подпространств, то она может быть использована и в этом случае.

Прежде чем переходить к конкретным случаям использования ПСЖА, изучим вопрос о ее сходимости. Этому будет посвящена вторая глава.

Рассмотрим следующую задачу: при каких условиях на систему подпространств {14} ПСЖА по этой системе сходится для любой последовательности {ск/с}?1о> ак 0 при к оо. Мы не будем в данной диссертации рассматривать вопросы сходимости ПСЖА в зависимости от последовательности погрешностей {о^}.

В первом параграфе второй главы будет рассмотрен вопрос о сходимости ПСЖА в произвольном квазинормированном пространстве с непрерывной квазинормой. Для таких пространств получен следующий критерий сходимости.

Теорема 2 ПСЖА по системе {114} сходится для любой последовательности аь —> 0 при к —оо, тогда и только тогда, когда существует, а < 1 такое, что для любых / е X и N существуют п > N и <р € Уп, что.

II/ -ИК <т||/||. (3).

Как видно из формулировки, проверка данного критерия на практике является довольно сложной задачей. Поэтому хотелось бы в частных случаях получить более наглядные критерии сходимости.

Этой задаче для гильбертовых пространств будет посвящен 2 параграф второй главы.

Пусть Н — гильбертово пространство. Точку ф € Н, будем называть пределом в слабом смысле для последовательности {(/?" }, если для любого д? Н выполнено: (д:(рп) {9,Ф) ПРИ п 00• Пусть Вмножество точек ф, для которых существует последовательность {<рп}, Н^Н = 1) <Рп € Уп, слабо сходящаяся к ф. Пусть, А — замыкание выпуклой оболочки множества В. Для гильбертова пространства удается получить следующий критерий сходимости.

Теорема 3 ПСЖА по системе {14} сходится в гильбертовом пространстве для любой последовательности ап —> 0 тогда и только тогда, когда внутренность множества, А не пуста.

Проиллюстрируем данное утверждение простым примером. Пусть Н = Ж2, подпространства 14 — одномерны. Легко показать, что в этом случае сходимость ПСЖА эквивалентна существаванию двух и более предельных точек у последовательности единичных векторов из 14 не симметричных относительно начала координат.

Критерий сходимости ПСЖА в дальнейшем будет активно использоваться при применении ПСЖА к конкретным задачам.

В третьей главе будет рассмотрено применение ПСЖА к задачам о системах представлений в Ьр.

Будем изучать системы представления в ЬР (Ш.), порожденные сжатиями и сдвигами последовательности функций. Впервые в общем виде данный вопрос был поднят в работе [12]. Пусть (р е яиррср 6 [0,1].

Рассмотрим систему двоичных сжатий сдвигов = (р (2кх — г), к € Z, к ^ 0, г == 0, ., 2к — 1. Возникает задача: при каких условиях система {</?£, г} является системой представлений в Ьр[0,1]?

Филиппов и Освальд в [12] доказали следующую теорему: 1.

Теорема А. (Филиппов — Освальд) 1) при р ^ 1, f (р (х)с1х ф 0, </? € о.

Ьр, система является системой представлений в Ьр.

2) при р < 1, ф ^ 0, 1р Е ?, 2 система {<Рк,{} является системой представлений в Ьр.

Третья глава будет посвящена различным обобщениям и улучшениям результата Филиппова — Освальда. В первом параграфе будет дор казан технический результат. Пусть — последовательность функций из? Р (К), где 0 < р < оо, и — неограниченная последовательность положительных чисел. Определим = А^ж + г), где к? М, к ^ 0, г € Z. Пусть — подпространства, порожденные элеменк) тами (р)[ ! при фиксированном к ж {? Z. Тогда имеет место следующие утверждение:

Лемма 2 Пусть существует, а < 1, номер ко и сдвиг ¿-о такие, что для любого числа I существует А, для которого верно неравенство:

Х[о, 1]- А^о||ьр (к) <а. (4).

Тогда для любой последовательности (а^ —> 0 при к —> оо).

ПСЖА по системе подпространств 14, к ^ 0 сходится для любой функции f? Ьр (Щ.

Во втором параграфе будет рассмотрена задача о сходимости ПСЖА в ЬР (Ш) при 1 ^ р < оо. Будет получена следующая теорема о сходимости ПСЖА.

Теорема 4 Пусть выполнены следующие условия:

1) для любого к функции ср^? 1а (М) П ЬР (М), где р ^ 1.

2) существует константа Ь такая, что для всех к выполнено:

3) существует константа 5 > 0 такая, что при всех к верно.

ЦУ*)(*)<�Й|>*. к.

4)существует последовательность положительных чисел {£п}, еп —" 0 при п —> оотакая, что / <�р (кх)р (1х ^ еп и.

Ж[-п, п].

J (р (кх)с1х ^ £п при любом к.

Ш[-щп.

5) для любого е ^ 0 существует 7⁰ такое, что для любого числа к и любого множества АсМ, < 7, выполнено: / <? и 1<рЮ (1-)(И<�е. А.

Тогда для любой последовательности (ак —> 0 при к оо).

ПСЖА по системе подпространств к ^ 0 сходится для любой функции f е Ьр (Ж).

Данный результат является непосредственным обобщением результата Филиппова — Освальда. Действительно, в случае одной фиксированной функции (р (х) с носителем на отрезке [0,1] второе, четвертое и пятое условия теоремы 4 выполняются автоматически. Первое условие трансформируется в требование принадлежности функции 1р пространству Ьр, 1 а третье условие утверждает, что / ф 0. о.

В третьем параграфе будет рассмотрен вопрос о сходимости ПСЖА в ЬР (Ш) при 0 < р < 1. Получен следующий результат:

Теорема 5 Пусть р < 1, последовательность чисел {Щ} не ограничена и выполнены следующие условия:

1) для любого к выполнено ср^ € Ьр (Ш), € ЬГ (Ж), где 2 > г > Р + 1;

2) существуют константы 0 < а < Ь такие, что, а ^ / ф (кх)р (1х ж и J <�рЮ (х)Чх < Ь при любом к, к.

3)существует последовательность положительных чисел {£п}- £п —> 0 при п —оо, такая, что / <�р№{х)р<1х ^ £п и.

Щ-п, п] п при любом к, тогда для любой последовательно.

Е[-н, п] emu (dk —> 0 при к —"• oo) ПСЖА no системе подпространств.

Vf-, к ^ 0 сходится для любой функции f? Ьр (Ж).

Будут приведены примеры, доказывающие неулучшаемость условий 2 и 3 теоремы. Для любого q < р + 1 В. И. Ивановым построен пример функции /? Lp, набор подпространств V/c и последовательность погрешностей {ак} для которых ПСЖА не сходится.

Также будет доказано, что в случае классической задачи Филиппова-Освальда (т.е. задачи на отрезке для сдвигов-сжатий одной функции) можно брать q = р + 1. Это утверждение не следует в явном виде из теоремы и требует более тонких рассуждений. Непосредственно из теоремы 5 следует результат только для q > р + 1. В качестве следствия доказано, что на отрезке из сходимости ПСЖА следует, что система сжатий-сдвигов будет системой представлений в классическом смысле.

Четвертый параграф будет полностью посвящен доказательству предыдущей теоремы.

В пятом параграфе рассмотрена задача о сходимости ПСЖА для периодических функций.

Пусть — последовательность 2Ni — периодических функций. Тогда сжатия — сдвиги ipf1] = ip (kNk% + г) являются 2 — периодическими к) функциями. Пусть Vfc — подпространства, порожденные элементами <рк [ при фиксированном к и i € Z. Рассмотрим вопрос приближения периодических функций с помощью введенных подпространств.

Имеет место следующая теорема:

Теорема 6 Пусть 0 < р < 1, последовательность чисел {iV^} неогра-ничена и выполнены следующие условия: r.

1) для любого к имеем: cpW? Lr[—Nk, iVjfe], где 2 > г > р + 1,.

2) существуют константы 0 < а < b такие, что, а ^ Nk Nk f ip (kx)pdx и f tpw (x)rdx < b при любом k, -NkNk.

3)существует последовательность положительных чисел {£п}, еп —" О при п —> оотакая, что при любом к выполнено f tpV){x)*dx ^£пи f 14>W (x)Tdx < ?",.

— Nk, Nk}l-n, n] [^, iVfc][-n, n] тогда для любой последовательности (ак О пРи к оо).

ПСЖА по системе подпространств V&, к ^ О сходится для любой функции f eLp[-1,1].

В последнем параграфе третьей главы будет расмотрено применение результата для периодических функций к тригонометрической системе. Пусть Vk — подпространства, порожденные наборами тригонометрических функций sin mjcX, cos irikX, sin (m^ + l) x, cos+ 1) ж,., sin (mfc+i — i) x, cos (rr?/c+i — 1) ж, где {m^} - возрастающая последовательность натуральных чисел.

Получен следующий простой критерий сходимости для ПСЖА.

Теорема 7 ПСЖА по системе подпространств V^ сходится для любой пследовательности погрешностей {"aJ^Lo (аь ~0 пРи к оо) и любой функции / € Lp—7г, 7г] тогда и только тогда, когда последовательность разностей {rrik+i — неограничена при к? N.

Теорема 7 дает ответ на вопрос, поставленный Е. Д. Лившицем в 2007 году.

Таким образом в третьей главе рассмотрены применения ПСЖА к различным системам функций в Lp. Основными результатами являются улучшение и обобщение известной теоремы Филиппова — Освальда о системах представлений.

1. Schmidt Е. «Zur Theorie der linearen und nichtlinearen 1. tegralgleichungen,» Math. Ann (1906;1907). 63. P. 433−476.

2. Стечкин B.C., Стечкин С. Б. «Среднее квадратическое и среднее арифметическое,» Докл. АН СССР Т. 137(1961), № 2. стр. 287−290.

3. Friedman J.H., Stuetzle W. «Projection pursuit regression» J. Amer. Statist. Assoc. 76(1981), P. 817−823.

4. Mallat S., Zhang Z. «Matching pursuit with time-frequcncy dictionaries,» IEEE Trans. Signal Process. ?1(1993), № 12 P. 3397−3415.

5. Jones L. «On a conjecture of Huber concerning the convergence of projection pursuit regression» Ann. Statist. 15(1987), P. 880−882.

6. DeVore R.A. and Temlyakov V. N, «Some remarks on Greedy Algorithms,» Adv. Comput.Math. 5(1996), P. 173−187.

7. Konyagin S.V. and Temlyakov V.N., «Rate of convergence of pure greedy algorithm,» East Journal On Aproximations, 4(1999), P. 493−499.

8. Livshitz E.D. Temlyakov V.N., «Two lower estimates in greedy approximation,» Constr. Approx., 19(2003), Щ, P. 509−523.

9. Лившиц Е. Д. «О скорости сходимости чистого жадного алгоритма,» Магпем. Зам., 73(2003), № 3. стр. 539−552.

10. Лившиц Е. Д. «О нижних оценках скорости сходимости жадных алгоритмов,» Изв. РАН Серия Матем. 73(2009), № 6. стр. 95−130.

11. Temlyakov V.N., «Greedy expansions in Banach Spaces,» Department of Mathematics, University of South Carolina, Columbia, SC 29 208, Research report 2003, 06, preprint.

12. Filippov V.I., Oswald P., «Representation in Lp by Seriess of Translates and Dilates of One Function,» Journal of Approximation Theory, 82(1995) P. 15−29.

13. Иванов В. И., «О представлении функций в пространствах Lp по системам сжатий и сдвигов,» Тезисы докладов Всероссийской конференции «Современные проблемы математики, механики, информатики». Тула: ТулГУ.2000. С 33−34.

14. Терехин П. А., «Неравенства для компонентов суммируемых функций иих представления по элементам системы сжатий и сдвигов Известия ВУЗов, 8(1999), стр. 74−81.

15. Сильниченко A.B., «О сходимости порядкосохраняющих слабых жадных алгоритмов,» Матем. заметки, 84(2008), № 5, стр. 795−800.

16. Сильниченко A.B., «О скорости сходимости жадных алгоритмов,» Матем. заметки, 76(2004), Щ, стр. 628−631.

17. Сильниченко A.B., «О скорости сходимости жадных алгоритмов,» тезисы докладов 26-ой конференции молодых ученых мех-мата МГУ, стр. 111.

18. Сильниченко A.B., «О сходимости порядкосохраняющих жадных алгоритмов,» Современные методы теории функций и смежные проблемы, материалы конференции Воронежской зимней математической школы, 2009, стр.164−165.

19. Сильниченко A.B., «О сходимости порядкосохраняющих жадных алгоритмов Lp,» Российский университет Дружбы Народов, 2011.