Е-энтропия и табулирование компактных классов функций тема автореферата и диссертации по математике, 01.01.01 ВАК РФ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ■ ' и О,',

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

Потапов Владимир Николаевич

е-ЭНТРОПИЯ И ТАБУЛИРОВАНИЕ КОМПАКТНЫХ КЛАССОВ ФУНКЦИЙ

Специальность 01.01.01 — математический анализ

АВТОРЕФЕРАТ

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

Новосибирск — 1997 г.

Работа выполнена на кафедре математического анализа Новосибирского государственного университета.

Научный руководитель: Официальные оппоненты:

доктор физико-математических наук, профессор Р. Е. Кричевский. доктор физико-математических наук, профессор С. К. Водопьянов, доктор физико-математических наук, профессор В. Д. Степанов.

Ведущая организация:

Механико-математический факультет Московского государственного университета им. М. В. Ломоносова.

Защита диссертации состоится " ' ' " 1997 г. в /р ча-

сов на заседании диссертационного совета К 002.23.02 в Институте математики им. С. Л. Соболева. СО РАН (630090, г.Новосибирск, пр. ак. Коп-тюга 4).

С диссертацией можно ознакомиться в научной библиотеке Института математики им. С. Л. Соболева СО РАН.

Автореферат разослан " М " 1997 г.

Ученый секретарь л ^ ^ /

диссертационного совета К 002.23.02, /¿/с /

/

кандидат физико-математических наук * ^ •/ А. С. Романов

/ '

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Одним из главных вопросов классической теории приближений является оценка точности, с которой функция из некоторого функционального класса может быть приближена с помощью различных методов аппроксимации. Решение этой проблемы было получено для самых различных классов функций и аппаратов приближения. Однако, важно не только сравнить между собой различные методы приближения, но и выяснить насколько их точность близка к наилучшей возможной. Решению этой проблемы посредством вычисления поперечников и е-энтропии различных функциональных множеств посвящены многочисленные работы А.Н.Колмогорова, А.Г.Витушкина, К.И.Бабенко, В.М.Тихомирова, В.Д. Ерохина и других исследователей. Подробный обзор указанного круга вопросов имеется в работе В.М.Тихомирова [14].

Понятие е-энтропии было введено А.Н.Колмогоровым в работах [7,8], как обобщение идеи характеризовать "массивность" метрического компакта мощностью его наиболее экономных покрытий. ^-Энтропией вполне ограниченного множества X называется величина Нх{£), равная логарифму мощности минимального (по мощности) покрытия множества X множествами диаметром не более 2е. Здесь и далее подразумевается логарифм по основанию 2. В диссертации исследуется проблема получения асимптотических (при е —► 0) оценок г-энтрошш компактных подмножеств функциональных пространств.

Пусть множество ^(Х) состоит из вещественнозначных ограниченных функций, определенных на некотором компакте X, модули непрерывности которых ограничены сверху некоторой неотрицательной, полуаддитивной функцией ш. В работах А.Н.Колмогорова, В.М.Тихомирова [10], А.Г.Витушкина [4], А.Ф.Тимана [12-13] были предложены различные условия на множество X, обеспечивающие справедливость асимптотического равенства

2»х(е) -яРв(Х)(ы(£)) при £ —» 0.

Для классов функций, определенных на некотором связном компакте К метрической размерности 1 и, обладающих конечным числом производных А.Н. Колмогоровым и В.М.Тихомировым [10] получен следующий результат. Обозначим через Рп+а(Кт) множество п-раз дифференцируемых ограниченных на Кт вещественнозначных функций, каждая производная п-ого порядка которых удовлетворяет условию Гёльдера с показателем а. В [10] показано, что

^„(К^М-Е"^ При £ —► 0. Аналогичный результат получен В.И.Арнольдом для пространствах2. Ее-

ли К = [0, 27г] и через обозначить множество суммируемых с

квадратом функций, (п + с*)-ая производная в смысле Вейля которых ограничена в I2, то

НР2+а(к)(е) =21оёе • (п + а)е-1,1п+а)(1 + 0(1/п)) при с -> 0,п -» оо.

В.М.Тихомиров [14] распространил оценку В.И.Арнольда на пространства V.

Наиболее общий результат, касающийся оценки ¿-энтропии классов п-раз дифференцируемых функций в Ьр, был получен М.Ш.Бирманом и М.З.Соломяком [3]. Для соболевских классов \¥%(1т), заданных на единичном кубе 1т в Кт в норме пространства Ьч, ими было доказало, что если компактно вкладывается в Ья(1т), то

Я^р(/т)(е) ж £ тп/п при £ д.

