Дискретные аналоги классов непрерывных функций различной гладкости и сложность их схемной реализации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ



МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М. В. ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 517.5, 519.7

АМАНЖАЕВ Гурбангелди Гурбанмаммедович

ДИСКРЕТНЫЕ АНАЛОГИ КЛАССОВ НЕПРЕРЫВНЫХ ФУНКЦИЙ РАЗЛИЧНОЙ ГЛАДКОСТИ И СЛОЖНОСТЬ ИХ СХЕМНОЙ РЕАЛИЗАЦИИ

(специальность 01.01.09 — математическая кибернетика)

АВТОРЕФЕРАТ диссертации на соискание ученой степени

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

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

чл.-корр. РАН, профессор О. Б. Лупанов Официальные оппоненты: доктор физико-математических наук,

профессор А. А. Карацуба, доктор физико-математических наук, профессор В. М. Тихомиров, доктор физико-математических наук, профессор Л. А. Шоломов

Ведущая организация: Институт математики Сибирского

Отделения РАН.

Защита диссертации состоится 27 декабря 1996 г. в 16 ч. 05 м на заседании Специализированного Ученого совета по математике ДО (Д.053.05.05) в Московском Государственном университете по адре 119899 ГСП г. Москва, Воробьёвы горы, МГУ, механико-математиче« факультет, аудитория 14-08.

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

Автореферат разослан 26 ноября 1996 г.

Ученый секретарь Специализированного Совета Д.053.05.05 при МГУ, д. ф.-м. н„ проф.

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

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

А. Н. Колмогоров и В. М. Тихомиров для выражения минимально возможного объема такой таблицы, обеспечивающей погрешность вычисления не более заданной, ввели в рассмотрение величину, названную е-энтропией1. Для случая, если требуется не просто задавать функции, а строить вычисляющие их устройства (схемы) с использованием возможно меньшего числа элементов, выполняющих простейшие операции, А. Н. Колмогоров предложил исследовать соответствующую характеристику — сложность приближенного вычисления2.

Эти величины активно исследовались, и для различных классов функций (в частности, для классов г раз дифференцируемых (в смысле Вейля, Римана — Лиувилля и т. п.) функций, аналитических в различных областях функций, для различных классов, определенных вариацией и т. п.) были получены их оценки, обычно с точностью до порядка3.

1 См., например, Колмогоров А. Н., Тихомиров В. М. s-энтропия и е-емкость множеств в функциональных пространствах // Успехи математических наук. — 1959. — Т. 14, № 2 (86). — С. 3-86.

2 Колмогоров А. Н. Различные подходы к оценке трудности приближенного задания и вычисления функций // Proc. Intern. Congr. Math. Stockholm, 1963. — P. 230-250.

3 См., например, Офман Ю. О приближенной реализации непрерывных функций на автоматах // ДАН СССР. — 1963. — Т. 152, 4. — С. 823-826; Офман Ю. Об алгоритмической сложности дискретных функций // ДАН СССР. —1962. — Т. 145, № 1. — С. 48-51; Карацуба А. А., Офман Ю. П., Умножение многозначных чисел на автоматах

Однако при этом подходе исследуемым объектом являются исходные непрерывные функции, а дискретный метод их вычисления является только вспомогательным объектом, не определяемым «в себе», «внутренним образом». В частности, практически не рассматривается проблематика разрешения, например, вопросов такого рода: «верно ли, что заданная таблица представляет функцию из указанного класса?».

Тем самым задача состоит в том, чтобы для различных классов К непрерывных функций построить их дискретные аналоги KN, где функции / 6 KN имеют вид j:A —> А. Щ = N, так, чтобы условие f е KN эффективно алгоритмически проверялось и было таким, что ему удовлетворяют наилучшие приближения функций из К дискретными отображениями из Л в Л, причем желательно «не слишком» увеличить множество сверх этих «минимально необходимых» функций.

Мерой последнего свойства служит величина log Арргох — дискретный вариант е-энтропии с минимально возможной величиной е (будет рассматриваться множество А, состоящее из равноотстоящих друг от друга чисел; при этом е есть расстояние между ближайшими элементами из А); целью является получение для классов KN того же порядка (а еще лучше — того же асимптотического поведения) этой величины, как и для классов из «минимально необходимых» функций.

Наконец, представляет интерес реализация функций из классов вида KN (если N — число вида 2/с, fc £ N) схемами из функциональных элементов. Имеется в виду следующий вычислительный процесс. Элементы множества А кодируются (в естественном порядке) двоичными наборами длины1 п = [log TV]; при этом каждую функцию f\A —> А можно отождествить с булевым оператором /: {0,1}" —► {0,1}". Такие операторы реализуются схемами из

// ДАН СССР. — 1962. — Т. 145, № 2. — С. 293-294; Асарин Е. А.

0 сложности равномерных приближений непрерывных функций // Успехи математических наук. — 1984. — Т. 39, № 3. — С. 157-169.

