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

Ш 1 я $

¿КОВСШ'1 ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ P1.L

И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ilOMHOCOt

На правах УДК 517. 5,

Гашков Сергей Борисович

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

дальность OL. Ol. 09. - математическая кибернетика

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

МОСКВА - 1992

^^^^^^ 'й-иатекагического факультета Московского стеэнного университета км. И. В. Ломоносов:

даальные оппонента : доктор фкзико-иатеш профессор А. А. Карацу доктор фкзнко-штема В профессор В. Н. Сачков

■ доктор физико-матена

■ профессор В. И. Тихоми V Идущая организация - институт ыатеяатики Сий | 1 I отделе

Защита диссертаций состоится " j | б \fic- 03 мин. аа заседании Специализированно во вкатике № 2 (Д. 053.03.05) при МГУ по адр& МсА,Ленинские Гора,МГУ, «пханико-кгтекатическ йу/ория 14-08.

С диссертацией кожио ознакомиться в бж штеиатяческого факультета ИГУ С Главное здание, 1< Автореферат разослан " сгк^ц?^ Учений секретарь ^

Специализированного сове га Д. 033.05.05 ври МГУ, д.ф. М.Н. .Проф.

чт5,ел I

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

Актуальность той u. Многие задачи теории приблисэ-цпй иогут бить сфорнулировани следус-адм ойрэлси.Пусть Й- банахово прсстранстио, а К и А -его подююзестга.тзхнсьчто для дабш х е Я я с > 0 найдется у е sS, удовлетворят--;::! неравенству g аг-у [¡< < с .Пусть гакгз -некоторый,фуЕКционад.сопоставляивдЯ

каэдоку у е А число ,называемое слошсстьв элемента у. Тогда спозиостьо с-пржЗггагеяия эшгганта х е К яазоваа число

¡К-*.«) = iпГ { ГЛу~> : у £ >1 , В х-и 0 < с > , а слоагостьп г-пркОяаяеция класса 5С - число

ЯЯ.гЭ = sup < Kx.t) : х е 5Г > . Например,в качзстпз X uosao взять пространство C(In) всои непрерывных функций f: In -»-К , опредолвнкшг на п-нараси замкнутом ик-

торвалэ Спараллэяяяияэдэ) ln = х ... к 1а с Е?\ = ,

1 < i < n ,с чейкаввсхся норкой | f g я ка» £ |ГСяЗ| : xeln J ,

а в качестве i - класс всех яолияошальтя Сравдюйалыюх) функций; поя слогносгьс функции обычно пояхшазтея степень полниоиа Срациональной дроби), рааяаз'ущей эту функции Сец. t i, 2D. Если км хотим,чтобы кара слоююстн функция более точно отражала время,затраченное на ее вичи<гл«юг-е,то в качества такой игры лучше взять ьа нямальноэ число производишь при этой аряфзатнчаояих операций-Поэтому представляет интерес изучение следугрего класса ыер сложности'.

Пусть В = ■( wи : k = 1,2,,.. } - вак'етороэ цаогзство непрерывна ■ аых функция vfj^. : С? -н R , называемое даяэе базисом. Сзеиой з

йазисе В назовем проазвольнул последозатэльл&еть непрерывных

йункцнЯ f((x) .....fLCx3, ж = С« ,.,. ,рсп) ,'в которой f|Сзс) = xi npif

I S 1 £ n, а каждал елфдуклзя функция fj вичасляется через кйадо-

ГО прэдшэствуванэ функция fi ,f. с яокощьа некоторой базисной

Ji . J.u

рункции w .- ¡гР-у- Ш огласка следующему равенству f^Cjs) =

• viff, Сх),.... ,f\ (ж) ).Слегзостьп сх&иы назовем чйейо L,a глубиной

• каксимальнув д-rafHy 'я®д5к?ся9довательностя ft ■ ..... f. , каядая

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

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

В, реализующей Г, обозначим 1.дШ; число ЦСП назовем сложностью

схемной реализации функции Г в базисе В.Аналогично определяем £ВШ -сложность форыулыюй реализации,и О0СГ) - глубину функции

Г. Аналогичные определения вводим и для вектор-функций.

В качестве Л возьмем множество всех функций ГС ж] е С(1П), реализуемых схемами в базисе В,а в качестве £ - любой из функционалов Ьр.Сд.Ор .Будем изучать асимптотическое поведение при с О

функций ЦСХ,£"),с),Р^СХ,г),которые,следуя установившейся в

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

Величина Ь^СГ.г;?, гле В = { х ± у ,яу ,х/ц ,1 },является достаточно естественной мерой сложности приближенного вычисления функции Г о точностью в,хотя в.этом утверждении есть большая доля идеализации Спредполагается,что все очерации выполняются точно и с одинаковой скоростью}. Для различных базисов Скак правило,содержащихся В В),и для различных индивидуальных функций и вектор-функций'Скак правило, алгебраических полиномов) .вопрос о вычислении ЦСП и других мер сложности интенсивно исследуется в так называемой алгебраической теории сложности [3). Лля булевых функций и базисов аналогичные исследования еще раньше начались в теории сложности булевых функций (41. Вопросы о сложности приближенной реализации непрерывных функций с разных точек зрения давно рассматриваются в теория приближений и в вычислительной математике [1-2,5-91.

Мы будем исследовать асимптотическое поведение при с 0 функций Шеннона еЗ.ОдСЯ.с) для классов Я,которые обычно

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

А

щионаяьных и кусочно-линейных функций. По-видимому, впервые »дойные вопросы рассматривались в IIО],а именно в случав % = ,,Ь] с К!! 8 = { х í у .ж/v Д I таи найдены асимптотики для C3U) и DgC3í,eí . Но зная в тот момент о [101,автор в С2.63

вторил эти результаты в несколько усиленной и обойденной форме, также перенес их на случай некоторых классов аналитических функ-й,и исследовал подобные вопросы для некоторых других базисов. Не будем ограничиваться базисами,содержащимися в {«¿у,у,ж/у,1}, равдывая это тем обстоятельством,что компьютерные программа час-содергат,кроме арифметических операций,еще'и различные элементные функции. В £11] фактически рассматривают,например,базисы,сс-эжаше радикалы и другие алгебраические функции,и называет соот-гствугщуи им «еру сложности алгебраической сложностью,а меру, этветствующув базису {%±у,ху,х/у,Ц - рациональной сложностью. Кроме конечных базисов,будем рассматривать базисы,состоящие из ючного числа функция и континуума констант,и называть оти бази-почти-конечнымн. Схемы в этих базисах можно интерпретировать как ;ели аналоговых вычислительных устройств,а «эру сложности LgCf : минимальную стоимость такого устройства для вычисления функции точностью с. Так как параметры,управляющие изменением функций, . лизуемых элементами аналоговых устройств,а также входы и выходы х элементов имевт ограниченную область изменения,то целесообразно ■ ли почти-конечных базисов глделить класс,состоящий из базисов, ввдх .лишь ограниченные константы (т.е. г.ртаадлежадиз данному от-<у),а в этой класса - подкласс,состоящий из базисов,содеряаэдх ько функции,удовлетворяющие условия Липшица (так как функция, тазуемкэ элементами аналоговых устройств,являются достаточно дома); такие базиса далее будем называть 'лишшцевыми. 1ряду со схемной,будем рассматривать также формульную реализацию, [улы образуют простой и вагный подкласс схем,причем любую схему :о,не изменяя глубины,лресбразсвть в формулу,Глубина является :ой мерой сложности,так как сна оценивает время вычисления ции с учетом возмокности параллельного использования многих ессоров.Изучение формул оправдывается тгкке тем.что некоторые вычислительных устройств моделируются именно формулами, ель работ и - исследование асимптотического поведения ций Шечнона LgCK.r) ,£вС?С,с) .DgCK.e) д.тч классов X,обычно

рассматривающихся в теории приближений,и для различных базисов ;

- обоснование эффекта Шеннона или доказательство существования в классе К функции,сложность ¿-приближения которой по порядку рав на соответствующей функции Шеннона ;

- доказательство существования в классе К функции,сложность „ ¿-приближения которой по. порядку равна заданной мере сложности ;

- сравнение возможностей различных базисов ;

- исследование сложности с-приближения некоторых конкретных функции;

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

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

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

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

Центральный результат первой главы диссертации,доказываемый в параграфах 4-6 (точная формулировка которого приводится во втором разделе автореферата)/является количественным аналоге;.! теоремы ; Вейерштрасса о полиномиальной аппроксимации в той же «ере.что и теорема Джексона. Однако доказательство этого утверждения осноеэн не на применении теоремы Джексона,а на использовании сплайноЕых методов [5,121. Поэтому в доказательстве вначале используется базис {х + у ,5ф , |х| ,-1/2} ,а потом устраняется использование |>.| за счет его приближенной реализации с малой схемной сложностью в базисе { х+у,ху,-1У2 У о помощью результатов § 3. Все ото можно рассматривать как возвращение на новом-Стеоретико-сложностном) уровне к лебеговскому доказательству теоремы Вейерштрасса. 6

Теорема 2.12 из второй главы,доказательство которой основано на вменении теоретико-вероятностных (теорема 2.1,в которой исполь-гется колмогоровская мера на бесконечномерных функциональных кометах) и теоретике-функциональных соображений (использование бази-, Фабера-Шаудера при построении упомянутых компактов),доказывает шествование функций,нижняя оценка сложности которых совпадает с лученной в упомянутом результате первой главы верхней оценкой. Вытекающая из упомянутой верхней оценки и энтропийных нижних енок функций Шеннона теорема 1.5 является надстройкой над работа-А.Н.Колмогорова и других авторов об с-энтропии в том же смысле, к и внешне очень похожие на нее результаты из работ [13-16]. осматриваемая в них постановка задачи о сложности приближенной ализации непрерывных функций была указана А.Н.Колмогоровым в <але шестидесятых годов [17]). Колмогоровская постановка задачи шчается от рассматриваемой в диссертации тем,что в ней пробна получения верхней оценки сводится к получение-верхней оценки шции Шеннона некоторого класса булевых операторов,которая потом 1а<?тся в рамках теории сложности булевых функций Св [15-16] -юмоаыэ метода локального кодирования О.Б. Лупанова [4]). :ашей постановке сведение к теории сложности булевых функций не ется,хотя в доказательствах•тоже используются идеи,параллельные ям 0. Б. Лупанова из теории сложности булевых функций. Другое отли-состоит в возможности использования различных не эквивалентных г другу базисов,в том числе и континуальных; все конечные пол-булевы базисы эквивалентны друг другу,что позволяет их все дить к базису ( ) Сем.напр. [4]). Проблема получения