Понятие ¿-энтропии функционального множества тесно связано с проблемой кодирования функций, состоящей в следующем: для каждой функции из некоторого компактного множества необходимо построить такую таблицу (код функции), по которой функцию можно восстановить с заранее заданной точностью. Основными параметрами эффективности метода кодирования являются длина кода, то есть объем таблицы по которой можно восстановить функцию, сложность составления таблицы и сложность восстановления функции из ее таблицы. Кроме того, естественно ввести в качестве критерия эффективности метода кодирования следующую величину — сложность получения из таблицы функции значения функции в единственной точке. Задача одновременной минимизации всех четырех параметров кода называется задачей табулирования. Проблема оценки эффективности методов кодирования явилась одним из главных оснований для введения понятия е-энтропии множества, поскольку £>энтропия множества является нижней гранью длины кода элементов множества, а также сложности кодирования и декодирования.

Связь понятия е-энтропии с теорией кодирования и различные направления решения задачи кодирования описаны А.Н.Колмогоровым в [9]. Проблемам кодирования и нахождения сложности вычисления непрерывных и дифференцируемых функций посвящены работы Ю.П.Офмана [11], Е.А.Асарина [1], К.И.Бабенко [2] и С.Б.Гашкова [5, б], использовавших различные формализации понятия сложности вычисления функции.

Целью работы является, во-первых, получение новых асимптотических (при е —* 0) оценок £-энтропии компактных подмножеств функциональных пространств, во-вторых, построение эффективных методов табулирования.

Методика исследований. В работе использованы методы классического анализа, в частности, методы приближения гладкой функции кусочно-постоянными и кусочно-полиномиальными функциями. При исследовании свойств компактных подмножеств в Lp была применена теория всплесков (wavelets) и многомасштабного приближения (multiresolution approxi-matiuon), разработанная С.Мала (S.Mallat) [17] и И.Добшес (I.Daubechies) [15, 16]. Оценки е-энтропии были получены посредством построения е-сетей и е-различимых подмножеств.

Научная новизна. В диссертации получены следующие новые результаты:

1. Предложены необходимые и достаточные условия на множество X, обеспечивающие справедливость асимптотического равенства

Як,(Ме)) = 0(2Ях(Е)) при е —► 0.

2. Получено обобщение оценки е-энтропии множества Fn+a(X) на случай, когда X — произвольный, возможно несвязный, компакт.

3. Получены оценки е-энтропии компактных подмножеств пространства Lp{0,1], состоящйк из функции, производные которых обладают ограниченным интегральным модулем непрерывности.

4. Предложены методы табулирования w-непрерывных функций и п-раз дифференцируемых функций в норме пространства С, а также функций, обладающих ограниченным интегральным модулем непрерывности, п-раз дифференцируемых функций и функций с ограниченным изменением в пространствах Lp[0,1]. Все предлагаемые методы позволяют строить е-прп-ближающие таблицы функций асимптотически минимальной (с точностью до порядка) длины. Сложность кодирования и декодирования этих таблиц также асимптотически минимальна. При этом сложность вычисления зналения функции в точке из е-приближающей таблицы не превышает О (log* 1/е) арифметических операций для всех предлагаемых методов, где через log* обозначен итеративный логарифм (черезвычайно медленно растущая функция).

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

Апробация работы. Основные результаты работы докладывались на международных научных конференциях по теории информации ISIT-95 (Whinster, Canada) и по прикладной и индустриальной математике ИНПРИМ-96 (Новосибирск). Все результаты докладывались на семинаре отдела геометрии и анализа Института математики им. С.Л.Соболева СО РАН.

Публикации. По теме диссертации автором опубликованы работы [18-22].

Объем и структура диссертации. Диссертация состоит из введения, четырех глав и списка литературы. Объем диссертации — 79 страниц.

СОДЕРЖАНИЕ РАБОТЫ

Первая глава диссертации посвящена исследованию е-энтропии и е-покрытий вполне ограниченных множеств. Здесь перечислены основные свойства е-энтропии, а также предложены определения множеств равномерного и выпуклого типа.

