Метод Гаусса-Зейделя (покоординатного спуска)

Процедура поиска сводится к решению последовательности задач одномерной минимизации по каждой переменной. Пусть выбрана начальная точка

.

Зафиксируем все переменные, кроме первой, на начальных значениях и решаем задачу

одним из одномерных методов. Фиксируем х ₁ на полученном в решении значении x₁' и делаем свободной переменную х ₂. Приходим к очередной одномерной задаче

.

Аналогично строятся и решаются последующие одномерные задачи, последняя из которых имеет вид:

.

Эти n задач составляют один цикл. Его результатом является точка X¹. Она принимается за начальную точку для следующего аналогичного цикла. Поиск заканчивается, когда расстояние между двумя последовательными точками становится меньше заданной величины:

.

Работу метода иллюстрирует рис. 8.16, на котором показана траектория поиска минимума функции f= (2- x ₁)⁴+2(x ₁-2 x ₂)².

x2

Метод отличается алгоритмической простотой. Однако ему присущ ряд недостатков. Его эффективность существенно зависит от направления осей координат относительно линий уровня. Это хорошо видно на примере квадратичной функции: при совпадении координат с осями эллипсов минимум достигается за один цикл из любой начальной точки (рис. 8.17), а при их повороте число циклов значительно возрастает (рис. 8.18). Из этого примера также следует, что метод неэффективен в условиях оврага. Если функция не дифференцируема в отдельных точках, поиск может остановиться, не достигнув окрестности минимума. Рис. 8.19 демонстрирует такой случай: точка останова А далека от искомого минимума.

Из анализа траекторий поиска в приведенных примерах можно заключить, что эффективность поиска повысится, если к описанным однотипным циклам добавить движение в направлении, проходящем через точки X^(k) и X^{(k +1)}. Это движение называют ускоряющим шагом. Он используется в методе, рассматриваемом в следующем разделе.