Метод Гаусса-Зайделя

Метод Гаусса-Зайделя предусматривает поочередное нахождение частных экстремумов целевой функции по каждому фактору x_i (i =1, 2, …, n). При этом на каждом i-м этапе стабилизируют n-1 факторов и варьируют только один, i-й фактор. Задачу поиска экстремума решают в несколько этапов, которые затем объединяют в циклы.

Рассмотрим последовательность поиска максимума методом Гаусса-Зайделя с иллюстрацией двухфакторного примера. Графическая интерпретация метода дана на рисунке 10.1, где на плоскости двух факторов x1, x2 изображена функция отклика у топографическим способом с помощью замкнутых линий постоянного уровня этой оптимизируемой выходной функции. Эти линии соответствуют некоторым относительным величинам, однако форма функции отклика до начала исследования обычно неизвестна.

I этап. Производится поиск частного экстремума по первому фактору x₁, остальные факторы остаются неизменными, то есть стабилизируются.

1 – Выбирают основную (начальную, базовую) точку М₀, обычно она соответствует номинальному режиму ведения технологического процесса ₀=(x₁₀; x₂₀; …; x_k0). Иногда эту точку выбирают в центре области, которую желательно исследовать, либо в центре области ограничений, если они имеются.

x₂

M₁₁ M₉ M₁₂ M₁₃ M₁₄

M₈ M₁₅

Δx₂ M₆ M₅ M₄ M₃ M₂ M₀ M₁

x₂₀

M₇

x₁

0 x₁₀

Δx₁

Рисунок 10.1 – Поиск экстремума функции отклика

методом Гаусса-Зайделя

2 – Выбирают интервал варьирования Δx₁ по фактору x₁. Интервал не должен быть слишком малым, иначе движение к экстремуму окажется замедленным. Кроме того, на интервале варьирования Δx_i (i=1, 2, …, k) изменение целевой функции Δy должно быть существенно большим, чем погрешность ее измерения δy (не менее чем в 5–10 раз)

3. Определяют координаты пробных точек М₁ и М₂:

(М₁) = (x₁₀+Δx₁; x₂₀; …; x_k0),

(М₂) = (x₁₀–Δx₁; x₂₀; …; x_k0).

4. В точках М₁ и М₂ ставят пробные опыты (для повышения точности результатов могут выполняться параллельные опыты) и измеряют отклики у(М₁) и у(М₂).

5. Сравнивают полученные отклики, и если у(М₂) > у(М₁), то совершают рабочее движение на один рабочий шаг Δx₁ по направлению в точку М₃.

6. Аналогичные шаги продолжают в том же направлении до тех пор, пока на каком-то m-м шаге не окажется, что у(М_m) < у(М_m–1), то есть значение отклика в очередной, m-й рабочей точке станет уменьшаться, – это и служит признаком достижения частного экстремума. За частный экстремум принимают (m–1)-ю точку с откликом у(М_m–1). На рисунке 4.1 это точка М₅.

II этап. Его проводят в том порядке, что и I этап, с той лишь разницей, что стабилизируют все факторы, кроме x₂. За новую базовую точку принимают точку с координатами

(М_m–1) = (x₁₀+Δx₁·(m–2); x₂₀; …; x_k0),

а x₂ варьирую на выбранную по аналогичным условиям величину интервала Δx₂. По достижении частного экстремума по фактору x₂ точку нового частного экстремума принимают за новую базовую точку. На рисунке 10.1 это точка М₉.

Первый цикл продвижения к экстремуму заканчивается n-м этапом, на котором стабилизируются все факторы, кроме x_k. Для него выбирают интервал варьирования Δx_k и совершают пробное, а затем рабочее движение до достижения частного экстремума по фактору x_k. Если экстремум не достигнут, то выполняют второй цикл поиска.

Второй цикл, как и первый, начинается с I этапа, на котором варьируют фактор x₁ (i ≠ 1), затем последовательно выполняют k этапов по каждому из k факторов.

Поисковое шаговое движение к экстремуму заканчивают по достижении такой точки факторного пространства, при движении из которой в любую сторону по всем n факторным осям x_i в положительном или отрицательном направлениях значения отклика оказываются меньшими. Такую точку принимают за экстремум (в рассматриваемом случае – максимум).

Достоинства метода Гаусса-Зайделя:

– простота стратегии и наглядность;

– высокая помехозащищенность в смысле выбора направления движения.

Недостатки:

– путь к главному экстремуму оказывается обычно долгим, особенно при большом числе факторов;

– если поверхность отклика имеет сложную форму, то использование метода может привести к ложному ответу на вопрос о месте расположения экстремума;

– метод не дает информации о взаимодействиях факторов.

Исторически метод Гаусса-Зайделя известен как первый из рассматриваемых. При увеличении количества воздействующих факторов до 5–6 применять этот метод для оптимизации процессов неэффективно.