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

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

.

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

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

.

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

.

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

.

Работу метода иллюстрирует рис. 8.16, на котором показана траектория поиска минимума функции f=(2-x1)4+2(x1-2x2)2.

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