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

ВВЕДЕНИЕ.

ГЛАВА I. ОПТИМАЛЬНЫЙ ПАССИВНЫЙ ПОИСК КОРНЯ МОНОТОННОЙ ФУНКЦИИ

§ X. Оптимальный по критерию "длина отрезка локализации корня" алгоритм поиска корня монотонной функции . •

§ 2* Оптимальный по критерию "невязка" алгоритм поиска корня монотонной функции.

ГЛАВА П. ПОСЛЕДОВАТЕЛЬШ-ОПШШЬНЫЙ ПОИСК КОРНЯ ФУНКЦИИ, УДОВЛЕТВОРЯЮЩЕЙ УСЛОВИЮ ЛИПШИЦА

§ 3. Последовательно-оптимальный по критерию "невязка" алгоритм поиска корня.

§ 4. Оптимальный выбор количества вычислений значения функции и оптимальное распределение вычислительных ресурсов.

§ 5. Последовательно-оптимальный алгоритм поиска корня функции, удовлетворяющей на отрезке условию Липшица с различным значением константы Липшица на разных частях отрезка.

ГЛАВА Ш. ОПТИМАЛЬНЫЙ НА ОДИН ШАГ СТОХАСТИЧЕСКИЙ ПОИСК КОРНЯ ФУНКЦИИ, УДОВЛЕТВОРЯВШЕЙ УСЛОВИЮ ЛИПШИЦА

§ 6. Постановка задачи •

§ 7. Оптимальный стохастический выбор первой точки

§ 8, Оптимальные на один шаг стохастические алгоритмы

ГЛАВА 1У. ОДИН АЛГОРИТМ ЧИСЛЕННОГО РЕШЕНИЯ СИСТЕМЫ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

§ 9, Описание алгоритма и результаты тестирования

§ 10. Пример расчета сложного технического объекта

В последние три десятилетия интенсивно исследуется круг вопросов, связанных с эффективностью вычислительных алгоритмов и построением оптимальных алгоритмов для самых различных задач. Появилось много работ, посвященных построению оптимальных алгоритмов приближенного решения нелинейных уравнений и систем нелинейных уравнений (см,, например, [ю] - ¡13],[17] - [26], [28] - [54]). При этом оптимальность алгоритмов определяется в разных работах неодинаково. Так, под оптимальным понимают алгоритм, который при заданной информации о функции (например, значения функции и ее производных) имеет наиболее высокий порядок сходимости; требующий наименьших затрат ресурсов ЭШ. Особое место занимает минимаксная концепция оптимальности, основы которой заложил еще П.ЛЛебышев. Согласно этой концепции под оптимальным понимается алгоритм, гарантирующий наименьшую погрешность нахождения корня при применении к "наихудшей" функции из данного функционального класса, либо алгоритм» требующий наименьшего количества вычислений значения "наихудшей" функции для достижения заданной погрешности. Поставленная в рамках минимаксной концепции задача построения оптимальных алгоритмов естественно вписывается в общую схему исследования операций [ 9]. Оперирующая сторона -вычислитель выбирает некоторый алгоритм оС поиска корня из множества А допустимых алгоритмов, неконтролируемым фактором является функция ^ , корень которой нужно найти. Обычно относительно известно, что она принадлежит некоторому функциональному классу Р • Задача оперирующей стороны состоит в минимизации погрешности ¿Си>$) решения задачи, руководствуясь принципом гарантированного результата за оценку эффективности алгоритма о< следует цринять величину р) £ бир ¿СОС^).

Оптимальная стратегия оперирующей стороны заключается в выборе алгоритма 6 /\ , для которого

F) « mln- С(о<аР) = frxirv Sup e(ot?-f)r *' ос^А ОfeF

Вид правой части последнего соотношения оправдывает название "минимаксный алгоритм". При реализации этого подхода в диссертации часто используется наряду с названием "алгоритм" название "стратегия", используются характерные для исследования операций методы.