Определение. Вполне ограниченное подмножество X некоторого метрического пространства будем называть множеством выпуклого типа, если существует выпуклая (вниз) функция / : Е+ —> К+, /(0) = 0, такая что /(0 ж 2И*<-1М при г -> оо.

Примером пространства выпуклого типа может служить любое выпуклое множество в Ет, множества положительной меры Лебега в Кт, а также пространства липшицевых, дифференцируемых и аналитических функций.

Определение. Вполне ограниченное подмножество X некоторого метрического пространства будем называть пространством равномерного типа, если его £-энтропия обладает следующим свойством:

Существуют такие вещественные числа (3 > 1, С > 0 и ео > 0» что для любого е < £о справедливо неравенство Нх(Рс) + С < #х(е).

Классы множеств равномерного и выпуклого типа являются наиболее широкими классами вполне ограниченных множеств для которых справедливы заключения теоремы 3.1 и теоремы 3.2 соответственно.

В лемме 1.1 показано, что все связные множества являются множествами равномерного типа.

Лемма 1.1 Пусть X — связное, вполне ограниченное подмножество некоторою метрического пространства. Тогда существует ео > О, что для любого е, ео/4 > е > 0, справедливо неравенство

Нх(е)>1 + Нх(4е).

Лемма 1.2 иллюстрирует равномерность убывания е-энтропии множества выпуклого типа при возрастании е.

Лемма 1.2 Пусть X — вполне ограниченное множество выпуклого типа, тогда существуют С > 1 и ео > 0 такие, что для любых ех и е?,

£1 < £2 < £о, выполняется неравенство

2ЯхЫ ^ 2Нх(ех) ~ г2'

Из последнего неравенства при £ < ^ следует, что

ЯХ(2С£) + 1<ЯХ(£),

то есть класс множеств равномерного типа включает множества выпуклого типа.

Известно ( см., например, [10]), что если X — открытое ограниченное подмножество т-мерного нормированного векторного пространства, тогда Ях(е) = (1 + о(1))тпк^(^) при е —» 0. То есть в конечномерном пространстве скорость роста £-энтропии множества зависит от размерности множества. Поэтому для вполне ограниченных подмножеств метрического пространства естественно ввести понятие метрической размерности (размерности по Хаусдорфу):

¿т(Х) = Нш

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

Следующая лемма показывает, что множества положительной метрической размерности являются множествами равномерного типа.

Лемма 1.3 Пусть X — вполне ограниченное множество, 0 < (1т{Х) < оо и существует такая постоянная С, что справедливо неравенство

\Нх(е)-<1т(Х)1ое1/е\<С,

тогда X является множеством равномерного типа.

В частности канторово множество имеет метрическую размерность равную 1/к^З и является примером несвязного множества равномерного типа.

Кроме того, в первой главе вводится понятие £-покрытия и порожденного е-покрытия.

Определение. Совокупность множеств Л называется е-покрытнем множества А, если объединение элементов Л содержит А и диаметр каждого элемента Л не превосходит 2е. ех-Покрытие Л\ называется порожденным £о-покрытием Ко, если каждый элемент покрытия Лх является объединением элементов пЬкрытия До-

В лемме 1.4 показано, что для любого £о-покрытия 7?о существует порожденное им £х-покрытие Л\ (ео £1) такое, что число элементов в Л1

незначительно превышает минимально возможное число элементов в г\-покрытии множества.

Лемма 1.4 Пусть X — вполне ограниченное метрическое пространство, Ло — его £о-покрытие, 0 < ео < £1/2. Тогда существует ех-покрытле йх пространства X, порожденное покрытием До такое, что

|Й1| < 2"х(Е1-2£О)

Понятие порожденного покрытия и лемма 1.4 используются при доказательстве теорем 3.1-3.3. Наиболее важным свойством покрытия Дх, порожденного покрытием До является то, что функция постоянная на каждом элементе покрытия Дх является постоянной и на каждом элементе покрытия Ло.

Во второй главе вводятся понятия связанные с задачей табулирования. Пусть Е = {0,1}, обозначим через Е" множество двоичных последовательностей длины N. Пусть 5 — некоторое конечное множество, кодом множества 5 называется инъективное отображение К : Б —► Длиной кода К называется величина Ь(К) = N.

Сложностью кодирования К называется величина Ь(К) равная наибольшему по всем 5 € 5 количеству операций над битами, которое необходимо затратить для вычисления К(з).

Сложностью декодирования К называется величина с1(К) равная наибольшему по всем е € К (Б) количеству операций над битами, которое необходимо затратить на вычисление К~1(е).

Если 5 С то можно определить еще один параметр эффективности кода К. Сложностью покоординатного декодирования К называется величина в!(К) равная наибольшему по всем г = 1.. . тп и всем е € К {Б) количеству операций над битами, которое необходимо для вычисления в,, где з = К~1(е).

Пусть М — некоторое вполне ограниченное множество в метрическом пространстве Пусть Я — некоторая конечная е-сеть множества М в пространстве Р. Тогда е-приближающей таблицей (е-кодом) множества М называется код множества Д.

Из перечисленных выше определений непосредственно вытекает, что для произвольной е-приближающей таблицы К множества М справедливы неравенства

(1) Нм(е)<Ь(К), Нм(е)<1(К), Нм{е)<й{К).

В диссертации применяется следующий способ построения е-приближаю-щих таблиц в функциональных пространствах с базисом. Пусть Р —

вполне ограниченное подмножество нормированного векторного пространства V. Пусть найдется такое конечномерное подпространство Ут и е-сеть Л множества Р1, такая что Я С Ут- Рассмотрим базис <р1,...,<рт пространства Ут и линейное отображение р : Ут —> Кт, которое ставит в соответствие каждому вектору V € Ут набор из его координат. Пусть К — некоторый код множества р(Я) С Мт, тогда отображение К. = К о р является, в соответствии с определением, е-приближающей таблицей множества Из определения е-кода К, видно, что Ь(К.) = Ь(К). Сложность кодирования и декодирования К относительно базиса {¡р,} определим следующим образом: ¿<Д/С) = Ь(К) и с11р(1С) = й(К). Кроме того можно определить сложность покоординатного декодирования К относительно базиса {¥><}= =

Если У — функциональное пространство, то есть V = {/ : X —> У}, то определим величину «¿'^(/С) — количество операций, которое необходимо затратить для получения значения функции / в точке из е-приближающей таблицы £(/) функции /. Определим величину <^(/С) формально следующим образом: пусть 1^(х) — число базисных функций </?{ неравных 0 в точке х 6 X и = тах1бх 1<р(х), тогда =

Если кусочно-постоянная функция задана набором своих значений, то для вычисления ее значения в любой точке не требуется дополнительных операций. Поэтому сложность кодирования, декодирования, покоординатного декодирования и вычисления из кода значения функции в точке относительно базиса, состоящего из индикаторов непересекающихся сегментов, мы будем считать абсолютной и обозначать через ¿(/С), с?(/С), в!(К), в."(К) соответственно.

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

Лемм а 2.2 Пусть У\ и У-х — нормированные векторные пространства, ^ л б — вполне ограниченные подмножества пространств У^ и У2 соответственно. Пусть р — линейное отображение р : У\ —» У^ такое, что Ух = р(У\), р(^) Об и для каждого / 6 У\ справедливо неравенство ИЛЬ < С||р(/)||2, где С — некоторая постоянная, а || Ц1 и || Ц2 нормы в VI и Ух соответственно. Тогда если К — некоторый е-код множества О, то К, = К о р является Се-кодом множества Р, причем Ь(К) = Ь(К).

Заметим, что если в условиях предыдущей леммы дополнительно предположить, что У-х = и {у1}1=1...т некоторый базис множества .Р, а отображение р ставит в соответствие каждому / € ^ его координаты в этом базисе, то = Ь(К), = с1(К), ¿'^(К.) = (К) по определению этих

величин.

Обозначим через — тп-мерный шар в Кш в норме пространства

lp, радиуса г, то есть

т i=l

Лемма 2.3 Для каждого е > О существует е-код К множества В^г), такой что

L{K) < m log ^ + Cim, t{K) < C2m log T~,

d(K) < C3m log d'(K) < C4 log - log log m, £ £

где CUC2)C3, С a — некоторые постоянные.

