Слабые жадные аппроксимации тема автореферата и диссертации по математике, 01.01.01 ВАК РФ

На нравах рукописи

Сильниченко Александр Владимирович

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

01.01.01 - вещественный, комплексный и функциональный анализ

4851903

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

2 8 ИЮЛ 2011

Москва -2011

4851903

Работа выполнена на кафедре нелинейного анализа и оптимизации Российского университета дружбы народов

Научные руководители: доктор физико-математических наук

профессор Конягин Сергей Владимирович доктор физико-математических наук профессор Протасов Владимир Юрьевич

Официальные оппоненты: доктор физико-математических наук профессор Лукашенко Тарас Павлович доктор физико-математических наук профессор Терехин Павел Александрович

Ведущая организация: Институт математики и механики Уральского отделения РАН

Защита состоится 2011 года в 16ч. 00 мин. на заседании диссертационного

совета Д 212.203.27 в Российском университете дружбы народов по адресу: г. Москва, ул. Орджоникидзе, д. 3, ауд. 495а.

С диссертацией можно ознакомиться в Учебно-научном информационном центре (Научной библиотеке Российского университета дружбы народов) по адресу: г. Москва, ул. Миклухо-Маклая, д. б.

Автореферат разослан X 9 , О ¿> 2011 г.

_____

кандидат физико-математических наук, доцент /

Общая характеристика работы.

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

Жадные аппроксимации - это способ нелинейного приближения функций с помощью некоторой фиксированной полной системы функций (б частности, переполненной системы), при котором выбирается конечное число элементов приближения с наибольшими, в том или ином смысле, коэффициентами. Жадные аппроксимации активно изучались с середины 80-х годов XX века. Основную роль в становлении теории жадных аппроксимаций сыграли Дж. Фридман, В. Стузл, С. Маллат, Ж. Жанг, П. Хьюбер, Л. Джоунс, А. Бэррон, Р. ДеВор, В.Н. Тепляков, Д. Донохо и др. Свое применение жадные аппроксимации нашли в теории обработки сигналов, передачи и хранения информации.

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

Во-первых, наличие хороших оценок на скорость сходимости жадных аппроксимаций позволяет применять их для практических задач аппроксимации при обработке сигналов.

Во-вторых, использование ПСЖА позволяет решить большое количество теоретических задач о системах представления. Для банаховых пространств работы в этом направлении были начаты В.И. Филипповым и П. Освальдом. Применение нового метода позволяет обобщить, а в некоторых случаях и улучшить, их результаты.

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

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

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

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

1) В работе приведена лучшая на сегодняшний момент оценка скорости сходимости жадной аппроксимации с параметром.

2) Введен новый вид жадной аппроксимации - ПСЖА, для него получены критерии сходимости в различных пространствах.

3) С помощью ПСЖА получены новые результатов в теории систем представления в пространствах Lp.

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

Практическая значимость. Работа носит теоретический характер. Улучшение оценок скорости сходимости популярных жадных аппроксимаций позволяет расширить область их применения для решения практических задач. Результаты, полученные для систем представления, позволяют строить простые системы представления и находить методы приближения, удобные в той или иной реальной ситуации.

Апробация работы. Основные результаты диссертации докладывались на научном семинаре кафедры нелинейного анализа и оптимизации РУДН в 2010 г., г. Москва (руководитель - д.ф.-м.н., профессор A.B. Арутюнов); на научном семинаре "Ортоподобные системьг"в 2006 г., г. Москва, МГУ им. М.В. Ломоносова, мех.-мат. фак-т (руководители - д.ф.-м.н., профессор Т.П. Лукашенко, к.ф.-м.н. Т.В. Родионов, к.ф.-м.н. В.В. Галатенко); на научном семинаре "Ортогональные и тригонометрические ряды"в 2009 г., г. Москва, МГУ им. М.В. Ломоносова, (руководители - д.ф.-м.н., профессор B.C. Кашин, д.ф.-м.н., профессор C.B. Конягин); на Миас-ской летней математической школе им. С.Б. Стечкина в 2004 г.. 2005 г., 2006 г.,

2010 г.; на Воронежской зимней математической школе в 2009 г.; на Саратовской зимней математической школе в 2006 г.; на конференции молодых ученых механико-математического факультета МГУ iim, М.В. Ломоносова в 2004 г., 2005 г., 2006 г. Публикации.