Кроме минимаксного подхода к задаче приближенного решения нелинейных уравнений и систем нелинейных уравнений в последние годы интенсивно развиваются различные варианты вероятностного подхода, разрабатываются информационно-статистические и стохастические алгоритмы для решения нелинейных уравнений и систем нелинейных уравнений (см., например,[ 8], fl4j-p6]). В диссертации затронута и эта тематика - построен оптимальный на один шаг стохастический алгоритм поиска корня для класса функций, удовлетворяющих на отрезке условию Липшица»

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

6.

Диссертация состоит из четырех глав,

В первой главе рассматривается пассивный поиск корня монотонной функции. Вводится функциональный класс

F = (i I {(х.) & R1, X £[.<*-?&] , 0<**>*f*(x)4

-ftf)?о}.

В качестве множества допустимых алгоритмов (стратегий) поиска корня рассматривается множество

Предполагается, что одновременно^ вычисляются значения функции во всех точках -xf 1., oz^ , т.е. поиск пассивный.

В § I в качестве критерия эффективности алгоритмов поиска рассматривается £ (Y?1? -f) - длина отрезка локализации корня. Ищутся и X * = х*"7.из условия

Е^й sup - жи, sup £<fxV).

Доказано-, что оптимальный пассивный алгоритм имеет вид

ОС? - CL +

1 ^

B.I) у ¿*= S/2- ? > s т.е. точки ^Ту^г > •"> распределены на отрезке равномерно и симметрично относительно середины отрезка, причем (М - ил} (4— аЛ г

В § 2 в качестве критерия эффективности алгоритмов поиска корня рассматривается - "невязка" (точное определение этого критерия см. на стр.30 ). Ищутся с^ и л*^^,^,.,^) из условия t^if ^f £'iXl,-f) - min. suP e'o^f). оптимальный , гг

Показано, что в этом случае^пассивный алгоритм X ^ имеет вид ъм-»С)С ¿-а.)

1 -а + —:-г-г

Z[(ln+OM-/nJ , (В.2) я- -х- Jf* г т.е. точки o:f 7. , ^ распределены на отрезке L^^J равномерно и симметрично относительно середины этого отрезка, причем

I М(М-ъ)(4-сС) tn+i)M -fit] .

Нетрудно видеть, что стратегии (В.1) и (В.2) различны. Это вызвано тем, что для функционального класса Р критерии £ и не эквивалентны, т.е. функции "наихудшие" по одному критерию не являются "наихудшими" по другому критерию. Известны £17] функциональные классы для которых пассивные алгоритмы, оптимальные по критерию £ , оптимальны и по критерию и наоборот.

