Методы спуска

Поиск корня системы нелинейных уравнений можно свести к задаче минимизации некоторой целевой функции.

Пусть необходимо решить систему уравнений (5.12)

Составим целевую функцию Ф(x):

Ф(x ₁, …, x_n) = f ₁²(x ₁, …, x_n) + f ₂²(x ₁, …, x_n) + … + f_n ²(x ₁, …, x_n) ³ 0.

Минимальное значение целевой функции, равное нулю Ф(х) = 0, достигается на корне x ^* = { x ₁^*, …, x_n ^*} исходной системы, который обращает все f_i (x) в нуль.

Поэтому решение исходной системы эквивалентно поиску минимума функции Ф(x ₁, …, x_n).

Если минимальное значение Ф(x ₁, …, x_n) в заданной области строго больше нуля, то это свидетельствует о том, что в этой области система уравнений не имеет решения.[1]

Рассмотрим некоторые методы решения задачи минимизации. Они представляют и самостоятельный интерес, не связанный с решением систем уравнений: найти минимум некоторой функции.

Основная идея всех методов спуска, используемых для нахождения минимума функции, состоит в том, чтобы исходя из начального приближения точки х ⁽⁰⁾ = { х ₁⁽⁰⁾, х ₂⁽⁰⁾, …, х_n ⁽⁰⁾} перейти в следующую точку х ⁽¹⁾ так, чтобы значение Ф(х) уменьшилось:

Ф(х ⁽¹⁾) < Ф(х ⁽⁰⁾).

Важным элементом всех методов спуска является минимизация функций одной переменной. Поэтому прежде чем говорить о минимизации функций многих переменных, рассмотрим некоторые методы минимизации функции одной переменной j (х).

1. Пусть функция j (х) –дифференцируемая (по крайней мере два раза).

Тогда нахождение минимума сводится к решению уравнения j' (х) = 0.

Метод Ньютона применительно к этому уравнению

.

В практических расчетах производные часто заменяют конечными разностями, причем стараются пользоваться симметричными разностями с постоянным шагом (выше точность). Тогда формула метода Ньютона:

.

Это эквивалентно замене кривой j (х) интерполяционной параболой, построенной по трем точкам: x_k – h, x_k, x_k + h.

2. Пусть функция j (х) не дифференцируема, например, могут существовать разрывы первого рода.

Предположим также, что эта функция – унимодальная кусочно-непрерывная на некотором отрезке [ a, b ], т.е. имеющая на этом отрезке один минимум х _* (рис.5.9), причем j (х) строго возрастает при х ³ х ^* и строго убывает для всех х £ х ^*.

Рис.5.9 – Поиск минимума функции одной переменной

Для унимодальной функции по любым двум значениям j (х ₁), j (х ₂) можно указать интервал, в котором находится точка х ^*, минимизирующая функцию j (х). Это делается следующим образом.

Вычисляем функцию на концах отрезка, а также в двух внутренних точках х ₁ и х ₂, сравниваем все четыре значения и выбираем наименьшее. Пусть наименьшее оказалось в точке х ₁.Очевидно, минимум расположен в одном из прилегающих отрезков. Поэтому отрезок [ х₂, b ] следует отбросить, а отрезок [ а, х ₂] оставить. Первый шаг процесса сделан.

Теперь на отрезке [ а, х ₂] снова надо выбрать две точки. Но одна точка х ₁ уже есть, поэтому достаточно определиться с выбором только одной точки и в ней найти значение функции. Снова сравниваются все четыре значения, выбирают наименьшее и выбирают отрезки. Второй шаг процесса сделан.

В зависимости от стратегии выбора двух точек х ₁ и х ₂ , на интервале будет различна скорость стягивания интервала, содержащего минимум, к точке х^*.

Одна из стратегий основана на методе золотого сечения.

Золотое сечение открыто Евклидом и заключается в нахождении точки, разбивающей интервал [ а, b ]на две части таким образом, чтобы отношение длины всего интервала к большей части было равно отношению большей части к меньшей:

или .

Рассмотрим первое соотношение. Если ввести обозначения

с = b – a, y = x – a,

то получим квадратное уравнение относительно y: y ² + cy – c ² = 0. Корни этого уравнения или , где .

Рассмотрим второе соотношение. Вводя обозначения с=b–a, y=b–x, получим уравнение, аналогично предыдущему, решение которого имеет вид: x ₁ =b – t (b–a).

Алгоритм метода золотого сечения следующий:

1) вычисляют значения х ₁, х ₂;

2) вычисляют φ (х ₁), φ (х ₂);

3) если φ (х ₁) £ φ (х ₂), то для дальнейшего деления оставляют интервал [ a, x ₂];

4) если φ (х ₁) >φ (х ₂), то для дальнейшего деления оставляют интервал [ x ₁, b ].

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

Отметим, что точка х ₁ производит золотое сечение интервала [ a,x ₂], а точка х ₂ – интервала [ x ₁ ,b ]. Поэтому на оставшемся интервале нужно определить только одну точку, производящую золотое сечение.

Метод золотого сечения, естественно, можно применять и к дифференцируемым функциям. Он надежный, но медленно сходится. Это аналог метода бисекции применительно к задачам на минимум.

Теперь вернемся к функциям многих переменных.