Основные результаты опубликованы в трех статьях и двух тезисах научных конференций.

Работы [1] и [2] соответствуют перечню ведущих журналов и изданий ВАК РФ. Структура и объем работы. Диссертация состоит из введения, трех глав, разбитых на параграфы, и библиографического списка, содержащего 19 наименований. Объем работы составляет 67 страницы.

Содержание работы.

Во введении обоснована актуальность исследования, проведен краткий исторический обзор наиболее важных результатов, и проанализированы результаты диссертации.

Пусть H - гильбертово пространство со скалярным произведением (•, •). Подмножество элементов D С Я назовем словарем, если ||g|| = 1 для любого g & D и при этом замыкание линейной оболочки D в Я совпадает с Я. Для / 6 Я обозначим g = g(f) 6 D - элемент из D. который максимизирует |(/,д)| (предполагаем, что такой элемент всегда существует). Если таких элементов более одного, то будем выбирать в качестве g произвольный. Определим

G(f) = <?(/, D) = Ц g)g- R(f) = Rif, d) = f- Gif).

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

Gm(f)=Gn-1(f)+G(Rm-l(f)), Rmif) — f — Gmif) = R(Rm-lif)).

На каждом шаге индукции элемент G(flm_i(/)) может, вообще говоря, быть выбран несколькими способами. Полученные последовательности Gmif) и Ят(/) будем называть реализацией ЧЖА.

Естественным обобщением ЧЖА является слабая жадная аппроксимация с пара-иетром /? (далее СЖА). Так же как и ЧЖА она строится с помощью индуктивной процедуры.

Определим СЖА как метод построения последовательностей (?т(/) и Дт(/) следующим образом: Ло(/) = /, С7о(/) = 0- Далее по индукции

ст(/) = ст_1(/) + /гс(лт_1(/)), ЯМ) = / - <?«(/)•

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

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

а/'(х) + 1>/'(х — 1) ^ /(х) — /(х — 1).

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

Лемма 1 Пусть неотрицательная функция / на промежутке [0, +оо) дифференцируема и удовлетворяет неравенству:

а/\х) + 6/'(х - 1) < ¡(х) - Дх - 1), х € (1, +оо). (1)

Тогда, если пара чисел (а, Ь) принадлежит одному из следующих множеств:

П! = |(а,Ь): 6 > ае-~2, а € (0,

П2 = |(а, Ь) : Ь > I — а, О ^ |! то функция / ограничена на [0. +зо).

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

Теорема 1 Для любого словаря D и любого элемента f 6 ^i(O) верпа оценка: где 7 - корень уравнения h(x) = 0 на отрезке [1,1.5] и

ад = ( l + ^l + JL)-!-^, (2)

0 - параметр СЖА.

Теорема 1 дает улучшение верхней оценки скорости сходимости СЖА. В случае ЧЖА - показатель порядка оценки скорости сходимости равен 0.182, т.е.

||/-Gm(/,D)||<q/Ul(D)m-°-182.

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

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

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

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

1) Ух 6 X ||х|| ^ 0 и ||з:|| = 0 О х = 0,

2) Vzex, Va е я IMI = H 1М1>

3) Vx, у 6 Х\\х + у\\ ^ С(||г|| + |М|), где С - абсолютная константа. Заметим, что нормированное пространство является частным случаем квазинор-

мированного с константой С = 1. Одним из наиболее распространенных примеров квазинормированиого пространства, не являющегося нормированным, является Lp с квазинормой II/H = (J\f(x)\vdx)l/p при 0 < р < 1.