1 Всюду символом log мы обозначаем логарифм по основанию 2; \х\ — наибольшее целое число, не большее х; [ж] — наименьшее целое число, не меньшее ж; {ж} = х ~ [х\.

функциональных элементов1. При этом «энтропийной» постановке задачи об оценке минимального е-покрытия множества функций соответствует задача об оценке сложности самых простых функций, е-приближающих данные (снова е берется минимально возможным).

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

Кроме того, решаются аналогичные задачи и для классической е-энтропии: требуется построить «сплошную» шкалу классов непрерывных функций в том смысле, чтобы для любого наперед заданного порядка роста е-энтропии при е —» 0 (в границах от Iogl/e до (1 /е)с, с > 0) можно было указать соответствующий класс.

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

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

Построена полная (с точностью до порядка величины logApprox) шкала классов дискретных функций: от порядка logiV, соответствующего классам констант, до N logN, соответствующего классу всех дискретных отображений f:A —» А, |А| — N. Показано, что для каждой регулярно растущей (т. е. принадлежащей некоторому телу Хар-ди2) функции с порядком роста между log N и N log N найдется класс

1 Лупанов О. Б. Асимптотические оценки сложности управляющих систем. — М.: Изд-во МГУ, 1984.

2 Тело Харди (см. Н. Бурбаки, Функции действительного переменного. — М.: Наука, 1965) — это множество классов эквивалентности (по

с такой по порядку величиной log Арргох, и указан способ его определения. Аналогичные результаты получены и для непрерывного случая, при исследовании е-энтропии. При этом исследованы также «промежуточные» классы, состоящие из бесконечно гладких, но в общем случае не аналитических функций, а также рассмотрена более тонкая классификация целых аналитических функций, чем обычно применяемая (в терминах порядка и типа).

Для некоторых дискретных классов получены оценки сложности приближенной схемной реализации. "В случае дискретных аналогов классов конечной гладкости найден порядок сложности схемной реализации. Для задачи о сложности приближенного вычисления аналитических функций описан метод, требующий О (rt2 log п) логических операций при вычислении с точностью п знаков, тогда как обычно применяемое разложение в ряды требует спг log п log log п операций.

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

Апробация работы. Результаты работы докладывались и обсуждались на Межгосударственных школах-семинарах по синтезу и сложности управляющих систем (Новосибирск, 1989 г.; Нижний Новгород, 1992 г.; Минск, 1993 г.; Нижний Новгород, 1994 г.; Нижний Новгород, 1996 г.), школах-семинарах «Дискретные модели в теории управляющих систем» (Москва, МГУ, 1993 г., 1994 г.), конференциях молодых ученых механико-математического факультета МГУ, научных семи-

отношению / = д (ЗЫ)(Ух > ЛГ) /(ж) = д(х))

дифференцируемых функций, замкнутое по сложению, умножению на константы, поточечному умножению, дифференцированию и такое, что для любого его элемента / при всех достаточно больших х выполнено ровно одно из соотношений /(ж) = 0, /(х) > 0 или /(х) < 0.

нарах механико-математического факультета МГУ (под руководством чл.-корр. РАН, проф. О. Б. Лупанова и проф. В. М. Тихомирова).

Публикации. По теме диссертации автором опубликовано 16 работ, список которых приведен в конце автореферата. Работ, выпол-нешшх в соавторстве, нет.

Структура и объем диссертации. Диссертация состоит из введения, шести глав, состоящих в совокупности из 19 параграфов, добавления, состоящего из 5 параграфов, и списка литературы, насчитывающего 56 наименований. Полный объем диссертации — 209 стр. текста. Изложение иллюстрируют 3 рисунка.

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

Во введении излагается предлагаемый подход к определению и изучению дискретных аналогов непрерывных функций. Для определенности пусть все рассматриваемые классы непрерывных функций состоят из функций, определенных на {0,1) и принимающих значения также из [0,1). Часто нас будут интересовать периодические функции — мы будем рассматривать функции с периодом 1 и значениями из [0,1); в ряде случаев мы будем отождествлять такие функции с их сужениями на [0,1) — по таким сужениям функция в целом однозначно восстанавливается по периодичности.

Имея функцию вида /: [0,1) —» [0,1), мы хотим построить ее «дискретный аналог», т. е. некоторое приближенное описание в виде дискретного оператора. Один из самых естественных путей введения таких операторов состоит в том, чтобы на [0,1) указать набор точек Т — {¿о; - • •, ¿^-1} и построить оператор /V: Т —» Т, положив в качестве значения /т(к) ту точку из Т, которая окажется ближайшей1 к /(¿¿). Далее, можно заменить точки их номерами г и получить оператор /Г:{0,1,..., N - 1} {0,1,..., N - 1}, где /т(ъ) = 3 в том и только в том случае, когда /-/(¿г) = tj.

Конечно, при этом разный выбор набора точек Т дает разные операторы /у; среди них естественно взять тот, который «точнее все-

1 Если /(£,-) окажется ровно посередине между некоторыми точками из Т (т. е. ближайшая не определяется однозначно), то в качестве /т(£г) выберем меньшее из возможных двух значений.

го» соответствует исходной функции. Но, не имея дополнительной информации о функции и для облегчения дальнейшего исследования, естественно зафиксировать в качестве Т из N точек множество IN = {l/(2JV),3/(2iV),..., (2N- 1)/(2N)}, т. е. tf - (1 + 2i)J(2N). Это множество, в частности, удобно тем, что «равномерно» приближает отрезок [0,1), доставляя минимум величине

sup min \х — у\.

При Т — In функцию fj будем обозначать просто /; множество {0,1,..., JV — 1} обозначим In, так что можно записать /: /д? —»• In. Такую функцию / будем называть дискретным аналогом функции / при N уровнях квантования; аналитически / через / можно выразить формулой

f(x) = [Nf{x/N+l/(2N))\,

где х € In, т. е. х = 0,1,..., N - 1.

Имея какой-либо класс К функций /: [0,1) —> [0,1), можно рассмотреть множество KN дискретных аналогов этих функций. Точнее, положим

KN = {g:IN IN | (3/ е K)(Vx е IN) g(x) = [Nf(x/N+ l/(2iV))J}.

Множество KN назовем внешним дискретным аналогом класса К. В этом названии отражен тот факт, что элементы множества KN определены не «сами по себе», а через некоторое «внешнее» множество, даже не имеющее дискретной природы, — класс К. Эта причина приводит, например, к тому, что задача проверки соотношения g € KN для какой-либо конкретной функции g: In In становится весьма трудной.

Предложена следующая идея решения такой задачи. Надо исследовать множество KN и установить некоторый набор Е = {сг\,..., о-т} свойств элементов этого множества, причем желательно выбирать просто (эффективно) проверяемые свойства. Далее можно рассмотреть множество всех тех дискретных функций, каждая из которых обладает всеми свойствами из Е. Полученное множество дискретных функций заведомо будет включать KN, а при удачном выборе

свойств Е может отражать сущность тех ограничений, которые выделяют непрерывные функции первоначального класса К среди всех возможных функций /: [0,1) —> [0,1).

На этом пути удалось найти такой подход, при котором возникает разумный ответ на вопросы типа «что такое дискретная функция с ограниченной Пгй производной?» или даже «что такое дискретная аналитическая функция?». При этом удалось обойти казалось бы неизбежные трудности, связанные с «необходимостью» определения дифференцирования и производных для дискретных операторов. Оказалось, что для определения, например, «дискретных функций с ограниченной производной» можно обойтись не только без производных как таковых, но и без предельных переходов типа Ах —> 0.

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

Конечные разности А„(/; хо,..., хп) гг-го порядка от функции / с узлами хо,...,хп определяются индуктивно по п следующим образом1:

Ао(/;.хо) = /(х0); д ,, >, _ Ац-1(7; Дь •' •! Дц) ~ Ая-1(/; Др,,.,, Дп-1)

Хц

В ряде важных случаев при хо —► х, ..., хп —* х значение • • >з:п) стремится к f^(x)fnl. Можно, кроме того, утверждать, что если для функции / существует (п — 1)-я производная, удовлетворяющая свойству Липшица с константой п!С„, то |Д„(/;а;о,..., хп)\ < Сп. Если же (п — 1)-я производная имеет модуль непрерывности не более ш(-), то (Д^/;^ ..., х„)| < (^зут^, где £ —- тахЖг — ттг;.

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

1 См.: Гельфонд А. О. Исчисление конечных разностей. — М.: Наука, 1967.

непрерывных функций задан ограничениями вида

|/(">(а:)| < const

или

|/<n)(*)-/<n)(v)l< const |s -2/1,

или

|/in)(»)-/(B)(2/)|<m®-!/|).

Тогда любую функцию д £ KN можно представить в виде fli + р2, где 9l = 1/2 +Nf{x/N + 1/(2ЛГ)) и |Ä| < 1/2.

Тогда п-е разности от функции gi можно очевидным образом выразить через п-е разности от функции /, а для п-х разностей от (¡2 можно воспользоваться естественной оценкой

def

\&n{g2;x0,-..,xn)\<tpn(x0,...,xn)= sup |A„(/i;x0,...,a;n)|.

\h\<l/2

Из этих соображений автоматически выписывается набор оценок конечных разностей, которым удовлетворяют все функции д из KN. Собственно говоря, надо всего лишь заменить условия

!/(п)(*)|<Спп!

или

\f^-1\x)~f^(y)\<Cnn\\x-y\

на

|Дп(0;яо,...,:сп)| < CnNl~n + рп{х0, ...,х„),

а условие на

хй,...,хп)\ < N2~n+ <Рп{хо, • - ■,а?„), ъ(п — 1)!

