Введение 4
Глава 1. О методе сопряженных градиентов 5
1.1. Минимизация квадратичной функции 5
1.2. Общая задача безусловной минимизации 6
1.3. Обновление 6
1.4. Линейный поиск 7
1.5. Параметр сопряженности 10
Глава 2. Сходимость 12
2.1. Условия 12
2.2. Теорема Зойтендейка 12
Глава 3. Численные эксперименты и их анализ 14
3.1. Целевая функция 14
3.2. Численные эксперименты 15
3.3. Анализ результатов 18
Глава 4. Минимизация циклической функции 20
4.1. Неравенство Шапиро 20
4.2. Постановка задачи и метод решения 20
4.3. Начальное приближение 21
4.4. Результаты вычислений 22
Глава 5. Геометрический вариант метода сопряженных градиентов . . 25
5.1. Особенности геометрического варианта 25
5.2. Сходимость 26
Заключение 29
Список литературы 30
Метод сопряженных градиентов применяется для решения задач безусловной минимизации. Метод имеет длительную историю развития, начальный этап которого был подробно описан Голубом и О’Лири в обзорной статье [10].
Первая работа в данной области принадлежит Хестенсу и Штифелю и датируется 1952 годом [1]. В этой работе метод споряженных градиентов применялся для решение систем линейных уравнений. В 1964-м году Флетчер и Ривз [9] в первый использовали метод сопряженных градиентов для минимизации гладких функций.
Развитие метода продолжается и сейчас: разрабатываются новые варианты метода, исследуются вопросы сходимости.
Достоинствами метода сопряженных градиентов являются его простота и низкие затраты памяти, что делает его особенно эффективным при решении задач большой размерности.
В данной работе представлен обзор и сравнение различных вариантов метода сопряженных градиентов. Большое внимание уделяется наиболее эффективным способам осуществления линейного поиска. Исследуются вопросы сходимости. На примере задачи о минимизации циклической функции проверяется эффективность работы метода.
1. В рамках данной работы проведен обзор и численное сравнение различных вариантов метода сопряженных градиентов.
2. С помощью метода сопряженных градиентов решена задача о построении контрпримеров для неравенства Шапиро.
3. Доказана теорема о сходимости геометрического варианта метода сопряженных градиентов при точном линейном поиске.
4. Установлено свойство убывания целевой функции в геометрическом варианте метода сопряженных градиентов при неточном линейном поиске.
Предварительные результаты опубликованы в [8].