Отметим еще, что как в стратегии (В.1), так и в стратегии (В.2) точки располагаются на отрезке ^ ] равномерно и симметрично относительно его середины. Такое расположение характерно не только для оптимальных пассивных алгоритмов поиска корня, но и для оптимальных пассивных алгоритмов поиска экстремума функции (СМ. [7], Сгф.

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

Считается, что заданы натуральное п и положительные числа ^ 1 ^г. п ••• ? • Предполагается, что значения функции $ е I» могут быть вычислены в произвольных УЬ точках отрезка , при этом в результате г -го вычисления получается не точное значение -рС» а некоторое число ^ такое, что ^ 7 ¿- -1,1,. , И- . Предполагается* что при выборе точки ос^ используется информация, полученная в результате предыдущих вычислений.

Введем обозначения г = (Х1,У(") = .«г.,-.«^.,^.---.^) >

I 2,.I}.

Рассмотрим СОВОКУПНОСТЬ IX функций А - (эс1 1 ^ 5 • • ■ 1 Хгь) где есть фиксированный элемент Ос^ £ [а, &] , а

Будем называть такие совокупности последовательными алгоритмами (последовательными стратегиями) поиска корня. В качестве множества

Г*-? ^ допустимых алгоритмов рассмотрим множество К всех последовательных алгоритмов поиска корня. Вводится описывающий погрешность отыскания корня критерий эффективности алгоритмов поиска корня имеющий смысл "невязки" (точное определение этого критерия см. на стр.44 ). Для этого критерия используется также обозначение

Ц—J -„^х-P^O "'J Хп ) последовательно-оптимальным на классе L , если ЭС* реализует нижнюю грань в выражении

Lrvf sup Lnfi sup in-f .Уир a L+1 реализует для произвольного вектора нижнюю грань в выражении sup .ml sup t(X ,V ), k-i. ос,., 4J CC uH ¡Ji/H "^n.

Здесь нижние грани берутся по , а верхние по множествам всех допустимых ^ , ^ - 1Д,., п.

В § 3 доказано, что алгоритм половинного деления сегмента локализации корня является последовательно-оптимальным. Алгоритм заключается в следующем. Положим с10 ~ си „ &0 — £ , ^ - (о>0 •

Вычислим . При полагаем = , При у^^^сО полагаем х^Щ+ф/М , 4>о .В случае 1^1 ^ с^ считаем х корнем и прекращаем вычисления, разумность этого допущения обоснована в § 4. Далее полагаем , вычисляем и т.д. Определенный таким образом алгоритм гарантирует за гъ- шагов погрешность отыскания корня

9 * г о *> , ,

- мах { и:, -/.

В § 4 рассматривается задача минимизации выражения (В.З) за счет выбора М- и величин ,«. из условия + 4 + = л, (в*4)

Смысл такой постановки задачи заключается в следующем. Пусть в распоряжении вычислителя имеется некоторое количество 17" вычислительных ресурсов (будем предполагать» что это некоторые обобщенные безразмерные ресурсы. Разумеется, реальные вычислительные ресурсы всегда измеряются в каких-то физических единицах, например, в единицах времени ЭВМ, но всегда можно перейти к безразмерным ресурсам, надо только ввести подходящий коэффициент цропорциональности). Вычислитель волен по своему усмотрению выбрать количество гь вычислений значения функции и распределить имеющееся количество вычислительных ресурсов на Л- вычислений: Разумно предположить, что ¿¿»¿/"и^ , ¿ = 7 п* ; т.е. чем больше ресурсов выделено на Г -ое вычисление, тем меньше погрешность этого вычисления. Для целого ряда задач численного анализа дело обстоит именно так, см., например, [21]. При этом равенство (В.4) эквивалентно выражению Т/г + ., + Т^ •= Т7; (В.47) где 17 = 1/Д .

Показано, что минимизирующее величину (В.З) при условии (В.41) значение П- определяется из условия ма-*) ± тг, (в-5) при этом вычислительные ресурсы следует распределить на П. вычислений равномерно. При таком расцределении ресурсов справедливо соотношение где п. определяется из условия (В.5). Кроме того, при таком выборе П- и справедливо соотношение 2(1л+-1) которое показывает, что если на т -ом (Се .,&}) шаге в результате вычисления ^ получено неравенство то достигнута погрешность, которую алгоритм гарантирует за шагов, а так как оставшиеся вычисления могут и не улучшить уже достигнутого результата, то сделанное в § 3 допущениег предписывающее считать эс^ корнем и прекращать вычисления, оказывается вполне разумным и даже целесообразным, если каждое вычисление значения функции обходится дорого. Разумеется, определенное из условия (В.5) П не обязано быть целым числом. В этом случае можно, например, сделать Ивычислений.

Отметим еще, что оптимальность равномерного распределения ресурсов в рассмотренной задаче минимизации неочевидна, поскольку величины ^> ; Кь входят в формулу (В.З) для погрешности с неодинаковыми весами.

В § 5 рассматривается задача последовательно-оптимального поиска корня функции, удовлетворящей на отрезке условию Липшица с различным значением константы Липшица на разных частях отрезка. Считается, что заданы отрезок Ел-,6] , натуральное число гь и числа такие, что а=л0<оСчитается, что заданы положительные числа Му, • Вводится функциональный класс

-fCu)^ М1 /и-тг|, V ы^б ,^,1=1,2,.,

