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

Введение к работе

Актуальность touu. feorao задачи теории приближенна иогут сдаъ сфорнулироваші следус-ады образец. Пусть (X,|| jj)- da-пахово пространство^ Я и Л -его подіпю2есгга,тзхі!о,что для любих ж е Я я с > 0 найдется у е й. удовлетворявший'неравеастзу g »-у flS і с .Пусть такгэ Z-.& -і- К₊ -некоторый, функционал .сопостзлляягий кахдоку і/ еї число (), называемое далее слошостьв элемента у. Тогда спозиостьо е-пркбяигекия эшэгаята х <= ЭС'иазозэи число

*(*.«) = inf і ГЛу~> : у s Л , В я-у 0 '< є > , а слопгастья й-пркСлзжэгогя класса К - число

ЖЯ.лЭ = sup < Ях.г) : х є 5С > . Напримэр.в качзстоо X uosao взять пространство C(Iⁿ) всея яепрэ-рывных функций f: 1^п -»- К , определенкшс на п-ггараси замкнутой интервала Спараллэянпияада) Iⁿal₍x.,. к 1_п с Е?\ I_t = ja_t»e_t] , 1 < і < п ,с чебіававсксй норкой | f g я каж j |ГСяЭ| : я; є Iⁿ ],

а в качестве і - класс всех аоланоииальяия Сравдюйалъных) функция; поя слокностьо функции обычно пашшаатея степень полниоиа Срациональкоа дроби),рааяаз'ущей эту функции (си.tі,2D.Если км хотим,чтобы кара слохноотн функция болеа точно отражала время,затраченное на ее вичнзленяе.то в качества такой иэры лучше вэять ш нямальноэ число производишь при атоа арафзатичаежих операций-Поэтому представляет интерес изучение следуодего класса нер сложности'. Пусть B=-(W|_C:k*l,2,... } - вакоторое наогэство кепрерыв-

ных функция и_к : 18 ^к -н R , называемое даяее базисом. Схеиоя з Зазисе В назовем прдазвгальяув последовательность непрерывных

Йгекцай f_tL^c»³.. x = Ся,,... ,я_п3 ,'в которой fjCx) = xj npif

I S l n, а каждая елфдувзіая функция f_t вычисляется через какнэ-

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

рункции w .- $*—-> К с&гяаена следующему равенству f;(js) '

viff, Сх),... ,,f\ (x)1.Gses?ocTbD схейы назовем Число L,a глубиной

иаксимальнув длину яД5осяедовательностя T_t ,,,., f» ,каадая

- *!.' *D

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

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

В,реализующей f, обозначим Lg(f); число ЦСП назовем сложностью

схемной реализации функции f в базисе В.Аналогично определяем g(f) -сложность формульной реализации,» Dg(f) - глубину функции

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

В качестве Л возьмем множество всех функций fix) є C(Iⁿ), реализуемых схемами в базисе В,а в качестве - любой из функционалов .Будем изучать асимптотическое поведение при с -* О

функций LgCX,},gCX,сі,DgCX,г),которые,следуя установившейся в

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

Величина LgCf,),rae В = { х і у ,жу ,х/У Л }, является достаточно естественной мерой слоаности приближенного вычисления функции f с точностью в,хотя в.этом утверждении есть большая доля идеализации Спредполагается, что все очерации выполняются точно и с одинаковой скоростью}. Для различных базисов Скак правило,содержащихся в В),и для различных индивидуальных функций и вектор-функций'Скак правило,алгебраических полиномов).вопрос о вычислении Lg(f3 и других мер сложности интенсивно исследуется в так называемой алгебраической теории сложности 13). Для булевых функций и базисов аналогичные исследования еще раньше начались в теории сложности булевых функций (41. Вопросы о сложности приближенной реализации непрерывных функций с разных точек зрения давно рассматриваются в теория приближений и в вычислительной математике 1-2,5-91.

