Минимаксные алгоритмы решения некоторых классов уравнений и систем уравнений

• Автор: Васильев, Павел Петрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1983
• Место защиты: Москва
• Количество страниц: 131 c. : ил

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

§ I. Оптимальный по критерию "длина отрезка локализации

корня" алгоритм поиска корня монотонной функции

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

корня монотонной функции

Глава II. ПОСЛЕДОВАТЕЛЬГО-ОПТИМАЛЬВЫЙ ПОИСК КОРНЯ ФУНКЦИИ,

УДОВЛЕТВОРЯВДЕЙ УСЛОВИЮ ЛИПШИЦА

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

алгоритм поиска корня

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

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

ресурсов
§ 5. Последовательно-оптимальный алгоритм поиска корня
функции, удовлетворяющей на отрезке условию Липшица с различным значением константы Липшица на разных частях отрезка
Глава III. ОПТИМАЛЬНЫЙ НА ОДИН ШАГ СТОХАСТИЧЕСКИЙ ПОИСК КОРНЯ
ФУНКЦИИ, УДОВЛЕТВОРЯВДЕЙ УСЛОВИЮ ЛИПШИЦА
§ 6. Постановка задачи
§ 7. Оптимальный стохастический выбор первой точки
§ 8. Оптимальные на один шаг стохастические алгоритмы . •
Глава IV. ОДИН АЛГОРИТМ ЧИСЛЕННОГО РЕШЕНИЯ СИСТЕМЫ НЕЛИНЕЙНЫХ
УРАВНЕНИЙ
§ 9. Описание алгоритма и результаты тестирования .... 105 § 10. Пример расчета сложного технического объекта
СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ

В работе используется двойная нумерация формул, теорем, рисунков и таблиц. Первое число означает номер параграфа, второе -номер формулы, утверждения или рисунка внутри параграфа. При нумерации формул во Введении вместо первого числа ставится буква "В", например: (В.1).
Список использованных обозначений.
- равно по определению
Р1 - множество действительных чисел
К0, - п. -мерное координатное пространство
0 - пустое множество
Дв - теоретико-множественная разность множеств А и -В :
АВ- | -Ь € А р “Ь ф В}
[ос] - целая часть числа ос
;= - положить равным: символ из алгоритмического языка МГОЛ, запись Й Й17
означает, что в качестве множества Й далее рассматривается множество Й х Т7"

В последние три десятилетия интенсивно исследуется круг вопросов, связанных с эффективностью вычислительных алгоритмов и построением оптимальных алгоритмов для самых различных задач. Появилось много работ, посвященных построению оптимальных алгоритмов приближенного решения нелинейных уравнений и систем нелинейных уравнений (см., например, £ю] - [13], [17] - [26], [28] - [54]), При этом оптимальность алгоритмов определяется в разных работах неодинаково.
Так, под оптимальным понимают алгоритм, который при заданной информации о функции (например, значения функции и ее производных) имеет наиболее высокий порядок сходимости; требующий наименьших затрат ресурсов ЭШ. Особое место занимает минимаксная концепция оптимальности, основы которой заложил еще П.ЛЛебышев. Согласно этой концепции под оптимальным понимается алгоритм, гарантирующий наименьшую погрешность нахождения корня при применении к "наихудшей" функции из данного функционального класса, либо алгоритм, требующий наименьшего количества вычислений значения "наихудшей" функции для достижения заданной погрешности. Поставленная в рамках минимаксной концепции задача построения оптимальных алгоритмов естественно вписывается в общую схему исследования операций [ 9], Оперирующая сторона -вычислитель выбирает некоторый алгоритм с< поиска корня из множества А допустимых алгоритмов, неконтролируемым фактором является функция ^ , корень которой нужно найти. Обычно относительно -£ известно, что она принадлежит некоторому функциональному классу Р . Задача оперирующей стороны состоит в минимизации погрешности £(*>■$) решения задачи. Руководствуясь принципом гарантированного результата за оценку эффективности алгоритма оС следует цринять величину
£(<хР) = 4.С<*,£).
50.
венства
-1^1+5} «= 0.5] -£гъ< ^ =1,2- п.
Справедливы следующие неравенства
е.-Л., = £^5 &.Г,
I М <2. Л/ ,
^-дг_ й^1!=!:+*.(& г)_гл/.<
2. Л| 2 х ** ' £ -V М ( *■>
м 1 - £«-г
)- 4 — а. г*
* ■+ 1 * 1 +
г'
^ — £
л.-/ /г-г МI Л*'"*'
жО+Ь~+£ъ)- +
-/- (. л. + Л
АЛ V пл-'
Из доказанного ранее вытекает, что после /г. -го шага погрешность решения задачи будет не больше, чем

Используя полученное выше неравенство ДЛЯ —^А-/ » ше“
ем соотношения
М +^^п. 4 Г М{4-а) с 0 2 -/ ,
£ ^ 1Г1~1 1п~1
■>- Ь [■§=, + £я.+- + + &) ] = [_М _
- гЛ + * ± £~'гс ]