markov_teorija_algorifmov (Марков - Теория алгоритмов), страница 77

Мы будем называть их соответственно суммой, разностью и произведением чисел Йзбя)з и Яабя)з Нетрудно показать, что могут быть построены нормальные алгорифмы, перерабатывающие любую пару конструктивных действительных чисел х и у в их сумму х+у, разность х — у и произведение х у. Пусть Й'69' — конструктивное действительное число.

Конструктивная последовательность рациональных чисел 31, такая, что для любого М Й, (М) — 1 ч[ (М) [, как легко видеть, является фундаментальной: ее регулятором сходимости является алгорифм 14). Конструктивное действительное число Я,'6«з» мы будем называть абсолютной величиной числа Я'6х)'.

Для нахождения абсолютной величины [х[ конструктивного действительного числа х также может быть построен соответствующий нормальный алгорифм. После этого мы можем определить максимум и минимум двух конструктивных действительных чисел х и у; шах(х, у) ='/«(х+у+[х — у [), поп(х, у) ='!» (х+у — [х — у [). Для нахождения шах(х, у) н ш1п(х, у) без труда могут быть построены соотвсгствующие нормальные алгорифмы. Читатель, вероятно, уже заметил, что [х[, а ' затем и шах(х, у) и ш[п(х, д) мы из-за теоремы 3,1 определяем, не прибегая к обычному для классического анализа приему «разбора случаев». Аналогично сумме, разности и произведению конструктивных действительных чисел может быть также определено и частное от деления двух таких чисел.

Здесь возникает небольшая трудность, связанная с тем, что делитель может равняться нулю. Однако она легко преодолевается (см. об этом у Н. А. Шанина ([2); $6) нли у Б. А. Кушнера ([1[; гл. 2, 2 4)). 414 АлгориФмы и мАтемАтический АнАлиз 1гл. 1х 5. Рассмотрим еще один вспомогательный вопрос — воп- рос о кусочном задании конструктнвных действительных функций.

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

Тогда констРУктивнаЯ действительнаЯ фУнкциЯ 1, по- строенная е) так, чтобы для произватьного х выполнялось условное равенство 1(х)ж[з(ш[п(х, а))+[з(шах)х, а)) — 1,(а), удовлетворяет условию **) ( 1»(х), если х(а, 1(х) ы [ уз(х), если х)а.

й 66. Теорема Коши о нуле знакопеременной непрерывной функции В настоящем параграфе мы рассмотрим вопрос о возможном влиянии накопленного в теории алгорифмов опыта на постановку задач численного анализа. 1. В классическом математическом анализе важную роль играет теорема Коши о нуле зиакопеременной непрерывной действительной функции. Она утверждает, что существует функционал Г, определенный на множестве всех непрерывных на промежутке [О, 1[ функций [, удовлетворяющих условию [(0) [(1)<О, такой, что для любой функции )' из этого множества г'(1) Е(0, 1) и 1(Р(1))=0.

Возникает естественный вопрос об эффективности этого функционала, т. е. вопрос о том, насколько эффективно мы можем решать уравнения [(х) =-0 для произвольных функций из указанного множества. Известно, что хороших численных методов для решения этой задачи нет. Проводимое ниже рассмотрение в известном смысле вскрывает причину этого обстоятельства. е) Летали нестроевая мы оставляем читателю. '") По анзлогнн со знаком, идущий далее знаком мы понимаем таким образом, <то обе части связываемого нн равенства осмыслены прн одних н тех же х н в случае осмысленности нх значения суть равные конструктнвные действительные числа.

4 661 ТЕОРЕМА КОШИ 415 2. Прежде всего нам необходимо ввести понятие непрерывной конструктивной действительной функции. Мы сделаем это типичным для конструктивного анализа способом. Пусть конструктивная действительная функция [ определена в точке х. Конструктивную последовательность натуральных чисел е« мы будем называть регулятором непрерывности функции [ в точке х, если для любого конструктивного действительного числа у такого, что 1(у) определено, и для любого натурального У имеет место импликация «если [х — у[ < 2-н 1п), то [1(х) — 1(у) [ < 2-"». Мы будем говорить, что 1 непрерывна в точке х, если может быть построен ее регулятор непрерывности в точке х. Функция 1' будет называться непрерывной на отрезке [а, Ь[, где а и Ь вЂ” конструктивные действительные числа такие, что а<Ь, если может быть указан нормальный алгорифм, перерабатывающий всякое конструктивное действительное число х такое, что а<х Ь, в регулятор непрерывности [ в точке х.

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

Заметим, что на самом деле всякая конструктивная действительная функция в любой точке, где она определена, непрерывна (Г. С. Ц е й т и н [4)). Однако это утверждение доказывается очень сложно, и мы им пользоваться не будем, предпочитая включить в условия ряда приводимых ниже теорем заведомо выполняющиеся требования. Несколько более слабое свойство конструктивных действительных функций — их неразрывноопь — было обнаружено ранее А. А. Марковым (см. [10), [11[). Развивая подход А.

А. Маркова, Г. С. Цейтин своим только что упомянутым результатом довел его до логического завершения. Не имея за недостатком места возможности привести результат А. А. Маркова в полном виде, мы, тем не менее, проиллюстрируем его на одном простом примере. Мы покажем, что 2.1. Невозможна конструктивная действительная функция [, удовлетворяющая следующим условиям: 1) [' (0) = 1, 2) [(х)=0 для любого конструктивного действительного числа х, отличного от О. «лгот««мы и чхггч«т!««« гг«по лп«лпз 4!6 «гл.

~х можиа В самом деле, в предположе нии, что такая н ч а, взяв произвольное конс р нструкгивное функция воз- исло х н вычислив наченн " ) н ости (например, с точ««ость 1/4), нне «/««х) с достаточной и 0 или ! Равно г(х). а юдо,мы з ' из членов дизъюнкции тогда мы сумеем в ч ыяснить, какой «х=О или х~О> имеет место.

Нормалпзогзв з1от б,, гпосо,мы пол речпе с утверждепи.м 4 64 1 1 3. Пусть теперь с / — — ------- ное к 'онструктнвиое с — пропзвольчисл Р о. ассмотрим конст у ную фу««к«п«ю , оп й" ел с ! ленную так, чтоб ! фик' ы график зке 10, !] и. на Рис, 1 (мы ы~мств функция эта при любом с м бп предыдущего параграфа. Легко бе- ка(0!]( ядет о конструктивных ей Разумеется ечь -/ ных числах х, х действительвию 0:хв..!).

, удовлетво я ряющих услоРнс. !. Предположим, пако ется нормальный алг онец, ч о алгорнфм, приме- конструктивной действительной нк й непрерывной на е бать вающий эт ное число х, лежащее м между и 1 и такое, что Ру «тинное действнтельВозьмем и з . . Роизвольное конструктивное ейст с, построим функп« по,'„и применим эт вное действительное число ~ыиси Эю дас н х/,, такое, что ам конструктивное ей действительное число /«(х/,) =О, ь гс! о«««««««п«~ л«~«««««««пвпт > и Вычислив число хп с достаточной точностью, мы найдем верный ч и'и дизтюнкции ««.В > 1/3 или х/ < 213».

Если верен первый ее член, то с<0. Если же верен вто« рой член этой дизъюнкцин, то с> О. Таким образом, мы разработалн алгорифм, позволяющий при любом конструк- тивном действительном с находить верный член дизъюнкции «,с «" О илв с': О», Нормализовав этот алгор««фм, мы поль«пи противоречя«г .«еоремой й 66.1.1. Таким образом, имеет место следующее утверждение (Г.С. Це Йтин ]3]); 3.1.

Невозможен нор>«алиный алгорифл«, применимый к за- писи всякой непрерывной и л«еняющей знак на отрезке !О, 1] конопрук/п««вной действа//«ельной Функции 1 и перерабатываю- щий зту запись в лежащее между 0 и 1 конструктивное дей- ствительное число, являющееся корнем уравнения /(х)=-0, Между тем нетрудно показать (Г. С, Г( е й т и н ]3]), что 3.2. Никакая непрерывная и меняющая знак на отрезке 10, 11 комс/пруктивная действи/пельная Функция не может бь«п«ь отлична от нуля в любой конструктивнойдействитель- ной точке отрезка 10, 11 Доказа гельство этого утверждения будет приведено вз 681, $67. Принцип конструк.гивиого д чюгвае««ся с необходнмост ю при менить рассуждение, пользоваться которым мы до сих пор воздерживались и относительно допустимости которого различные математики, по-виднмому, расходятся друг с другом во мненяяк.