Пусть V — конечномерное векторное пространство. В декартовом произведении Уш введем норму следующим образом:

|Н| = max ||vi||) где v = (i>i,... ,vm),vi G V.

t—l...m

Обозначим через Б^[У](г) — шар радиуса г в Vm, то есть

Лемма 2.4 Для каждого £ > 0 существует такой £-код К множества B°m[V}(r), что

L(K) < mHB(£/r) + Сцп, t{K) < С2тНв{£/г),

d(K) < C3mHB(E/r), d\K) < С4(logт + HB{£/r)),

где С1,С2>С3, Сц — некоторые постоянные, а В — единичный шар в V.

Леммы 2.3 и 2.4 будут использованы для построения е-приближающих таблиц компактных подмножеств функциональных пространств Lp и С.

В третьей главе исследуются две взаимосвязанные проблемы: вычисление е-энтропии и построение методов табулирования компактов в пространстве С{Х, V), состоящем из непрерывных функций, действующих из некоторого вполне ограниченного множества X в конечномерное векторное пространство V. Множество С(Х, V) является нормированным векторным пространством с нормой

||/||c = sup||/(x)||v.

х€Х

Модулем непрерывности со называется непрерывная, полуаддитивная, равная нулю в нуле функция, действующая из М+ в . Будем называть ш модулем непрерывности степенного типа, если кроме перечисленных свойств справедливо асимптотическое равенство u>(t) х ta при t —* 0 для некоторого а, 0 < а < 1.

Пусть У ограниченное подмножество V. Обозначим через FW(X, У) или через Рш, в случае когда это обозначение не может вызвать недоразумений, подмножество С(Х, V), состоящее из функций, модуль непрерывности которых не превосходит некоторого модуля непрерывности и:

= {/ € С(Х,У) : Чхих2 <Е X, ПДхО - /Ы||и < и{Рх{.хих2))}.

Элементы множества Рш (X, У) будем называть о;-непрерывными функциями.

Теорема Арцела-Асколи утверждает, что любое вполне ограниченное множество в С состоит из равномерно ограниченных и равностепенно непрерывных функций. То есть любой компакт в С(Х, У) содержится в РШ(Х,У), где и/ — некоторый модуль непрерывности и У — некоторое ограниченное подмножество пространства V.