Мы будем исследовать асимптотическое поведение при с -v 0 функций. Шеннона LgC*,e),t_BC9(,e),DjjCSi,) -для классов ^.которые обычно

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

щионаяьных и кусочно-линейных функций. По-видимому, впервые >добные вопросы рассматривались в ПО],а именно в случав X = ,,Ь\ с R и В = і х t у ,ху .ж/v Л \ таи найдены асимптотики для ,СЭ(,) и DgC3t,«3 . Но зная в тот момент о [10І,автор в (2,8)

вторил эти результаты в несколько усиленной и обойденной форме, также перенес их на случай некоторых классов аналитических функ-й,и исследовал подобные вопросы для некоторых друтмх базисов. Не судей ограничиваться базисами,содержащимися в {*+у,у,*/у.1}, равдывая это тец обстоятельством,что компьютерные программы час-содергат,кроме арифметических операций.еще'и различные элементные функции.В till фактически рассматривают,например,оазисы,сс-эжаше радикалы и другие алгебраические функции,и называй* соот-гствувщую им «еру слокносги алгебраической сложностью,а меру, угветствусщув базису {z±y,xy,x/y,i\ - рациональной сложностью. Креме конечных базисов,будем рассматривать базисы,состоящие из іечного числа функция и континуума констант,и називать оти бази-почти-конечныга. Схемы в этих базисах можно интерпретировать как ;ели аналоговых вычислительных устройству ыэру сложности LgCf.c)-: иининальнус стоимость такого устройства для вычисления функции точностью с. Так как параметры,управляющие изменением функций, . лизуемых элементами аналоговых устройств,а также входы и выходы х элементов имев? ограниченную область изменения,то целесообразно. ни почти-конечных оазисов глделить класс,состоящий из (базисов, ввдх .лишь ограниченные константы (т. е. принадлежащие данному от-<у),а в этой класса - подкласс,состоящий из базисов,содеряаэдх ько функции,удовлетворяющие условия Липшица (так как функция, тазуемые элементами аналоговых устройств,являются достаточна дани); такие базиса далее Иудеи называть 'лиышцевыми. іряду со схемкой,будем рассматривать также формульную реализацию, [улы образуют простой и вагныи подкласс схем,причем любую схему :о,не изменяя глубины,пресбразовть в формулу,Глубина является :ой мерой сложности,так как сна оценивает эре«я вычисления ции с учетом возмоїсности параллельного использования многих ессоров.Изучение формуя оправдывается такке тем.что некоторые вычислительных устройств моделируются именно формулами. ель раСоти- исследование асимптотического поведения ций Шечнона LgC^.^.tgCX.ri.DgCK.e) длч классов X, обычно

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

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

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

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

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

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

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

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

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

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

Теорема 2.12 из второй глави,доказательство которой основано на вменении теоретико-вероятностных (теорема 2.1,в которой исполь-^гется колмогоровская мера на бесконечномерных функциональных ком-ктах) и теоретике-функциональных соображений (использование бази-, Фабера-Шаудера при построении упомянутых коштактов),доказывает шествование функций,нижняя оценка сложности которых совпадает с лученной в упомянутом результате первой главы верхней оценкой. Вытекающая из упомянутой верхней оценки и энтропийных нижних енок функций Шеннона теорема 1.5 является надстройкой над работа-А.Н. Колмогорова и других авторов об е-энтропии в том же смысле, к и внешне очень похожие на нее результаты из работ [13-16]. осматриваемая в них постановка задачи о сложности приближенной їлизации непрерывных функций была указана А.Н.Колмогоровым в іале шестидесятых годов 117]). Колмогоровская постановка задачи шчается от рассматриваемой в диссертации тем,что в ней пробна получения верхней оценки сводится к получение-верхней оценки шции Шеннона некоторого класса булевых операторов,которая потом іается в рамках теории сложности булевых функций Св f15-16] -юмоаыэ метода локального кодирования О.Б. Лупанова [4]). іашей постановке сведение к теории сложности булевых функций не ется.хотя в доказательствахтоже используится идеи,параллельные ям 0. Б. Лупанова из теории сложности булевых функций. Другое отли-состоит в возможности использования различных не эквивалентных г другу базисов,в том числе и континуальных; все конечные пол-булевы базисы эквивалентны друг другу,что позволяет их все дить к базису < &.V,- } Сем. напр. [4]). Проблема получения них оценок в случае почти конечных и других континуальных исов значительно отличается от решаемой мощностным методом , Шеннона-0. Б. Лупанова 14] соответствующей проблемы из I13-16J, как этод метод приходится комбинировать с методом А.Г.Витушкина I,основанным на применении теоремы И.Г.Петровского-0. А.Олейник, которыми геометрическими соображениями. Кроме того,в работе ієдєньі примеры и незнтропийньга нижних оценок функций Шеннона. Ь нижней оценки для Lg(3f,) не следует никаких оценок для ',) - мер сложности индивидуальных функций из К. А.Н.Колмогоров іамкак своего определения сложности є-прибликения) t173 предпо-л.что в классах,обычно рассматриваемых в теории приближений,