Введем понятие системы представления. Система элементов {уЛ^о называется системой представления в X, если для любого элемента f € X существует набор

ос

чисел {о„}^0 такой, что f = Yl ап'-Рп■ В отличие от базиса, набор коэффициентов

п=0

{а„} может быть не единственным.

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

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

Определим ПСЖА для любого элемента / € X с помощью следующей индуктивной процедуры. Пусть /0(/) = 0, г0(/) = /, k0(f) = 0. Если определены /„(/), г„(/) и k„(f), то выберем kn+í(f) > kn(f) и элемент 6 L¡¿n+1 так, чтобы

1МЯ - №„J| < inf \\rn(f) - V\\+aa.

Далее положим fn+i{f) = fn{f) + и rn+i(/) = f ~ /n+i(/)-

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

Система представления также может быть определена как система подпространств {14}, Уь С X, если для любого элемента / е X существует последовала

тельность элементов рь € Vi¿, такая, что f = Y2 '-Рк■ Последнее определение

(.—i

С

является обобщением классического определения системы представления. Для того, чтобы в этом убедиться, достаточно положить Vi =< <рк >• Так как ПСЖА определена для системы подпространств, то она может быть использована н в этом случае.

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

Рассмотрим следующую задачу: при каких условиях па систему подпространств {14} ПСЖА по этой системе сходится для любой последовательности ец —> О

при к —> оо. Мы не будем в данной диссертации рассматривать вопросы сходимости ПСЖА в зависимости от последовательности погрешностей {ак}.

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

Теорема 2 ПСЖА по системе {V/t} сходится для любой последовательности {Qfc}^0, Q-k —> 0 при к —> оо, тогда и только тогда, когда существует а < 1 такое, что для любых f € X и N существуют п > N и ip s L„ такие, что

II/-ИК 41/11- (3)

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

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

Пусть Я - гильбертово пространство. Точку у е Я, будем называть пределом в слабом смысле для последовательности если для любого g 6 Я выполнено:

(<7. Vn) —* (</> Ф) ПРИ п —> оо. Пусть В -множество точек ф, для которых существует последовательность {v?n}, ||Уп|| = 1, ft 6 Vn, слабо сходящаяся к гр. Пусть А -замыкание выпуклой оболочки множества В. Для гильбертова пространства удается получить следующий критерий сходимости.

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

Проиллюстрируем данное утверждение простым примером. Пусть Н = R2, подпространства Vk - одномерны. Из теоремы 2 следует, что в этом случае сходимость ПСЖА эквивалентна существаванню двух и более предельных точек у последовательности единичных векторов из V*, не симметричных относительно начала координат.

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

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

Будем изучать системы представления в LP(R), порожденные сжатиями и сдвигами заданной последовательности функций. Впервые в общем виде данный вопрос был поднят 1995 г. Филипповым и Освальдом 1 . Пусть у? 6 suppy? С [0,1].

Рассмотрим систему двоичных сжатий сдвигов ipk,i{x) = — г), к е Z, к ^ 0,

г = 0,..., 2к — 1. Возникает задача: при каких условиях система {уз^} является системой представления в Lv[0,1]?

Филиппов и Освальд доказали следующие утверждения: 1

1) при р ^ 1, / tp(x)dx ф 0, tp G Lp, система {y?*,t} является системой представле-

о

ния в Lp.

2) при р < 1, <р ф 0, ip € Ь2 система {vt.i} является системой представления в Lp.

Третья глава посвящена различным обобщениям и улучшениям результата Филиппова - Освальда. В первом параграфе доказан технический результат. Пусть {¡р(к)} - последовательность функций из LP(R), где 0 < р < оо, и {A'jt}JL0 - неограниченная последовательность положительных чисел. Определим ^\{х) = tp(l\NkX + i), где к (г N, к ^ 0, i 6 Z. Пусть V^ - подпространства, порожденные элементами <p£J при фиксированном к и i £ Z. Тогда имеет место следующее утверждение.

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

НХ[о,1] - Ay^J|Mr) <<т. (4)

1Filippov 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.

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

системе подпространств V*. к ^ О сходится для любой функции / € £р(Е).

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

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

1) для любого к функции ¡р^ € ¿1(К) П £Р(Е), где р ^ 1.

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

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

к

4) существует последовательность положительных чисел {£„}, е„ —> 0 при п —* со, такая, что f \ф№{х)\р(1х < £„ и f \р№(х)\с1х < е„ при любом к.

К\[—п,п] К\[-п,п]

5) для любого е ^ О существует 7^0 такое, что для любого числа к и любого

множества А с к, А) < 7, выполнено: / < е и / < е.

а а

Тогда для любой последовательности (о* —► 0 при к —> оо) ПСЖА по

системе подпространств 14. к ^ 0 сходится для любой функции / €

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

1

функции ¡р пространству Ьр, а третье условие утверждает, что f р(х)ёх ^ 0.

о

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

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

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

2) существуют константы 0 < а < Ь такие, что а ^ рйх и

к

/ ^ Ь при любом к,

к