Требуется приближенно определить корень функции , относительно которой известно только, то, что она принадлежит классу Ь . Считается, что значения могут быть вычислены без ошибки в произвольных Уь точках отрезка , причем при выборе очередной точки используется информация, полученная в результате предыдущих вычислений. Вводится критерий эффективности последовательных алгоритмов поиска корня, имеющий смысл "невязки" (подробное определение см. на стр. £5 ). Вводится определение последовательно-оптимального алгоритма (аналогичное определению, данному при рассмотрении поиска корня функции, вычисляемой приближенно, в § 3). Построен после-довательноюптимальный алгоритм, который оказался обобщением бисек-ции. Последовательно-оптимальный алгоритм поиска корня функции, удовлетворяющий на отрезке условию Липшица, предписывает на каждом таге поиска вычислять значение функции в середине текущего отрезка локализации корня. Последовательно-оптимальный алгоритм поиска корня функции, удовлетворяющей на отрезке условию Липшица с различным значением константы Липшица на разных частях отрезка, предписывает делить пополам не отрезок локализации корня, а отрезок изменения допустимых значений абсолютной величины значения функции. Поясним это подробнее. Пусть перед выбором точки Х^ корень локализован на отрезке . Строится функция : из левого конца отрезка локализации корня проводится ломаная линия с максимальным угловым коэффициентом на каждом отрезке С0^,0^*^ , входящем в отрезок /Д—| , 4i-.fl • Функция \ О-) является мажорантой для всех функций из класса I, , имеющих корень на отрезке , 7 . Последовательно-оптимальный алгоритм предписывает вычислять значение функции в точке ос^ е [а.}, такой, что = £ ={

Разумеется, при 1 этот алгоритм совпадает с обычной бисекцией.

В третьей главе рассматривается последовательный стохастический поиск корня функции, удовлетворяющей на отрезке £о,1 ] условию; Липшица. Вводится функциональный класс

Предполагается,, что значение функции £ может быть вычислено без ошибки в любой точке отрезка [о741 . Каждый шаг поиска состоит в вычислении значения функции / в выбираемой вычислителем точке отрезка • После I шагов, , информация о -[■ есть известный вектор где г^ , I . Положим

Вводится описывающий погрешность решения задачи критерий эффективности алгоритмов поиска корня, имеющий смысл "невязки". Подробное определение критерия см. на стр. ВЪ .

Обозначим через 21 множество всех вероятностных мер на <э -алгебре борелевых подмножеств отрезка i] . Следуя работе poj, будем называть совокупность отображений , , . , »

1 *> ••• стохастическим последовательным алгоритмом поиска корня, если есть фиксированный элемент из множества -Z! ,

Применение стохастического алгоритма к некоторой функции -fe L состоит в выборе случайным образом в соответствии с вероятностным распределением некоторого е L°?1J , вычислении определении вероятностного расцределения ), случайном выборе в соответствии с вероятностным распределением и т.д.

Стохастический алгоритм ,й — называется оптимальным на один шаг на классе L среди всех стохастических <— последовательных алгоритмов, если для i

Sup fax] = miVL Sup f6L 0 1 feL ° и для любого вектора z: i i

Sup mm S\a &

В § 7 рассматривается задача оптимального стохастического выбора первой точки вычисления значения функции. Показано, что оптимален выбор первой точки в соответствии с равномерным вероятностным распределением на L°,1] » причем trxiw <juP = Jup ^ el f6L ° 0 ' '

Отметим для сравнения, что для оптимального детерминированного выбора первой точки имеет место соотношение

Таким образом, оптимальный стохастический выбор первой точки гарантирует среднюю точность решения задачи , что лучше, чем точность М/6 , гарантированная оптимальным детерминированным выбором Пусть ^ Ф 0 . Положим при ¿¿¿^а^о^^^-^/М . а

При положим , = / . Задача оптимального стохастического выбора второй точки на отрезке полностью аналогична уже решенной задаче об оптимальном стохастическом выборе первой точки на отрезке [0**1 • Поэтому оптимален выбор второй точки в соответствии с равномерным вероятностным распределением на отрезке Вычислив ^ , определим новый отрезок локализации корня. Оптимален выбор <ь[ах /¿у в соответствии с равномерным вероятностным распределением на [«¿г и т.д. Таким образом, последовательный стохастический алгоритм, предписывающий выбирать точку -^¿+1 » 6 ^ О в соответствии с равномерным вероятностным распределением на отрезке 1р~с >£¿3 локализации корня, является оптимальным на один шаг на классе стохастическим алгоритмом.

Оказалось, что существует бесконечно много оптимальных на один шаг на классе Ь стохастических алгоритмов поиска корня. В частности, в § 8 показано, что можно осуществлять выбор точки ^¿+1 0, не в соответствии с равномерным вероятностным распределением на С^с ,£¿1 , а в соответствии с произвольным вероятностным распределением в для которого выполнены следующие условия:

1) ^¿+1 имеет непрерывную плотность

2) <с>1+-{ симметрично относительно середины отрезка Л0-с >¿¿1 » т.е.

3) Ч+ик-ьд

4) 0.1 М^-фрс+гФ > Ухе £<£¿,£¿1.

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

