Разработка компьютерного лабораторного практикума "Теория оптимизации и численные методы" (стр. 3 из 12)
1.1.3 Метод покоординатного спуска
Алгоритм метода:
здесь:
·
- проекция на ось 
антиградиента функции·
- шаг выбирается из условия убывания функции в точках последовательности: 
Геометрическая интерпретация метода
Рисунок 1.5. Геометрическая интерпретация метода
Основной критерий окончания метода:
Начальные параметры метода:
Изменяемые параметры метода: величина шага
и направление проекции антиградиента (здесь абсциссы – ось 
, ординаты – ось 
)Особенности реализации алгоритма. Вопрос о величине шага на каждой итерации решается пользователем, причем шаг может быть, как уменьшен, если не выполняется условие
, так и увеличен, если скорость сходимости алгоритма невысока (по субъективной оценке пользователя). Вопрос о выборе направления оси для проекции антиградиента, также решается пользователем на каждой итерации.1.1.4 Метод Гаусса-Зейделя (наискорейшего покоординатного спуска)
Алгоритм метода:
здесь:
- проекция на ось 
антиградиента функции·
- шаг вычисляется из условия наибольшего убывания функции в точках последовательности: 
Геометрическая интерпретация метода
Рисунок 1.6. Геометрическая интерпретация метода
Основной критерий окончания метода:
Начальные параметры метода:
.Изменяемые параметры метода: отрезок для уточнения шага
.Особенности реализации алгоритма. Задача о поиске оптимального шага
(задача 
) решается численно методом дихотомии на отрезке 
с заданной точностью 
. Вопрос о границах отрезка 
на каждой итерации решается пользователем. Направление проекции градиента меняется циклически: сначала спуск в направлении оси абсцисс, затем – ординат и т.д.Рекомендации по выбору параметров метода. Отрезок
задается из тех же соображений, что и в методе наискорейшего спуска.1.1.5 Метод сопряженных градиентов
Алгоритм метода:
здесь:
·
·
·
·
- шаг вычисляется из условия наибольшего убывания функции в точках последовательности:
Геометрическая интерпретация метода
Рисунок 1.7. Геометрическая интерпретация метода
Согласно алгоритму, первая итерация метода сопряженных градиентов совпадает с первой итерацией метода наискорейшего спуска.
Вычисление величины
по формуле (5.4) обеспечивает для квадратичных функций построение последовательности H-сопряженных направлений 
, для которых 
. При этом в точках последовательности 
градиенты функции 
взаимно перпендикулярны, т.е. 
Основной критерий окончания метода:
Начальные параметры метода:
Изменяемые параметры метода: отрезок для уточнения шага
.Особенности реализации алгоритма. Задача о поиске оптимального шага
(задача 
) решается численно методом дихотомии на отрезке с заданной точностью . Вопрос о границах отрезка 
на каждой итерации решается пользователем.Замечание. Т.к. шаг
на каждой итерации вычисляется численно с точностью , за счет накопления ошибки, метод сопряженных градиентов в отдельных случаях может сходиться для квадратичной функции за число итераций, превышающее число переменных.Рекомендации по выбору параметров метода.
Отрезок
задается из тех же соображений, что и в методе наискорейшего спуска.1.1.6 Метод Ньютона
Алгоритм метода:
здесь:
·
- направление спуска·
Особенностью метода Ньютона является то, что при
метод позволяет отыскать минимум квадратичной функции за одну итерацию.Геометрическая интерпретация метода для квадратичной функции:
Рисунок 1.8. Геометрическая интерпретация метода
Для неквадратичной функции метод Ньютона предполагает построение последовательности минимумов аппроксимирующих квадратичных функций
. 
Рисунок 1.9. Последовательность минимумов
Основной критерий окончания метода:
Начальные параметры метода:
1.1.7 Метод Ньютона-Рафсона
Алгоритм метода:
здесь:
·
- направление спуска·
- шаг выбирается из условия убывания функции в точках последовательности: 
.Геометрическая интерпретация метода для квадратичной функции:
Рисунок 1.10. Геометрическая интерпретация метода
Основной критерий окончания метода:
Начальные параметры метода:
.Изменяемый параметр метода: величина шага
