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

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

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

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

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

Работу метода иллюстрирует рис., на котором показана траектория поиска минимума функции

f= (2- x ₁)⁴+2(x ₁-2 x ₂)².

x2

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

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