А.Г. Витушкиным в [4] получена следующая оценка снизу е-энтропии множества РЫ(Х, У):

(2) #^М0)>2Ях(С£),

где С — некоторая положительная постоянная.

Следующая теорема, при некоторых ограничениях на и и множество У, предлагает необходимое и достаточное условие на X, чтобы е-энтропия множества РШ(Х,У) удовлетворяла противоположному неравенству.

Доказательство теоремы основано на методе последовательных приближений непрерывной функции суммой конечного числа кусочно-постоянных функций, множество которых составляет достаточно малую по мощности е-сеть множества РШ{Х, У).

Теорема 3.1 Пусть X — вполне ограниченное метрическое пространство, V — конечномерное векторное пространство, У — содержащее некоторый отрезок ограниченное подмножество пространства V, ш — модуль непрерывности степенного типа, Рш —■ множество (¿-непрерывных функций, действующих из X в У. Тогда для выполнения равенства

НРш{4ы(е)) = 0(2Нх(с)) при е -> О

необходимо и достаточно, чтобы X было множеством равномерного типа.

Заметим, что если множество X имеет конечную ненулевую метрическую размерность, то

(3) 2я*<С£> ж 2я*<£) при е -» О,

для произвольного С > 0, и из теоремы 3.1, леммы 1.3 и неравенства (2) следует эквивалентность

(4) Я^Ме))х2я*<£> при е —» 0.

В теореме 3.2 построен е-код множества Fu, имеющий асимптотически минимальные (с точностью до порядка) длину, сложность кодирования и декодирования. Сложность вычисления значения функции из е-приближающей таблицы также близка к минимальной.

Теорема 3.2 Пусть X — вполне ограниченное пространство выпуклого типа, V — конечномерное векторное пространство, Y — ограниченное подмножество V, ш — модуль непрерывности, FU(X, Y) — множество ш-нспрсрывных функций, действующих из X в У. Тогда найдется ео > 0, что для любого 0 < е < Ео существует е-приближающая таблица К. множества FU(X,Y) со следующими свойствами:

1)L(K)<Ci( 2я* Ю)

2)t{K.) < С2(2Я*<«))

3)d(fC) < С3(2Я*<«))

4) d"(IC) < С4 (log* j (log I + Hx(6))) (в операциях над битами),

где 6 = и>_1(е/6), a Ci, Сг > Сз > Сц — некоторые положительные постоянные.

Если множество X является подмножеством конечномерного векторного пространства, то имеет место эквивалентность (3). Тогда из неравенств (1) и (4) следует, что для любого е-приближающего кода К, множества FU(X,Y) справедливы неравенства

Ь{Ц>С[{2Я*<«)), t{K) > С'2(2Нх^6)), d(K.)>C'z{2Я*<5)).

То есть построенный в теореме 3.2 е-приближающий код имеет асимптотически неулучшаемые длину, сложность кодирования и сложность декодирования. Причем d"(fC) < С4(log* j log j) в операциях над битами, что соответствует конечному числу арифметических операций. То есть количество операций, требуемых для получения значения функции в точке из ее таблицы, построенной с помощью кода /С, также является практически неулу чшаемым.

Рассмотрим подмножества пространства С(Х, V), состоящие из дифференцируемых функций. Пусть X — ограниченное подмножество пространства Ега, с нормой ||z — i'|| = rnaxj=li..im — x'i\. Будем обозначать через Xh. наименьшее открытое множество в Rfc такое, что для каждой точки х (Е X открытый шар В(х, h) с центром в х радиуса h содержится в Х^, то есть Xh = UX£xB(x,h). Пусть множество Fn^{X,d,h) С C(Xh,R) состоит из функций, производные n-го порядка которых принадлежат множеству Fu(Xh, [1,-1]). Будем в дальнейшем обозначать множество FniW (X, d, h) через Fn<UJ в случаях, когда это не может вызвать недоразумений. В качестве базиса множества то есть набора функций, линейная оболочка которого плотна в F„iW, можно использовать множество кусочно-полиномиальных функций. Сложности кодирования, деко-

12

дирования, покоординатного декодирования и вычисления из кода значения функции в точке относительно этого базиса будем обозначать через соответственно. Для оценки точности с которой образ функции из Рп и приближаются кусочно-полиномиальными функциями использована теорема Тейлора.

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

Теорема 3.3 Пусть X € Мш — ограниченное пространство выпуклого типа, и — модуль непрерывности. Тогда найдется £о > 0, что для любого О < £ < £о существует е-приближающая таблица К множества Р„,ш(Х, в,, Л) со следующими свойствами:

1) ЦК) < С1(2я*<в/а>)

2) ¿х(£) < С2(2я*<*/2>)