них оценок в случае почти конечных и других континуальных исов значительно отличается от решаемой мощностным методом ,Шеннона-0. Б. Лупанова 14] соответствующей проблемы из [13-16], как этод метод приходится комбинировать с методом А. Г. Витушкина I,основанным на применении теоремы И.Г.Петровского-0. А.Олейник, ■которыми геометрическими соображениями. Кроме того,в работе 1едены примеры и незнтропийных нижних оценок функций Шеннона. Ь нижней оценки для ЬдСЯ, не следует никаких оценок для ',£) - мер сложности индивидуальных функций из К. А.Н.Колмогоров |амках своего определения сложности е-прибликения) [17] предпо-л.что в классах,обычно рассматриваемых в теории приближений,

существуют функции,меры сложности которых по порядку равны мерам сложности содержащих их классов. Возникает также вопрос о существовании Т е К,у которых меры сложности по порядку равны заданным функциям от е. Подобные вопросы о существовании функций с заданно!! точностью приближения пространствами полиномов ограниченной степей и вообще любыми флагами конечномерных подпространств рассматривали С. Н. Беркштейном [19] и А.ФЛиманом Ш,а о существовании компактов с заданными последовательностями поперечников - В.И.Тихомировым 12 В работе для многих классов доказано предположение А.Н Колмогорова и предложены методы,которые позволяют доказать существование функций с заданной по порядку сложностью приближенной реализации при незначительных ограничениях на последнюю.и существование "лакун" в мэрах сложности некоторых функций. Эти методы основаны на использовании теоретико-вероятностных.теоретико-функциональных и теоретико-сложностных соображений Св частности,результатов Н.Пшшенджера [20] о сложности систем мономов). '

Развитый в работе подход применяется также к исследованию сложности приближенного вычисления непрерывных линейных функционалов. С других точек зрения сложность приближенного вычисления линейных функционалов и операторов исследуется в так называемой теории аналитической сложности Сем. [6,7]).

Для класса функций п переменных.удовлетворяющих условию Липшица, исследовано асимптотическое поведение функции Шеннона сложности с--приближения этого класса при п ->- ш С так называемое "проклятие-размерностей") .

.Ряд результатов был получен с целью сравнения возможностей различных базисов (теоремы 1. 8-10,2. 6).Более полно это удалось сделать в гл. III в случае приближенной реализации действительных констант благодаря возможности использования многих известных результатов теории диофантовьгх приближений. В этой главе исследована тзчже связь задачи получения эффективных нижних оценок сложности приближенной реализации действительных констант с задачей о получении эффективных нижних оценок сложности булевых функций.

Работа написана под сильным влиянием статьи [21] А. Н. Колмогорова и В. М. Тихомирова и многие ее результаты.можно рассматривать как теоретике-слоя.нсстные аналоги результатов [21].

Приложения. Работа носит теоретический характер. Ее ре-

Б

¡ультати могут быть использованы в некоторых областям вычислительной (атематики .теории приближений,математической кибернетики.Так, в ка-1есгве приложения полученных результатов в работе выводятся некото-1ые (частично известные) утверждения о невозможности представлении |ункиий многих переменных суперпозициями функций меньшего числа пе-ерементга.Некоторые результаты работы имеют теоретико-автоматные налоги»,приведенные в § 8 гл. II.В работе найдены оценки ¿-энтропии екоторых естественных классов,вероятно не рассматривавшихся ранее, то время как колмогоровскув сложность можно интерпретировать как ценку числа битовых операций,необходимых для вычисления функции и применять ее для оценки сложности вычислений с очень большим яалсм значащих цифр ), величину Ь^СГ,е),где В = (х±у, яу<х/у) и К, эжно интерпретировать как сложность приближенного вычисления Г зи не слишком малых с, позволяющих использовать для выполнения зифмегических операций машинную арифметику Сили калькулятор). 1Я некоторых почти-конечных базисов эту величину можно иитерпре-фовать как минимальнув стоимость аналогового устройства для вц-юления функции Г с точностью с. Поэтому результаты работы могут |.йти применения при оценке времени вычисления сложных функций как . обычных,так и на многопроцессорных ЭВМ С осуществляющих распарал-ливанке вычислений),а также при проектировании программных моду-й и специализированных аналоговых устройств для вычисления' нкций.Возможны приложения в моделировании нейронных сетей. Апробация. Результаты работы докладывались на последних . тырех Всесоюзных конференциях по теоретической кибернетике,на местре по дискретной математике в центре им. С.Банаха СВаршава, энь 1985),на конференции ГСТ - 87 в Казани,на Ломоносовских эниях е МГУ последних лет,на семинарах О.Б..Лупанова,С. В. Яблон-зго, В. М. Тихомирова в МГУ,на школах-семинарах и коллоквиумах тодых ученых в Москве,Берлине,Нижнем Новгороде. Публикации. По теме диссертации автором опубликовано работ,список которых приведен в конце автореферата Стезисы док-(оа Всесоюзных конференций в него не включены).Еще 4 работы ав->а включены в список литературы диссертации,насчитывающий всего I наименований.

Структура.дисс. е рт а ц и и. Диссертация состоит введения.трех глав,состоящих в совокупности из двадцати двух

параграфов,и списка литературы. Полный-обьем - 351 стр.текста.

СОДЕРЖАНИЕ РАБОТЫ В параграфе 1 главы 1 излагаются необходимые определения.обозначения и некоторые используемые далее факты,в основном из анализа и теории приближений.

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

Пусть Я обозначает произвольное компактное подмножество С(1п);л.т.; которого при любом с > 0 определена функция Шеннона Предполагаем, что с достаточно мало,чтобы все встречающиеся далее выражения имели смысл.Индексы при константах и знаках 0(1) указывают на ■ зависимость этик констант от величин,указанных в индексах.ш теорема является аналогом нижней оценки функции Шеннона из 14]. Теорема 1.1. Для любого конечного базиса справедливы неравенства * Н(Ю , 1од1од Н (90 - °|В|,рв'.п(1)1 Г,вСЯ,е) > Рв-ТодТртТ 11+ - !од уХЭ-- ]■

СдСЯ.е) > С|В| П Не(50, Б0СХ,с) > тв(1од Н£(Ю - 0|В| ПШ) . Теорема 1.2.

(1) Если В - Липшицев базис и с < е(Ю, то

LB(9U) > cBmin(/На£СЮ',Ha£CJD/logl/e), Dg(9i,e) > rBlog HaeCSQ - Cgloglog max ,(Нг£.СЮ. 1 A) . CiD Если все функции из В удовлетворяют условию jf(x)-fiy) |£||х-у||, то при е ->- 0 LqCSU) * ^ HaeC30/lcglA .

(ill) Если у f (feB =» (у i(coi (Cf,r)<t))),to при с —>- О

,£вСЯиЭ X Н fiC30/£log max (Нае(50;1Д) .

(lv) Если В является обьединением липшицева• и «егалкинского \~.::::ос:ь (базис,состоящий из рациональных функций,назовем жегалкинскич.если все его функции содержат переменные только в первых степенях) и все его константы ограничены (т.е.принадлежат некоторому отрезку), то £в(Ж,£) удовлетворяет тому же неравенству,что и L¡}(ЗС,е) в n.Ci).

Условие ограниченности констант в базисе В необходимо для справедливости всех утверждений теоремы.а в п. Civ) заменить £ на [..или уб-

рать ограничения на полиномы,входящие в базис,вообще говоря,нельзя.

В следующей теореме рассматриваются почти-конечные базисы, содержание нее действительные константы. Теорема 1. 3.

(1) Если В-полиномиальный базис и с < е(5Ю , то

LBca,í) > rain (Ссв/п)/Нге(50 , Нг£СЮ/21од 1 /с ), DgCX.e) > Tglog Нг£(30 - Oß(loglog max CHaCCSD, 1/е)). (и) Если В - полиномиальный жегалкинский базис,то при е—у- О £в(?:,с) i (С1 f pg)/Cn+l))H2£(fO/log max(H2£(50,iÀ) . Cm) Если В - рациональный базис, % с V(r,M,N,In) и е < еСЮ, то

LBCX,£) > minfovfi^îQ.i H5s+2fi3CÍQ/loglA],