существуют функции,меры сложности которых по порядку равны мерам сложности содержащих их классов. Возникает также вопрос о существовании f є К,у которых меры сложности по порядку равны заданным функциям от е. Подобные вопросы о существовании функций с заданно!! точностью приближения пространствами полиномов ограниченной степей и вообще любыми флагами конечномерных подпространств рассматривали С. Н. Беркштейном 1193 її А.Ф.Тиманом tl),a о существовании компактов с заданными последовательностяии попзречников - В.И.Тихомировым 12

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

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

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

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

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

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

іультати могут быть использованы в некоторых областях вычислительной іатематики.теории приближений,математической кибернетики.Так, в ка-іесгвє приложения полученных результатов в работе выводятся некото-іьіе (частично известные) утверждения о невозможности представлении іункций многих переменных суперпозициями функция меньшего числа пе-еременных.Некоторый результаты работы имеют теоретико-автоматные налоги»,приведенные в 8 гл. II.В работе найдены оценки -энтропии екоторых естественных классов,вероятно не рассматривавшихся ранее. то время как колмогоровскув сложность можно интерпретировать как цепку числа битовых операций,необходимых для вычисления функции и применять ее для оценки сложности вычислений с очень большим нолем значаїііих цифр ), величину Lg(f,e),nie В = (х+у, ss^.x/y) UK, эжно интерпретировать как сложность приближенного вычисления f эй не слишком малых с,позволяющих использовать для выполнения зифмегических операция машинную арифметику Сияй калькулятор), ія некоторых почти-конечных базисов эту величину можно иитерпре-іровать как минимальнув стоимость аналогового устройства для вы-юления функции f с точностью с. Поэтому результаты работы могут ійти применения при оценке времени вычисления сложных функций как . обычных,так и на многопроцессорных ЭВМ С осуществляющих распарал-ливанне вычислений),а также при проектировании программных моду-а и специализированных аналоговых устройств для вычисления' нкций.Возможны приложения в моделировании нейронных сетей. Апробация. Результаты работы докладывались на последних . гырех Всесоюзных конференциях по теоретической кибернетике,на местре по дискретной математике в центре им. С.Банаха (Варшава, энь 1985),на конференции FCT - 87 в Казани,на Ломоносовских эниях е МГУ последних лет.на семинарах О.Б..Лупанова,С. В. Яблон-эго, В. М. Тихомирова в МГУ,на школах-семинарах и коллоквиумах юдых ученых в Москве,Берлине,Нижнем Новгороде. Публикации. По теме диссертации автором опубликовано работ,список которых приведен в конце автореферата (тезисы док-108 Всесоюзных конференций в него не включены).Еще 4 работы ав->а включены в список литературы диссертации,насчитывающий всего і наименований.

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

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