з; (**(£) < С3(2я*(«/2>)

4) с^(/С) < С4(1о§* | log (в операциях над битами),

где £ = Зш(<5)<5п, а С\, С2, Сз, С4 — некоторые положительные постоянные.

Следствием теоремы 3.3 и неравенства (1) является оценка сверху е-энтропии множества

при 5 —> 0.

Последнее асимптотическое равенство является обобщением оценки £-эн-тропии множества РП>Ы(Х, <1, К), которая была предложена А.Н.Колмогоровым и В.М.Тихомировым в [10].

В четвертой главе рассматриваются вопросы, связанные с £-энтропией и табулированием вполне ограниченных подмножеств пространств Ьр[0,1] (1 < р < оо). Обозначим через Л.о) (или Р%ш) подмножество про-

странства 1/р[0,1], состоящее из функций, п-ая производная которых имеет интегральный модуль непрерывности ш на отрезке [—<5,1 + <5] для некоторого 6 > 0. То есть о) состоит из функций удовлетворяющих условиям:

2) ¡1? |/(п)(Л + 0 - /(п)(<)1р Л < и>р(Н), при |Л| < Ло, где ш — некоторый модуль непрерывности.

В £р[0,1] справедлива теорема аналогичная теореме Арцела-Асколи: вполне ограниченные множества в Ьр исчерпываются подмножествами множеств вида С • о), где С, 6 и — некоторые положительные

постоянные, аи — некоторый модуль непрерывности.

Пусть у? — некоторая ограниченная функция : К —> К, через (Л > 0) будем обозначать функцию у?д(£) = ^'р(^), а через {к > 0, к е Ъ) будем обозначать функцию (¿>л,ь(<) = — Определим несимметричную

свертку двух функций / : Е —» Е и g : Е -+ Е следующим образом

г+оо

/1-00

f(t)g(t-x)dt.

-оо

При вычислении е-энтропии множества F£ ш использованы следующие утверждения.

Лемма 4.2 Пусть h0 > 0,6 > 0 и / е FP^{S,h0). Пусть tp : Ш Ш

— ограниченная функция с компактным носителем, то есть sup |с/з| < R и носитель р содержится в отрезке [0, в]. Пусть ip удовлетворяет следующим равенствам

/+оо

ip(x) dx = 1.

Тогда существует такая постоянная С{<р) > 0, что при h —» 0 справедливо неравенство

II/ - £ М/ * <Ph№)vh,k\\p < cfrMh).

itez

Лемма 4.6 Пусть h0 > 0,6 > 0 и f е F%w(6,h0). Пусть ф : Е R

— ограниченная функция (sup \ф\ < R), носитель которой содержится в отрезке [si,S2], где slrs2 € Z. Причем для каждого i = 0...п справедливо равенство

Г + оо

x'i/)(x)dx — 0.

1—00

Тогда существует такая постоянная С(ф) > 0, что при h —► О справедлива неравенство

/ l/A-«i ч 1/р

( Ш*ЫЩ\") <C(iPMh)hn.

Ч = -»2 + 1 '

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

Ограниченную функцию <р : Е —> М называют масштабной функцией (scaling function), если она обладает свойствами:

1) <p(t) = Ekck<p{2t-k),

2) S+~V>(t-k1)<p(t-k2)dt = 6{kuk2), 4) ZMt-k) = 1.

Будем использовать только те масштабные функции, которые обла дают ограниченным носителем, то есть

f

J —(

5) Существует такое s 6 N, что носитель функции ip содержится в отрезке [0,5].

Всплеском (mother wavelet) называется функция ф, определяемая следующим равенством:

tez

Нетрудно показать, что если функция ip удовлетворяет условиям 1)—5), то функция ф удовлетворяет условиям:

1) ф(Ь)ф -k)dt = 0 для всех к <Е Z,

2) Ф(1 - кхШг - к2) dt = S(ki, к2),

3) Носитель функции ф содержится в отрезке ^з1]-

С.Мала [17] показал, что система функций —Л:), 2J/,2i0(2J —fc), где j G N и к € Ъ составляет ортонормальный базис пространства L2(—оо, +оо). Наиболее известной системой многомасштабного приближения является приближение кусочно-постоянными функциями. Пусть функция ip — индикатор полуинтервала [0,1), тогда ip удовлетворяет свойствам масштабной функции 1)-5), при этом co = ci = 1hc¿ = 0 при г ф 0,1. Соответствующий данной масштабной функции всплеск ф является ступенчатой функцией равной —1 на полуинтервале [0,1/2), 1 на полуинтервале [1/2,1) и 0 вне полуинтервала [0,1). Система функций y?(í), — к), где j € N

и к = 0...2J — 1 составляет ортонормальный базис пространства L2[0,1], называемый базисом Хаара.