где t — max Xi - min x{.

Такие условия надо записать для всевозможных наборов значений Xi € /дг (а в периодическом случае — для Xi € Z, считая функцию

д продолженной на Ъ периодически с периодом TV"). Если же исходный класс функций не имеет явного определения через оценки производных, то сначала надо перейти к такому определению (это нужно, например, для классов аналитических функций: вместо ограничений типа |/(z)| < const при z £ О, надо перейти к < const(n) при

z € R, п е N).

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

Пример. Для класса непрерывных функций гладкости 2

{/: [0,1) -> [0,1) | {Ух, у) \f(x) - f (у)| < С\х - у\}

внутренним дискретным аналогом при N уровнях квантования является

In -*■ IN | (Varj, x2, 6 IN, Ф x,-)

Величина logApprox. Очевидно, что по построению для любого класса К будет выполнено соотношение KN С KN, так что класс KN также содержит дискретные аналоги всех функций из К. Но, чтобы оправдать именно такое определение внутренних дискретных аналогов, как было описано выше, необходимо показать, что в некотором разумном смысле класс KN не будет «гораздо больше», чем минимально необходимое его подмножество — класс

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

С этой целью предлагается рассмотреть такую характеристику множества дискретных функций D, как минимально возможная мощность множества функций М, для которого

max min max |/(ж) — g(x) | < 1.

/so g€m x€in

Мы обозначим эту минимальную мощность через Approx О, но обычно будем оценивать не саму эту величину, а ее двоичный логарифм — log Approx D. В терминологии А. Н. Колмогорова и В. М. Тихомирова величину log Approx Z> можно обозначить 7ii(D), т. е. это —

1-энтропия; в случае функций fy^ соответствующая величина является (1/Л/г)-энтропией.

Оказалось, что с точки зрения этой величины предложенный метод определения дискретных аналогов классов непрерывных функций различной гладкости дает практически во всех случаях значения величин log Approx KN и log Арргох KN того же порядка, что и (1/ЛГ)-энтропия исходного класса непрерывных функций. Различие в порядках роста имеет место только для классов функций малой гладкости, для которых не выполнено условие Липшица (этот эффект объясняется тем, что для таких функций по значениям, заданным на нельзя оценить значения функции во всех остальных точках с ошибкой 0(l/N) ).

Далее во введении дается сводка полученных результатов (см. ниже). Для получения оценок величины log Арргох в ряде случаев удается воспользоваться идеями, использовавшимися в непрерывных случаях для оценки е-энтропии. В частности, нижние оценки е-энтропии, полученные предъявлением 2е-различимого множества, для всех «гладких» случаев практически без изменений переносятся на дискретный случай. В случае классов функций малой гладкости 2е-различимое множество строится из всевозможных функций с малыми значениями.

Основную сложность составили доказательства верхних оценок. Тут «непрерывные» идеи не работают, во-первых, из-за того, что мы не можем вообще ничего говорить о значениях в «промежутках» между точками из /¿v (или 7jv), а во-вторых, из-за того, что применение интерполяции (по формуле Лагранжа, например) осложняется тем, что в определениях участвует слагаемое ipn, которое можно интерпретировать таким образом, что сами используемые значения известны с ошибкой1. Поэтому потребовалось дополнительное изучение задачи оптимального выборе узлов интерполяции при тех ограниче-

1 Возвращаясь к смыслу вводимых определений дискретных функций, можно сказать, что дискретные классы мы определяем как семейство таких функций, заданных на дискретном множестве, у которых величины конечных разностей оцениваются такими же значениями, как для сумм / + /¿, где / — элемент «исходного» непрерывного класса, а Л — некоторые произвольные «малые» функции.

ниях, которые накладывает рассматриваемая постановка.

Другая важная идея оказалось такой. Для задания дискретной функции сначала надо выяснить ее значения в точках некоторой (редкой) сетки; затем, исходя из определения класса, надо оценить значения в остальных точках, и, привлекая дополнительную информацию о конкретной функции, довести значения в середине между узлами исходной редкой сетки до точных. Эта процедура продолжается до тех пор, пока очередная сетка не станет столь мелкой, что по ней все (еще неизвестные) значения функции можно будет оценить с погрешностью не более 1. Эта конструкция использована в §§1—3 гл. 2; при этом оценка неизвестных значений производится экстраполяцией по формуле Лагранжа по некоторому числу известных значений. В § 4 гл. 2 для получения более точных значений эту конструкцию пришлось усложнить: здесь для получения «достаточно точных» оценок неизвестных значений приходится строить интерполяционные многочлены, в которых не все узлы сами известны точно (они также получаются интерполяцией, причем подобный процесс также является многоступенчатым).

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

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

Пусть все функции /: [0,1) —> [0,1), принадлежащие некоторому классу К, дифференцируемы и их производная удовлетворяет свойству Липшица с некоторой константой. Пусть и — выпуклые вверх возрастающие положительные функции, определенные при t > 0, причем при £ —> оо выполнено1

1 Для сравнения скорости роста функций здесь и далее используются обозначения / ~ д, если Ит//д = 1; / ж д, если / = О(д) и д — 0(/); / < д, если 0 < / < д(1 + о(1)); / ^ д, если / = О(д). Соотношения / ~ д и / < д называются асимптотическими равенством и неравенством, а соотношения / х д и / < д — равенством и неравенством по порядку.

~ cr^2(i)j где cr — положительная константа. Пусть при е —> 0 и N —» оо выполнены оценки

ПС(К) > zx{ 1/е), logApprox^ <

гЭе ^ — некоторое множество функций /дг —» 7jv, содержащее KN. Тогда справедливы соотношения

z1(l/e)<HE(K)<(3lo)z1(l/e), (,<t/3)z2(N) < log Approach < log ApproxКN < z2{N).

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

Лемма 2. Пусть А — ограниченное подмножество действительной оси, п — целое неотрицательное число. Пусть функция f определена на А и для любых различных точек xq, ... ,хп £ А выполнено неравенство

|АП(/; х0,... ,жп)К ci + с2(рп(х0, ...,хп),

где с\ и с г — положительные константы. Тогда / можно приблизить на А многочленом степени п — 1 с погрешностью не более сг/2 + сг • \А\п - 2/4", где \А\ = supvl - inf А.

Лемма 4. Пусть при некоторых фиксированных п, xq,Xi, ■ ■ ■ ,хп (где хо < Х\ < • • ■ < хп или Xq > Xi > ■ ■ ■ > хп), Ci,c2 выполнено неравенство

| Д(/; го, хи..., хп) | < с\ + с<м{х о, хъ...,хп).

Пусть р(х) — многочлен степени п — 1, совпадающий с f{x) в точках хо,х1;.. Тогда

Ь(®п) - 1(хп)\ < сх |(а:п - х0)... {хп - in_i)| +

с \(хп — хр)(хп — жх)... (хп — a;n-i)[

- х0)(а;2 - ®i) • • • (хп - a?n-i)|'

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

Задача. Пусть функцию /: R. —> Е можно измерить вне отрезка [а, 6] с погрешностью не более с, в точках а и b — с погрешностью не более d (естественно рассмотреть только случай d < с), причем известно, что

I f{n-l)(x)-f^(y)\<e\x-y\

при х, у Е R. Требуется выбрать узлы интерполяции ..., хп (при условии х\,...,хт < а, хт+1,... ,хп > Ь) так, чтобы интерполяционный многочлен Лагранжа давал наилучшую возможную погрешность в точке х £ [а, Ь]. Здесь a,b,c,d,e — параметры, для которых а < Ъ, с > d > 0, е > 0.

Лемма 5. Пусть р(х) — многочлен степени п, имеющий локальные знакочередующиеся экстремумы в точках у\,..., yn-i> у которого:

1) абсолютная величина старшего коэффициента есть е/п\;

2) Р(Ут) > 0;