Метод покоординатного спуска. Пусть задано нулевое приближение х ⁽⁰⁾ = { х ₁⁽⁰⁾, х ₂⁽⁰⁾, …, х_n ⁽⁰⁾}. Фиксируем х ₂⁽⁰⁾, х ₃⁽⁰⁾, …, х_n ⁽⁰⁾ и находим минимум Ф(х ₁, х ₂⁽⁰⁾, …, х_n ⁽⁰⁾) функции одной переменной х ₁ одним из вышеизложенных методов. Значение х ₁, доставляющее минимум, обозначим х ₁⁽¹⁾, т.е.

Ф(х ₁⁽¹⁾, х ₂⁽⁰⁾, …, х_n ⁽⁰⁾) £ Ф(х ₁⁽⁰⁾, х ₂⁽⁰⁾, …, х_n ⁽⁰⁾)

Далее, фиксируем х ₁⁽¹⁾, х ₃⁽⁰⁾ ,…, х_n ⁽⁰⁾и находим минимум функции Ф(х ₁⁽¹⁾, х ₂, х ₃⁽⁰⁾, …, х_n ⁽⁰⁾) одной переменной х ₂. Значение х ₂, доставляющее этот минимум, обозначим х ₂⁽¹⁾, т.е.

Ф(х ₁⁽¹⁾, х ₂⁽¹⁾, …, х_n ⁽⁰⁾) £ Ф(х ₁⁽¹⁾, х ₂⁽⁰⁾, …, х_n ⁽⁰⁾).

Продолжаем процесс. После n шагов получаем

Ф(х ₁⁽¹⁾, х ₂⁽¹⁾, …, х_n ⁽¹⁾) £ Ф(х ₁⁽¹⁾, х ₂⁽¹⁾, …, х_n ⁽⁰⁾).

Таким образом, завершен один цикл покоординатного спуска. Мы перешли из точки х ⁽⁰⁾ в точку х ⁽¹⁾. Если Ф(х ⁽¹⁾) < Ф(х ⁽⁰⁾), то выполняется следующий цикл покоординатного спуска, в котором за начальную точку принимается х ⁽¹⁾. В результате переходим в точку х ⁽²⁾ и т.д. Этот процесс продолжается до тех пор, пока не выполнится какое-нибудь условие окончания алгоритма, например.

| Ф(х ^{( k +1)}) < Ф(х ^(k))| < e,

где e – заданная точность.

Этот метод несложен и легко программируется на ЭВМ. Сходится он медленно, сходимость зависит от поведения функции Ф. Хорошая сходимость, например, для функции двух переменных, когда линии уровня похожи на эллипсы (рис.5.10). Плохая сходимость – когда линии уровня кусочно-гладкие, т.е. имеются точки излома (рис. 5.11).

Метод градиентного спуска. Двигаться к минимуму функции можно не только параллельно осям координат. Определим направление спуска таким образом, чтобы в этом направлении функция Ф(х) быстрее всего убывала.

Как выбрать это направление?

Известно, что вектор

ортогонален линиям уровня Ф(х)= const (рис.5.12) и его направление совпадает с направлением максимального роста функции Ф(х) в заданной точке. В точке минимума grad Ф(х) = 0.

Рис.5.10 – Котловинный тип рельефа Рис.5.11 – Овражный тип рельефа

Рис.5.12. Направление вектора градиента

Поэтому итерационный процесс нахождения минимума функции можно определить следующим образом:

,

где h_k – шаг спуска, х ^(k) – k -тое приближение к точке минимума.

Если grad Ф(х ^(k)) ¹ 0, то для достаточно малых значений h_k будет выполняться условие:

Ф(х ^{(k +1)}) < Ф(х ^(k)). (5.17)

В случае нарушения (5.17) шаг h_k дробят до тех пор, пока это условия не выполнится, и продолжают вычисления.

Итерационный процесс можно остановить, например, по выполнению условия

.

Можно модифицировать этот метод, специальным образом выбирая шаг. Найдем значение функции Ф(х) в точке х ^{( k +1)}:

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

на каждом шаге итерационного цикла.

Рис.5.1 – Нахождение оптимального шага h _*

Пример. Выполнить шаг по методу градиентного спуска для функции .

Итерационная схема имеет вид:

; .

Примем за начальную точку х ⁽⁰⁾ = {1, 1} и найдем начальный шаг. Для этого необходимо решить задачу нахождения . Аргументами функции Ф будут

и .

Таким образом, задача определения шага h ₀ сводится к задаче нахождения минимума функции

.

Вычисляя производную и приравнивая ее к нулю, получим:

; .

С этим шагом переходим в новую точку

и .

Далее процесс повторяется: ищем шаг h ₁ и новую точку .

Основной недостаток методов спуска – зависимость от начального приближения х ⁽⁰⁾ и возможность попасть в локальный минимум (рис.5.14). Поэтому в задачах минимизации важно использовать всю имеющуюся информацию о функции Ф(х), чтобы правильно выбрать начальные значения и попасть в глобальный минимум.

	б)

а)

Рис.5.14. Поверхность Ф с глобальным и локальным минимумами (а)

и ее проекция на плоскость x ₁, x ₂ (б)

[1] Речь идет о глобальном минимуме функции Ф. Но могут быть и ненулевые локальные минимумы, что усложняет решение задачи минимизации функции.