Интересно отметить, что для задачи поиска экстремума функции, удовлетворяющей на отрезке условию Липшица, существует единственный оптимальный на один шаг стохастический алгоритм (см.1201).

В четвертой главе предложен алгоритм численного решения системы нелинейных уравнений. Идея заключается в сведении задачи решения системы нелинейных уравнений к задаче минимизации некоторого функционала, для которого известно минимальное значение - ноль. Рассмотрим систему нелинейных уравнений Г , = 0

СВ.6)

Предположим, что заданы два вектора ( ¿Ц, - - - ?

1 ¿^/^-^ И параллелепипед р = I ас 6 ^ 71=1,2,.у п], содержащий решение • •• ^О системы (В.6).

Предположил, что в пространстве задана метрика •

Определим невязку - функцию и - IЖ АЭС. .

Будем предполагать, что функции (ЪО , С~ 1,2}. , 9 удовлетворяют в параллелепипеде Р условию Липшица с константой М , тогда и невязка удовлетворяет в Р условию Липшица с константой М , т.е. ус*) ^ V

Пусть заданы натуральные числа -, ^п * ,

4,2. ,УЬ . Построим в параллелепипеде Р сетку Т , равномерную по каждой координате. Шаг сетки Т" по I -ой координате определяется формулой /¿'т1 -1) , 2,., И. . Построенная в параллелепипеде Р сетка "Г содержит п^-и*^ . • ии-^ узлов.

Обозначим через £> множество всех узлов сетки "Т , в которых невязка еще не вычислялась. Перед началом работы алгоритма множество 5 содержит все узлы сетки ~Г .

Случайным образом выберем 6 Й и вычислим .