3) !рЫ1 = с при i ф т;

4) Р(а) = P{b) = d;

5) 3/i,..., Ут-i <а и ym+i,..., 1 > b при ут е (а, Ъ).

Тогда искомый наилучший набор узлов интерполяции — ото

XI — У\, ■ ■ ■ , — ут-1,хт = а, хт+2 - Ь, хт+2 = ут+1,. . . , хп =

а в любой точке интервала (а,Ь) неулучшаемая оценка погрешности полиномиальной интерполяции есть р(х).

Оценку погрешности интерполяции для функций из рассмотренных дискретных классов дает

Лемма 6. Пусть < • ■ • < х\, функция f определена в ... ,xi, причем

|Afc+i(/; a;_fc,..., жг)| < а + hpk+i(x-k,

Пусть 6 — функция, определенная в ... ,х\ (кроме хо) так, что S(x_i) = 6(xi) = 0, < с при |г| > 1. Пусть p(t) — многоч-

лен степени к 4-1 со старшим членом atk+l(—1)!, для которого

(-1 Ур(х{) < 0 при i ф 0, p(x±i) = 6/2, |p(x±t-)| > 6/2 + с при |г'| > 1. Пусть q(t) — интерполяционный многочлен Лагранжа, построенный по значениям функции / -f ё в точках Х{, г ф О. Тогда

\f(x0)-q(x0)\<p(x0)+b/2.

В §§4-6 даются другие вспомогательные утверждения. Главы 2, 3, 4 посвящены построению и исследованию дискретных аналогов классов функций различной гладкости.

В главе 2 исследуются классы функций конечной гладкости Пусть w(i) ■— определенная при t > О непрерывная неотрицательная функция, выпуклая вверх, не убывающая и удовлетворяющая условию ui(t) > t при малых t. Обозначим

- {/: [0,1) - [0,1) | |/(ж) - f(y)| < и){\х - у|)} Дискретный аналог этого класса есть

= In-* In \ (Vr0,a;i е IN, х0 ф х^)

Теорема 4. 1) При N —> оо справедливы оценки

log АрргохЯ^, х logApproxtf0* ж N\og{Nuj(l/N)).

2) При oj(1/N) ф 0(1 ¡N) при N —> оо эти оценки можно усилить до асимптотических:

1°6 АрртохHq w ~ 1оёАрргохЯ0Л; ~ Nlog{Nu(l/N)),

в частности, для классов, удовлетворяющих условию Гёльдера (т. е. при ui(t) — ctT, 0 < г < 1) имеем

log Арргох Яо'ш ~ log Approx Н^ ~ (1 - г )N log N.

3) При и?(£) = с£, с > 1, выполиены равномерные по с оценки

Теорема 5. При N —> оо для классов с и]{Ь) < Ь (Ь > 0) справедливы оценки

Замечание. Для случая х £ результаты можно объединить в виде

равномерно по с — Ншш(<)/<.

(—>оо

Далее (§3 гл. 2) рассмотрены классы более гладких функций. Пусть снова ш(С) —- определенная при t > 0 непрерывная неотрицательная функция, выпуклая вверх и не убывающая, причем <м(0) = 0; пусть п — натуральное число. Обозначим

ЬйАрргохЯ^ х Арргох х ЛГ^с.

^ Арргох Я0¥ш х Арргох П^ х ЛГ,

или, обозначая с = Нто;(£)/£, равномерно по с

к^ Арргох х 1ой Арргох Я^ ~ сУУ.

к^ Арргох Я^ х Арргох Я^ х + с)

Я„,ш = {/: [0,1) [0,1) | |/И(х) _ /(п)(у)| < и(\х - 2/1)} •