И.Добшес [15-16] предложила метод построения масштабных функций любой гладкости с компактным носителем. Она доказала, что для каждого п £ N найдется такая n-раз дифференцируемая масштабная функция ip, что ее носитель содержится в [0,з(п)], где s(n) < оо. Причем при i = 0...п справедливы равенства

/+оо

?ф{г) dx = о,

-оо

где ф — всплеск, соответствующий масштабной функции ip.

Из определений масштабной функции и всплеска видно, что функции и ф, предложенные И.Добшес, удовлетворяют условиям леммы 4.2 и леммы 4.6 соответственно. В теореме 4.1 на основании леммы 4.2, леммы 4.6 и результатов И.Добшес получена асимптотическая оценка e-энтропии множества

Теорема 4.1 Пусть FP<U(S, hQ) подмножество пространства Lp[0,1], (6 > 0, ho > 0,1 < р < оо, л б N, üj — модуль непрерывности). Пусть е > 0, тогда

HFp^(e) ж 1/6 при е 0,

где 8 — корень уравнения Сш(8)8п = е и С > 0 — некоторая постоянная.

В теореме 4.2 предлагается метод табулирования множеств F£ w. Указанный метод подобен методам табулирования, описанным в теоремах 3.2 и 3.3, за исключением того, что в качестве аппарата приближения используется базис всплесков вместо кусочно-полиномиальных и кусочно-постоянных функций.

Теорема 4.2Пусть Fpu(8, ho) подмножество пространстваLp[0,1], (6 > О, ho > 0,1 < р < оо, п 6 N, w — модуль непрерывности). Пусть е > О, тогда найдутся такие положительные постоянные С, С1, С2, С3, С4, масштабная функция tp и такая е-приближающая таблица /С множества что справедливы неравенства

1) ЦК.) < С1 Щ8)

2) <„(£) < С2{1/8)

3) dv(K) < С3(1/6)

4) d''(IC) < С4(log* i),

где 6 — корень уравнения Cu(ß)8n = е и <р — некоторая масштабная функция.

Из теоремы 4.1 и неравенств (1) следует, что построенная в теореме 4.2 е-приближающая таблица множества Fpu имеет асимптотически минимальную (с точностью до порядка) длину, сложности кодирования, декодирования и вычисления значения функции в точке.

Производной функции / порядка а (0 < а < 1) в смысле Вейля называется функция удовлетворяющая равенству

№) - №) = =}-гг Г fM(r)(t2 - т)а~1 dr Vtj, t2 е Damf,

ГИ Jti

где Г — гамма-функция Эйлера. При а = 1 производная в смысле Вейля совпадает с обычной производной. При а > 1 производная функции / в смысле Вейля определяется как (/(LaJ))(a-LaJ)i где [а| — целая часть а.

Обозначим через Рр(8,Со) подмножество пространства Lp[0,1], состоящее из функций, а-ая производная которых ограничена в Lp. Рр(8,Со) состоит из функций, удовлетворяющих условиям:

1 )flts \M\pdt<i,

У iJt6\f{a)(t)\p dt < Co.

В лемме 4.1 показано, что Рр(2£,С0) с Fpu(6,6), где n = |aj при нецелых аив = а-1 при целых a; u>(h) — Cha~n, где С — некоторая постоянная.

Тогда из теоремы 4.2 получаем

Следствие. Пусть е > 0, 8 > О, С > 0. Тогда найдутся такие по ложителыше постоянные С1, С2, С3, С4, масштабная функция ip и така>

-.-приближающая таблица К. множества Р£(6,С), что справедливы неравенства

1) L(fC) < Cle~l'a

2) tv(IC) < сч-1'«

3)dv{K,)<Cze~lla

4) d"(K.) < С4 (log* (j-)) (в арифметических операциях над двоичными чи-глами размерности log j).

Пусть функция / действует из отрезка [0,1] в К. Полной вариацией функции на отрезке [0,1] называется величина V[f\,

п-1

F[/]=sup£|/(it+1)-/(i,)|, t=i

где 0 = ti < t2 < • • • < in = 1 — произвольное разбиение отрезка [0,1]. Через Vl{C) обозначим подмножество пространства L1, состоящее из функций с ограниченной полной вариацией на отрезке [0,1], то есть

V4C) = {/ : [0,1] - R : /(0) = 0, V[f] < С}

Через М1{С) обозначим подмножество пространства L1, состоящее из неубывающих на отрезке [0,1] функций, то есть

Мг(С) = {/ : [0,1] —► R : /(0) = 0,/(1) < C,/(ti) < f(t2), если tx < t2}

Теорема 4.3 Пусть е > 0, С > 0, тогда

Hv>{c)(e) - 1/е, ЯМ1(с)(е) >: 1/е.

В теореме 4.3 в частности показано, что М1{ 1/2) С Fq1 (1/2,1/2), где w(i) = t. Тогда из теоремы 4.2 получаем

