Оптимизация численных алгоритмов

• Автор: Михеев, Сергей Евгеньевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2006
• Место защиты: Санкт-Петербург
• Количество страниц: 269 с. : ил.

Глава 1.

ОБЩИЕ ВОПРОСЫ

НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Глава 2.

РЕЛАКСАЦИОННОЕ УСКОРЕНИЕ ИТЕРАТИВНЫХ ПРОЦЕССОВ

§2.1. ОПИСАНИЕ ПРИНЦИПА МИНИМАЛЬНОСТИ

§2.2. ТОЧНЫЕ РЕЛАКСАЦИИ

ДЛЯ МЕТОДА ПРОСТЫХ ИТЕРАЦИЙ

§2.3. ТОЧНЫЕ РЕЛАКСАЦИИ

В СКАЛЯРНОМ ПРОСТРАНСТВЕ

§2.4. МНОГОМЕРНЫЙ СЛУЧАЙ (р = 1)

§2.5. ОБОБЩАЮЩАЯ СХЕМА
§2.6. СТАТИСТИЧЕСКИЕ СВОЙСТВА ТОЧНОЙ
РЕЛАКСАЦИИ МЕТОДА ПРОСТОЙ ИТЕРАЦИИ (р — 1)
§2.7. АСИМПТОТИКА ТОЧНОЙ РЕЛАКСАЦИИ
§2.8. НЕЛИНЕЙНАЯ СХОДИМОСТЬ (р> 1)
§2.9. ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ
Глава 3.
ДИФФЕРЕНЦИРОВАНИЕ ПО ИТЕРАЦИИ
§3.1. ПОЛУПРОИЗВОДНАЯ И ЕЕ СВОЙСТВА
§3.2. АНАЛИЗ СХОДИМОСТИ
С ПОМОЩЬЮ ДИФФЕРЕНЦИРОВАНИЯ ПО ИТЕРАЦИИ
Глава 4.
НЕЛИНЕЙНЫЕ УРАВНЕНИЯ
§4.1. СУЩЕСТВОВАНИЕ И ОЦЕНКА РЕШЕНИЯ
НЕЛИНЕЙНОГО УРАВНЕНИЯ
§4.2. СРАВНЕНИЕ С ИЗВЕСТНЫМИ РЕЗУЛЬТАТАМИ
§4.3. СХОДИМОСТЬ МЕТОДА НЬЮТОНА
§4.4. РАСХОДИМОСТЬ МЕТОДА НЬЮТОНА

Глава 5.
МЕТОД КВАДРАТИЧНОЙ ОПТИМИЗАЦИИ (МКО)
§5.1. ОПИСАНИЕ МЕТОДА
§5.2. ЛОКАЛЬНАЯ СХОДИМОСТЬ
§5.3. ПОЛУГЛОБАЛЬНАЯ СХОДИМОСТЬ
§5.4. ВЫБОР НАЧАЛЬНОЙ ТОЧКИ
§5.5. МОДИФИКАЦИИ МЕТОДА
КВАДРАТИЧНОЙ ОПТИМИЗАЦИИ
Глава 6.
КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ
§6.1. РАЗЛИЧНЫЕ ПОДХОДЫ К ПОСТРОЕНИЮ
КВАДРАТИЧНЫХ ПРОГРАММ-АППРОКСИМАЦИЙ ... 154 §6.2. ЛИНЕЙНАЯ ИНТЕРПОЛЯЦИЯ И АППРОКСИМАЦИЯ
§6.3. КВАДРАТИЧНЫЕ АГРЕГАТЫ
§6.4. ВЫБОР УЗЛОВ ИНТЕРПОЛЯЦИИ
§6.5. ВЫПУКЛОСТЬ ЛИНЕЙНО-КВАДРАТИЧНОГО АГРЕГАТА
§6.6. АЛГОРИТМ ТРЕХКООРДИНАТНОГО СПУСКА
§6.7. АЛГОРИТМ ЧАСТИЧНОГО ПРОЕКТИРОВАНИЯ
§6.8. АЛЬТЕРНАТИВНЫЙ ПОДХОД
§6.9. МОДИФИКАЦИЯ МЕТОДА БИЛА
Глава 7.
ДИСКРЕТНЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
И ПОИСКА ЭКСТРЕМУМА
§7.1. ДИСКРЕТНЫЙ МЕТОД ЧЕБЫШЕВА
§7.2. МЕТОД МЮЛЛЕРА
§7.3. ПОИСК ОДНОМЕРНОГО МИНИМУМА
НА ОСНОВЕ п-ТОЧЕЧНОЙ ИНТЕРПОЛЯЦИИ
§7.4. УЧЕТ ПОГРЕШНОСТЕЙ ИЗМЕРЕНИЙ ПРИ МИНИМИЗАЦИИ
МЕТОДОМ ТРЕХТОЧЕЧНОЙ ИНТЕРПОЛЯЦИИ

