Введение к работе
Актуальность темы. Одним из главных вопросов классической теории приближений является оценка точности, с которой функция из некоторого функционального класса может быть приближена с помощью различных методов аппроксимации. Решение этой проблемы было получено для самых различных классов функций и аппаратов приближения. Однако, важно не только сравнить между собой различные методы приближения, но и выяснить насколько их точность близка к наилучшей возможной. Решению этой проблемы посредством вычисления поперечников и е-энтропии различных функциональных множеств посвящены многочисленные работы А.Н.Колмогорова, А.Г.Витушкина, К.И.Бабенко, В.М.Тихомирова, В.Д. Ерохина и других исследователей. Подробный обзор указанного круга вопросов имеется в работе В.М.Тихомирова [14].
Понятие е-энтропии было введено А.Н.Колмогоровым в работах [7,8], как обобщение идеи характеризовать "массивность" метрического компакта мощностью его наиболее экономных покрытий. ^-Энтропией вполне ограниченного множества X называется величина Hx{z), равная логарифму мощности минимального (по мощности) покрытия множества X множествами диаметром не более 2є. Здесь и далее подразумевается логарифм по основанию 2. В диссертации исследуется проблема получения асимптотических (при є — 0) оценок г-энтропии компактных подмножеств функциональных пространств.
Пусть множество FU{X) состоит из вещественнозначных ограниченных функций, определенных на некотором компакте X, модули непрерывности которых ограничены сверху некоторой неотрицательной, полуаддитивной функцией ш. В работах А.Н.Колмогорова, В.М.Тихомирова [10], А.Г.Витушкина [4], А.Ф.Тимана [12-13] были предложены различные условия на множество X, обеспечивающие справедливость асимптотического равенства
2Ях(е|«Я?.(Х)И)) приє-^0.
Для классов функций, определенных на некотором связном компакте К метрической размерности 1 и, обладающих конечным числом производных А.Н. Колмогоровым и В.М.Тихомировым [10] получен следующий результат. Обозначим через Fn+a(Km) множество n-раз дифференцируемых ограниченных на Кт вещественнозначных функций, каждая производная п-ого порядка которых удовлетворяет условию Гёльдера с показателем а. В [10] показано, что
Я^+ЛК^М-е"^ приє-^О.
Аналогичный результат получен В.И.Арнольдом для пространствах2. Ее-
ли К = [0,27г] и через F%+a(K) обозначить множество суммируемых с квадратом функций, (п + а)-ая производная в смысле Вейля которых ограничена в L2, то
HF2+JK)(e) = 21oge (n + а)є-1/(п+а)(1 + 0(1/п)) при є -> 0,n -> со.
В.М.Тихомиров [14] распространил оценку В.И.Арнольда на пространства V.
Наиболее общий результат, касающийся оценки -энтропии классов n-раз дифференцируемых функций в Lp, был получен М.Ш.Бирманом и М.З'.Соломяком [3]. Для Соболевских классов Wg(Im), заданных на единичном кубе Іт в Rm в норме пространства L4, ими было доказано, что если W%{Im) компактно вкладывается в Lq(Im), то
Щурцт){с) х є~т/п при є -> 0.
Понятие -энтропии функционального множества тесно связано с проблемой кодирования функций, состоящей в следующем: для каждой функции из некоторого компактного множества необходимо построить такую таблицу (код функции), по которой функцию можно восстановить с заранее заданной точностью. Основными параметрами эффективности метода кодирования являются длина кода, то есть объем таблицы по которой можно восстановить функцию, сложность составления таблицы и сложность восстановления функции из ее таблицы. Кроме того, естественно ввести в качестве критерия эффективности метода кодирования следующую величину — сложность получения из таблицы функции значения функции в единственной точке. Задача одновременной минимизации всех четырех параметров кода называется задачей табулирования. Проблема оценки эффективности методов кодирования явилась одним из главных оснований для введения понятия -энтропии множества, поскольку -энтропия множества является нижней гранью длины кода элементов множества, а также сложности кодирования и декодирования.
Связь понятия -энтропии с теорией кодирования и различные направления решения задачи кодирования описаны А.Н.Колмогоровым в [9]. Проблемам кодирования и нахождения сложности вычисления непрерывных и дифференцируемых функций посвящены работы Ю.П.Офмана [11], Е.А.Асарина [1], К.И.Бабенко [2] и С.Б.Гашкова [5, б], использовавших различные формализации понятия сложности вычисления функции.
Целью работы является, во-первых, получение новых асимптотических (при — 0) оценок -энтропии компактных подмножеств функциональных пространств, во-вторых, построение эффективных методов табулирования.
Методика исследований. В работе использованы методы классического анализа, в частности, методы приближения гладкой функции кусочно-постоянными и кусочно-полиномиальными функциями. При исследовании свойств компактных подмножеств в Lp была применена теория всплесков (wavelets) и многомасштабного приближения (multiresolution approxi-matiuon), разработанная С.Мала (S.Mallat) [17] и И.Добшес (I.Daubechies) [15, 16]. Оценки е-энтропии были получены посредством построения є-сетей и е-различимых подмножеств.
Научная новизна. В диссертации получены следующие новые результаты:
1. Предложены необходимые и достаточные условия на множество X, обес
печивающие справедливость асимптотического равенства
Яп,(Мє)) = 0(2я*(е)) приє^О.
2. Получено обобщение оценки е-энтропии множества Fn+a{X) на случай,
когда X — произвольный, возможно несвязный, компакт.
-
Получены оценки е-энтропии компактных подмножеств пространства Lp[0,1], состоящих из функции, производные которых обладают ограниченным интегральным модулем непрерывности.
-
Предложены методы табулирования w-непрерывных функций и п-раз дифференцируемых функций в норме пространства С, а также функций, обладающих ограниченным интегральным модулем непрерывности, п-раз дифференцируемых функций и функций с ограниченным изменением в пространствах Lp[0,1]. Все предлагаемые методы позволяют строить е-прп-ближающие таблицы функций асимптотически минимальной (с точностью до порядка) длины. Сложность кодирования и декодирования этих таблиц также асимптотически минимальна. При этом сложность вычисления зналения функции в точке из є-приближающей таблицы не превышает 0(log* І/є) арифметических операции для всех предлагаемых методов, где через log* обозначен итеративный логарифм (черезвычайно медленно растущая функция).
Практическая ценность. Работа носит теоретический характер, полученные в ней результаты применимы в теории приближений и теории кодирования. На основе предложенных методов табулирования могут быть разработаны алгоритмы архивирования баз данных.
Апробация работы. Основные результаты работы докладывались на международных научных конференциях по теории информации ISIT-95 (Whinster, Canada) и по прикладной и индустриальной математике ИНПРИМ-96 (Новосибирск). Все результаты докладывались на семинаре отдела геометрии и анализа Института математики им. С.Л.Соболева СО РАН.
Публикации. По теме диссертации автором опубликованы работы [18-22].
Объем и структура диссертации. Диссертация состоит из введения, четырех глав и списка литературы. Объем диссертации — 79 страниц.
![О приближении функций класса Wap([0,1]2) билинейными функциями](/i/i/4377/303944.png "О приближении функций класса Wap([0,1]2) билинейными функциями Меленцов Александр Александрович")
