Метод Гаусса-Зейделя (наискорейшего покоординатного спуска).
Стратегия поиска.
Суть метода заключается в эквивалентной замене общей многопараметрической задачи поиска экстремума критерия последовательностью однопараметрических задач поиска частных экстремумов
Стратегия решения задачи состоит в построении последовательности точек ,
k=0, 1, 2, ... таких, что , k=0, 1, 2, ....
Точки последовательности
вычисляются по правилу:
j
– номер цикла вычислений, j =0, 1, 2, ....; k –
номер итерации внутри цикла, k=0, 1, 2,
....,n-1;
– единичный вектор. Начальная
точка
задается
пользователем. Величина шага выбирается
из условия:
В данном методе при
фиксированном j за одну итерацию с
номером k изменяется только одна
координата вектора
с
номером k+1, а за весь цикл с номером j,
начиная с k=0 и кончая k=n-1, изменяются все
координаты вектора
.
После этого точке
присваивается
номер
и
она берется за начальную точку для
вычислений в (j+1) –м цикле. Расчет
заканчивается в точке
,
для которой выполняется условие
,
где
заданное
малое число.
В случае двух переменных данный метод имеет следующую геометрическую интерпретацию.
Алгоритм метода.
Начальный этап
Задать , .
Найти градиент функции в произвольной точке
Положить j=0.
Основной этап
Шаг 1. Положить k=0
Шаг 2. Проверить
выполнение условия k
n-1
а) если k n-1, то перейти к шагу 3;
б) если k = n, то положить j= j+1 и перейти к шагу 1
Шаг 3. Вычислить
Шаг 4. Проверить
выполнение критерия останова
а) если критерий
выполнен, расчет окончен,
б) если критерий не выполнен, то перейти к шагу 5.
Шаг 5. Вычислить величину шага из условия
Шаг 6. Вычислить
Шаг 7. Положить k= k +1 и перейти к шагу 2
Пример.
Решение.
Положим
Градиент функции есть:
Положим j=0
Анализ точки. Так как матрица Гессе
является положительно определенной, то функция f(X) строго выпукла и, следовательно, в стационарной точке достигает глобальный минимум .
Метод Флетчера-Ривса (Метод сопряженных градиентов).
Стратегия поиска.Рассмотренные выше градиентные методы отыскивают точку минимума функции в общем случае лишь за бесконечное число итераций. Метод сопряженных градиентов формирует направления поиска, в большей мере соответствующие геометрии минимизируемой функции.
Определение.
Два n-мерных вектора
х и у называют сопряженными
по отношению к матрице H (или H-сопряженными),
если скалярное произведение (x, Ну) = 0.
Здесь Н - симметрическая положительно
определенная матрица размером
пхп.
Стратегия метода Флетчера-Ривса
состоит в построении последовательности
точек
, k=0, 1, 2, ... таких, что
,
k=0, 1, 2, ...
Точки последовательности вычисляются по правилу:
Величина шага выбирается
из условия минимума функции f(х) по t в
направлении движения, т. е. в результате
решения задачи одномерной минимизации:
Отметим, что при данном
выборе
в
случае квадратичной функции f(x)= (х, Нх)
+ (b, х) + а направления
будут H-сопряженными, т.е.
При этом в точках
последовательности
градиенты
функции f(x) взаимно
перпендикулярны, т.е.
При минимизации неквадратичных функций метод Флетчера-Ривса не является конечным. Для неквадратичных функций используется следующая модификация метод Флетчера-Ривса (метод Полака-Рибьера), когда величина вычисляется следующим образом:
Здесь I- множество индексов:
I = {0, n, 2n, Зn, ...}, т. е. метод Полака-Рибьера
предусматривает использование итерации
наискорейшего градиентного спуска
через каждые n шагов с заменой
на
.
Построение последовательности
заканчивается в точке, для которой
.
Геометрический смысл метода
сопряженных градиентов состоит в
следующем. Из заданной начальной точки
осуществляется
спуск в направлении
.
В точке
определяется
вектор-градиент
.
Поскольку
является
точкой минимума функции в направлении
,
то
ортогонален вектору
.
Затем отыскивается вектор
,
H-сопряженный к
.
Далее отыскивается минимум функции
вдоль направления
и
т. д.
Алгоритм метода
Начальный этап Сходимость метода.
Теорема
3. Если квадратичная
функция f(x) = (х, Нх) + (b, х) + а с неотрицательно
определенной матрицей Н достигает
своего минимального значения на
,
то метод Флетчера-Ривса обеспечивает
отыскание точки минимума не более чем
за n шагов.
Теорема
4.Пусть функция f(x)
дифференцируема и ограничена снизу на
,
а ее градиент
удовлетворяет условию Липшица
Тогда при произвольной начальной точке для метода Полака-Рибьера имеем
Отметим, что теорема 4 гарантирует сходимость последовательности к стационарной точке , где . Поэтому найденная точка нуждается в дополнительном исследовании для ее классификации. Метод Полака-Рибьера гарантирует сходимость последовательности к точке минимума только для сильно выпуклых функций.
Оценка скорости сходимости получена только для сильно выпуклых функций , в этом случае последовательность сходится к точке минимума функции f(x)со скоростью:
Пример.
Решение.
Итерация 0.
Итерация 1.
Задать , .
Найти градиент функции в произвольной точке
Положить k=0.
Основной этап Шаг 1. Вычислить
Шаг 2. Проверить выполнение критерия останова
а) если критерий выполнен, расчет окончен,
б) если критерий не выполнен, то перейти к шагу 3, если k=0, иначе к шагу 4.
Шаг 3. Определить
Шаг 4. Определить
или в случае неквадратичной функции
Шаг 5. Определить
Шаг 6. Вычислить величину шага из условия
Шаг 7. Вычислить
Шаг
8. Положить k= k +1 и
перейти к шагу 1.
Итерация 2.
Анализ точки.Найдем матрицу Гессе функции
Так как матрица Гессе является положительно определенной, то функция f(X) строго выпукла и, следовательно, в стационарной точке достигает глобальный минимум .