Глава 8.
МИНИМИЗАЦИЯ НА КОМБИНАТОРНЫХ ПРОСТРАНСТВАХ
§8.1. АЛГОРИТМ СОСТАВЛЕНИЯ РАСПИСАНИЯ
ДЛЯ ОДНОГО СЕМЕЙСТВА ЗАДАЧ ОБСЛУЖИВАНИЯ . 227 §8.2. КОМБИНАЦИОННОЕ ДОЗИРОВАНИЕ
Глава 9.
МИНИМИЗАЦИЯ СЕПАРАБЕЛЬНЫХ ЦЕЛЕВЫХ ФУНКЦИЙ
ЗАКЛЮЧЕНИЕ
Указатель литературы

а для гипотезы II независимо от размерности пространства такая эффективность доставляется формулой (2.52) при п = 1.
Доказательство. Ключевым параметром в предыдущих построениях является величина г = \г - х\, (х — текущее приближение). Найдем ее плотность вероятности, приняв гипотезу I.
Как известно, формула объема Уп п-мерного шара радиусом и> имеет вид К = кпып, а площадь поверхности п-мерной сферы, его ограничивающей, задается формулой <т„ = пкппп~1. Поэтому при равномерном распределении случайной величины г в шаре радиуса р = д + сд и с центром в точке х случайная величина г будет иметь плотность вероятности
Рп(г) = оп(г)/У„(р) = пгп~1/рп, г € [0,р]. (2.53)
Пусть, как и ранее, д+(т) является оценкой погрешности следующего приближения, полученного применением основанной на (2.26) точной релаксации из приближения х, имеющего оценку погрешности д. Из формулы (2.41) извлекаем

:= Г € [0,г],
1 / д*{1 - с2)2 ^2’54^
52(г) := + с2) - г2 - й[1г2С) , г е (Г,р],
где Г = £?(1 - С2)//1 + С2.
Напомним, что максимум функции д„ достижим при г = г и сЦг) = сд.
Непрерывная функция д*(г) строго монотонно растет от 0 до 52(г) = сд на
сегменте [0, г], затем строго монотонно убывает до нуля на сегменте [г, р], где, как и ранее, г = ду/1 - с2 > г.
Таким образом, обратная к с?, функция Ь(д>) := (с/*)-х(го) имеет две ветви: возрастающую: Ь_([0, сс?]) = [0, г] и убывающую: 6+([0, с.д]) = [г, р.
Когда ги < 6х(г) — дс//1 + с2 = ветвь Ь_(го) определяется элементарно: Ь-(ги) = и)(1/с-с). Для определения этой ветви на сегменте [^(г),«^] и ветви 5+ на сегменте [0, сд] разрешим уравнение
относительно г. Возведя его в квадрат и умножив затем на г2, получим биквадратное уравнение, из которого будем иметь
г2 = (1 + с2)сР - 2и)2 ± у/{2д/2 - (1 + с2)й2)2 - #( 1 - с2)2. (2.55)
При га € [0, сд] дискриминант
В(и>) = (2ц>2 - (1 + с2)^2)2 - £?4(1 - с2)2 (2.56)
не отрицателен. И он меньше квадрата выражения
V(и>) = (1 + с2)д2 - 2ггЛ (2.57)
д*(г) = <