Тогда

1дг | С^г0,..., агп+1 е /дг, ж,- ^ асу) |Ап+1(/;а;о, ...,х„+1)| < ~~ + </>„+1(^0, ■ • •, 2^+1),

ЫШ"

Теорема 6. При N имеют место оценки

1о8 Арргох Я^ х 1ой Арргох х 1/И^/ЛГ),

где функция t — W(z) — обратная к z = tnu>(t).

Затем в (§4) эти оценки уточняются в том смысле, чтобы верхняя и нижняя оценки отличались лишь в абсолютную константу раз; это требуется в дальнейшем при анализе бесконечно гладких функций. Далее будут рассматриваться дискретные аналоги классов периодических функций, гь-я производная которых удовлетворяет свойству Гёльдера с параметром а, 0 < а < 1, и положительной константой, т. е. исходный класс — это

Нп<и! = {/:£—> [0,1) | f{x ± 1) = f(x); |/<«>(*) - /<">(у)| < ш{\х - у\)}, где oj(t) = с£аГ(1 + а + п), t > 0. Для того, чтобы отразить данный

о

вид функции w, введем для таких классов обозначение Hrfi, где г — «суммарный» показатель гладкости, равный п+ а (зная г, числа п и о: можно восстановить однозначно: при г ЕЪ имеем п = г — 1, а = 1; а при г ф. Z — соответственно п = [rj, а = {г}).

Рассматриваемый случай — г > 1. Внешний дискретный аналог

о о

Н{Ус класса Нг<с определим стандартным образом (как множество всех

о

функций вида [iV/ + ¿г)]) / € НТ>С) а внутренний аналог, т. е.

о

класс — соотношением

Нт,с = Г | (^0, • • • , Хп+1 х5)

1л Л м <*Т(1 + г)

|Дп+НЛхо,... ,хп+1)| < —--Ьу„+1(а;о,...,хп+1)},

о

где / — ^-периодическое продолжение / на 2, £ = (тахжг—тша^)/АГ. Теорема 7. Имеют место оценки

С1 (г2(сЛГ)1/г + \ogN~j < 1оёАррго<

< 1о§ Арргох#£ < с2 (г2(сЛГ)ЧГ + 10§ЛГ + 1) ,

Ч^Г+1оФ ЧЧ Ч'2 (;ГИ •

где Ci,C2,C3, С4 — абсолютные положительные константы. Верхние оценки здесь выполнены всегда при г > 1, с > 0, а нижние — при дополнительных ограничениях е < с5е~г, е < с(с$г)г, N > cieT, N > 1/(с(с8г)т), С5,С6,С7,С8 — также абсолютные положительные константы.

Для е-энтропии из этих результатов вытекает

Следствие. При г > 1, с > 0 или г = 1, 0 < с < со = const, при е —> О (или N —» оо) выполнены равномерные по г и с оценки

log Арргох~ log Арргох ^ r2(cN)^r, 7ie{Hrfi)^r\clsf/\

В главе 3 рассматриваются классы бесконечно гладких функций и их дискретные аналоги.

Пусть х{г) — функция, принимающая положительные (возможно, бесконечные) значения при г > 1. Обозначим

о _ О

НХ = |] Яг,

Г>1

v

Пусть Н* — внешний дискретный аналог класса Нх; очевидно, что

НХ = П Нг,х(г) ■

т> 1

Пусть также по определению

= П ^пх(г);

т> 1

Теорема 8. Пусть для функции х{г)> определенной при г > 1, выполнены следующие условия:

1) Х(1) = 1/2,

2) х(г) пе убывает,

3) логарифм х(г) выпуклый вниз,

4) х(г) непрерывна либо всюду при г > 1, либо tía [1,ггаах), а при г > Гпшх выполнено х(г) — Тогда имеют место оценки

log АрргохН^ х log АрргохЯ х minг2 (Лгх(г))1/г;

г>1 1/г

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

1. Пусть х(г) < оо при г < т-тах, х(г) = оо при г > гГШ1Х. Тогда

*(г)У/г_ 2 /Х(гшах)\1/Т™

mmr2 I I = гтах

0)

2. Пусть lnx(^) ~ ctr (это соответствует классам функций, аналитических в некоторой полосе: если 1пх(г) ~ сиг, то функции из

о

Нх аналитические в полосе ширины ~ 1/а, и наоборот). Тогда Hiinr г2(х{г)/^У^т достигается при г рз (1/2)1п(1/е) и равен по порядку 1п2(1/е).

3. Пусть Inx(r') — arlnr + О (г). a > 0; этот случай соответствует некоторым классам, состоящим из бесконечно гладких, но не аналитических функций. Тогда minr г2 (х(г)j¿)1//г достигается при г » и равен по порядку ln2+a(l/e). При a —> 0 этот порядок близок к тому, который получен для аналитических функций.

4. Пусть 1пх(г) = ar13 - 2r lnr + О (г), a > 0, /? > 1. Этот случай также соответствует некоторым классам бесконечно дифференцируемых, но не аналитических функций. Тогда minr r2(x(r)/e)1/r достигается при

1

АР-1) е

и равен по порядку

exp faWW ^(bi)

1-1//3>

подбором параметров а и /3 можно, очевидно, получить любой порядок вида

ехр(с! 1пС2(1/е)),

где Ci > 0, 0 < С2 < 1. При C'i —* 1 такие порядки близки к величинам

(l/e)const,

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

В главе 4 рассматриваются классы аналитических функций. В §1 исследуются функции, аналитические в ограниченных областях. Пусть Л — положительный параметр. Обозначим через fî(A)

о

А-окрестность отрезка [0,1], а через fi(A) — полосу |Imz| < А. Введем следующие классы аналитических функций: Л\с — класс всех бесконечно дифференцируемых функций вида /: [0,1) —> [0,1), таких, что

|/<">(œ)| < сА-"п!;

о

Д\,с — класс бесконечно дифференцируемых функций / : К —» [0,1), периодических с периодом 1 и также удовлетворяющих при всех ne N условию

|/<п>(*)| сА-"п!;

А'Хс — класс аналитических на iî(A) функций /, ограниченных на Î2(A) константой с и таких, что

- ■ ■ «

при всех х € R, при х 6 [0,1);

А'Хс — класс аналитических на Г2(А) функций /, имеющих период

о

1, ограниченных на О, (А) константой с и таких, что удовлетворяют условию (1).

Легко видеть, что при 0 < А' < А, с' = с/(1 — А'/А), имеют место

ООО

вложения А'Х с С Ах,с С А\1с, и А'Х с с Ал,с С А'Х с,.

Внешние дискретные аналоги Afc, А'^с классов A\fi, Ах,с,

о

Лд и А'Л с определим стандартным образом; для построения внутренних заметим, что

|Д„(/; ..., сА~"ЛГ1-п -f ^„(zo,..., аг„);

г о °

если / 6 Ад с или / = д, д € с помощью набора таких условий введем дискретные классы

|А„(/; х0,..., хп)\ < cA~"iV1_" + Vn(:c0,..., *„)};

AL = if-lN^lN I (Vn€ N)(V®0.....®

|Д„(/(# {-/ЛГ}); *o, ■ • •, ®„)| < cA-^JV1-" + v»n(®o, • • •, *»)},

Теорема 9. s-энтропия каждого из указанных непрерывных классов аналитических функций имеет порядок log2(l/e), а величина log Арргох любого из указанных га: дискретных аналогов имеет порядок log2 N.

В §2 изучаются целые аналитические функции. Сначала укажем определение для непрерывного случая.

Пусть т: ¡R_|_ —> К+ — функция, удовлетворяющая условиям:

1) т(0) = 0;

2) т — непрерывная функция;

3) т(х)/х — возрастающая к бесконечности функция;

4) т — выпуклая вниз функция.

о

Обозначим через класс целых 1-периодических функций, для

которых выполняется условие

|/(2)|

о

а через Ат обозначим его подмножество, для элементов которого дополнительно выполнено условие f(z) € [0,1) при Теорема 10. Имеют место оценки

где т — произвольная функция, удовлетворяющая условиям 1)-4), т"1 — функция, обратная к т.

