Содержание к диссертации
Введение
ГЛАВА I. Оптимальный пассивный поиск корня монотонной функции
1. Оптимальный по критерию "длина отрезка локализации корня" алгоритм поиска корня монотонной функции 20
2. Оптимальный по критерию "невязка" алгоритм поиска корня монотонной функции 29
ГЛАВА II. Поиск корня функции, удовлетворяли условию Липшица
3. Последовательно-оптимальный по критерию "невязка" алгоритм поиска корня 42
4. Оптимальный выбор количества вычислений значения функции и оптимальное распределение вычислительных ресурсов 52
5. Последовательно-оптимальный алгоритм поиска корня функции, удовлетворяющей на отрезке условию Липшица с различным значением константы Липшица на разных частях отрезка 60
ГЛАВА III. Оптимальный на один шаг стохастический поиск корня функции, удовлетворявдей условию Липшица
6. Постановка задачи 76
7, Оптимальный стохастический выбор первой точки 83
8, Оптимальные на один шаг стохастические алгоритмы 93
ГЛАВА ІV. Один алгоритм численшго решения системы нелинейных уравнений
9, Описание алгоритма и результаты тестирования 105
10. Пример расчета сложного технического объекта 118
Список литературы 125
- Оптимальный по критерию "длина отрезка локализации корня" алгоритм поиска корня монотонной функции
- Оптимальный выбор количества вычислений значения функции и оптимальное распределение вычислительных ресурсов
- Оптимальный стохастический выбор первой точки
- Пример расчета сложного технического объекта
Введение к работе
В последние три десятилетия интенсивно исследуется круг вопросов, связанных с эффективностью вычислительных алгоритмов и построением оптимальных алгоритмов для самых различных задач. Появилось много работ, посвященных построению оптимальных алгоритмов приближенного решения нелинейных уравнений и систем нелинейных уравнений (см,, например, [10] - [із],[Г7] - [26], [28] - f54]) При этом оптимальность алгоритмов определяется в разных работах неодинаково. Так, под оптимальным понимают алгоритм, который при заданной информации о функции (например, значения функции и ее производных) имеет наиболее высокий порядок сходимости; требующий наименьших затрат ресурсов ЭВМ. Особое место занимает минимаксная концепция оптимальности, основы которой заложил еще ПЛЛебышев. Согласно этой концепции под оптимальным понимается алгоритм, гарантирующий наименьшую погрешность нахождения корня при применении к "наихудшей" функции из данного функционального класса, либо алгоритм» требующий наименьшего количества вычислений значения "наихудшей" функции для достижения заданной погрешности. Поставленная в рамках минимаксной концепции задача построения оптимальных алгоритмов естественно вписывается в общую схему исследования операций [ 9]. Оперирующая сторона -вычислитель выбирает некоторый алгоритм с< поиска корня из множества А допустимых алгоритмов, неконтролируемым фактором является функция f , корень которой нужно найти. Обычно относительно -f- известно, что она принадлежит некоторому функциональному классу F . Задача оперирующей стороны состоит в минимизации погрешности 0*>- ) решения задачи, руководствуясь принципом гарантированного результата за оценку эффективности алгоритма о<. следует принять величину
S-eF
5. Оптимальная стратегия оперирующей стороны заключается в выборе алгоритма ОС^ 6 /} , для которого
Pfc* F)«rnin. Z(*yE) = ґгхігь Sup ЄО<,-). *' oc*A о(бА feF
Вид правой части последнего соотношения оправдывает название "минимаксный алгоритм". При реализации этого подхода в диссертации часто используется наряду с названием "алгоритм" название "стратегия", используются характерные для исследования операций методы.
Кроме минимаксного подхода к задаче приближенного решения нелинейных уравнений и систем нелинейных уравнений в последние годы интенсивно развиваются различные варианты вероятностного подхода, разрабатываются информационно-статистические и стохастические алгоритмы для решения нелинейных уравнений и систем нелинейных уравнений (см., например, 8j, і4]-[їб]). В диссертации затронута и эта тематика - построен оптимальный на один шаг стохастический алгоритм поиска корня для класса функций, удовлетворяющих на отрезке условию Липшица.
Задача построения оптимальных алгоритмов для решения уравнений представляет теоретический и прикладной интерес. В результате построения оптимальных алгоритмов решения уравнений выясняется, на какую точность отыскания корня можно рассчитывать при данной информации о функции и имеющихся вычислительных ресурсах. На практике нередко встречаются функции, нахождение значения которых в каждой точке связано с большим объемом вычислений или дорогостоящими экспериментами, наблюдениями - понятно, что здесь приходится дорожить каждым вычислением значения рассматриваемой функции. Для таких случаев экономичные оптимальные алгоритмы имеют особенную ценность. Большой интерес представляет задача отыскания оптимальных алгоритмов поиска корня для важных в прикладном отношении классов, содержащих негладкие функции.
6.
Диссертация состоит из четырех глав.
В первой главе рассматривается пассивный поиск корня монотонной функции. Вводится функциональный класс
В качестве множества допустимых алгоритмов (стратегий) поиска корня рассматривается множество
Предполагается, что одновременно* вычисляются значения функции во всех точках -xf ^ос% 1..., оск , т.е. поиск пассивный.
В І в качестве критерия эффективности алгоритмов поиска рассматривается YX ,-f) - длина отрезка локализации корня. Ищутся 1+ и X* =of,x"7...7х) из условия
Е^й s*? (*%) - mi*, sup
ЭС~Г - CL +
1 (П + 1)М4-С^~^)1^ ^
(B.I)
/_ У ? и — /
.*- -v*-
т.е. точки ^/ 7 t—fxtt распределены на отрезке іа>^ равномерно и симметрично относительно середины отрезка, причем
* ^ (*L+l)M+(A-f)HL
7.
В 2 в качестве критерия эффективности алгоритмов поиска корня рассматривается (К , т) - "невязка" (точное определение этого
критерия см. на стр.30 ). Ищутся с^ и Л* =» (^,^.-,^) из условия
l^H sup 11аІЛ) - *l suP e'fxV).
.оптимальный . гг
Показано, что в этом случае^пассивный алгоритм Х^. имеет вид
СХ1 =га + _- -
Z/CZk+Om-mJ , (В.2)
# -х- Jf* г ff~i
т.е. точки o:f , ,... , 3^ распределены на отрезке L^^J
равномерно и симметрично относительно середины этого отрезка, причем
* =
%[сгь+і)ц -mJ .
Нетрудно видеть, что стратегии (B.I) и (В.2) различны. Это вызвано тем, что для функционального класса F критерии и
не эквивалентны, т#е« функции "наихудшие" по одному критерию не являются "наихудшими" по другому критерию. Известны fl?3 функциональные классы для которых пассивные алгоритмы, оптимальные по критерию , оптимальны и по критерию и наоборот.
8,
Отметим еще, что как в стратегии (B.I), так и в стратегии (В.2) точки располагаются на отрезке Са>^] равномерно и симметрично относительно его середины. Такое расположение характерно не только для оптимальных пассивных алгоритмов поиска корня, но и для оптимальных пассивных алгоритмов поиска экстремума функции (см. [7], ft?]).
Во второй главе рассматривается последовательный поиск корня функции, удовлетворяющей на отрезке условию Липшица. Вводится функциональный класс
lfM-fM\^ М |и-тг1 , Vu/ire а.,4]}т
Считается, что заданы натуральное п и положительные числа ^Л і^% п 7 Kv Предполагается, что значения функции f & L могут быть вычислены в произвольных YL точках отрезка C«,^J , при этом в результате г -го вычисления получается не точное значение -f-Ox-i) f а некоторое число fa такое, что l^-ffc^l^-^b L^-i,!,... , ^. Предполагается* что при выборе точки ос^ используется информация, полученная в результате предыдущих вычислений.
Введем обозначения
Z = (Xl,YL) = (=1,=4,...,^4,3,,^,...,3^ ,
Рассмотрим совокупность IT функций а ~ Lx1 ох& ,..- , ^nJ і где -3cf есть фиксированный элемент Ос j О, La/&1 , а
9.
Будем называть такие совокупности последовательными алгоритмами (последовательными стратегиями) поиска корня. В качестве множества допустимых алгоритмов рассмотрим множество К всех последовательных алгоритмов поиска корня. Вводится описывающий погрешность отыскания корня критерий эффективности алгоритмов поиска корня
(а , т) , имеющий смысл "невязки" (точное определение этого
критерия см. на стр.44 ). Для этого критерия используется также
обозначение
ц—j -^^ ґ ^"^f эаС,'*'-'Х>г'
последовательно-оптимальным на классе L , если ^ реализует нижнюю грань в выражении
Inf sup Ln-f sup ,., inf Sup (X > У J9
a XL+1 реализует для произвольного вектора ї нижнюю грань в выражении
rn.
v.f sup ...m| sup t(X ,V ), Ї--(Д7...Д-І.
~l+i Яі-Н "^n, ^
Здесь нижние грани берутся по C*-,6j , а верхние по множествам всех допустимых 9^,^-1,1,...,^.
В 3 доказано, что алгоритм половинного деления сегмента локализации корня является последовательно-оптимальным. Алгоритм заключается в следующем. Положим сі0 = си „ &0 — і » а/ "ґ^-о -*~&о)/Ъ .
Вычислим JJ^ При ^-j >0 полагаем di-0.Q ,
^=0:,-(^-^)//4. При Їі+^і < 0 полагаем b^^-Cty+ty/M ,
10.
в1 = &0 . В случае ljff I ^ с^ считаем jt корнем и прекращаем вычисления, разумность этого допущения обоснована в 4. Далее полагаем ^-^-/-^)/2^ , вычисляем у^ и т.д. Определенный таким об-* разом алгоритм гарантирует за гъ- шагов погрешность отыскания корня
, -»«І гд И > Kf+'-i)— / (в-3)
В 4 рассматривается задача минимизации выражения (В.З) за счет выбора ґь и величин f^,^,,,,,^ из условия
і + к*~*і~і'л>о- (в,4)
Смысл такой постановки задачи заключается в следующем. Пусть в распоряжении вычислителя имеется некоторое количество "С/" вычислительных ресурсов (будем предполагать» что это некоторые обобщенные безразмерные ресурсы. Разумеется, реальные вычислительные ресурсы всегда измеряются в каких-то физических единицах, например, в единицах времени ЭВМ, но всегда можно перейти к безразмерным ресурсам, надо только ввести подходящий коэффициент пропорциональности). Вычислитель волен по своему усмотрению выбрать количество П вычислений значения функции и распределить имеющееся количество ~V вычислительных ресурсов на ГЪ вычислений: Uj i~t^,..,7I. Разумно предположить, что $l**i/iJ^ , 4 = -/,2,,... ? vi ; т.е. чем больше ресурсов выделено на Г -ое вычисление, тем меньше погрешность этого вычисления. Для целого ряда задач численного анализа дело обстоит именно так, см., например, [2l]. При этом равенство (В.4) эквивалентно выражению
\J1 +X/Z +.., + 1^-=^ (В.47)
где V = l/A . Показано, что минимизирующее величину (В.З) при условии (В.4 ) зна-
II.
чение П- определяется из условия
при этом вычислительные ресурсы следует распределить на Ґі вычислений равномерно. При таком расцределении ресурсов справедливо соотношение
І4-І
+.-4 = 17
где п. определяется из условия (В.5). Кроме того, при таком выборе П- и ^i ,^%,..., ^. справедливо соотношение
которое показывает, что если на і -ом (Че ^,2.,..., »г}) шаге в результате вычисления JL- получено неравенство lfc^
Отметим еще, что оптимальность равномерного распределения ресурсов в рассмотренной задаче минимизации неочевидна, поскольку величины &і*^%,~*)Къ входят в формулу (В.З) для погрешности с неодинаковыми весами.
12.
В 5 рассматривается задача последовательно-оптимального поиска корня функции, удовлетворяющей на отрезке условию Липшица с различным значением константы Липшица на разных частях отрезка. Считается, что заданы отрезок />-,j » натуральное число ги и числа ^,ЛЛ7...,^ такие, что a«^e
Требуется приближенно определить корень функции т » относительно которой известно только, то, что она принадлежит классу L . Считается, что значения -f- могут быть вычислены без ошибки в произвольных YL точках отрезка [а,-5J , причем при выборе очередной точки используется информация, полученная в результате предыдущих вычислений. Вводится критерий эффективности последовательных алгоритмов поиска корня, имеющий смысл "невязки" (подробное определение см. на стр. 5 ). Вводится определение последовательно-оптимального алгоритма (аналогичное определению, данному при рассмотрении поиска корня функции, вычисляемой приближенно, в 3). Построен последовательно-оптимальный алгоритм, который оказался обобщением бисек-ции. Последовательно-оптимальный алгоритм поиска корня функции, удовлетворяющий на отрезке условию Липшица, предписывает на каждом шаге поиска вычислять значение функции в середине текущего отрезка локализации корня. Последовательно-оптимальный алгоритм поиска корня функции, удовлетворяющей на отрезке условию Липшица с различным значением константы Липшица на разных частях отрезка, предписывает делить пополам не отрезок локализации корня, а отрезок изменения допустимых значений абсолютной величины значения функции. Поясним
ІЗ.
это подробнее. Пусть перед выбором точки v6- корень локализован на отрезке &>_f94^f] . Строится функция V^^jc) : из левого конца отрезка локализации корня проводится ломаная линия с максимальным угловым коэффициентом на каждом отрезке Lpt-s^s+il » входящем в от-резок [в-1-1 Функция т^ &Х-) является мажорантой для всех функций из класса L , имеющих корень на отрезке Z"^^_f,^:_/J . Последовательно-оптимальный алгоритм предписывает вычислять значе-ние функции в точке ос- є [а. ._Л такой, что
Разумеется, при wi=l этот алгоритм совпадает с обычной бисекцией. В третьей главе рассматривается последовательный стохастический поиск корня функции, удовлетворяющей на отрезке io,] условию; Липшица* Вводится функциональный класс
l-pM-f6r)UM|u^! , V u7v-±Lo,i]}.
Предполагается,, что значение функции т может быть вычислено без ошибки в любой точке отрезка [o?Q . Каждый шаг поиска состоит в вычислении значения функции в выбираемой вычислителем точке отрезка L?Q После I шагов, l^i , информация о -f есть известный вектор
где ^j-ffej") ,1=1,2,...,1 . Положим
L(ZL>-(fL|?f*^=^ .)=1.2,...,1}. _
Вводится описывающий погрешность решения задачи критерий ^Х %т) эффективности алгоритмов поиска корня, имеющий смысл "невязки". Подробное определение критерия см. на стр. BZ .
14.
Обозначим через 21 множество всех вероятностных мер на <э -алгебре борелевых подмножеств отрезка Jj?i] Следуя работе poj, будем называть совокупность отображений 4>А , <>^ , ... , І^ »
^\>1 "> стохастическим последовательным алгоритмом поиска корня, если <$>л есть фиксированный элемент di из множества 21 ,
Применение стохастического алгоритма к некоторой функции -fe L состоит в выборе случайным образом в соответствии с вероятностным распределением ё1 некоторого ^1<=C,1]] , вычислении ^^-fcacj),
определении вероятностного распределения «^(2. ), случайном
выборе ОСх в соответствии с вероятностным распределением 6^ и т.д.
Стохастический алгоритм ^f ,^ ...,^^,^+f ,... называется оптимальным на один шаг на классе L среди всех стохастических последовательных алгоритмов, если для ь, «^
Sup J^C^f)^ ^оізс] = тсИ- Sup ]*<>:,f}{oU}
f6L 1 **Z feL
и для любого вектора Ї С >\ї JL^2 )Фф} 7 і ^i >^и~^-/2/
<( L 1
Sup — mm sup
В 7 рассматривается задача оптимального стохастического выбора первой точки вычисления значения функции. Показано, что оптимален выбор первой точки в соответствии с равномерным вероятностным распределением на ЇР,1І » причем
15.
A 4
^el f6L fe ^ '
Отметим для сравнения, что для оптимального детерминированного выбора первой точки имеет место соотношение
men. Sup C~,f>~4fi )-
Таким образом, оптимальный стохастический выбор первой точки гарантирует среднюю точность решения задачи Ml% , что лучше, чем точность М/в , гарантированная оптимальным детерминированным выбором Пусть ^ Ф 0 . Положим при %i>o а.^=*аоИо,^=хг-#г/М
При $і<0 положим Af^OLf—yf/M , -if =40 =г / . Задача оптимального стохастического выбора второй точки на отрезке //*/7^J
полностью аналогична уже решенной задаче об оптимальном стохастическом выборе первой точки на отрезке [Оу^І Поэтому оптимален выбор второй точки в соответствии с равномерным вероятностным распределением на отрезке L^-iy^f]» Вычислив fa , определим новый от-резок //^, ^, J локализации корня. Оптимален выбор ^e^/J
в соответствии с равномерным вероятностным распределением Ha*Z|z]] и т.д. Таким образом, последовательный стохастический алгоритм, предписывающий выбирать точку х-с+1 » *-'^ О в соответствии с равномерным вероятностным распределением на отрезке / ? 4 -7 локализации корня, является оптимальным на один шаг на классе L стохастическим алгоритмом.
Оказалось, что существует бесконечно много оптимальных на один шаг на классе L стохастических алгоритмов поиска корня. В частности, в 8 показано, что можно осуществлять выбор точки "^бм [Д-,-1 1^0 у не в соответствии с равномерным вероятност-
16.
ным распределением на С^сЛ с* » а в соответствии с произвольным вероятностным распределением <с+і в 2, для которого выполнены следующие условия:
^с+1 имеет непрерывную плотность/^+/fac);
<&і+і симметрично относительно середины отрезка L^c^cl і
т.е. ?и<(«с+чь-*0)*^С11-ъ(к-чУ,ч**&>Я:
3) bL+Uh-*!)
Любой стохастический последовательный алгоритм* предписывающий на каждом шаге выбирать точку вычисления значения функции в соответствии с вероятностным распределением, удовлетворяющим на текущем отрезке локализации корня перечисленным четырем условиям, будет оптимальным на один шаг на классе L стохастическим алгоритмом.
Интересно отметить, что для задачи поиска экстремума функции, удовлетворяющей на отрезке условию Липшица, существует единственный оптимальный на один шаг стохастический алгоритм (см.І20І).
В четвертой главе предложен алгоритм численного решения системы нелинейных уравнений. Идея заключается в сведении задачи решения системы нелинейных уравнений к задаче минимизации некоторого функционала, для которого известно минимальное значение - ноль. Рассмотрим систему нелинейных уравнений
,^,4,...,30 =
"bLO'S.Xa.,.--:,**.)-^ СВ.6)
« ш
Предположим, что заданы два вектора ( <*-/, <49 ... ? лО у
17.
(.*i,ex,-,V? 4
P = ^в^д| ..., хи) | ac 6 ^^ *C ? b*f,2,„* ftf, содержащий решение ^^/з^ії-^О системы (В.6).
Предположим, что в пространстве R задана метрика fQ*-,^) .
Определим невязку - функцию
и(эс} = Wax l-fc^30^
Будем предполагать, что функции yi(=^> , С = 1,2,..., ft* , удовлетворяют в параллелепипеде Р условию Липшица с константой /И , тогда и невязка удовлетворяет в Р условию Липшица с константой М , т.е.
Пусть заданы натуральные числа Ynioтг,-7 ^и. » тс> , L^-(,2 ,..., К. . Построим в параллелепипеде Р сетку Т , равномерную по каждой координате. Шаг сетки Т по l -ой координате определяется формулой ^1~С^-л{) /YmL -f) , l= 1,2,..., Vb . Построенная в параллелепипеде Р сетка Т содержит tv\.t-iw2'... kvt^ узлов.
Обозначим через S множество всех узлов сетки ~Т , в которых невязка еще не вычислялась. Перед началом работы алгоритма множество содержит все узлы сетки "Г .
Случайным образом выберем xf6 S и вычислим yC^i*) . При ЧС^-О ~ 0 решение системы (В.6) найдено. Предположим, что Ч. (ос^ т> 0 . Пусть 2 6- Р и удовлетворяет неравенству
тогда из условия Липшица получаем
Ч&) s* ^(аО —Mf (*<,*) > 0, т.е. 5 не может быть решением системы (В.6), и множество
18. не может содержать решение системы (В.6). Поскольку для каждого узла <=S ft~Ui значение невязки заведомо положительно, исключим все такие узлы из рассмотрения, т.е. положим > = > \(р^П$).
Если после этого исключения & не пусто, выбираем случайным образом 2^е , вычисляем ftf^z) При у6*х)>0 находим множество
и полагаем $ : = \ffliz). Если после этого исключения множество S не пусто, выбираем случайным образом -*3 е S и т.д.
Поскольку сетка ~Г содержит конечное число узлов и на каждом шаге описанной процедуры из множества S исключается хотя бы один узел, процесс закончится через конечное число шагов. Как только множество > стало пустым, производится просмотр всех вычисленных значений невязки, соответствующий минимальному из этих значений узел ос выбирается в качестве приближения к решению системы (В.6). Затем происходит уточнение решения при помощи локально сходящегося итерационного метода ньютоновского типа (являющегося модификацией метода, предложенного и обоснованного в 27])
В 9 приведен ряд примеров тестирования алгоритма, которые показывают, что во многих случаях предварительный подбор "хорошего" приближения для работы итерационного метода позволяет сократить затраты вычислительных ресурсов, что может оказаться немаловажным в случаях, когда вычисление левой части системы связано с большим объемом вычислений или дорогостоящими экспериментами.
В 10 приводятся результаты расчета сложного технического объекта (двигателя самолета) при помощи предложенного алгоритма решения системы нелинейных уравнений. Полученные результаты вполне устроили конструкторов.
Результаты диссертации опубликованы в работах C3J - И» ?е~
19.
зультаты докладывались на конференции молодых ученых факультета ШиК МГУ (г.Москва, 1982 г.), на заседании научно-исследовательского семинара кафедры исследования операций факультета ВМиК МГУ в 1983 г* Разработанный алгоритм численного решения системы нелинейных уравнений нашел применение на МЗ им. П.О.Сухого, в Иркутском ВЦ СО АН СССР, а также включен в общую библиотеку программ системы Коллективного Пользования ЭВМ МГУ и в ГосФАП СССР.
Автор считает своим приятным долгом выразить искреннюю благодарность своему научному руководителю доценту АіГ. Сухареву за помощь в постановке задач, постоянное внимание, полезные советы и поддержку в течение всего времени работы над диссертацией, а также сотруднику ВЦ АН СССР А.НДукову за помощь в постановке задачи расчета сложного технического объекта и многочисленные ценные советы, способствовавшие успешному выполнению этой задачи.
20.
Г Л А В А I
ОПТИМАНЬШЙ ПАССИВНЫЙ ПОИСК КОРНЯ МОГОТОНЮЙ ФУНКЦИИ
I. ОПТИМАЛЬНЫЙ ПО КРИТЕРИЮ "ДЖНА ОТРЕЗКА ЛОКАЛИЗАЦИИ КОРНЯ" МГОРИТМ ПОИСКА ІЮРНЯ МОЮТОНЮЙ ФУНКЦИИ
Рассмотрим класс вещественных функций
Очевидно, что имеют место неравенства
Каждая функция - из класса F монотонна и имеет на отрезке [а.,43 единственный корень Г Необходимо приближенно определить f , если известно только то, что функция принадлежит классуF. Предполагается, что значение можно вычислить в любой точке отрезка ЇР'Лі без ошибки.
Пусть до начала вычислений задается натуральное число ґі ^. 2 . Выбираются точки ^,0^ .... , ^ так, что выполнено условие
0,4 X, < X, < ... < Х„ ^ і
Такие наборы точек будем называть алгоритмами (или стратегиями) приближенного отыскания корня функции j . Будем использовать для стратегии обозначение Л - (ос1озс% ,..,_, х^) . После того, как выбраны точки Х1 ,Х^ ,... зх^ , одновременно вычисляются значения функции J в этих точках: ^.= fc^) » І = і, 2.,... , Ч .
Будем далее предполагать, что все числа U j Ч «»* Jf« отличны
21.
от нуля.
В результате проведения вычислений имеет место одна из следующих трех ситуаций.
I) ij. > 0 » т.е. Г є Іа.а^З ;
2)^<0 , т.е. 1*е[х,,1];
3)3U{u,...,ib}:j.
Определим функции G(oc) и $00 следующим образом (см. рис. I.I)
/И (х-О +^ , осе[>^?]
''max fmfr-xj-f-^, М (х-О) , хе а.Л, >6 3
ГХ) =
і =НД,...7/г-1
Зависимость функций QM и ac) от значений 4^,4% , .*#*. не УК&" зывается для простоты записи.
2,
Рис. I.I.
22.
Функции Gcx) и $(5с) монотонны. Справедливы неравенства
Отсюда следует,, что корень 1* функции J- лежит на отрезке L"fc^,"t^], где "Ь^и "г - корни функций QO) и ^(^соответственно. Отрезок С^іт^^І есть наименьший среди всех заведомо содержащих точку Ґ отрезков, которые можно построить по имеющейся информации. Примем в качестве критерия эффективности алгоритмов длину этого отрезка и будем использовать для нее обозначение
(Xa,f).
Введем теперь ряд обозначений:
H<4) = {*g f\ ico= Ъ*о,{(*Л-ъ+1 >o,
t — 7 j /^^... у 'і' 'I
Отметим, что имеют место соотношения
/7 = (/ F / rє f*. ,^ J^ t = У, 2,..., /1-і.
23.
Пусть Ге<г,х,]# Тогда t и t , а, следовательно, и
зависят только от а^ и от ^ * /() » поэтому будем
в этом случае использовать для (Х ,f) обозначение ^C^uf)
Аналогично будем использовать для обозначение (xn>f)
во; второй ситуации (гє [х.лу 12) и обозначение -(х С > ^,-f) в
третьей (г є 1^., xc+fl). Имеет место соотношение Sup (ХЛ,) = шл f Sup С*іЛ), Su? &*>),
ггъасс su-p EC^cJyi-)}. (I.I)
Введем обозначения
Тогда соотношение (I.I) принимает вид
Є(Х^ = тлж{^ДГх,Д *кг^ Є.(ХІ9сІ)}я (1.2)
^ = ^э=/ 7 эс э.,,з эс^") оптимальной, если
где минимум берется по всевозможным стратегиям А Введем обозначение
Рассмотрим первую ситуацию. Справедливо соотношение
24.
6(^)- Suf> (3cf7f) = sup sup ЄС*-І9-р)~
Нетрудно) показать, что справедливо соотношение
^ , при о^у^т^-л)
/х-a,--^, при ^г б^-^^^^-л), причем для ^ ~Уп(эСу—а,) имеет место неравенство
Таким образом, получено соотношение
- EC~i,y;) - Г^-л,)^-а)//И. (1.3)
Для второй ситуации аналогичные выкладки приводят к соотношению
Z(zc. ) = гпа.эс (*„,) ^(4t-t*)(
/в/к
Теперь рассштрим третью ситуацию. Введем обозначение
Имеет место соотношение
С-'
Рассмотрим функции Gfc) и ^^) на отрезке ^с уОСІН~^ :
G(Toc)= ^:^ ^-^)^,^^^)+^^
25.
(см. рис. 1.2, прямая4!) наклоном /И и прямая 3 с наклоном т образуют график функции G(x.) , прямая 2 с наклоном т и прямая 4 с наклоном М образуют график функции 9(^-) ).
Рис. 1.2. Обозначим через W1 и W^ абсциссы точек излома функций (*) и ^(зс) соответственно. Для определения wf имеем уравнение
откуда нетрудно: получить выражения
W, -
fry г -Jj + Мхс - в**?**
М — т.
1 М-т-
Дяя определения U^_ имеем уравнение откуда нетрудно получить выражения
9(4) -
М-Лг
26.
Имеет место одна из следущих четырех возможностей.
I)G{Vr)^ 0 , 4(w^)^ 0 . Прямая 3 пересекает ось абсцисс в точке "Ц , прямая 4 пересекает ось абсцисс в точке "t^ .
2) G(Wf)^. О » я(\аі^^ 0 (как на рис. 1.2). Прямая I пересекает ось абсцисс; в точке -Ь , прямая 4 пересекает ось абсцисс в точке
B)G(w1)^ 0 , 4-().^ О Прямая I пересекает ось абсцисс в
точке -tj , прямая 2 пересекает ось абсцисс в точке -Ь^ .
4) Gttvii)-^ 0 t Ыь)^ 0 Прямая 3 пересекает ось абсцисс в
точке ~Ь, , прямая 2 пересекает ось абсцисс в точке ~Ь^
Рассмотрим первый из указанных четырех случаев. Используя ранее введенные обозначения с(-х. ~ос> ,-/. = у. — ^. , получаем
следующие неравенства
Введем обозначение
Тогда справедливо неравенство
»h1 * Lai).
Кроме того, имеет место неравенство
Легко видеть, что для 4. —Мууі4/(М+иг) имеет место неравенство
27.
\/ІеЦ = [mJ/z, МЛ/ъ],
Таким образом, справедлива цепочка соотношений
^'^) - hbaoc(azL,Jy-) = /%.ах. («х. с/Д) =
- (M~to)cl/(M + to) = f/W-*0fc.,-^-)/7^+^). CI.5J
Рассмотрим теперь второй случай (<5 W& "" *%+/ +>»MJ^ о. Подставляя 4., .^Ці+l-L , получим МО*с!-К) ^ ^ tn(ZA-MJ) Для разрешимости полученной системы двух неравенств необходимо выполнение неравенства откуда следует соотношение -ft, 2 Mmd /(М + ^), 28. Нетрудно показать, что при А = тШ/'(М+тп) имеет место неравенство Таким образом, справедливы соотношения = (M-hi)(*c+1 -зс^/СМ + н,). (1.6) Рассмотрение третьего случая проводится аналогично рассмотрению первого и приводит к соотношениям (1.5). Рассмотрение четвертого случая проводится аналогично рассмотрению второго и приводит к соотношениям (1.6). Учитывая соотношения (1.2) - (1.6), получаем Исходя из соотношения (1.7) и применяя принцип уравнивания 9, теорема ХХХУТ], получаем для оптимальной стратегии X ^. следующие соотношения Отсюда видно, что в оптимальной стратегии точки распределены на отрезке [(1,4] равномерно, т.е. величинах, — осі*' одинакова для І-Іі17,.,7ґі-І Точки распределены симметрично относительно середины отрезка L&?] , т.е. о:*-л, ~4—ос^ . Наконец, 29. име- ет место соотношение С + 1 ь» ' Из соотношений (1.8) получаем выражение для оптимальной стратегии 'L+i ~ ОС-;, j — ОС. + + i)M +(n-i)ht у і - 1/^3-7^1 *- При этом справедливо соотношение 2. ОБШШЬНЫЙ ПО КРИТЕРИЮ "НЕВЯЗКА" АЛГОРИТМ ПОИСКА КОРШ М0Б0Т0НШЙ ФУНКЦИИ Будем рассматривать сформулированную в I задачу пассивного поиска корня монотонной функции на отрезке C^7^J . Введем функциональный класс F^ {i& F I -fO-> \ , i= 1-2,..., к}. Введем функцию ^удем предполагать, что вектор У - допустим, т.е. класс г не пуст. Поскольку справедливо неравенство зо, п. jjCx)* fCzb^ <*(*), V^ta-jth V<= F, то верно и неравенство Так как через каждую точку множества {"^лб^ ^jC^^ty^GCsOj проходит график хотя бы одной функции из класса F , имеет место соотношение Обозначим через "Ь точку отрезка [~Ц .,4:^1^ для которой Нетрудно видеть, что Sup /-f(4*)J = mw ^/з l-f(^)l, Введем обозначение t'ftVbmut Vx»)-mtn. *«*ty&l,lGC**l}. Величина (xn, V1^ зс) есть абсолютная величина значения "наихуд-шей" (для точки х ) функции из класса г и имеет смысл "невязки". Величина есть минимальное на отрезке /#, С7 среди зна- чений "невязки" для "наихудших функций из класса F . Ясно также, что Поскольку о функции -f известно только, что она принадлежит классу F" , за погрешность решения задачи отыскания корня, гарантированную v и* алгоритмом а приходится принять величину ЗІ. где верхняя грань берется по множеству всех допустимых У . Введем обозначение -f ^Х J = Y Нетрудно видеть, что ^(X^^su? '(x^-f(x*)) = SL l(x*Wn))s= Будем называть стратегию л^ оптимальной, если где минимум берется по множеству всех стратегий X . В результате вычисления Чі^Ч^ ..,,^ имеет место одна из следующих трех ситуаций: 1)уу >0 (следовательно, $L> о ,/=2,..., #. ), ГєС<г,ос,У; z^n.^ (следовательно, %с<0 ,С** 1,1,...,*-/)> Г &л^,{]; Рассмотрим первый случай. Будем использовать введенные в I обозначения Y0 »^^/)7^ Рассмотрим на отрезке У-С1*-,^^ функции l(X^Yloc) e ^газс { I jC=Ol , I GOO)}. На рис. 2,1 функции Gc=0 соответствует ломаная aCDE f функ-ции J(=0 - прямая FE , функции ^ҐХ^У^х) - ломаная KB CD Ё . Будем далее обозначать (X ->Y о^) через <.Сз:11^1,х) f поскольку нас интересует лишь поведение "f на отрезке C^-^i]» Будем 32. Рис. 2.1. 1...vi . .*- также использовать для (X ,У?х) обозначение 0*f,/*,}, as) , Для любой функции -f из класса ^ ^) имеет место неравенство поэтому справедливо и неравенство hxux ifC^l^^Coc ^) і тій- ІС*і^ь^). Обозначим через с абсциссу точки пересечения линий М х-л,) и I <1(ъ)\ , а через IV - абсциссу точки пересечения линий 1$0О| и Ч\±їуі(зс-^і) (см* Рис» 2.1). Взаимное расположение точек Ь и W 33. позволяет определить х - точку, где достигается минимальное на отрезке *] значение функции 'С^Р(у/:,сь). Рис. 2.1 поясняет справедливость соотношения **'*' " j/?*,, у,,*) . / J Выразив из двух последних уравнений "Ь ъ. W % получим в случае -fc -s w неравенство Нетрудно получить соотношение І(*і,Уі) - lfM\ -= (М-м)ц, /(М+т). Из двух последних соотношений вытекает неравенство Є'С^йтаьІ^ф) * ^^ (ос,-а) <2Л> где fa Є ( 0} M(M+n$(xf -л) /f3M-h*)]. Рассмотрение случая ~h>W приводит к неравенству fa^m±*l (*<-а.\ Нетрудно получить соотношение Из двух последних соотношений имеем 34. Є (х,)-= тах (а:{ф)^ 1-L (^-а,)? (2.2) #* о М — /п- Объединив (2.1) и (2.2), получаем неравенство где Уі єіо~ (7 M(xf-a)J , т.е. максимум берется по всем допустимым значениям yf Отметим еще, что для каждой функции / из класса F , такой что tW- —гг; ^1-^, Неравенство (2.3) превращается в точное равенство. Таким образом справедливы соотношения Z (ас,) == m.«.ac Zl(^i , -fC^ii)- yf6Vi 3^/^ <*> ^- (2.4) Перейдем к рассмотрению второго случая ^Л ^ tf) . Корень Г функции - содержится в отрезке tJ^E^St^J В этом случае будем использовать для -(X 7У , :t) обозначения < (хп, %п? ^) и (хп,т(х*ь7"х) Будем также использовать введенные в I обоз- начения Y^ , Fk(fyi) * ^п. Введем обозначения 35. fcV^-fCxJW Шеи. г.](ос^^{(^^)у^) } ^(эс^й Sup Z'f^s-ffrj), Рассуждения, аналогичные рассувдениям, проведенным для случая ух>0, приводят к соотношениям *„е^ ^») ^ /И^) ^-^) (2.5) Перейдем, наконец, к рассмотрению третьего случая ( и. -^ 0 > ^+1 у 0 , корень Г функции -f- лежит на отрезке йй[^. t-x.. 1 ) ФУНКЦИИ Qfat) И %С^) ИМеЮТ ВИД Как и ранее, положим Будем использовать введенные в I обозначения ъ, , А/ , Г/ Положим Такое обозначение можно мотивировать тем, что по величинам ^6-, с/ , ^ , ^ функции б^е) , 3^) » ^ ^^ 7 ^ г^ на интересующем 36. нас отрезке й = [ссс,ozc+i J строятся однозначно. Введем также обозначения Справедливо неравенство Рассмотрим рис. 2.2. Функции Gc*0 соответствует ломаная 4CD, функции $ґх) - ломаная AED , функции (X 7У,эс)~ ломаная FBCJ> # введем обозначение Рис. 2.2. (2.6) Рисунки 2.2, 2.3, 2.4 поясняют тот факт, что верхняя грань в (2.6) достигается для такой функции { Є ^.(4,) , для которой имеют место соотношения 37. c+l Рис. 2.3. Рис. 2.4. Предположим, что эти соотношения выполнены. Обозначим через ІГ абсциссу точки пересечения прямых ij{_+ МОх-^О и ^+14- YY\ (зс-Dd^^j Из рис. 2.4 видно, что точкой минимума функции Е-'о^^А^) является середина отрезка D*^ v^c+i] , которая является также абсциссой точки пересечения графиков функций Gtf») и (jC^)| . Если 38. точка *t лежит правее середины отрезка D , то Q(»0 и І9(=о| имеют наклон в точке своего пересечения М и -/И соответственно. В противном случае Q(=c) имеет (в точке пересечения с l^caoj ) наклон Иг , a 1^(=^)1 - наклон - Иг . Для вычисления -Ь имеем уравнение Выразив из этого уравнения ~t , получим для случая Ь С*с+1 + ocll ) /% неравенство Имеем для С» с і J, -) очевидное равенство из которого с учетом последнего неравенства получаем '<><> <Ы) ^ (M-m)J/4. (2.7) Рассмотрение случая -6^.( + зс^)/я, приводит к неравенству -ft. s& CM-H^)d/4. Для C^L)^/4^) имеет место очевидное равенство из которого с учетом последнего неравенства получаем '(^,J,-i)^CA-tn)j/4. (2.8) Объединив неравенства (2.7) и (2.8), имеем dC^A-O < Введем обозначение 39. Нетрудно показать, что при lL=(M+fn)ct/4 неравенство (2,9) обращается в точное равенство, поэтому справедливо соотношение г'^,«0=г 0*/-*)f*Vf-*dO/4. (2-ю) Таким образом, показана справедливость следующей цепочки соотношений Sup ^(У^МГ)) = SuP wi*. eYx* #*"), *) = -a fnaac ma* />ьсЯ f^,^,/V=ct*)7 ^ зс)— = ^,^-^-^)^-^0/4. Объединив выражения (2.4), (2.5) и (2.10), /«-/,2,..., и.-/ , можем записать следующее соотношение ? — w#x} гпаэс 3M~tn > ЗМ-М >і4І4Л_± * J.(2.II) Исходя из соотношения (2.II) и используя принцип уравнивания 9Г теорема ХХХУІ], получаем для оптимальной стратегии л # следующие, соотношения ЗМ -^ "" ЗМ-м, = С ^К ^у -: /_у о л у (2.12) 40. Отсюда видно, что в оптимальной стратегии точки распределены на отрезке L^-ej равномерно, те. величины эс>г ~DCLi одинаковы для I -=Н, 2., ..., м - і # Точки распределены симметрично относительно середины отрезка L-,^ , т.е. оср'-а, =4-эс* . Кроме того имеет место соотношение Из соотношений (.2.12) нетрудно получить выражение для оптималь- ной стратегии -к- ЗМ — Иг, осж = ел а-*), *- *" 1М(4-<ії (2.13) При этом справедливо соотношение ; ^///^)=- ^^-^)^-^- (2.14) Сравнивая выражения (1.9) - (1.10) с выражениями (2.13) - (2.14), можно убедиться, что алгоритм, оптимальный по критерию не является оптимальным по критерию и наоборот. Это вызвано тем, что функции "наихудшие" по одному критерию, по другому критерию таковыми не являются. Дня некоторых функциональных классов (например, для класса функций, удовлетворяющих условию Липшица, см. [ill) алгоритмы, оптимальные по критерию , оптимальны и по критерию и наоборот. Таким образом, критерии и не всегда "эквивалентны". Отметим еще, что в обоих рассмотренных случаях в оптимальной пассивной стратегии точки распределены на отрезке Со-,] равномерно. Это характерно не только для оптимальных пассивных стратегий поиска корня, но и для оптимальных пассивных стратегий поиска экстре- 41. мума (см., например, [7], [г?]). Найденные в I и 2 оптимальные алгоритмы можно использовать в расчетах на ЭШ, когда имеется возможность одновременно вычислять несколько значений функции (например, в случае распараллеливания вычислений на многопроцессорной ЭШ) 42. Любой стохастический последовательный алгоритм предписывающий на каждом шаге выбирать точку вычисления значения функции в соответствии с вероятностным распределением, удовлетворяющим на текущем отрезке локализации корня перечисленным четырем условиям, будет оптимальным на один шаг на классе L стохастическим алгоритмом. Интересно отметить, что для задачи поиска экстремума функции, удовлетворяющей на отрезке условию Липшица, существует единственный оптимальный на один шаг стохастический алгоритм (см.І20І). В четвертой главе предложен алгоритм численного решения системы нелинейных уравнений. Идея заключается в сведении задачи решения системы нелинейных уравнений к задаче минимизации некоторого функционала, для которого известно минимальное значение - ноль. Рассмотрим систему нелинейных уравнений Предположим, что заданы два вектора ( -/, 49 ... лО у Предположим, что в пространстве R задана метрика fQ -, ) . Определим невязку - функцию Будем предполагать, что функции yi(= , С = 1,2,..., ft , удовлетворяют в параллелепипеде Р условию Липшица с константой /И , тогда и невязка удовлетворяет в Р условию Липшица с константой М , т.е. Пусть заданы натуральные числа Ynioтг,-7 и. » тс , L -(,2 ,..., К. . Построим в параллелепипеде Р сетку Т , равномерную по каждой координате. Шаг сетки Т по L -ой координате определяется формулой 1 С -л{) /YmL -f) , L= 1,2,..., Vb . Построенная в параллелепипеде Р сетка Т содержит tv\.t-iw2 ... kvt узлов. Обозначим через S множество всех узлов сетки Т , в которых невязка еще не вычислялась. Перед началом работы алгоритма множество содержит все узлы сетки "Г . Случайным образом выберем xf6 S и вычислим yC i ) . При ЧС -О 0 решение системы (В.6) найдено. Предположим, что Ч. (ос т 0 . Пусть 2 6- Р и удовлетворяет неравенству тогда из условия Липшица получаем . не может содержать решение системы (В.6). Поскольку для каждого узла =S ft Ui значение невязки заведомо положительно, исключим все такие узлы из рассмотрения, т.е. положим = \(р П$). Если после этого исключения & не пусто, выбираем случайным образом 2 е , вычисляем ftf z) При у6 х) 0 находим множество и полагаем $ : = \ffliz). Если после этого исключения множество S не пусто, выбираем случайным образом - 3 е S и т.д. Поскольку сетка Г содержит конечное число узлов и на каждом шаге описанной процедуры из множества S исключается хотя бы один узел, процесс закончится через конечное число шагов. Как только множество стало пустым, производится просмотр всех вычисленных значений невязки, соответствующий минимальному из этих значений узел ос выбирается в качестве приближения к решению системы (В.6). Затем происходит уточнение решения при помощи локально сходящегося итерационного метода ньютоновского типа (являющегося модификацией метода, предложенного и обоснованного в 27]) В 9 приведен ряд примеров тестирования алгоритма, которые показывают, что во многих случаях предварительный подбор "хорошего" приближения для работы итерационного метода позволяет сократить затраты вычислительных ресурсов, что может оказаться немаловажным в случаях, когда вычисление левой части системы связано с большим объемом вычислений или дорогостоящими экспериментами. В 10 приводятся результаты расчета сложного технического объекта (двигателя самолета) при помощи предложенного алгоритма решения системы нелинейных уравнений. Полученные результаты вполне устроили конструкторов. Результаты диссертации опубликованы в работах зультаты докладывались на конференции молодых ученых факультета ШиК МГУ (г.Москва, 1982 г.), на заседании научно-исследовательского семинара кафедры исследования операций факультета ВМиК МГУ в 1983 г Разработанный алгоритм численного решения системы нелинейных уравнений нашел применение на МЗ им. П.О.Сухого, в Иркутском ВЦ СО АН СССР, а также включен в общую библиотеку программ системы Коллективного Пользования ЭВМ МГУ и в ГосФАП СССР. Автор считает своим приятным долгом выразить искреннюю благодарность своему научному руководителю доценту АІГ. Сухареву за помощь в постановке задач, постоянное внимание, полезные советы и поддержку в течение всего времени работы над диссертацией, а также сотруднику ВЦ АН СССР А.НДукову за помощь в постановке задачи расчета сложного технического объекта и многочисленные ценные советы, способствовавшие успешному выполнению этой задачи. В соотношении (4.9) уже при ru = {О имеем «х. 30» . Таким образом, из соотношений (4.8), (4.9) видно, что при таком выборе количества вычислений уменьшение погрешности примерно в два раза (от t до в ) требует увеличения затрат вычислительных ресурсов в эе » % раз, т.е. такой выбор гь явно неэффективен. Аналогичные соображения позволяют утверждать, что невыгоден выбор из условия с(и =с /тт- с І/оІи, . Выберем теперь гъ из условия Из (4.6) следует, что в этом случае вычислительные ресурсы необходимо распределить на ҐЬ вычислений равномерно; это гарантирует погрешность решения задачи не хуже чем При ггъ и. точность решения задачи при т. вычислениях и фиксированном "17" есть JLm/T/ , т.е. хуже, чем -2л./17". Таким образом, выбор ҐІ из условия (4.10) оптимален (эффективен). При этом из соотношений (4.5), (4.6) вытекает, что вычислительные ресурсы необходимо распределить на ҐЬ вычислений равномерно, т.е. тогда выполнены соотношения причем справедливо равенство Это показывает, что если на І -ом шаге поиска оказалось, что I U то такая ситуация является благоприятной, поскольку при этом оказывается достигнутой точность решения задачи 2 , совпадающая с гарантированной точностью решения задачи за УЬ шагов. Тем самым оправдано сделанное в 3 допущение, предписывающее при д считать Х корнем и прекращать вычисления, поскольку гарантировать улучшение уже полученного результата за оставшиеся П.- Z вычислений нельзя. Разумеется, выбранное из условия (4.10) оптимальное количество вычислений ҐІ может оказаться не целым числом. В таком случае можно, например, произвести L l вычислений, израсходовав количество W f/d -. вычислительных ресурсов С W t7 . При этом считается, что лучше не использовать часть ресурсов, чем истратить их неэффективно (т.е. так, что увеличение затрат в Э 1 раз вызывает уменьшение погрешности в о( і раз, причем С -О Сэе 0). Замечание 4.1. Итак, установлено правило оптимального выбора количества вычислений значения функций при заданных вычислительных ресурсах. При этом оптимальным оказывается равномерное распределение ресурсов. Этот вывод представляется далеко не очевидным (см. Замечание 3.3). Полученный результат может найти применение при написании подпрограмм численного решения уравнений для ЭШ. Разумно применять такую подпрограмму, например, в случае, когда значение функции вычисляется в результате работы некоторой программы на ЭВМ, причем точность вычисления задается вычислителем. Замечание 4.2. Можно поставить задачу построения последовательно-оптимальных на классе L алгоритмов поиска корня по критерию эффективности "длина отрезка локализации" корня. Однако эта задача оказывается тривиальной. Любая стратегия X (х19 .,ух ) является последовательно-оптимальной и гарантирует результат (4 —ее) , так как класс L содержит такую функцию -f , что lfCx:)\ $ . , Таким образом, даже сколь угодно большое конечное количество вычислений значения функции может не принести информации, позволяющей указать отрезок длины локализации корня функции -f , меньший чем L L?4 3 . Пусть заданы отрезок Г , ] , натуральное число П и числа о(0 , о » » » такие, что &= o(0 ocA ct.x „, roi =4. Введем обозначения Пусть требуется приближенно определить корень функции -f , если относительно - известно только то, что она принадлежит классу U . Считается, что значения функции -f могут быть вычислены в п. произвольных точках из Э , причем вычисления происходят без ошибок. Предполагается, что вычисления осуществляются последовательно, т.е. при выборе точки 3 используется информация, полученная в результате предыдущих вычислений. Дудем называть вектор XL =(x1 -хп ...„эеЛ допустимым, если з ї,/-1Д,..., І .Вектор Zl=CxWl) = ,... , , ,..., ) называется реализуемым, если вектор X - допустимый и существует функция f е L такая, что Введем обозначение Рассмотрим совокупность И функций, принимающих значения из D , X = б / 0 ,—,Л:Л)» причем х, есть фиксированный элемент »у из множества t/ , а т.е. первая из этих функций постоянна, а областью определения функции t+f является множество всех реализуемых векторов 2Z , і =Н, 2.,..., И.-I . Будем называть такие совокупности последовательными алгоритмами (последовательными стратегиями) поиска корня. Мно-жество всех алгоритмов обозначим через К . Последнее неравенство можно переписать в виде откуда вытекает, что всякий стохастический алгоритм, предписывающий выбирать первую точку вычисления значения функции в соответствии с равномерным вероятностным распределением Т. на D , опти-мале на классе функций L на первом шаге и гарантирует среднюю точность решения задачи не хуже, чем М/& (как видно из (7.2), оптимальный детерминированный поиск гарантирует лишь точность М/б ). Аналогичные рассуждения можно провести, взяв вместо отрезка [оД] произвольный отрезок а,&] . Оптимален выбор первой точки в соответствии с равномерным распределением вероятностей на отрезке [Ajf] ; такой выбор гарантирует среднюю точность решения задачи не хуже, чем Выше показано, что выбор первой точки в соответствии с равномерным вероятностным распределением на 3 оптимален. Пусть точка Л:. выбрана именно таким образом и J 0 . Так же, как и ранее, определим отрезок f= L 1 7 1 Корень каждой функции -р- из класса L (2 ) лежит на этом отрезке. Возникает задача оптимального стохастического выбора на отрезке второй точки вычисления значения функции. При этом относительно -f- известно, что т.е. сохраняется постановка задачи об оптимальном стохастическом выборе первой точки вычисления значения функции, удовлетворяющей условию Липшица на отрезке (только вместо отрезка 3 теперь рассматривается отрезок [ iJj) Поэтому сохраняют силу все проведенные выше рассуждения, позволившие найти оптимальный способ стохастического выбора первой точки. Таким образом, выбор второй точки в соответствии с равномерным вероятностным распределением на 31 оптимален и гарантирует среднюю точность решения задачи не хуже, чем М ( -(1 / . Аналогично осуществляется выбор третьей точки и т.д. Опишем оптимальный на один шаг на классе L стохастический алгоритм поиска корня. Первая точка выбирается в соответствии с равномерным вероятностным распределением на 3 . При fC0 ) фО определяется (согласно указанным выше правилам) tL - новый отрезок локализации корня. Затем в соответствии с равномерным вероятностным распределением на 3 выбирается сс . При f(?c \zfz О определяется J, - очередной отрезок локализации корня. В соответствии с равномерным вероятностным распределением на 0 выбирается и т.д. Описанный алгоритм легко реализовать на ЭВМ, так как стандартные подпрограммы - датчики псевдослучайных чисел с равномерным рао пределением имеются во всех пакетах стандартных подпрограмм. При рассмотрении последовательно-оптимального на классе L поиска корня функции (глава 2) был построен последовательно-оптимальный алгоритм, причем из построения вытекает его единственность. Оказывается, что существует бесконечно много оптимальных на один шаг на классе L стохастических алгоритмов поиска корня. Укажем некоторые из таких алгоритмов. Зудем рассматривать симметричные вероятностные распределения, имеющие непрерывную плотность. Зафиксируем такое распределение 6 , плотность его обозначим через р(=с) . Зафиксируем е[о,/И/з] . Справедливо соотношение (см.рис. 8.1) Отметим еще, что использованный итерационный метод не требует от вычислителя написания подпрограммы для вычисления значений частных производных и требует на одну итерацию (иЛ + Ьк ) /% вычислений значения левой части системы (9,1). Существующие стандартные подпрограммы метода Ньютона предполагают написание вычислителем подпрограммы вычисления частных производных и требуют ь г + п. вычислений значения левой части на одну итерацию» При подборе "хорошего" приближения важную роль играет знание вычислителем константы Липшица М для невязки. Но априорная оценка для М известна далеко не всегда, поэтому в реализующую описанный алгоритм подпрограмму был введен блок адаптивной оценки константы Липшица для невязки. Вычислитель задает целое положительное число N 2, . Программа случайным образом выбирает на сетке узлы затем вычисляются значения невязки по которым определяется величина где о 5; і есть некоторый "коэффициент осторожности" задаваемый вычислителем. При дальнейших вселеннях величина М использует ся в качестве константы Липшица для невязки. Далее алгоритм работает согласно приведенному выше описанию: подбирается "хорошее" приближение, а затем происходит его локальное уточнение. Подбор хорошего приближения имеет важное значение, так как все методы ньютоновского типа имеют лишь локальную сходимость, и при неудачно выбранном начальном приближении для достижения требуемой точности может потребоваться очень много итераций. Нередки случаи, когда метод вообще расходится (происходит неограниченное возрастание нормы текущего приближения к решению, приводящее к переполнению). Кроме того, если вычисление значения левой части сиетемы (9.1) обходится дорого (например, вычисляется в результате работы некоторой программы ЭВМ, выполнение которой требует больших затрат ресурсов ЭВМ - ситуация, типичная для задач проектирования сложных технических объектов), то предварительный подбор "хорошего" приближения может существенно уменьшить общие затраты вычислительных ресурсов. Проиллюстрируем сказанное примерами. имеющую единственное решение ( 4,0 . Сначала было задано на-чальное приближение (&,б) и применен итерационный метод, при этом для нахождения решения потребовалось 43 итерации (всего было сделано 215 вычислений значения левой части системы (9.6)). Та же система решалась с предварительным подбором начального приближения. Поиск велся на прямоугольнике -5",40J , в котором была построена сетка Г с шагом 0.5 по каждой координате, содержащая 961 узел. а) При М = 1 было сделано 9 вычислений невязки в узлах сетки, найдено начальное приближение С -5,3) . Итерационный метод сошелся к решению за 36 итераций, т.е. всего было сделано 189 вычислений левой части. в) При №= было сделано 8 вычислений невязки, найдено приближение Г-5"-ИУ1", итерационный метод сошелся за 16 итераций (всего 88 вычислений левой части). с) При М = было сделано 8 вычислений невязки, найдено прибли-жение (-5,-1.5) f итерационный метод сошелся за 6 итераций (всего 38 вычислений левой части). Та же система решалась на прямоугольнике L 6,3j 9 в котором 115, была построена сетка 1 с шагом 0.5 по каждой координате, содержащая 961 узел. d ) При М = і было сделано 9 вычислений невязки, найдено приближение ( Ъ?&,5) , итерационный метод сошелся за 9 итераций (всего 54 вычисления левой части). Пример 2. Система (9.6) решалась с адаптивным определением константы Липшица. Сначала решение искалось в прямоугольнике L l по сетке Tj . Мл-40 # Было сделано три запуска программы пфяд. а) Сделано 32 вычисления невязки, для М получено значение 137,75. Найдено приближение (-4,0 , совпадающее с решением системы (9.6). Итерационный метод сошелся за I итерацию (всего 37 вычислений левой части). в) Сделано 22 вычисления невязки, М = 32.65625, найдено приб лижение (-5УЦ-) , метод сошелся за 5 итераций (всего 47 вычислений левой части). с) сделано 28 вычислений невязки, М = 64.35, найдено приближение Г-з.в, І.5У , метод сошелся за 5 итераций (всего 53 вычисления левой части). Для прямоугольника -6,э] и сетки Т при N = 10 численные эксперименты дали следующие результаты (вновь было сделано подряд три запуска программы). d ) Сделано 200 вычислений невязки, М = 284.75, найдено приближение f — Ч- 71 , совпадающее с решением системы (9.6), метод сошелся за I итерацию (всего 205 вычислений левой части). е) Сделано 43 вычисления невязки, М = 207.25, найдено приближение (- f ,l)T» метод сошелся за I итерацию (а всего 48 вычислений левой части).
Таким образом, во втором случае областью изменения п. является от
резок Имеем соотношения
- 1Ь»Ь fa* - а) =г (Я-to) (*-*>) (I#I0)
V*r) ^*«« г'г^О ^ Щг^ С*,-*, (2.3)Оптимальный по критерию "длина отрезка локализации корня" алгоритм поиска корня монотонной функции
Оптимальный выбор количества вычислений значения функции и оптимальное распределение вычислительных ресурсов
Оптимальный стохастический выбор первой точки
Пример расчета сложного технического объекта
Похожие диссертации на Минимаксные алгоритмы решения некоторых классов уравнений и систем уравнений