Следствие. Пусть е > 0, С > 0, тогда найдутся такие положительные постоянные С1,С2,С3,С4 и такие е-приближающие таблицы К\,К,2 множеств М1(С) и V1 (С) соответственно, что справедливы неравенства

1) L{Ki)< С1/е

2) t(JCi) < С2/е

3) d(Ki) < С3/е

4) d"(K.i) < С4(log*(1/е)) (в арифметических операциях над двоичными числами размерности log 1 /е), где i — 1,2.

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

Литература.

1. Асарин Е. А. О сложности равномерных приближений непрерывных функций// Успехи мат. наук. 1984. Т. 39. Вып. 3. С. 157-169.

2. Бабенко К. И. Основы численного анализа. М.: Наука, 1986.

3. Бирман М. Ш., Соломяк М. 3. Кусочно-полиномиальные приближение классов WpQ// Мат. сб. 1968. Т. 76. Вып. 2. С. 288-303.

4. Витушкин А. Г. Оценка сложности задачи табулирования. М.: Физмат-гиз, 1959.

5. Гашков С. Б. О сложности приближенной реализации некоторых классов дифференцируемых функций одной переменной схемами из функциональных элементов// Вестн. МГУ. 1984. Вып. 3. С. 35-44.

6.Гашков С. Б. О сложности приближенной реализации функций, удовлетворяющих условию Липшица схемами в непрерывных базисах// Мат заметки. 1984. Вып. 4. С. 543-557.

7. Колмогоров А. Н. Оценки минимального числа элементов £>сетей в различных функциональных классах и их применение к вопросу о представлении функций нескольких переменных суперпозициями функций меньшей: числа переменных// Успехи мат. наук. 1955. Т. 10. Вып. 1. С. 192-194.

8. Колмогоров А. Н. О некоторых асимптотических характеристикам вполне ограниченных метрических пространств// Докл. АН СССР. 1956 Т. 108. Вып. 3. С. 385-388.

9. Колмогоров А. Н. Различные подходы к оценке трудности приближенного задания и вычисления функций// In: Proc. Intern. Congr. Math Stokholm. 1963. P. 369-376.

10. Колмогоров A. H., Тихомиров В. M. e-Энтропия и е-емкость множеств i функциональных пространствах// Успехи мат. наук. 1956. Т. 14. Вып. 2 С. 3-86.

11. Офман Ю. П. О приближенной реализации непрерывных функций нг автоматах// Докл. АН СССР. 1963. Т. 152. Вып. 4. С. 823-826.

12. Тиман А. Ф. Об £-энтропии арцелавских компактов функций, заданны? на замкнутых множествах положительной меры Лебега// Докл. АН СССР 1967. Т. 177. Вып. 2. С. 285-287.

13. Тиман А. Ф. О точном порядке роста e-энтропии и е-емкости арце-лавских компактов сколь угодно высокой массивности// сб. Метрические вопросы теории функций и отображений, Киев: Наук, думка, 1977. С. 131142

14. Тихомиров В. М. Некоторые вопросы теории приближений. М.: МГУ 197¿. 304 с.

15. Daubechies I. Orthonormal basés of compactly supported wavelets// Comm. Pure Appl. Math. 1988. V. 41. P. 909-996.

16. Daubechies I. Ten Lectures on Wavelets. CBMS Lecture Notes n 61, SIAM, Philadelphia. 1990

17. Mallat S. Multiresolution Approximation and Wavelet Orthonormal Bases of L2 // Trans. Amer. Math. Soc. 1989. V. 315. P. 69-87.

18. Потапов В. Н. Табулирование гладких функций// Межвуз. сб. науч. тр. Анализ и дискретная математика, Новосибирск: НГУ, 1995. С. 115-

19. Потапов В. Н. е-Энтропия компактов в С и табулирование непрерывных функций// Сиб. мат. жур. 1997. Т. 38. Вып. 4.

20. Кричевский Р. Е., Потапов В. Н.. Быстрое восстановление квадратично интегрируемых функций// Второй Сибирский Конгресс по Прикладной и Индустриальной математике: Тезисы докладов. Новосибирск. 1996.

21. Krichevskii R. E., Potapov V. N. Compression and Restoration of Square [ntergable Function// ERA of the AMS. 1996. V. 2. N. 1.

22. Krichevskii R. E., Potapov V. N. Compression and Restoration of Square Integrable Function: Fourier vs Wavelets// Proceedings of 1995 IEEE International Symposium on Information Theory. 1995. P. 431.

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

125.

С. 118.

1одписано к печати 26.06.97 г. Заказ N 191 Формат 60/84/16. Объем I уч.-изд. л. Тираж 100 экз.

)тпечатано в Институте теплофизики СО РАН 30090, Новосибирск, пр. Акад. Лаврентьева, I