о

Определим дискретные аналоги класса Ат. Внешний пусть определен стандартным образом; для определения внутреннего оценим

о

|/"(ж)1 при х € К, / е Ат. По формуле

/"(*) = Гй [ f(x + z)z~n\dz\

¿ттК

'N=

имеем

e^n!

п1 Г nl ет(Д) n|

u Wl ~ 2-лR J ~ Rn |г|<л л _ Rn

откуда

|/п(г)| < п! т£ е^/д» = пЫт{п),

О

где ¿т(п) = щ&>0 ег^/Яп. Поэтому дискретный аналог класса Аг можио задать так:

о

^ = {/: //V -> /дг | (Утге М)(Уж0,...,хл хй < хг < • ■ ■ < хп)

о

|Д„(/; ю, • • •, хп)\ < ]У3-Псгт(п) + <рп(хо,.. -, £„)},

о

где / — ^-периодическое доопределение / на множество всех целых чисел Z.

Для введенных дискретных аналогов выполнена Теорема 11. Если функция г удовлетворяет условиям 1)-4), то имеют место оценки

1оц Арргох^ х ^Арргох А^ ^

г-1

(In И)'

где г"1 — функция, обратная к т.

В главе 5 устанавливается своего рода «полнота» построенного набора дискретных классов, т. е. утверждается существование дискретного класса для любого наперед выбранного порядка роста функции log Арргох. Точнее, имеет место следующее утверждение.

Теорема 12, Для любой функции У(х), принадлежащей любому телу Харди и такой, что logх < У(х) -< хloga;, найдется

о

такой класс непрерывных 1-периодических функций К, что для

о о

его дискретных аналогов К и KN имеет место соотношение

о о

log Арргох КN х log Арргох KN х V(N);

о

при этом если V{x) Ухс, с> 0, то класс К можно выбрать

о

из классов конечной гладкости Hn,wi если log х ^V(x) -< хс (при

о о

всех с > 0), то К можно выбрать из семейства Нх; если же

о

loga; ^ V(x) ^ log2х,~\/(х) yi log х, то К можно выбрать из семей-

о

ства АТ

Аналогичное утверждение можно сформулировать для е-энтропии: Теорема 13. Для любой функции V(x), принадлежащей любому телу Харди и такой, что loga; ■< V{x) X хс, где с —

о

любое положительное число, найдется такой класс К, что

0 0 о

7ie{K) ^ V(1 /е); причем К можно взять вида Нппри V(x) У хс, 0 0

вида Нх — при меньших порядках V{x), вплоть до log х, и АТ — для остальных

В §1 рассматривается случай V(x) У хс, в §2 — log2 х < V(х) X хс (при всех с); в §3 — loga; К V{x) < log2a;, V{x) ^ log2а;.

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

Дискретные функции /: In —> In при N — 2П можно рассматривать как булевы операторы /:{0,1}" —> {0,1}™, сопоставляя каждому числу из Iff его двоичную запись, состоящую из п цифр 0 и 1. Для реализации таких операторов введем понятия схемы и сложности1. Пусть дан конечный набор булевых функций В = {/ь • •. ,/т} где /¿: {0,1}4 —» {0,1} (т. е. /¿ имеет n¿ аргументов), называемый

1 См. Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики, вып. 10. — 1963. — С. 63-97; Лупа-

базисом. Пусть каждой функции /г- 6 В приписано положительное

число - вес р(/г) этой фуНКЦИИ. Схемой с ВХОДаМИ Х1,...,Хк и

выходами ух,... ,уе называется конечная последовательность команд 5 = Ль А2,..., А/> Команда Д- имеет вид = • • •, *г(0,1')> где

2г — вычисляемое этой командой значение, <Р1 — один из элементов базиса, г (г) — число аргументов функции у?,-, а — либо одна из входных переменных, либо результат какой-либо из предыдущих команд (т. е. ¿у,- есть либо хи, либо где V < г). В качестве выходов можно взять любые из величин хи и/или г1>. При таком определении очевидно, что схема с к входами и I выходами вычисляет некоторый булев оператор Р: {О, I}*1 -> {0,1}г. Сложностью Ь(в) схемы 5 называется сумма весов составляющих ее функций, т. е.

¿=1

Сложностью булева оператора L(F) назовем min £(.*?), где минимум берется по всем схемам, реализующим F. Вообще говоря, сложность может быть определена не для всех операторов (для какого-либо оператора может не найтись ни одной реализующей его схемы). Чтобы такой проблемы не возникало, будем далее считать, что базис В полный, т. е. схемами в этом базисе можно реализовать любой оператор F. Если рассматривается множество операторов, то можно ввести функцию Шеннона L(n), взяв в качестве значения L(ri) величину maxL(F), где max берется по всем tv местным операторам F из рассматриваемого класса. Естественно, что все введенные величины — L(5), L(F), L(n), — зависят от базиса В. Как показано в указанных работах О. Б. Лупанова, при этом существенное влияние оказывает величина

. рШ

РВ = mm-

тц>2 7b¿ — 1

нов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования // Проблемы кибернетики, вып. 14. — 1965. — С. 31-110; Лупанов О. Б. Асимптотические оценки сложности управляющих систем. — М.: Изд-во МГУ, 1984.

где минимум берется по всем тем элементам /г- базиса В, которые имеют по крайней мере 2 аргумента (т. е. щ> 2).

Для функции / : 7дг —* 7дг при N = 2" можно обозначить через £(/) ее сложность, если отождествить / с булевым операторам /: {0,1}" —♦ {0,1}", где вектор х = (жп_ь ..., г0) является двоичной

записью числа |5] = 2n~1xn-i -\-----1- 2°хо.