Dg(?[,г) > Tglog Hgfit2e,(5Q - 0Bnr(loglog шах (H^^C*), !/*))•

(ív) Если В - рациональный жегалкинский базис, % с W(r,M,N,In) и £ < Í.CÍK,БЭ, то ÈgCSC.e) > (срС1 + PgD/h)^ ^ гСХ)/1од1/£ .

Заменить условие рациональности базиса на более слабое условие аналитичности,вообще говоря,нельзя. Для произвольных компактов % с С(1п) теорема 3 (iii),Civ) не верна.Показано также,что оценки теорем 2 Ci),Ciii),(iv) и 3,вообще говоря,достижимые по порядку.

В параграфе 3 доказываются некоторые используемые далее вспомогательные утверждения,которые имеют и самостоятельный интерес. Лемма 1.38. Пусть В = С х-у,ху,1/2 >.Для любых а. > 0 и n е N можно построить алгебраический полином fn степени n такой,что при |x|S а

max(0,|x|-0((3/4)na)5 < fnCx3 < |х| и LB(fn) < 0<rn-log( |log л|+1))

Теорема 1.4.Пусть В = < х-у,ху, 1/2 ) и fCx) e CCD - кусочно-рациональная функция,составленная из s рациональных функций fi степени Меньше d. Тогда при с < 1/4

LBCf,£ ) < 0(s log \/с + sd(logl/s)/loglogl/с) + OfCl).

В параграфе 4 доказаны некоторые вспомогательные утверждения,

сформулированы доказываемые в параграфах 4,3 и б теоремы 1.5-1.7.

п #) _

Пусть Wj- любой из классов W^r.r' ,M,N,In),w О е I,r,r' ,M,N,In

фиксированы,а число с стремится к нулю. Тогда справедливы следующие

«

теоремы (в оценках которых с целью простоты записи зависимость констант в знаках X , ,0 от различных параметров класса Wj не отмечается). ,

Теорема 1.5.Для базисов В = < у,ху,с--j 1/2 ) справедлива оценка

4(4^ OCH^W^/log Н^)). Теорема 1.6.Для базисов В=(х(±)у,ху, |х| 1(---,1/Н} справедлива оце:1ка Ci) tBCWlr£:> < 0CHc(WA>>.

Для базисов В = С х-у,ху,|х|> U [0,1] или { х+у.ху,|х|) и [-1,1] справедливы оценки * ^'

CiD /n£WLj* Е^.е)* H^Vp/log Hc(Vp .

Для базисов В = С х^у.ху > U [R или ( хс±3у.ху,1/х > U S справедливы оценки

СШ) He(Wt)/log £B(WilC) ^H^vp ,

а в случае n = 1 - равенство

Civ) Ев(«х,о * He(Wp ..

Формулировка теоремы 1.7,посвященной оценке функции Шеннона Dg(W^,с) при различных В,с целью краткости здесь не приводится.

Сначала теорема 1.5 доказывается для базиса ( х-'у.ху, |х|,-1/2 ), а функция |х| устраняется с помощью леммы 1.38. Отметим.что для

меры сложности £в(К,е),где В = ( х-у,ху,|х|) U (0,1) или

< х+у,ху,|х|) U [-1,1],проделать это не удается,как показывает теорема 6 Cii),(iv).Причина,в частности в том,что функцию |х| нельзя с-приблизить на отрезке,содержащем нуль,формулами в базисе В = С х+у,ху) U К сложности по порядку меньшей,чем 1/сс

Теорема 6 Cii) интересна еще тем,что показывает,что наличие в базисе |х| и всех констант из некоторого отрезка компенсирует ограничения на "топологию" схем,накладываемые понятием формулы.

В § 4 доказывается теоремы 1.7,1.6Ciii-iv) и строится грубое приближение с невысокой сложностью в виде гладкого сплайна 112]. Разность между функцией и ее указанным приближением имеет норму,не превосходящую сС1од1/«)с,и по порядку те же модули непрерывности, что и исходная функция. Приближение с точностью е этой разности осу-П

.ествляется с помодью лагранжевых сплайнов [5] в одномерном слу-ае в параграфе 5,а во многомерном-в параграфе 6. Для оценка слож-ости построенных приближений в обоих параграфах используются идеи . Б.Лупанова из теории сложности булевых функций,но различие между араграфами существенное.

Отметим еще,что при доказательстве теорем 1.5 - 1.6 оценивается е сложность всего класса,а сложность каждой индивидуальной Функции з него и эти теоремы на самом деле вытекают из следющих более об-их результатов: для любой функции f £ С(1п) и г € ffT при В = { х-у,ху,1/2 > и n = 1 верны неравенства

LBCf.c) < 0(Xr fCe/cr)/logXr J(£/cr) > 0fC»)f. при n ï 2 - неравенства Lg(f,c) ^

и В = ix+y.xy,|x|> U [-1,1],a в случае n = 1 при дополнительном ловии log Хр j.(e) < 0р ,-( logl/с) .справедливо неравенство

при В = < х-у,ху,|х|,1/2 > - неравенство

£B(f,s) < 0(Xr f<ccjj[i||)),

э С||гц - некоторые константы, большие 1 С с целью краткости исполь-5М всюду без оговорок одинаковые обозначения для различных конс-ггЭ . В параграфе 7 доказывается теоремы 1.8-1.9, уточнящие при n I и г ^ 2 результаты параграфов 4-6.Теорема 1.9,доказываемая с ющыо теоремы 1.8,уточняет и обобщает последнюю,поэтому с. целью скости здесь приводится только ее формулировка.Везде далее для •бывавших функций о(т) определим и'ЧеЭ как шах )т :о(т) = с}. ! о р е и а 1. 9.

Пусть шСт5 - выпуклая мажоранта модуля непрерывности uCf,r),

) е CCI), и KfCc) равна по определению 2|1 I/o"1 (2е), ^(с) -v- а>

да для В = { х - у, x/Z, 1 I

rfCe) , 41oglog + 0(13 , r'e) s log rtie) l1 + -log Md- j + .°|f|, Ш(П'

случае В = { x - y, xy, 1/2 } в этом неравенстве множитель 4

H

надо заменить на 6.

При rfCe) < 0(|-log и В = { х - у, х/2. \х\, 1 }

ЁВСГ(£3 < OiKticrs/rrCs))) [U yog "ijil^l^^^OClogC [|f Ц+2)) .

а при В = ■{ X - у, \х\, 1 } U { сх : 0 < с < 1 }

* log

(И)" Пусть ^(с) равна по определение

С |I |logCk+3))/(2u;,Clc£/Ck+4))), где ы^Сг) = o^Cf,О - модуль непрерывности второго порядка,к Л, е -ь 0 , ||f ||, )1 |,ои = ыг(|1|) фиксированы.

Тогда для В = { х - у, ж/2, |х|, 1 } или В = \ х - у, 1/2 ^ . , „ . УгСе-вДгСе)) , OCloglogyfCc-c^Cel)) .

LBCr'eJ * log r^e-eAfW) 11+ log y^c-c/y^e)) J При rfCe) * 0(| log и В = \ x - y, x/2, \x\, .1 \

tgCf ,£) < 0(rT(c-£/r{t£))'), а при В = -{ x - у, \x\, 1 } U { сх : 0 < с < 1 }

•'Ь^^ат) • '

Отметим,что теорема 1.9 (i) в применении к классу V CI,M.N,С^а^ асимптотически точную оценку, а согласно теореме 1.1 остаточный ч.-vj в нижней оценке отличается от такого же в верхней асимптотически г 6 раз. Теорема 1.9 интересна еще тем,что в ней получены уточнявшие результаты параграфов 4-6 оценки и для базисов {х - у, х/?., |х(. 1} {х - у, \х\, 1-}. -U {сх : 0 < с < .у ,вв содержащих элементаумно«он;:: и в доказательстве не исшлЕзувтся гладкие сплайны. Получить подобные оценки в- терминах модулей непрерывности порядков вдае второго уже не" представляется возможным.

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

графов,она получена для довольно широкого класса базисов (правда, ft

лишь для "формульной" меры сложности).

Опенки для Ls(W(r,M,N,In),г),полученные в § В, отличаются от

сответствуквд;: пгжник оцякок в с^^ раз. Это вызвано не только

аналогичный расхождением в оценках для с-энтропии,приведенных в § 1,но п грусостьв относительно параметра п метода § 6. В следующем важны,; частном случае его можно уточнить,что и сделано в § 9.

Пусть Y s ?Р,для любого i о^СгЭ - выпуклая мажоранта модуля непрерывности функции Г е С(1п) по i-ой переменной, и у ¡-С ei равна по определению 11n |/ h( ... hn,где ht = 2toJ'(k4 e/(2+|k |)), |k| = £ k4. ЭОозначим ,-. j. соответственно'среднее арифметическое, гео-

метрическое и гармопичзское чисел UjCIIj !)• Знак g * СХП ооначает, что cf < g i Cf, где с и С - некоторые константы.' Г е о р е н а 1.11.

Пусть В = ( ж - у. Щ, 1/2 },u4ff,o9>f,|lf||,niax{|I1 |+ l/|It [\ ограниченны,тогда при с i f и п -у- <о LjjCf.e) < 0(nlog(l<- max kt ) )ff (c-cfy^-Чс) ) /1 og^f(c-c/VfC e)) :сли ri = | ^ !/гш-'(к. ¿Д2+|кр) ->- « при всех 1, то множитель OCr) гожнс заменить на о(п),а если yi/log п ->- ю при всех 1,то множитель )(п) можно заменить на 1+оШ. Если п фиксировано, ас-)- 0,то

"В * log(l+max k^j rri^/r{U))[u log )•

!сли для любого i = .г{.(«)1/п+ОС15(условие однородности),то ео icex предыдущих неравенствах можно заменить log(l+ пах к.) на од(1+ min ).В частностиCID = M(-t , выбрав kt = 1,ка = ... s kn = в',получаем,что при ограниченных ЙП>ыа f¿..шадА^+ИуцД laxiMj |I, iJ/niniMj JIj |}, при с < iù0' r u.r{te) -ь в

Lg(f,e) S (UoCl))H/lög H , ДО H = 3(n/ß)n(U /е)п. -3<n/2fi)a |Г| П M. .

В § 1 гл. II для некоторых бесконечномерных компактов в С(1п)

' <5

получены нижние оценки,обосновывавшие вместе с верхними оценками § 3 аналоги эффекта Шеннона [41 .

Пусть система функций {р^: к € и/1} удовлетворяет условиям пункт;

1 параграфа 7 С451,т.е. существует число А такое,что для любой

конечной линейной комбинации £ а^р^ <= С(1п) справедливо

неравенство Бир 1^1 < || II - А Е 1й)( I >И пусть убывающая пс

каждой переменной функция 7 : 10,+ю)п —>- такова,что ряд

Е УСкЗ сходится. Обозначим Я класс всех функций Г = £ а^ру , кеГ кеГ

коэффициенты которых удовлетворяет неравенствам |ак| 5 ?СкЗ.

Положим в(еЗ = 1од ^^ ЯкЗ/е) ■!

Теорема 2.1.Можно построить колмогоровскую меру на Я такую,что для любого конечного базиса В,для почти всех функций ( е И и любого е < еШ справедливы следующие оценки

вСс) 1од1од ССс) - св „ -,

С13 ЬвСГ,еЗ > „д ТБГШТ (1 . ]од ЦСеЗ )

СИ) СдСГ,с) > св пССеЭ

С11П ВдСГ.с) > тв1од БСг) - Сд п .

Для почти-конечных базисов в § 1 доказаны также теоремы 2. 2-3,которые можно рассмативать как уточнения теорем 1.2-3 в той же мере, в какой теорема 2.1 является для классов 1 уточнением теоремы 1 1.

В § 2 доказываются две теоремы о сложности вычисления полиномов. Произвольный полином КХ) е ИХ! ,Х=(х1.....хр) .записываем в виде

Г с.Уа, где а = Са.....а 3 е (№, Ха = х/ .... х°п , Мг с 0<п .

аеМга ' " < п 1

Множество всех полиномов ГСX) б XI.таких,что М^ = М,обозначим КМ);его подмножество,состоящее из всех полиномов с коэффициентами

О,...,к-1,обозначим ^СМ). Множество М с иЛ назовём правильным,есл! вместе с каждым вектором оно содерзсит и все меньшие его вектора Спо определение а 2 если при всех 1 с^ 5 /5^3. Множество

{ У е : а £ ^ 5 /? } назовем п-мерным интервалом. Модность М обозначим |М|. 16

Теорема 2.4. Пусть базис В = < ху,х-у,1/2 ),М - правильное множество logk|M|—х- оо . Тогда справедливы неравенства

С О ma:c L„Cf) = ЦС^СЮ) < Ге^Ю Б к

|М| , 41 og.„loq„jM| + O(n+log к). , 1- J- , -, „

-—Mm n log|M|]+2

(MI r 31ogKlog 1M| + 0(1), , „ , "" W"» 4ляг[1+ log\|H|-)Л(|НП«Р-Х<0>|)

fui) Если И - правильный п-меряый интервал,то

1Ш , 51og„logJM| + 0(1),

4*V»> ' üfW^ К log'.lHI-)

(iv) Пусть ? : D(n—>- К - функция,убывающая по каждой переменной, f(X) = î^aapaCX) - обобщенный полином,где M с Gf1,^ б С£1п),

аа 6 'аа' ~ е " функция,равная loga (J^liCa) I/«].

С - число равное Y - число,равное Г^Цра|| .Тогда

GC е/ЭК) , 31og?log?G(e/2K2 +0(1), i Log^ygüt1* -log.L/dlj-J+0( |M|+loglogl/£) +

+ LB(( f>a а 6 M У,с/2С) .

• Теорема 2.4(i)-(iii) справедлива и для полиномов над конечны)! полем и соответствующего бази:а < 1,ху,х+у >.Она является обобщением некоторых результатов С10],а ее доказательство основано на конструкциях,параллельных конструкциям О.Б. Лупакова [43; из нее получается как следствие частный случай теоремы о сложности реализации булевых функций.схемами из функциональных элементов 141. Теорема 2.5. Пусть M с if1- правильное множество. Ci) Для В = ( 1,ху,х+у ) справедливо неравенство

DB(?kC№) < logt(|M|logsk) + 0/£Гдг(п+1) 1ода(|М|1одгк) ', а для В = { ху,х+у > U DR - неравенство

DB(rtM)) 5 logJM| + 0/1+ ,1одгп 1одг |М| (11) Для В = ( 1,ху,х+у > справедливо неравенство tBC^(M)) < 3]1одак[ |Н| - 2,

а для В = { ху,х+у 3 U К - неравенство

t (ЯЮ) < 3|М| - 2 .

Cili) Если М - правильный интервал и В = С1,ху,х+уЗ,то при г. ->- ю „ , - Ofn/log п)

- Iög£T • а ПРИ 1о9гк + • • + dB = 2

DB(J>kCM3) = logJM| - 1ода1одкп +0113 .

Теорема справедлива для класса всех многочленов от п переменных степени не выше р-1 по каждой из них над полем и базиса хy.:-;* /, I)

где операции.берутся по mod р.Любая функция р-значисй логики от п переменных однозначно представима многочленом из этого класса.поэтому для класса P¡} всех функций k-значной логики-от п переменных при простом к справедливы равенства

Lg(P[)) ~ kVlogkn . D0(P£) = n log.к - log2logkn + ОС 13 .

Эти утверждения являются обобщениями соответствующих результатов из С41,[221.Другое обобщение имеется в С231. Теорема 2.5(i3.(iii) является некоторым аналогом результатов [24-25] и [43.

В теории сложности булевых функций асимптотически точные оценки получены 0. Б. Лупановым для любых конечных полных базисов [4]. Получить подобные результаты в рассматриваемых в настоящей работе задачах не удается,однако справедива

Теорема 2.6.Для любого полного жегалкинского базиса Ё,такого,п- - . р.. справедлива оценка tB(KM3) < 0( |М|) .

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

• параграфе 1, и положим Яи) = < к : 5Ск) > и ), РСи) = ¡ЛцЗ|.'

QCu) = - Т log ?Ск) , RCu3 = Г " ЛкЗ , к,НкЗ>и к,7Ск)<и

vCu) = шх < V : RCy3 < и/2А > , s(u3 = PCv(u)) = |SCu31 , SC и) = < к : ?СкЗ > v(u3 >,<5Си) = 2ЙШ 'w(u) = шах < v(!JMCu)

тси) = scu31ogj^j-j - qcw(u33 . Для класса Я,определенного как и в параграфе 1,доказывается /8

Теорема 2.7.

ЦС».*)^^3^^,! 0»-)+0(sCgmogIogl/£)*LB(V8§).

где С = В = < х-у.ху.1/2 ).Фе = < ^Cx):* е SC«)}.

Для системы функций »^(хЭ е С(1п) такой,что для любой линейной комбинации || £ а.),^ Ц = sup |ak|,в частности ïp^ï = 1 для всех к,

доказывается аналог теорем 2.1 и 2. 7 - теорема 2.8. Из этих теорем в параграфе 3 выведен ряд следствий,из которых

с целью краткости здесь сформулируем одно.Следуя 121].рассмотрим

р

семейство функциональных классов СЮ,состоящих из функций f 6

C(In) .имеющих аналитическое продолжение на G с d\ ограниченное по модулю константой N. В качестве G можно взять эллиптический полицилиндр Э[ >;... х Эп ,где - эллипсы с фокусами и суммой

полуосей яг или произведение полос Р СсМх. ..к PnCdnD,где P^Cdpi

С*

= { : : |Im < },причем в последнем случае класс А^пСЮ по ■

определению состоит из 2л-периодических по всем переменным функций, и 1п = [-п,л)п.

Следствие 2.1. Пусть базис В = С x-y,xy,cos х,1/2 > и А - любой из упоминавшихся классов. Тогда сг~аведливы неравенства

H (A) , loglogHJA) -ОСП. Н,СА) r 31oglogHJA) + Offl,

logH£U)[u logH/AJ . J-LBCA'fi)-IôgH^ l1+ logH^AJ. J

tBCA,£) = ÎXHeCAD),

log Hfi(A) - OC 13 < DgCA.e) < log HfiCA) 0(VÎog Н£СА)) ,

причем cos x нужен в В лишь для справедливости двух последних соотношений для классов периодических функций.

Следствия 2.2-2.3 дают примеры континуальных аналогов эффекта Шеннона Сизвестного в теории сложности булевых функций [413. В следствиях 2.4-2.5 этот эффект доказан в ослабленной форме.

Следствие 2.10 показывает,что оценки теорем 2.2,2. З.вообщеговир.^ по порядку достижимые.

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

Î3

рост размерности ограничивается некоторой функцией от с Сер.с § 9 главы 1)

§ 4 носит иллюстративный характер и посвящен оценкам сложности некоторых конкретных функций,строящихся в классических контрпримерах анализа,а именно разным вариантам функций Вейерштрасса.Ван дер Вардена,Кантора,Пеано-Гильберта.В нем доказывается,что эти функции имеют невысокую сложность схемной реализации, но с помощью "узких" схем,т.е. схем,у которых сложность и глубина полиномиально эквивалентны; сложность же их "формульной" реализации экспоненциально высока в сравнении со схемной. Другими словами,хотя эти функции и "легко реализуемы",но их вычисление Плохо поддается "распараллеливанию", ибо сложность их вычисления полиномиально эквивалентна глубине.Утверждения,доказанные в § 4,дополняют следствие 2.3, и показывают вместе с ним,что мера сложности £g(S,c) существенно зависит от базиса. Показано также,что некоторые варианты функции Вейерштрасса являются эффективными примерами функций,для которых выполнено одно из утверждений следствия 2.5,а в формулировке следствия 2.7 устранить ограничение на полиномиальные базисы, вообще говоря,нельзя.

В § 5 строятся примеры классов с неэнтропийньши оценками сложности и доказывается существование "лакун" в мерах сложности некоторых функций. Теорема 2.9.

(1) Пусть функции Ц (с), L^Ce) > 2L2(e), монотоно стремятся к со

при с -у 0 и не имеют "скачков",т.е. lim L (б) i 0( lim L. (¡5)).

6-х- 6~>-Е*

Тогда существует f е CCI), такая,что

fi(LaCc)) < £BCf,£) < ПСЦСе)) и для некоторых последовательностей \ei n} ,i = 1,2,таких,что е „ < « „ , lira с „ = lira с = о,

,1П *'п п-н» п-хя

верно равенство EßCf.e^) = 'где Б = и

Cil) Существуют функция f б CCI).такие,что меры сложности LgCf.e), tgCf.e) как для В = <К4-у,ху> U Клак и для В = (х-у,ху,1/2> содержат "лакуны", т. е.. для некоторой последовательности еп -у О 20

ри П -Ь 03

(^L0<f,Cn-5))/LBCr.Cn) -„«,

iii) Пусть LCc) $ 0(е~1/г),г t W , и ие иыеот "скачков",тогда /шествует f е VCr, Hf. ¡jfg. П .такая,что для В = Сх+у.ху) UK

tBCf,e) = fi<LC£)), в случае г б W то же самое верно для некоторой

Г е VKr.rH.MplfU.I). :ли log LCi) < о(1од1/г),то существует Г € C^I^a если '.с) < 0(1од1/с).то Г с AC9,Nf.D такие,что tgCf,е) = nfLCe)).

Отметим,что ограничения на LCc) в виде верхних оценок в п.С111)

¡транить нельзя.

Далее в § 5 получается некоторый аналог теоремы 2.7 и указывался примеры классов с оценками сложности неэнтропнйного вида.

га

'сть Я - класс всех функций f(x) = Т а Т Сх),где |а> I S Яп),

Л <чЛ П

П:0 ,7

- его подкласс,определяемый неравенствами Яп)/2 S ап>

= 1Яп)Т (х). л=о 3

Допустим,что^£ Л к) < пКп),или,что равносильно, nRn аонотоно

возрастает,где R = Г Кк).Тогда введенная в § 1 функция п кгп

и) = гаах)у(и),5Си)^,где ¿Си) = и/С2s(и)).будет равна vCu) и этому ТСu) = sCu)log2/dCu) - QCvrCuD = sCu)log4sCu)/J - QCvCu)). орема 2.9. Пусть В = <ху,х-у,1/2) я BR = Сху,х-у> U К. Тогда

ЭЛ9з1ЩНЬг0Ш) ♦

для почти всех f е I относительно некоторой колысгоровской мери

* I©Ы1 > ^fffe-^ - OCl^oe* sw>).

ли при всех k 1одКк-1)ДСк) 2 ПС1°9а kj/fc. Последнее условие вы-пняется для не слишком медленно убываюних Кк),например для

<) = 2_1с9 ^ при с £ а +1.Если к тому же а 2 1 и 3 sCs) > n(loglog 1 /с), то вычитаемое в скобках южно не писать.

л выполнении условия logK)c-D/?Ck) t D{loga k)/c,a > 1,

в верхнее оценке последнее слагаемое можно заменить на слагаемое 0(l/lcgû~l ТС s)) внутри скобок.

СШ Пусть №) й к"4"0,где с > О,тогда ta (д.,с) = П(£в (I.c) =

r r

ж п^Сг^ s tBCl,e) 1 £X3sC2í}) ♦ sC2e)logl/c,

причем,очевидно,уже при 3sCc)2 (Xdogl/c)loglogl/e) последнее слагаемоe поглощается первым и тогда

tp^Cg,.«) = nctBRC..O = fXtB(.,e» = (XtB(gs,0) = 0(3st2£)). Кроме того,для всех fe« tB Cf,¿3 > fl(3sU£})

® R

и для почта всех f с I относительно некоторой колиогоровской меры

Если к тому же tfiO/Kn+13 > С > 1,то для всех f el

tBCf,c) - fiC3sCí:)).

В следствии 2.12. теорема 2.9 применяется к конкретным функциям fCnD и получаются асимптотически точные результаты.

В § В показывается,что с использованием системы Файера-Шаудера Сем.[391,с,2Ш иохао методом § 3 получить во многих случаях точные по порядку результаты о существовании "самых сложных" функций.

Напомним,что W(r,M,N,In) есть класс всех функций f € С(1п}у,ко'гсри>

|f| S И и по каждой переменной производная порядка Ir-lt

удовлетворяет условию Гельдэра оСт) S M та, где а = г - ]г-1[ .

Теорена 2.11. Для любьос г < IN.r.M.N e R+,r> с IN в классе WCr.M.N.ll

судествуют функции f.такие,что для базиса В = С иу,х-у,1/2 >

flCH.CW) LB(f'e) * logy w = Г5д-Т7Г-

а для базиса В «= < ху,х-у, |х|,1/2> $$)

t¿Cf,«) = £XHeCW3), DgCf.e) -v log HeCW . При r 6 IH можно доказать, что для класса Зигмунда Wr_1ZCM,N,Ir), состоящего из функций f e C(In),|fi i N,y который модуль непрерью-ности второго порядка по 1 - ой переменной производной г-1 порядка 21

ю той же переменной удовлетворяет неравенству iot(D^"lf,T) i Mr,

фи В = <х-у,ху,1/2), Bj = В U (|х|> справедливо следующее: nc 1 /с)пА

LBCWr-lZ-0 S log 1 /С : \ CWr-lZ'0 5 fXl/e)n^ ,

I существует f « W .Z(M, N,In) такая,что ПС 1

ЧэМ - ЩТ7Г • h if.£y> oci/eM .

В следующей теореме доказано более общее утверждение, бозначим Хг yXf,с) величину |1|/т,где Trtij(CDrf.T) = е, г,к > О, ,к е W, uj<CDrf- к-ыа модуль непрерывности г-ой производной ункции f. Как и в § 5 главы 1 положим Х^ f(c) = |I|/u£ (Г,с) . спользуем также обозначения Xj, JieJ - |I|/u^4c), Xj. ^Cu.e) »

|I |/r.где т^Сг) = с. еорема 2.12. Пусть удовлетворяет условиям

Z~k < lim inf ь^СгЗ/^Сгт) < Ilm sup (^(тЗД^СгтЭ < 1

не убывает с ростом т и класс К = WrH£(N,I) =

= <Г е (^(1) : If| £ N & uk(Drr,T) S с^Ст)}. U Тогда найдется f е К такая,что Ы|((ВгГ,т) = Пр ^(и^Ст)), ы^рСГ.т) = ПрдСт^Сг)), LgCf.e) = 0,.>к:СЬвСЯГ,«Э> »

= ^,k<xr+k,f(e)^lo9xr*k,rCe) = cV..kC4.Jctf-'e>5/l09xr,lcir'e>' tB cf.£) = n^ctg cx,er)' = «V.kW+k.r1«» = fV>kCV,k(r.O).

le B( = В U I fx,B = Cx-y,xy,l/2). А для BR = В U R .1) найдется f e К такая,что

cjk(Drf,r) = Пр ^с^Ст)), ы^СГ.тЗ = ПрдСг^Ст)),

Vf'£) = = ^.IcCV^.f^) = «V.lc<Xr.lc<f'e».

вообще для любой функции LCe) < Огд(\г кСи.«)) .н® имеющей скач-iB в смысле теоремы 2.9,найдется f е К такая,что Eg (f,е) = nrfk(LCe)).

Теорэыа 2.12 показывает,что верхние оценки,полученные в параграфа S главы 1,по порядку,вообще говоря.неулучшаемы. П.Си) обобщает одно утверждение теоремы 2.9 С ill).Подобно теореме 2.11, теорему 2.12 СП можно обобщить на многомерный однородный случай.

Далее излагается метод,который позволяет доказать существование функций с заданной по порядку сложностью приближенной реализации прп незначительных ограничениях на последнюю.Сначала доказывается теорема 2.13 и следствие из нее,формулировки которых здесь опуска ются.Потом показывается,что ценой усложнения доказательства эту теорему и следствие можно освободить от некоторых ограничений и усилить.Обозначение fCe)|0 означает далее,что Пг) монотонно стремится к нулю. Теорзма 2.14.

С1) Для любой монотонно стремящейся к ш при с —>- 0 функции LCc) такой,что L(e/2) S OCLCe)) и Кг) 1 fXlogl/c) .найдется функци

f е C(In),такая,что для В = {ху,х-у, |х|.1/2> LRCf,£) = C^LCe)). - ? ♦ 6

Если к тому Ев LCe) й с ' ,где п,г e W, 6 > 0 - не зависящие от £ константы,то такую функцию Г можно выбрать в любом классе

VCr,N.N,In).

СШ Если дополнительно к условиям п. (i) выполнено условие Дод LCe) , , LCe) .,

то равенство по порядку ыохдо заменить асимптотическим равенством

L]gCf,е) - LCe) .

log LCe) log LCej

(ill).Если условие ^¿g 10 заменить на условие jlog \/с)а 1°<

где а < 1/2,то можно доказать существование бесконечно дифференци

руемой и 2я-периодической по всем переменным функции f е C(Sp) та кой,что для базиса В = {xy,x-y,cos х, 1/2)- справедливо равенство пункта СН),а для базиса В *■■ <ху,х-у,1/2> - равенство пункта СП

Civ) Если выполнены условия' LCe) « Q(L(elog 1/е)) и fi(log 1/е) < LCe) i 0(1од 1/е)п_(5 , 6 > 0, то существует аналитическая и 2л-периодическая по всем переменным функция f е CCR") такая,что 2<t

для нее справедливы равенства пункта СИП.

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

Теорема 2.15 и следствие 2.14 являются некоторыми количественными аналогами теорем 26 и 27 1213.

Используя одну идею из 12"Л С развитую там применительно к ката-горовской сложности) и результаты параграфов 1,3,б,можно предложить еде одно доказательство теоремы А. Г. Витушкина и некоторых ее аналогов, один из которых несколько уточняет известный результат Д. Гильберта. Обозначив класс всех г-крагно непрерывно дифференцируемых на К" функций, Лр - класс Лэврэ всех бесконечно дифференцируемых ни

функций,таких, что для любых г е ?/\х е 5!"

_ п Г, ♦« • !ЗГ.

М^Кх)! * пс^! <г,+1)

Ап-класс всех аналитических на (^функций, Ар - его подкласс,состояний из всех 2я-периодических по всем переменным функций,аналитические продолжения которых удовлетворяют условию

|Г(г)|<0(ег 1 ].

Известно,что ^ = А. Множество всех суперпозиций функций из В обозначаем 1В1. Теорема 2.16.

С!) При £ ) ® класс Г" не содержится в [Г™]

СИ) при п > ш класс Ап не содержится в [Ап]

СШ) при пСр-Пуф > шСец—1Э/ч класс А^ не содержится в (А®],а при

пСр-1)/^> > и - и в классе [Ап].

(IV) при п/3 > ту класс не содержится в [Л®] .

По существу в доказательстве п. (IV) получается,что для любого класса на любом параллелипипеде I11 справедливо равенство-по

25

¿log l/£)1+n^

порядку LgCJjj.c) = löglog I/с' J ■пРичем для некоторых f£]jj LgCf.e) = fiCLgCJ^,«)).Отсюда и из теоремы 2.1 следует равенство HC(J£) = П(С1од l/e)1+nP),«m> можно проверить и непосредственно.

В одномерном случае предыдущие утверждения можно уточнить.Обозначим JßCa) класс всех fix) е Jß,таких,что |Drf(ac) | < сjxj mr(r!)ß.

Применяя результаты П.Я.Ульяноьа С281 и рассуждая также,как и в доказательстве теоремы 2.16,можно доказать,что

1 1 1 U/ß)ß*\l\

LßtJ^).*) ~ Г (ln^/inln^ .где г = ^ .

1 1 причем найдутся f е J^CeO такие,что Lg(f,c3 ~ Lß(J^Cm),е),

а также H£(J^Cm)j ~ rC(3+l)Clog eHln 1/с1и<3.

Некоторые результат® предыдущих параграфов имеют теоретико-автоматные аналогии,описание которых посвящен параграф S

Обозначим Z4 множеств!? '{0,1 ^двоичных последовательностей, -декартову степень множества множество n-местных детермини-

рованных функций.На 2 определим метрику

рСЬ.сЭ = 2"®,где л = min {1:^*0^. На определим метрику по формуле p(i,c) =^max p(b| .cj,

где t = СЬ V' c = Cc,»""cn5. bj.Cje Z2.

Тогда ^совпадает с шфвйствам всех функций —>- 2^,' удовлетво- '

ряюцих услови» Липшица |f<x)-fCy)| i рСх,у),а ¡^ гомеоморфно п-ой степени:кАйторова множества. ■

Определим метрику на- ^'равенством pCf,g). = max pCfCx) ,gCx)).

' xeir

ю a

Пусть В с i= Ur - произвольный А-пол$ый.базис (определение

nso * 1 , , ■ • s t »«

см. в [2913. Тогда обычным образом можно определить LgCf.e) для лп-

■бых f € ? и с > О,В качества В будем использовать, стандартный

полный базис В0 = {&,Vf~,ao,aJ .состояний из детерминированныхфунк % . ' .

ций единичного веса и задержек. Функции из ^ можно отождествить с

бесконечными полными корневыми 2п-арнкми деревьями,ребра которых помечены символами 0 или 1.Выбирая для каждого ребра эти символы с

вероятностью 1/2. определяем на ./"естественную вероятностную меру. Теорема 2. 17 является аналогом теорем 3.5 и 2.1 и ее формулировку опускаем. Из теоремы 2.17 выводится следую^иф аналог теоремы 2.16.

Теорема 2.18. Для почти всех f е справедливо неравенство

l .c'f.ri t ,

f с^1Э(.гп+1-1).

а в случае реализации схемами с обратной связью - неравенство

, log- Г

L/f-'3 » "(loglog ïvfe ;)■•

Следствие 2.15. Почти все функции из Z1*'1 ие выражается через функции из ,рП с помощью суперпозиции и обратной связи. Существование таких функций было ранее доказано в [271. Справедлив следусщий автоматный аналог теорем 2.13' и 2.14. Теорема 2.19. Для любой возрастающей последовательности </(m)},/(m) s (N,такой.что при m 2 m

0 ->!ЛП

LK.m) = /Cm) - /Cm-1) > f<m) . /Cm) < bjp - 1

найдется f e У1,такая,что Lg(f.c) = fi(/(]log 1 /г[)) . lo§ /Cm)

Если к тоMv же lin i. й = oo , lim A/Cm)/m = ю

ж-мэе ■ э m-хв

то LgCf ,c) - /(-]log l-/2c[) .

Параграф 9 в некотором смысле "параллелен" параграфу 9 C21J. В нем развитый в главах I и II подход применяется к исследованию ■ ■Л';,-:'Н"о;;! г:' ччтачлцпзго вычисления непрорырш'х "линояных^.упкцпоналов.

Пусть (X, || ||) - ба-н-ахово пространство,К - класс действительных непрерывных функционалов на X, вполне ограничений относительно метрики Ц Ft - F2|1a = s^U^Cx)- F2Cx) |. Допустим, что .для каждогооо

оракул б выдает для любого х е А значения линейных непрерывных

функционалов'^*.....х* е X*,N = N£, х*= х* fi.Будем говорить,что

схема S приближает функционал F с погрешности не бол.е.е с,если она

27

имеет N = Н£ входов и реализует функцию fs(xi.....хн), такую что

.....*M>lA$e-

Обозначим Lg 0<F,c) наименьшую сложность такой схемы,построенной из функциональных элементов,принадлежащих базисному множеству В, и определим Lg 0(Х,е) как max Lg eCF,<c). Тогда подобно теореме 1.1

получаем, что для любого конечного В Lg СС I Pg Н^Ш/log Н£(К)

Оценка для Hf(K),где К - класс всех функционалов F.удовлетворяющих

условию Липшица |F Cxt) - F Сх^Э J S c|xj-xj|, и неравенству РИА(С,

имеется в § 9 [211, Она такова,что делает маловероятным получение г.данок для Lg .точных по порядку.

Аля получения более закончены» результатов в классе К выберем подкласс А*(с>, состояний из линейных функционалов. Предположим,что А - выпуклое и центрально-симметричное относительно нуляиодмно».-л'~ во X.Тогда можно считать,что А*Сс) состоит из всех линейных функционалов х* с нормой S с. Отметим,что класс А*(с) будем

рассматривать в метрике | F - F^, но не в метрике,порожденной

нормой пространства X*.На замыкании lin А пространства lin A J будет нормой,а на всем пространстве X,возможно,лишь псевдонормой, но на подмножестве А*(с) она будет порождать метрику | F. - F^.

Через Хп обозначаем далее произвольные n-мэрныз подпространства пространства X. Пусть *П(ХЭ - класс всех непрерывных линейных отображений X -ь Хп ,а Р^СХ) - подкласс,состоящий из всех таких проекторов (т.е. линейных отображений Р,удовлетворяющих тождеству Ра- Ц Обозначим Xм (А, еУ - min { п : 3 tn е *п(ШПО |х-*г(х) ЦА < е} обратный.линейный поперечник множества А, а п'1 (А,е)-его обратный проекционный поперечник œin { п : 1 pn € J^Clin А) |х-рп(х)|д i 4 (о поперечнику см. 1215.

Теорема 2.20. Пусть А - выпуклое центрально-симметричное относительно нуля вполне ограниченное подмножество X. Тогда при 0 < с < ес

Hg^œ - 4,5 X-'(A,c/ec)logÎ.-'(A,£/ec)) - 2X"(A,i/2c) S He(A*(cÎf

S He/Ec(A) + 2'S (A, e/4c) logft"1 (A,e/4cj) 4 ЮгГЧА.с/Чс).

as

В частрости.если при лгбом с ) О H (А) ~

(rT-'CA.f)!cQiT-'CA.c))/ricCA) ->- 0.(Г" С А logX." С А ,с))/Нс( А) ->- О,

то при лсбсм с О Нс(АиСс)) -v HfiCA).

Допустим,что выполнены предположения.сделанные в начале § 1 относительно системы (vj.Cx)}, и функции /(к). В § 3 было доказано,

что GCil i H С Я) : ТС с), где 2 - класс, состояний из всех 1Чх) =

= Е а^Сх),таких.что при любсм к la^l < ?(kï.

Класс S содержится в пространстве (X,| Ц),Х = С(1п),норма чебы-кевская. Пусть с - произвольный убываний положительный ряд с

единичной суммой и G^Cu) - функция,определяемая также как GCu),

если только 7(п) заменить на сп^С пЭ.

Оракул О, выдащий лля любого с > 0 значения для любой функция Г* 171

системы линейных 6-ойраэнкх функционалов 0£ = | б : 1 S i S ,

назовем нормальным оракулом с вопросами.

Теорема 2.21. Пусть система ^(xDJ удовлетворяет условиям § 1 и

класс S определен как вьгае.

С О , Тогда для любого конечного набора В функциональных

элементов, оракула О и класса К = Н*Сс)

Ч Я-' * lebt1 + н = неш.

Zern з(î)log sCc) = о(Н2£СЮ).То Lg^CX.e) } Рд j^-jj, а если sCc)log sCc) = 0(H2cCI)/logH2fiCt)),TO

Ьв* leЫ1 + ^xir^'™ H - W">-

3 обеих предыдуиих неравенствах можно Hg^Cft) заменить на меньшую величину GCSi/c).Можно также утверждать,что. существует х* € К,та-

:сй,что LB>eCx".£) > ♦ H - G.Cc/c).

iij Пусть система Ip^Cx)} - кратная тригонометрическая,четная или ечетная тригонометрическая или чебышевская. Обозначим NC с) такое шпшальное N = N ... N .где М( - степени двойки,что интервал П(е)

inj

азмера N х...х N содержит множество Р(мСгЭ) и удовлетворяет

1 П ,

условия« ^Кк) < c/\ZK.

Тогда для Б = {ху,х-у,1/2} и подходяаого нормального оракула о с НСс) вопросами при Т = Т(е/2с)

- - 31oglog Т + 0.(1).. j

4i.«<*'e3s -log Т VHl°9 + OClogloglA:

Если Nloga N £ ОСТ) при a 2: 3 и Cloglogl/e)3/logloglogl/с < ОСЮ, то последние слагаеше поглощаются первым.

Следствие 2.16. Если ?(х) удовлетворяет условиям С22Э гл. II, то

для любого конечного набора В функциональных элементов, оракула ö

и класса К = В*Сс) существует хи б (С,такой, что

Т fv* ,1 > н Г, . joqlog Н - 0(1)1 LB>0(X ,«) i Pg Xög-R[l + Iög~H-J'

для В = {ху.х-у,1/2} и подходящего оракула 0 с NCe) вопросами и , 31oglog Н ♦ 0-С1).

. * ГёЬ(и -ГодИГ3- W н = НсСЮ.

Если класс В удовлетворяет условиям § 1,и функция KV:) - условию

УСк+1)/?Ск) й iCk)^*7^ ,то искно показать,что выполнени соотношения следствия 2.16.

Если в качестве класса А с CCID взять класс всех функций,имеющих ограниченные константой К аналитические продолжения в некоторый эллипс Э с фокусами в концах отрезка 1,то для любого с > О.Хх. = А*Сс) и подходящего нормального оракула 6 с 0(1од1Д) вопросами выполнены утверждения следствия 2.16.

Во параграфа 2 гл.З сравниваются между собой классические

базисы * ~ V. и |ху, х + у, * " V- с линейными

базисами. Упоминавшиеся выше результаты СЮ 1 уточняется и дополняются в теореме 3. Г, формулировку которой с целью краткости здесь не приводны,а формулировку теоремы 3.2 приводим в сокращенном виде

Далее через log^*3обозначаем k-кратнув итерации двоичного логарифма,а через А - поле действительных алгебраических чисел. Творена 3.-2.

CID Пусть В - произвольный конечный базис,состоящий из линейных функций с алгебраическими коэффициентами.Тогда для почти всех at IR и любых с S са DgCa,«} 1 Cglog^.

30

Iii) Пусть В = i (х+у)/2,х-у,1). Тогда для любого числа а е R

яраведливо неравенство

. DBCа,с) < LBCa,c) < DgCa.c) > + 0аС1) < lagt + 0аС1), СЮ

,ля почти всех а е К - неравенство loa; -D,(a.c)

lim sup —e--—■— =1, (**)

с ~уО log 1/e

lv) Если же В = С l,x-y,x/2 > то для почти всех a € R справедливо

авенство С **) и для любого числа a е К справедливы неравенства

DgCa,е) < log! + 0a(l). CI)

, logi • rlogilog"'iv

LnCa, e) < log! + --f-т- + of-6 / 1 ♦ 0 CI) CII)

3 £ log I 1 Clog'1 i)* J a

для почти аеех a e 0?

, log; гЬдПод'"?-.

LBCa,c) - logt t _+ of-6 С 1 + CLCl) . (Ill)

0 е Clog J a

Для монотонного базиса" В = <х/2,х+у,1> теорему 3.2'можно ополнить следующим образом.

Теорема 3.3.Для любых a > 0 справедливы все утверждения Civ) еоремы 3.2,а также следующие соотношения при с -у- О

31og| - tgCa.c) -у- оо СП

lim sup С31од; - Еп(а,«})(1одЪ"'/" 2 3 СИ)

Для некоторых a > О

ЕдСа,£) = СЗ-о(1))1од^ , (ill)

Для любой фСс) ->- я найдется a > 0 такое,что

lira Inf С 31 og; - tBCa,e))/ pi с) = 0. Civ)

я-ь о

Для почти всех a > О

i2 logl/e - С21одС1/е)1од,3>1А)'/а +L Са.е)

■ Г-«13 2~1/*3( logl/e)' /l( log'^'l/eXlog" 'l/e)"1 /а " В частности EgCa.e) = (2ю(D)logl/e.

Теорема 3. Э дает пример базиса,для которого наблвдатсяполуэффект екнона (в смысле 1321),но не наблюдается эффект Шеннона. ^

Линейная форма (а,х) ~ а,х, + йпхп называется лло;«

приближаемой, если для лобого вектора х с S^VQ)

0(0, х) в > са С max (х^Г" ,

где са > 0 - константа,не зависящая от х.а 1 у || обозначает здесь min ( |у — n J : п б 2 > . Теорем» 3,4 . (l) Пусть (а . . ♦ /¿^

- плохо приближаемая форма, В, = ( О, X ± ао, . . - , X t am ), В, - < X + у, с^. . . , . ап, >

Тогда для любого числа a s Ж

tgCa.e) = tgCa.t) = Dgг'""1 ,

(log е| ' (log с| 0(1од1/с)

Если с^,..,^ рационально независимы,то найдется a е (Г тако*1,

. (log el 1йСа,е)=ЕвСа,е)=Ов(а,с)ХЦСа,£)Х£""".1>вСа,г:^ --- ♦ 0(1),

lit г г

и для почти всех a е CR

11 од с I lojl/c

LnC«,£)--=— x ——— .

m log * 1/e

С11) Для почти всех с е {R,b том «меле и для с равного основанию натуральных логарифмов ,для В = < xiy.cx.l ) и любого a е (R

Lß(a,£) = a( logl/e) .

(Ill) Для любой монотонно стремящейся к ш при с -у- 0 функции*^ найдется число в «в такое,что для В = ( х - у,0,1 } •лрм'л-д.гл.« неравенства

LRn/2,c) DrC1/2,£)

■ S ' 1 '

йзвестно I"301 ,что все конечные базисы в двузначной логике параллелизуеш, а в трехзначной , вообце говоря, нет С базис В называется паралл'елизуемым.если всегда глубина равна по порядку логарифму сложности формульной реализации). Согласно теоремам 3.1С1), 3.4(1),3.2(111) базисы В,= <х±у,ху,+1/п),и е. №,n > 1, и

В4 = <xiy,ao,... .c^i для некоторых «о.....с^ параллелизуемы и для

32

почти всех а е IR

Dg Са,г) - log Ln(a,i) log tgCa.e) logi2)l/e

I I I

h для любого отрезка I с К функции Шеннона

DBCI,i) ^ L0CI,c) -v log tgCI.i) - *logi/e ,

a 2 A

а базисы ((x+y)/2,x-y, 1) я <l,x~y,x/2) непараллеллэуош и для эгих базисов и почти всех a « R

Dg(a.e) LgCa,«) X tgCcx, t) .

Теорема 3.4(1) показьшает,что в теореме 3.2(1) заменить в оценке константу eg на независящую от базиса константу.вообще говоря, нельзя. Теорема 3.4С1Ш показывает, что для произвольных конечных линейных базисов теорема 3. 2(1),вообще говоря,неверна, а теорема 3.4(iv) - что для тех ке базисов получить зависящую лишь от числа функций в базисе верхнюю оценку для Lg(I,<s), tg(l.e), Dg(l,c) ,

вообще говоря,нельзя.

Учитывая изоморфизм между (I, О и (5?f, •),для теорем 3.2-3.4 можно сформулировать соответствующие аналоги,например,таким аналогом для равенства (III) теоремы 3.2C1V) будет утверждение,что для В = (xy.x/ty./x > и почти всех a е К

Ln(xa,£) = logi- + -—— f 0| -—- + 0„ T(l) .

,B £ log * 1/e 1 (log " l/e)' } ai1

где функция xa рассматривается на отрезке I с СО,+ш) .Последнее утверждение ,а также другие утверждения о базисе ( ху.я/у.^З? > получаемые указанным образок,можно интерпретировать как оценку сложности вычисления степенной функции на калькуляторе с неисправными кнопкам) t и - .имеющем операцию не имеющем операции х^ [ 11,с. 509,задача '25).

В третьем параграфе рассматривается вопрос о существовании констант с заданными по порядку функциями Шеннона L^(a,cj Eg(а,с'), DgCa.e) - сложностью и глубиной схемной и формульной реализации в базисе В константы л с точностью е. Теорема 3. "5.

(i) Пусть В = {х-у,ху,х*,1/2> и L(e) - произвольная функция,удовлетворяющая следующим условиям: L(г) монотонно стремится к on так,что

33

СЮ LCc'JSLCe), logu>l/«*LCc) < (log 1 /с)с,с < 1 - некоторая константа. Тогда найдется а е К такое,что

LgCa.e) £ LCc) . tgCa,£)X LC«)logLCcl Если к тому же

С**) LCe)/(log^'lA) в ,(logLCc))/(logu'lA) | О, то LgCa.c) - LCc),a при logUcl X log;,"l/£ справедливо равенство по порядку DgCa.e) X log^'l¡с if logLCs) . (Ш Если LCc) удовлетворяет условиям С*) из п. CD,то множество

всех a с R таких,что LgCa.,c) S 0(LCt)) .является алгебраически замкнутым полем,причем для различных по порядку функций Hi) эти поля различны.Множество всех таких полей относительно отношения включения содержит континуальные цепи и антицепи. Отметим,что утверждения п. С D. касавшееся только ЬдСа.гО и DgCc.e),

справедливы и для базисов {ху, х-у. l/m},{xy,x+y, -1/hi} ,л1 > l,m е IN, {ху,х+у,хД},{xy,xiy,x/y, 1} .В случае реализации формулами к

любому из этих .базисов нужно добавить х2;без этого условия утверждение п.С О о мере сложности tgCa.e) будет не верным.

Теоремы 3.2 и 3.4 дают некоторые примеры базисов с "быстро растущими" функциями Шеннона. Однако для меры сложности Lg(a.e).где'В =

* ( х-у,ху,1/2 ) .эффективно указать сложно реализуемые константы не удается.Теорема 3.6,доказанная в § 4,указывает на связь этой задачи с задачей о получении эффективных нижних оценок сложности булевых функций.

ДЛЯ ЛЮбОА булеВОЙ ФУНКЦИИ fC*j.....Х^) ОбОЭНаЧИМ ЦИмШШИиЛ! •:!•/:>

сложность Ра-реализации функций f схемами в базисе <х-у,ху,1/2,[х]} где Ш - целая часть и Ссхема Р - реализует функцию Г,если

функция, реализуемая схемой,совпадает с f на всех булевых наборах длины п>.Можно проверить,что. LCD по порядку не больше сложности схемной реализации f в любом конечном булевом базисе. .Теорема 3.6. Для любого конечного базиса В можно построить CD конструктивную последовательность конструктивных действительных чисел СКДЧ) {a^,^ е СО, 11,и конструктивно стремящуюся к нули У

последовательность ,сп е 0^,такие,что при любых га > п LoglAm 1од-'1/ви - ОСП

( и). конструктивную последовательность КДЧ ,а_е (О.П.такую, Рп loql/e n п

что Lr,Ca_,c) ; тЛ - •

В n log 1/е

Ciii) Для любой конструктивной последовательности булевых функций

{ ГПСKj... ,хпН можно построить КЛЧ а е 10.11, такое,что если

LC f_)/h —ню , то La(a.,c)/log"'l/c —>- а> ,

г, log 1/е

а если L(f ) X 2 /П , то Lп(а,е)А --- ,

' В log 1/£

где В = < х-у,ху,1/2 > .

Из теорем 3 2 и 3.1Сv) следует,что если последовательность булевых функция f Cxj,...,хп) имеет нелинейную нижнюю оценку в базисе

{ х-у, 1/х, Ых1 f ,то число а .кодирующее эту последовательность так.как указано в доказательстве теоремы 3.б .является трансцендентными если Шп3 2п/п,то нелиувилпевским трансцендентным, потому.что для любого лиувшшевского числа а

hm inf LoCa.c) Clog^'l/iJ/logl/e = 0.

£ -Уо

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

в полном базисе.

Задача о сложности приближенной реализации непрерывных функций схемами и формулами в непрерывных базисах была поставлена перед автором 0.Б. Лупановым. Выражаю ему глубокую благодарность за внимание и поддержку..

Список ссылок и сносок

Ш Тиман А.Ф. Теория приближений функций действительного переменного. -М.: Физматгиз.I960. 12] Тихомиров В.М. Некоторые вопросы теории приближений.-Изд. МГУ. 1976.

[3) Strassen У. Algebraische Berechnungskomplexltat. - Annlv.

Obervrolfach,1984,p.509-550. [41 Лупанов О Б. Асимптотические оценки сложности управляющих

систем. - Изд. МГУ. 1984. [5! Бабенко К.И. Основы численного анализа, - М.-.Наука, 1986. [61 Трауб Дж.,Вожьняковский X. Общая теория оптимальных алго-

3S

puTuoa. - H. Пир, 1883.

£73 Трауб Д*.,Вожьняковский X..Басильковсккй Г. Информация, неопределенность,сложность. - М.Мир,1988.

181 С'ыейл С. Алгоритмы решения уравнений. - ICH 86. pp. 172-195.

19] Шенхаге А. Решение уравнении с точки зрения вычислительной сложности. - ICH 86. pp. 131-153.

[10] Strassen V.Berechnungen In partiellen Algebren endlichen Typs. - Computing, 11(1973).- p. 181-196.

[III Borwein J.К ,Borvain R.P. On the complexity of familiar functions and numbers. -SIAM Review, 1 §88,v. 30X4, p. 589-601.

112] Стечкин С. Б.Субботин D.H.- Сплайны в вычислительной математике. -М.: Наука,1976.

113] Асаpun Е. А. О сложности равномерных приближений непрерывных функцнз. - УШ.т. ЗЭ(З), 1984. -. с. 157-16Ö.

CHI Офман Ю.П.Od алгоритмической сложности дискретных функций.-ДАН СССР,т. 145,N5!,1362. - с.48-51.

115J Тогер A.B. О сложности некоторых функциональных классов.-ДАН СССР.т.189,N5-*, 1971;- с.7§9-7§1.

[16] Hakovoz J. On the Kolmogorov cooplexity of functions.-J. of coEplexity,1986,H 2,p. 121-130.

С17] Колмогоров A.H. Различные подходы к оценке трудности приближенного задания и вычисления функций .- Proc. Intern. Congr. Math. Stockholm. - 1863. - p. 369-376.

С18] Витушкин А. Г. Оценка сложности задачи табулирования. - И.: Физматгиз. 1Ё68.

(195 Бернштейн С. Н. Собр. соч. ,т.2. - К.: Изд. АН СССР, 1954.

120] Pippenger К. On the evaluation of powers and monomials. -SIAM jrComput. Г9.1980, - p. 230-250.

[21] Колмогоров A. H., Тихомиров В. U. с-энтропия и ¿-емкость множеств в функциональных пространствах УКН.т. 14. 2(86).-1959,- с 3-86.

С 22] Ггшков С.Б. О глубине булевых функций .- Проблемы кибернетики. вып. 34.- М.: Наука, 1978. - с. 265-263.

[231 Захарова Е.Ю. Реаяизация-фушсциа из Рк формулами Катеца-тичэские залеткн. т. 11. ii^ 1,- 1972.- с. 99-108.

С24) Haruyama К.On tho parallel evaluation of polynomials.- IEEE Trans. Ccsput.C-22. if 1.- 1973.

C2S] Munro I.,Patterson И. Optimal algorithms for parallel polynomial evaluation.- IEHRC 3437.August 11.1971,Computer sciences.

[26] Кашин Б. С.,Сааклк A.A. Ортогональные ряды.-М. Наука, 1984;

127] Марченко в С. С. - Об одк.ои катоде анализа суперпозиций непрерывных функций, -. Проблема кибернетики, вьа. 37. - П.; Наука, 1981. - с. 5-18.

[28] Ульянов П. Л. О классах бесконечна дифференцируемых функций.-ДАН СССР. - 1089.- т.ЗОЗ.^г.-с. 287-290

129) Кудрявцев В.Б. .Алешин С.В..Подколзни A.C. Введение в теорию автоматов, - М. •• Наука, 1986.

С 30] Угольников А. 5. О глубине и полиномиальной эквивалентности формул для замкнутых классов функций двузначной логики. -Математические заметки. г.42.№- 4. - 1887,- с. 603-612.

131] Кнут Д. Искусство программирования на ВВМ.т.2. -Н.:Мир, 1977.

[321 Кигматушин р.Г. Сложность булевых функций.-И. •. 1991.

зе

и)

НеСЮ - л-энтропия компакта К, рд - шшямуы приведенных весов, а Tg - минимум приведенных задержек элементов базиса В (определение сц.в ГШ. f X 9 - f больше g асимптотически. т V (r.H.N.I") - компакт

<f:f<= Cf(I^SIflSNSKViCf^I^-liaÇvrCio/D^f.OiM,/1 ~Г<))))}, W (r,r'H,N,I") - компакт

{Г: Г € С(1п) & If| S N â ÇVi<Vt<«lr,Cf,T) S M

где C*~C 2 п>, ~ просгранстю непрерывно дяфферепцнруомых на In

функций, Щ - оператор k-хратного дифференцирования,а * *

ы, k(f\T) - к-ыЯ модуль кэпрершвпоста по 1-оЯ лерекеяяой, tx) - целая часть х, 1st = -С-х).

|ХГ\ ' *

f Д g или f < 0(g) - g больше f по порядку, fr g -f и д но порядку равны.

) «¡'^(f.c) - функция,обратная к соответствутаеиу мбдулв непрерывности, L f(e) « |In|/n«;'v СГ,е), |In| - odbeM In. т.! i.Kj

"f •» з - f и g асимптотически равны. 1 X* - пространство,сопряженное к X.

Список публикация пр тона диссертации

Гашков C.B. О сложности приближение функций схемами.построенными иэ элементов данного конечного множества. - Seainarberlcht №56. - Sektion 'Mathematik dèr Humboldt Univrsitat. - BsrHn 1983. - s. 34-29.

Гашков С. Б. О сложности приближенной реализации аналитически:: функций схемами и формулами.-Вестник МГУ. Математика,механика.-1983. - Г4. - с. 36-43: .

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

Гашков С. Б. О сложности приближенной реализации некоторых классов дифференцируемых функций одной переменной формулами в непрерывных базисах .- Вестинк МГУ. Математика, иеханика. - 1984. -Г6.-с. 53-57. • .

Гашков С.Б. О сложности приближенной реализация некоторых классов дифференцируемых функций многих переменных при помоги схем и формул в некоторых базисах,состояв** из непрерывных функций. - Вестник МГУ. Математика,механика. -1988. N 3. с. 48-S7. Гашков-С. Б.* О сложности приближенной реализаций непрерывных функций-и о континуальных аналога* аффекта шеннова Вестник

МГУ. ^тааткке.ошш-л. - 1BS3.- ГS. - с. 25-33.

Т. Гшсоэ С. Е. О сложности приблавзниэ^ рэалазаши ивароротаих йункцвй сгеиггаз с формулам в цдпрершшшс базисах .- СМ.тсзс-оов конф. FCT - Е7,КазанъД9ЭТ. - Lecture Notes in Computer Sciences. - Sringer-Verlag. - V. 27C. - p.140-144.

0. Гавков C.S. 0 слодазств праблкЕэкаой раалззацшз йуюау^.унов-лвтворявзда условию Лшишц&.свдшдо в непрерывных. базнсах . -Пат. Зашткц. - 1088. - т. 43. НЧ - с, S43-SS7"

S. Гавков С. 5. 0 слоеноств. прибянЕзшого вычйслоиея непрерывна ФушсцяС .- Mathematical-probleas In conputation theory.-Eanach center publleallens,volю 21. -larsaw 1S33.-p. 487-407.

Ю.Гавхсв С. Б. О оодевосги вьтасягиаа иекоторщ классов каого-членов кеокольккх перэвдггш:. -Вести: ШТ Мдтоханзсг., .

- 1988.- Г1.- с.89-61.

И.Гавков C.S. О параляэшгов вачвелекзв нскоториг классов ьеного-чяаков о раотгаш адсяом первизвик. - Вэстша: ЮТЛкте^йТСка, кеадгека. - 1620. - !fJ2. - с. 83-92.

12. Гаиков С. Б. 0 слогЕости приблавзаного вычнеленва действнтешгш: часов скаиамз г форыуланз в ргзлЕчает рациояалы'щ: базгеаг . -декретная кататака. - 1090.- v.2,lr4. - с. 20-43.

13.Гашков С. Б, Сяогшорзаяазуеш® булоаы фушц№ а труди овкчие&азэ деветагеешшо часла дееяротквя штсматека,- т. 3.1Г1.- 1931. с.