. Метод спуска решения нелинейных систем.

 

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

                                                          (4.1)

Из функций, стоящих в левых частях уравнений системы образуем новую функцию

.           (4.2)

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

 Û

Последовательность точек xk – приближений к точке  минимума функции  F(x) обычно получают по рекуррентной формуле:

xk+1 = xk + akak,  k = 1, 2, …                                                  (4.3)

где ak – вектор, определяющий направление минимума, ak – параметр, характеризирующий величину шага в направление минимизации (шаговый множитель).

На рисунке изображен случай системы двух уравнений с двумя неизвестными. В точке минимума  в которой , график функции z = F(x) касается плоскости Oxy. Направление из точки приближения xk на следующую точку

xk+1 можно задать вектором антиградиента - agradF(xk), a - регулируемая величина шага в данном направлении.

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

F(xk+1) < F(xk).

Таким образом, при построении численных методов минимизации функции F(x) необходимо ответить на два вопроса:

1)     Как выбрать направление спуска ak?

2)     Как регулировать величину ak  шага в данном направлении?

При выборе направления спуска естественно выбирать такое направление, в котором функция F(x) убывает наиболее быстро. Известно из курса математики, что дифференцируемая функция нескольких переменных наиболее быстро убывает в направлении антиградиента. Таким образом, в качестве вектора направления можно взять вектор

ak = -gradF(xk) = .

Шаг в направлении антиградиента выбирается так, чтобы значение F(xk+1), для xk+1, вычисленного по формуле (4.3) было наименьшим среди всех возможных значений. Такой выбор шагового множителя называется исчерпывающим спуском, а метод методом наискорейшего спуска. При этом множитель ak  выбирается из условия минимума функции

F(xk - ak gradF(xk)).

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

Главное достоинство градиентных методов – глобальная сходимость, т.е. сходимость к точке минимума из любой начальной точки.