Обозначим

LApprm{f) =; mía L(ff)

т. е. сложность самой простой функции д, 1-приближающей функцию / в равномерной метрике || ■ ||, ||/|| = тахх \f{x)\.

1Арргач(К) =' таxiApprox(/)

f£K

— для класса К функций /: /2» —» /г»-

Нижняя (аналогичная так называемой «мощностной» оценке, обычной при исследовании различных классов управляющих систем) оценка для LApprox дается следующим утверждением.

Теорема 18. Если для некоторой последовательности дискретных классов

К2" функций /:/гп -1► -£2» (го. е., в двоичном представлении, /:{0,1}" —► {0,1}") выполнено соотношение

log Approx К2" , ,

----> оо (п —» оо),

nlogn

то

г Apprax (If 2" \ > log АррГОХ/Г2"

V ; ~ log log Approx jK"2" '

В §2 получена точная по порядку оценка LAрргох для классов Теорема 19. Пусть ш(-) — функция типа модуля непрерывности, для которой cj(t) ф 0(t) при t —» оо. Тогда

¿Appro* (я021.) ж X (я2;) (i + IlogW(2-)) ;

эти же оценки верны для периодических классов и для внешних дискретных аналогов.

Теорема 20. Пусть и>(-) — функция типа модуля непрерывности, г £ N или г = 0 и х I при £ —► 0. Тогда для любого

а N л ?

класса К^ = К^, , К^и, Кгы имеет место оценка

W(2-"log(l/W(2-"))'

где — функция, обратная

Существенный частный случай ш(£) х 0 < а < 1, дает оценку сложности порядка

p2n/(r+a) j

п.;

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

Далее (§3) рассматриваются классы аналитических функций. К сожалению, в случае аналитических функций получить асимптотику или даже порядок сложности реализации схемами не удается. С помощью могцностных соображений можно установить нижнюю оценку сложности порядка n2/ log п (для схем, вычисляющих аналитические функции с точностью п знаков). Тривиальная верхняя оценка сложности получается при вычислении аналитической функции1 через разложение в ряд Тейлора и организации счета по схеме Горнера и имеет порядок

0{n2\ogn log log п).

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

Для сложности приближенного вычисления дискретных аналогов аналитических функций получена верхняя оценка 0(п5 log nlog log п).

1 В данном случае имеется в виду вычисление аналитических функций дискретными операторами в смысле подхода А. Н. Колмогорова, или, что почти что то же самое, приближенное вычисление внешних дискретных аналогов аналитических функций.

о 2"

В §4 подобная оценка получена получена для классов при lnx = 0{г3). Она имеет вид

VAA'V- /оП

min -

fc 21ogfc4-iLogX(fc)+f \ Х/

. f(nk- logxityVffiP" ,3 2, , , ^ ^ min i-1/, П \ \ + к п loS ™ log log n .

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

1) возможность хотя бы в некоторых случаях сделать определения дискретных аналогов еще более эффективными; так, для класса можно в определении учитывать не разделенные конечные разности общего вида, а более узкий (не 3-параметрический, а 2-параметрический) набор конечных разностей вида f(x) — 2f(x + h) + f(x + 2/i); при этом, конечно, дискретный класс становится шире, но относительно порядка величин log Арргох и LApprox изменений не происходит;

2) указывается на возможность определения величин log Арргох и ^Арргох не для равномерных 1-приближений, а для 1-приближений в других метриках;