При ~ 0 решение системы (В.6) найдено. Предположим, что (ас/) > 0 . Пусть 2 е- Р и удовлетворяет неравенству тогда из условия Липшица получаем т.е. 5 не может быть решением системы (В.6), и множество -Ц ^ (гб Р| ^ не может содержать решение системы (В.6). Поскольку для каждого узла £ ^ & Л значение невязки заведомо положительно, исключим все такие узлы из рассмотрения, т.е. положим £> • = £>

Если после этого исключения $ не пусто, выбираем случайным образом СС^ е ^ , вычисляем ¡¡(^х) . При находим множество

17^ {ъе р| и полагаем ,3 Если после этого исключения множество не пусто, выбираем случайным образом в Й и т.д.

Поскольку сетка Т содержит конечное число узлов и на каждом шаге описанной процедуры из множества £> исключается хотя бы один узел, процесс закончится через конечное число шагов. Как только множество ё> стало пустым, производится просмотр всех вычисленных значений невязки, соответствующий минимальному из этих значений А узел ос. выбирается в качестве приближения к решению системы (В.6). Затем происходит уточнение решения при помощи локально сходящегося итерационного метода ньютоновского типа (являющегося модификацией метода, предложенного и обоснованного в £"27]).

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

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

Результаты диссертации опубликованы в работах СЗ] - И» зультаты докладывались на конференции молодых ученых факультета ШиК МГУ (г.Москва, 1982 г.), на заседании научно-исследовательского семинара кафедры исследования операций факультета ВМиК МГУ в 1983 г. Разработанный алгоритм численного решения системы нелинейных уравнений нашел применение на МЗ им. П.О.Сухого, в Иркутском ВЦ СО АН СССР, а также включен в общую библиотеку программ системы Коллективного Пользования ЭВМ МГУ и в ГосФАП СССР.

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

1. Бай Ши-и. Введение в теорию течения сжимаемой жидкости. - М.: Издательство Иностранной Литературы, 1962. - 410 с.

2. Батшцев Д.И. Поисковые методы оптимального проектирования. -М.: Советское радио, 1975. 216 с.

3. Васильев П.П. Об оптимальном пассивном поиске корня монотонной функции. Депонир. ВИНИТИ № 3485 - 83 от 28.06.83 - 22 с.

4. Васильев П.П. Оптимальный поиск корня функции вычисляемой приближенно. Депонир. ВИНИТИ № 3486 - 83 от 28.06.83 - 13 с.

5. Васильев П.П. Оптимальный поиск нуля функции, вычисляемой приближенно. В кн.: Математические методы оптимизации и управления в сложных системах. Калинин.: Изд-во КГУ, 1983, с.19-25.

6. Васильев П.П., Сухарев А.Г. Программа численного решения системы нелинейных уравнений методом Брауна с предварительным подбором начального приближения. Алгоритмы и программы, Изд-во ВЕТИЦ, 1983, № 5 , анн. П 006441, с. 20.

7. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1980. 520 с.

8. Высоцкая И.Н., Стронгин Р.Г. Метод решения нелинейных уравнений, использующий априорные вероятностные оценки корней. Ж.вычисл. матем. и матем.физ., 1983, т. 23, № I, с. 3 - 12.

9. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971. - 384 с.

10. Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. М.: Мир, 1975. - 558 с.

11. Островский A.M. Решение уравнений и систем уравнений. М.: Изд-во Иностранной Литературы, 1963. - 219 с.

12. Стронгин Р.Г. Вероятностный подход к задаче определения корня функции. Ж.вычисл.матем. и матем.физ., 1972, т.12., Л I,с. 3 13.

13. Стронгин Р.Г. Численные методы в много экстремальных задачах. -М.: Наука, 1978. 240 с.

14. Стронгин Р.Г. Информационно-статистический метод решения систем нелинейных уравнений. В кн.: Проблемы случайного поиска. Вып. 4. Рига: Зинатне, 1975, с. 54 - 65.

15. Сухарев А.Г. Оптимальный поиск экстремума. М.: Изд-во МГУ, 1975. - 100 с.

16. Сухарев А.Г. Оптимальный поиск корня функции, удовлетворяющей условию Липшица. Ж.вычисл.матем. и матем. физ., 1976, т.16, № I, с. 20 - 29.

17. Сухарев А.Г. Оптимальные и последовательно-оптимальные алгоритмы в задачах численного анализа. В кн.: Математические методы в исследовании операций, М., МГУ, 1981, с. 54-69.

18. Сухарев А.Г. Построение оптимального на один шаг стохастического алгоритма поиска экстремума. Ж. вычисл.матем. и матем. физь, 1981, т.21, № 6, с. 1385 - 1401.

19. Черноусько Ф.Л. Оптимальный алгоритм поиска корня функции вычисляемой приближенно. Ж. вычисл .матем. и матем.физ., 1968, т.8, № 4, с.705 - 724.

20. Черноусько Ф.Л. Об оптимальном поиске экстремума унимодальныхфункций. Ж.вычисл.матем. и матем.физ., 1970, т.10, № 4, с. 922 - 933.

21. Boo-fck e.S. Loc«*um. <4 2eroS of . SIAM3.А^.Ма+к., Vol. 4361.

22. Bootk fc.S. Location. orf Zeros X)eriira5tiires.il.-5//VMJ.App^./И^. 13637 403-415-.25. EW P. W E/^-cie^t frr Mu^Nmii^ E%ua*Coyu$ . 5/AM J. NuiMer.Avvai v.-iO^ 2

23. Bneia-fc R Wino^rcuJ 5., Wo£fe P. ОрЧггкаХ RerccHis^Processes -fvr Numjzt. Mot-tk. ^ Itn-b4.ъо^ггч-зщ. P

24. BrouJh. k.M. a Quadrat Leo. ConvergentN/ewboKt-htt Method Base J upirn Gaussian,BUvyUrLcxHcrvL % SIAM Л. Numer. Anal. J363b-SGO-5-&S.

25. Euck-^borfu В.И. Ок ^есцлеп-Нси Secin^k . — Selected S-UtisiicoLl Papers Mufk. Cerebrum,

26. Qae 5. Op-ti/vial cuid Рагц®г<£SearcL -frrr RndiiKj, -A feoot . Combed .IWr^ 5er. A- 23.И,

27. Gross 0, ^oUkxsoh. 5.M. Setjuen-Kai. Miniutcw. Search fnr * iero 4 ^ Corn/ex Function^ MTAC;vof^>i95B,44-5>i.

28. Kindhacirsk A. Op-KwaXt4^ Си d C£aSS foot-^nchw^ Aijorl^Ws.-S/AM 1 /V/ижег. 4W.,2oS-2<i4.

29. ICaceWicz. B. "TW Use o^f Integrals in-ttu? Jcr€utCcn^.uaii'Mtj in IV "Öj'iMjßMSimSj in "<A*\cJLftic.C^fu±o^i&naJi C&mj^C-h^'' (7. FT Treuere/.), pp. /2?-Ac^dewic Press, Wew Vörie ,18^6.

30. K.T,Traua 3.F. Order of OvuL-Pcrivct öuaol Trt&ncHons T /Uroc. Compu.rt' MacA.j

31. H .T. .Ttau-C J.F. j OfrKmai ÖreUfui &}u<dims.-SIAM ö • Numer. baaj. , i/.