3) существует последовательность положительных чисел {£„}, Еп ~* О при п —> оо, такая, что / \р^(х)\р(1х ^ £„ и [ \^к\х)\гйх ^ £„ при любом к.

К\[-п,п] К\[-п,п1

Тогда для любой последовательности {а*}^ (а^ —> 0 при к —> оо) ПСЖА по системе подпространств 14, к ^ 0 сходится для любой функции f 6 Lp(R).

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

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

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

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

Пусть {с/1} - последовательность 2TV; - периодических функций. Тогда сжатия - сдвиги = (p^(NkX + i) являются 2 - периодическими функциями. Пусть 14 -подпространства, порожденные элементами tp^j при фиксированном к и г 6 Z. Рассмотрим вопрос приближения периодических функций с помощью введенных подпространств. На задачу исследования периодических функций натолкнул вопрос, сформулированный Е.Д. Лившицем в 2007 г.

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

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

1) для любого к имеем.: tp^ 6 Lr[—Nt, Nk], где 2 > г > р 4- 1,

Nt

2) существуют константы 0 < а < Ь такие, что а Щ f \pW(x)\pdx и

-nk

Nk

J \^k\x)\rdx ^ 6 при любом k,

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

3) существует послсдовате^гъность положительных чисел {£„}, £п —> О

при п —> оо, такая, что при любом k J \if^(x)\pdx < £„ и

{-nk,nk}\|-r.,n]

J I ^(iH'iif,.

Тогда для любой последовательности (otk —> О при к —» оо) ПСЖА по

системе подпространств V^. к ^ 0 сходится для любой функции / £ Lp[—1,1].

В последнем параграфе третьей главы расмотрсно применение данного результата для периодических функций к тригонометрической системе. Полученный критерий как раз и является решением задачи, поставленной Е.Д. Лившицем. Пусть 14 - подпространства, порожденные наборами тригонометрических функций sinmj.x, cos т^х, sin(mfc + l)i, cos(mji + l)i,..., sin(mjt+i — l)x, cos(m^+i — l)i, где {nijt} - возрастающая последовательность натуральных чисел.

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

Теорема 7 ПСЖА по систелie подпространств 14 сходится для любой последовательности погрешностей (аь —» 0 при к —> оо) и любой функции / € Lp[—7г,7г] тогда и только тогда, когда последовательность разностей {mit+i — mfc} , isN неограничена.

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

Публикации по теме диссертации.

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

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

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

4. Силышченко A.B.. "О сходимости порядкосохранякнцих жадных алгоритмов," Современные методы теории функций и смежные проблемы, материалы конференции Воронежской зимней математической школы, 2009, стр. 164-165

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

Силышченко Александр Владимирович

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

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

Silnichenko Alexander V.

"Weak Greedy approximations" Annotation

The different types of Greedy approximations are studied. We get new estimates for rate of convergence of Pure Greedy Approximation and Weak Greedy Approximation with parameter. New type of Greedy approximations, called Order-Reserving Weak Greedy Approximation(ORWGA) are defined. Criterion of convergence for ORWGA are prooved. Further the application of ORWGA to the decision of problems on representation systems in Lr.

Подписано в печать 17.06.2011 Формат 60x88 1/16. Объем 1.0 п.л. Тираж 100 экз. Заказ № 1121 Отпечатано в ООО «Соцветие красок» 119991 г.Москва, Ленинские горы, д.1 Главное здание МГУ, к. А-102

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

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

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

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

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

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

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

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

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

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

3.4 Доказательство теоремы о сходимости ПСЖА в Ьр, при

О < р < 1.

3.5 Сходимость ПСЖА в Ьр для периодических функций.

3.6 Сходимость ПСЖА для тригонометрических полиномов.

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

В первой части мы рассмотрим чистую жадную аппроксимацию (далее ЧЖА). В литературе ЧЖА часто называется не аппроксимацией, а алгоритмом, но мы будем употреблять в дальнейшем слово "аппроксимация, "следуя терминологии В. Н. Темлякова. Дадим необходимые определения. Пусть 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) =f- Gm(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)|| < C\f\Al{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|| ^ М ||г„(/) - <И| + Оп. к>кп,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^0 такое, что для любого числа к и любого множества АсМ, < 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(k\Nk% + г) являются 2 - периодическими к) функциями. Пусть Vfc - подпространства, порожденные элементами <рк [ при фиксированном к и i € Z. Рассмотрим вопрос приближения периодических функций с помощью введенных подпространств.

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

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

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

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

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 — í)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 29208, 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