3) рассматривается другое изменение определения величин типа log Арргох или ХАрргох, состоящее в замене 1-приближения (^(^-приближением, где const < <p(N) <С АГ;

4) исследуются классы монотонных функций и выпуклых функций, определения которых «несимметричны» с точки зрения замен вида / -* const -/;

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

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

В §1 рассмотрен другой вариант дискретного аналога класса Н2 а именно

Щс = {/: In In | (Var, Л, 0 < х, а: + 2h < N)

|f(x) - 2f{x +h) + f(x + 2h)\< Ch2/N + 2}.

Для него также имеет место равномерная по С оценка

log ApproхН^с a VCN.

В §2 указывается на возможность рассмотрения 1-приближений не в равномерной метрике, а в метрике, порожденной нормой

/ N-1 \ VP

Показано, что при переходе к этому определению оценки для классов и сохранят тот же порядок. В §3 предлагается рассматривать не 1-приближение, а ^(^-приближение, где 1 <С <p(N) <С N при N —» оо. Пусть Арргох^,

KN

— минимально возможная мощность <р(Лг)-прибли-жающего класс KN множества;

(К2") — соответствующая функция Шеннона для реализации схемами, т. е. min ¿(Л), где минимум берется по всем ip(N)~при-л

ближающим класс

множествам А. Тогда, в частности, имеет место

Теорема ДЗ. Пусть функция <p(N) принимает натуральные значения, lim/y-,«, <p{N) = оо, limjv-юо <p{N)fN = 0. Тогда

logApprox^fffj ~ NJv(N).

Существование асимптотически точной оценки для log Арргох^ Н^ дает надежду на получение столь же точной оценки сложности (р(271)-приближенной реализации функций из И действительно, имеет место

Теорема Д4. Пусть функция <p(N) принимает натуральные значения, lim (p(N) = оо, lim <p(N)/N = 0. Тогда

iV—*оо

N—юо

¿Арргох,, СЯ2М ^ 2"/р(2П)

В §4 рассмотрены дискретные аналоги классов с несимметричными ограничениями (монотонные и выпуклые функции). Пусть

Мх = {/: [0,1) -> [0,1) | /(х-) < /(у) при ж < у}.

Дискретные аналоги этого класса являются монотонными (неубывающими) отображениями /: причем

N < log ApproxMj = log ApproxMf < 2N - 1.

Далее, обозначим класс выпуклых функций, обладающих свойством Липшица с константой 1, через Мг. Иначе говоря,

М2 = {/: [0,1) [0,1) | | Ai(/; x,z)| < 1, Д2(/; х, у, z) > 0, х < у < z}.

Дискретный аналог этого класса есть

М;

■N

N

In

\g{x)-g(z)\ < \x-z\,

9(У)<

У~х < \ , z~y i \ a\z) + -—rs(®)

z — X

z — x

x < у < z

Для этих классов выполнена

Теорема Д5. Имеют место оценки

Нс (Mi) х у/ТГе\ log Арргох Щ х log Approx М* х л/n.

•Интересно отметить, что log | х log |j х N2/3, хотя для всех «гладких» классов Нпи даже для всех бесконечно гладких и аналитических классов мощность не меньше 2N (и обычно равна 2N^l+0^r>\ если гладкость выше лишпицевой).

Кроме того, в §4 рассмотрен класс «обычных» выпуклых дискретных функций, для которых

/(у) < (г-*)/(») +(у-»)/(*).

~~ г - х

Теорема Д7.

1О52 ~ {2тт^2р\о£2 е)л/ЛГ.

В §5 рассмотрена реализация функций из классов Н£'с и Н%с в базисах из всех функций с т входами, где то —* оо при N —> оо. Для соответствующей функции Шеннона Ьт установлена

Теорема Д8. Имеет место оценка (к > 1, с > О, N — 2П):

' 2т + mlogN

Эта теорема допускает естественные обобщения. (Всюду N = 2", т. е. речь идет о булевых (п, п)-операторах.)

1) Если рассмотреть вместо условия Липшица на производные условие Гёльдера, то для классов где г > 1, с > 0, получится оценка

ДГ1/Г

Х^Ю = х 10*N +

2т + т log N

2) Для классов /Г^ при к > 1 имеет место оценка - X №

где £ = \¥(х) — функция, обратная к х =

Таким образом, в диссертации получены следующие основные результаты:

1) предложена методика построения дискретных аналогов для различных классов непрерывных функций;

2) разработаны методы приближенного табличного и схемного задания функций из дискретных аналогов классов непрерывных функций различной гладкости, позволяющие получать достаточно точные (в большинстве случаев — по порядку) верхние оценки величины logApprox (дискретного варианта е-энтропии) и сложности приближенной схемной реализации;

3) для классов бесконечно дифференцируемых функций предложен метод построения е-различимых подмножеств достаточно большой мощности (эта конструкция применена для получения нижних оценок в указанном случае);

4) в результате построена полная (с точностью до порядка роста величины logApprox) шкала классов дискретных функций: для любой наперед заданной функции, растущей «достаточно регулярно», причем не медленнее log A*" и не быстрее N log Аг, можно указать класс дискретных функций именно с таким порядком роста величины log Approx (указанные границы отвечают, соответственно, классу всех констант и классу всех вообще дискретных функций);

5) параллельно были исследованы соответствующие классы непрерывных функций и получены оценки порядка роста их е-энтропии, покрывающие диапазон от log(l/e) до (1/е)с, с > 0.

Пользуясь случаем, автор считает своим приятным долгом выразить искреннюю благодарность своему учителю, чл.-корр. РАН, проф. О. Б. Лупанову за постановку задачи и постоянное внимание к работе.

Список публикаций по теме диссертации

1. Аманжаев Г. Г. Дискретный аналог гладких функций // Сб. «Алгебра, геометрия и дискретная математика в нелинейных задачах». — М.: Изд-во МГУ, 1991. — С. 4-24.

2. Аманжаев Г. Г. Дискретные функции с заданным модулем непрерывности // Вестник Моск. ун-та. Сер. 1 (Матем., механ.). — 1992. — № 5. — С. 86-89.

3. Аманжаев Г. Г. О дискретных аналогах непрерывных функций из некоторых классов и сложность их схемной реализации (дисс. ... к. ф.-м. н.). — М.: МГУ, 1992.

4. Аманжаев Г. Г. О дискретных функциях с заданным модулем непрерывности // Сб. «Методы и системы технической диагностики». — Саратов: Изд-во Сарат. ун-та, 1993. — С. 14-15.

5. Аманжаев Г. Г. О дискретных аналогах аналитических и других бесконечно гладких функций // Вестник Моск. ун-та. Сер. 1 (Матем., механ.). — 1995. — N1 5. — С. 18-23.

6. Аманжаев Г. Г. Дискретный аналог бесконечно дифференцируемых функций // Сб. «Теоретические и прикладные аспекты математических исследований». — М.: Изд-во МГУ, 1995. — С. 22-26.

7. Аманжаев Г. Г. О дискретных аналогах классов непрерывных функций различной гладкости // Докл. РАН. — 1995. — Т. 342, N 2. — С. 54-58.

8. Аманжаев Г. Г. О дискретных приближениях непрерывных функций с ограниченной второй производной // Дискретный анализ и исследование операций. — 1995. — Т. 2, № 2. — С. 5-15.

9. Аманжаев Г. Г. Об е-энтропии и дискретных аналогах классов целых аналитических функций // Дискретный анализ и исследование операций. — 1996. — Т. 3, J* 2. — С. 3-14.

10. Аманжаев Г. Г. О дискретных аналогах классов функций, задаваемых модулем непрерывности n-й производной // Вестник Моск. ун-та. Сер. 1 (Матем., механ.). — 1996. — № 2. — С. 3-8.

11. Аманжаев Г. Г. О дискретных аналогах функций дробной гладкости // Вестник Моск. ун-та. Сер. 1 (Матем., механ.). — 1996. — № 4. — С. 3-7.

12. Аманжаев Г. Г. Об е-энтропии и дискретных аналогах классов целых аналитических функций // Mathematics and Operations Re-

search. — Warszawa, 1996. — N2 10.

13. Аманжаев Г. Г. Дискретные аналоги бесконечно гладких функций // Mathematics and Operations Research. — Warszawa, 1996. — № 10.

14. Аманжаев Г. Г. Дискретные аналоги бесконечно гладких функций // Дискретный анализ и исследование операций. — 1996. — Т. 3, № 3. — С. 3-39.

15. Аманжаев Г. Г. Эффективная конструкция дискретного аналога функций с ограниченной второй производной // Вестник Моск. ун-та. Сер. 1 (Матем., механ.). — 1997. — № 2.

16. Аманжаев Г. Г. О дискретных аналогах выпуклых функций // Математические вопросы кибернетики, вып. 7. — М.: Наука, 1997.