32. Meers Man, £. 0p-h>ici£ Use InfexiMah.'07/L tKCer-irdi^i J-berorti-tf-L ProC€SS€S 7 in "Awae^-h'c Com-pu+a+Cottai Com^Znuhf "CJ.RTiraiU ¿ed¡>p.iD3-/Z£AcaJemic. Press, Meu'York, <19*3.

33. Meeirswian. fc. 0^ Maximal OrcJer o£ Fami^cescrf. rter«,taon5 -ftrr Nomici^our ЩилНо^ .Ъос-ЬопхС Tkesis, "Vrijc IWv. Brüssel, Brüssel, 43

34. Miccketti A. , Mirahker U/.L. Ki^fc Order SecucA. M^-tW -f^r FiWiYij &ocrt$, J. Assoc. Cotnpui-. Mach., I/.22 ,

35. Risset пей J. Oki Op-ftknuin ßooi;-Fl u eiing . '-Э. Turner. Awa£. and App€< , 1, v. 3£,22o-225~.

36. Sohnev€nd G. Ои Ор-Ь^с^-Кои of At^oriHmsrftyr Function МтМ&Ьсцг Журнал вычисл.матем. и матем. физ., 1977, т.17, Jfe 3, с. 591 609.

37. ТосЫ м.1. OptcmaÄ. Cissecbows о^ 5i'»Hp£<cflS. Ityw-ita^w* Op^re^iöns &se<uck fep. 7Cornetl L/"/V.,f3?6Trau € 3.R ftercctc-re M e4Ws firr-tU So Zubern o£Bj ua+i о ns. Bhafewooc} Cic^fs , N/^w ^J^nsey : Ргси-ЬГса-НсиЙ., -«3 64.

38. Trau^ 3.F, Ол Fujoc-h'oMOÄ H^aiioH смаЫCLoJL<LxJlcbtCow crf. ¡Zoo-tS,Pr-eprClAiS crf. Paf&rS i^-Hu IVat.ACM Cowf. Session SA-i, pp.1-4 . Los Anwies,CcJlc+ervU* (13G -О • , *

39. TrauA 3.F. , WöbiakoUJSÜ А беМГаЛ cfOptimal МуопШшЯ -Nbj Vbrfc * /Icacte^c freS£, 46

40. Woknialcouski H. Max-iwiaQ. S-tafCim a ry Itercdi'zTe. IMe-Baocb -fcrr-ttuL Sotu,icon Op^ect^r SjucchJons ,-S/AM 1< Muvuer.AvicLe. ,v. M tmin) , 33y-sHsr.

41. Wo2niak#UjSk.{ U • Qx^x&JroJU'ieJi TvfcrriModticm. cwd Ma^UmaJ. Order crf IbercvtCcm, -fW CX^aradbr Syma4urvts .-S/AM J. NuMier. A*a£,v.f2 (ins) , f2<f-f35;