Введение к работе
Актуальность темы. Теория ортогональных рядов (рядов Фурье) является одним из классических направлений математических исследований, которое начало развиваться в первой половине XIX века. В настоящее время имеется большое количество публикаций, посвященных как общей теории ортогональных рядов, так и разложениям в ряды Фурье по конкретным системам.
В последние десятилетия в результате широкого внедрения компьютерных технологий разложения в ряды Фурье по различным ортогональным системам стали широко использоваться на практике при решении задач хранения, обработки и передачи данных различной природы. При этом обрабатываемый объект (изображение, аудиофрагмент, результаты сделанных спутником измерений и др.) моделируется некоторым элементом / пространства со скалярным произведением Я, в Н выбирается подходящая, учитывающая специфику конкретной задачи полная ортогональная система {е„} j, где К — или некоторое натуральное число (в случае конечномерных пространств Н), или бесконечность, и работа ведется нр. г г.амим элементом -( " в гоопп^о,,,,»., в рЯД фурье по системе {e„}f=1, то есть с р ^ дЄпі Где д = ^sL ) т ряд сходится
п=1
к элементу /, и в случае бесконечномерных пространств его заменяют на частную сумму, приближающую элемент с некоторой допустимой погрешностью.
Причинами, приведшими к широкому внедрению рядов Фурье в решение прикладных задач, являются такие свойства ортогональных разложений, как простота вычисления коэффициентов, наличие тождества Бесселя, обеспечивающего возможность быстрой оценки погрешности, то есть разности между элементом и частной суммой разложения, а также так называемое свойство оперативности ("on-line" свойство). Последнее свойство заключающееся в том, что если точность, с которой iV-ая частная сумма приближает разлагаемый элемент, не является приемлемой, то для получения следующего приближения — (N + 1)-й частной суммы — достаточно вычислить еще один коэффициент, не производя пересчет уже вычисленных коэффициентов. Свойство оперативности позволяет, в частности, параллельно осуществлять разложение и передавать уже вычисленные коэффициенты.
Вместе с тем, ортогональные разложения обладают свойствами, кото-
рые с точки зрения практических приложении являются отрицательными. Во-первых, условие ортогональности является очень жестким условием на систему, значительно сужающим класс систем, по которым осуществляется разложение. Во-вторых, ортогональные разложения принципиально не позволяют корректировать погрешности, возникающие в вычислении коэффициентов: для любой числовой последовательности
к t~\K
{с„} 1, отличной от последовательности < /п > коэффициентов Фу-
к к
рье элемента / по ортогональной с и {еп}п=\, РЗД Y1 спеп& о схо-
дится к элементу, отличному от /, либо расходится (последний случай возможен если К — оо).
В связи с вышесказанным, возникает актуальная задача определить процесс разложения, наследующий положительные свойства ортогональных разложений, но не обладающий приведенными выше отрицательными с точки зрения практики свойствами. Решению этой задачи и посвящена данная работа. В работе рассматриваются орторекурсивные разложения и жадные разложения.
Понятие орторекурсивного разложения было введено Т. П. Лукашенко в 2000 году году1). В случае ортогональной системы орторекурсивное разложение дает в точности ряд Фурье разлагаемого элемента по этой системе.
Пусть ( Н, (, ) I — пространство со скалярным произведением над
полем действительных или комплексных чисел, {e„}^L1 система ненулевых элементов Н, f - некоторый элемент Н. Индуктивно определим последовательность остатков {rn(/)}L0 и последовательность коэффициентов \fn\ Положим
Ы/) = /
Если уже определен остаток г„(/), то положим
? _ \гп\}),Єп+\) , г\ ( 1\ 7
/п+1 - "7 Г, rn+i{f) — Т-Д/J - /„-цЄп+i.
(Єп+ЬЄп+lj
11 Лукашенко Т. П. Об оргорекурсивных разложениях по системе Фабера -Шаудера // Современные проблемы теории функций и их приложения. Тезисы докладов 10-й Саратовской зимней школы. — Саратов: Изд-во Саратовского университета, 2000. С. 83.
oo ^
Определение 1. Формальный ряд Yl fnen называйся орторекур
п=\
сивным разложением элемента f по системе {en}^_j
Т П Лукашенко показал что орторекурсивные разложения обладают рядом свойств, имеющих место для ортогональных разложений2) А именно, для орторекурсивных разложений справедливы тождество Бесселя, неравенство Бесселя, эквивалентность равенства Парсеваля и сходимости разложения к разлагаемому элементу
Схема орторекурсивного разложения допускает принципиально различные подходы можно изначально фиксировать систему {е„}=1, а можно на каждом шаге для данного элемента / (или для данного остатка гп(/)) выбирать из некоторого фиксированного множества очередной разлагающий элемент en+i(/) Второй подход реализуется, в частности, в жадных разложениях Существенным отличием орторекурсивных разложений по фиксированным системам и жадных разложений является отсутствие у последних линейности Приведенные выше свойства определяются лишь схемой орторекурсивного разложения и не зависят от способа выбора разлагающих элементов, таким образом они справедливы как для орторекурсивных разложений по фиксированной системе функций, так и для жадных разложений
При решении прикладных задач в процессе реализации разложений неизбежно возникают вычислительные ошибки (погрешности) Наиболее существенными являются ошибки возникающие при вычислении коэф фициентов разложения В связи с этим возникает необходимость формализации понятия ошибок в вычислении коэффициентов орторекурсивного разложения и изучения возможности коррекции возникающих погрешности за счет выбора разлагающей системы
Пусть [Н, ( , )) — пространство со скалярным произведением над полем действительных или комплексных чисел, {е^}^ система ненулевых элементов Я, / — некоторый элемент Я Индуктивно определим последовательность остатков разложения {г^(/)}^_0 и последовательность коэффициентов р а з л о ж е | /д | ; р х н и й индекс указывает
l J 71=1
на то, что в вычислении коэффициенюв разложения возможны ошибки) Положим
reo(f) = /
2> Лукашенко Т II О свойствах орторекурсивных разложений по неортогональным системам // Вестник Моек ун-та Сер I Матем Механ 2001 Л» 1 С 6 10
Если уже определен остаток rf((/), то коэффициент /„+1 запигпем в виде
fn+1~ (е„+ье„+1)(1+"+,)+Сп+Ь где єп+і и n+i — некоторые числа. Положим
00 Л
Определение 2. Формальный ряд ^ /^е„ называется орторекур-
п=1
сивпым разложением элемента f по системе {е^}^ с ошибками
в = {(^Ж,
Используемая форма записи ошибок допускает естественную интерпретацию: при малых по абсолютной величине значениях єп величину п можно трактовать как число, характеризующее абсолютную величину ошибки в вычислении коэффициента /*; при малых по абсолютной величине значениях „ величину єп можно трактовать как число, характеризующее относительную величину ошибки в вычислении коэффициента
Jn'
При практической реализации орторекурсивных разложений последовательность ошибок Е неизвестна, но в ряде случаев эта последовательность может быть оценена. Например, можно специально реализо-вывать вычислительную схему так, что ошибка при вычислении коэффициента /п не превосходит некоторую изначально выбранную величину.
Необходимо также формализовать понятие абсолютной устойчивости орторекурсивных разложений к определенному множеству ошибок, возникающих при вычислении коэффициентов разложения.
Определение 3. Пусть — некоторое непустое множество последовательностей числовых нар. Орторекурсивное разложение по системе ненулевых элементов {en}^Lj абсолютно устойчиво к ошибкам из множества , если для любого элемента / Є Н и любой последовательности Е = {(єп, n)KJLi орторекурсивное разложение элемента / по системе {е„} j с ошибками Е сходится к /.
Жадные разложения впервые встречаются (в неявном виде) в работе Б.С. и СБ . Стечкиных3). В статистике и теории передачи сигналов жадные разложения по конкретным системам изучались с 1980-х годов. При
"Стечкин Б.С., Стечкин СБ. Среднее квадратическое и среднее арифметическое // Докл. АН СССР. 1961. 137, №2. С. 287-290.
этом в теорию передачи сигнала жадные разложения вошли под названием Matching Pursuit, а в статистику — под названием Projection Pursuit Активное изучение общей теории жадных разложений было начато в 1990-е годы математиками университета Южной Каролины, США Жадные разложения — нелинейная процедура разложения В случае ортогональной системы классическое жадное разложение дает ряд Фурье разлагаемого элемента по этой системе, переставленный в порядке убывания модулей коэффициентов
Наиболее общим жадным алгоритмом, осуществляющим разложения в гильбертовых пространствах, является в настоящее время обобщенный приближенный слабый жадный алгоритм Соответствующее определение было впервые приведено в совместной работе автора и Е Д Лившица4'
Пусть ( Н, (, ) 1 гильбертово пространство над полем действительных или комплексных чисел, множество D элементов Н — нормированный словарь (то есть для любого элемента d є D справедливо равенство \\<Щ = 1 и замыкание линейной оболочки D совпадает с Н) Пусть также / — некоторый элемент Н, {tn}^=l - последовательность чисел из отрезка [0,1], {qn}~i ~ последовательность действительных неотрицательных чисел, {(n>ra)}^i последовательность числовых пар Определим индуктивно последовательность остатков {г„(/)}^д, последовательность коэффициентов \fn\ и последовательность разлагающих
І і n=l
элементов {en(/)}^Lj Положим
го(/) - /
Далее, если уже определен остаток г„(/), найдем элемент е„+і(/) Є D, удовлетворяющий условию
I (*»(/), e„+i(/))| > <n+iSup|(V„(/),e)| - qn+i.
(Если элементов удовлетворяющих этому условию несколько, в качестве en+i(/) выберем любой из них Если элементов удовлетворяющих этому условию, не существует, будем говорить, что осуществить разложение не удалось Отметим что последний случай возможен только если tn+\ = 1 и Яп+1 = 0 ) Положим
/п+1 = (!"«(/), Є„+і(/)) (1 + Є„+і) +
*)Галатенко В В , Лившиц Е Д Об устойчивости жадных разложений к ошибкам в вычислении коэффициентов // Современные проблемы теории функций и их приложения Тезисы докладов 12-й Саратовской зимней школы Саратов Изд-во ГосУНЦ "Колледж", 2004 С 51 52
Гп+і(І) = rn(f) - fn+ien+1(f)
Определение 4 Описанный выше процесс будем называть обоб щепным приближенным слабым жадным алгоритмом (gAWGA generalized Approximate Weak Greedy Algorithm) Если разложение удалось осуществить, формальный ряд ]Р fnGn(f) будем называть обобщенным приближенным слабым жадным разложением (или gAWGA разложением) элемента / по словарю D с ослабляющими последовательностями {n}^Ll, {<7n}^Ll И ПОСЛеДОВаТеЛЬНОСТЬЮ ОШИбоК {{^пЛп)}п-1
Если qn = „ = О для всех натуральных п, то gAWGA совпадает с введенным Р Грибонвалем и М Нилсеном приближенным слабым жад ным алгоритмом (AWGA Approximate Weak Greedy Algorithm5') Если для всех натуральных п выполняются равенства qn — „ = 0, еп = 0, то gAWGA совпадает с предложенным В Н Темляковым слабым жадным алгоритмом (WGA —Weak Greedy Algorithm6') Если qn — n = єп = 0 и tn = 1 для всех натуральных п то gAWGA совпадает с рассмотренным чисто жадным алгоритмом (PGA Pure Greedy Algorithm7')
Интересным представляется изучение тех свойств орторекурсивных разложений и жадных разложений, которые не имеют места для ортогональных разложений Важным свойством такого рода является возможность коррекции вычислительных ошибок, неизбежно возникающих при практической реализации разложений
Целью работы является изучение абсолютной устойчивости орю рекурсивных разложений и жадных разложений к погрешностям, возникающим в вычислении коэффициентов а также изучение свойств орто рекурсивных разлоений и жадных разложений по конкретным функциональным системам
Методы исследований включают как классические методы математического анализа и теории функций действительного переменного, так и активно развивающиеся в последние годы методы теории жадных разложений
Научная новизна Все результаты диссертации являются новыми и состоят в следующем
3 Gnbonval R Nielsen М Approximate Weak Greedy Algorithms // Adv Comput Math 2001 14
№4 P 361 378
9Temlyakov VN Weak greedy algorithms, // Adv Comput Math 2000 12 №2 З P 213 227 " Jones L К On a conjerture of Hubcr concerning the convergence of PP regression // Ann Statist
получены условия на систему элементов, достаточные для того, чтобы орторекурсивное разложение по этой системе было абсолютно устойчиво к некоторому широкому классу ошибок в вычислении коэффициентов:
исследована устойчивость полученных условий к малым изменениям системы;
приведен пример функциональных систем специального вида, удовлетворяющих полученным условиям, исследована сходимость разложений по этим системам (сходимость почти всюду, равномерная сходимость, сходимость в метриках LP);
получены условия на параметры обобщенного приближенного слабого жадного разложения, гарантирующие сходимость разложения к разлагаемому элементу;
для счетных словарей предложен метод разложения, близкий к обобщенным приближенным слабым жадным разложениям, в котором выбор разлагающих элементов осуществляется конструктивно;
- рассмотрены жадные разложения по системе, обеспечивающей лег
кий конструктивный выбор разлагающих элементов, изучена сходи
мость разложений по этой системе (поточечная, равномерная, в мет
риках LP), а также исследована возможность других способов выбора
коэффициентов разложения по этой системе.
Приложения. Работа носит теоретический характер. Полученные результаты могут найти применение в теории представления функций. Кроме того, полученные результаты могут быть использованы при создании алгоритмов обработки и передачи данных различной природы.
Апробация работы. Результаты диссертации докладывались на механико-математическом факультете МГУ: на семинаре по теории ортогональных рядов под руководством чл.-корр. РАН, проф. П. Л. Ульянова, проф. М.К. Потапова и проф. М.И. Дьяченко, на семинаре по теории функций действительного переменного под руководством проф. Т. П. Лукашенко, проф. В. А. Скворцова и м.н.с. А. П. Солодова, на семинаре по теории ортоподобных систем под руководством проф. Т. П. Лукашенко и асе. Т. В. Родионова, на семинаре по теории ортогональных рядов под
руководством чл.-корр. РАН, проф. Б. С. Кашина и проф. С. В. Конятина; в Математическом институте им. В.А. Стеклова РАН на семинаре по теории приближений под руководством проф. С. А. Теляковского; на конференциях молодых ученых механико-математического факультета МГУ (2001, 2002, 2003); на Воронежских зимних математических школах "Современные методы теории функций и смежные проблемы" (2001, 2003); на Саратовских зимних математических школах "Современные проблемы теории функций и их приложения" (2002, 2004); на международных школах-семинарах по геометрии и анализу памяти Н.В. Ефимова (Ростов-на-Дону: 2002, 2004): на Научной конференции "Ломоносовские чтения" (Москва, 2004). Цикл работ В. В. Галатенко "О разложениях по системе сигнумов" награжден медалью и премией РАН как лучшая студенческая работа 2002 года в области математики. По теме диссертации автором весной 2004 года был прочитан специальный курс на механико-математическом факультете МГУ.
Публикации. Список основных работ автора по теме диссертации приведен в конце автореферата (12 публикаций).
Структура работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы, содержащего 40 наименований. Общий объем диссертации составляет 93 страницы.
