Метод скорейшего спуска (метод градиента)

Пусть имеем систему уравнений

f₁(x₁, x₂,..... x_n,)=0,

f₂(x₁, x₂,..... x_n,)=0 ,              (1)

........................

f_n(x₁, x₂,..... x_n,)=0

 {spoiler=Подробнее}

или в матричной форме

f(x)=0                                 (2)                  где 

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

U(x)=å[f_i(x)]² =(f(x),f(x)).                  (3)

 Видно, что каждое решение системы (1) обращает в нуль функцию U(x); наоборот, что числа x₁,x₂,...,x_n для которых функция U(x) равна нулю, являются корнями системы (1).

Будем предполагать, что система (1) имеет лишь изолированное решение, которое представляет собой точку строгого минимума функции U(x).

Таким образом, задача свершится к нахождению минимума функции U(x) в мерном пространстве

E_n={x₁, x₂,...., x_n}.

Пусть x-вектор-корень системы (1) и x⁽⁰⁾ -его нулевое приближение. Через точку x⁽⁰⁾ проведем поверхность уровня функции U(x).

Если точка x⁽⁰⁾ достаточно близка к корню x, то при наших предположениях поверхность уровня

U(x)=U(x⁽⁰⁾)

будет похоже на эллипсоид.

Из точка x⁽⁰⁾ двигаемся по нормали к поверхности U(x)=U(x⁽⁰⁾) до тих пор, пока это нормаль не коснется в некоторой точке x⁽¹⁾ какой то другой поверхности уровня (рис.)

U(x)=U(x⁽¹⁾).

Затем, отправляясь от точки x⁽¹⁾ снова двигаемся по нормали к поверхности уровня U(x)=U(x⁽¹⁾) до тих пор, пока эта нормаль не коснется в некоторой точке x⁽²⁾ новой поверхности уровня

             U(x)=U(x⁽²⁾ ), и т.д.

Так как U(x⁽⁰⁾)>U(x⁽¹⁾)>U(x⁽²⁾)>....., то , двигаясь  по такому пути, мы быстро приближаемся к точке с наименьшем значением U (дно “ямы”), которая соответствует искому корню x  системы (1). Обозначим через

ÑU(x)=grad(U(x))

градиент функции U(x).

Из  векторных треугольников  OM0M1,OM1M2 заключаем, что

x^(p+1)=x^(p)-lpÑU(x^(p) ) ,  (P=0,1,2, -    )

Остается определить множители lp.Для этого рассмотрим скалярную функцию

Ф(l)=v[x^(p)-lÑU(x^(p))],

функция Ф(l) дает изменение уровня функции U  вдоль соответствующей нормали к поверхности уровня в точке Х^(р). Множитель l=lР надо выбрать таким образом , чтобы Ф(l)  имела минимума . Беря производную по l и приравнивая  ее нулю, получаем уравнение

Ф’(l)=U[x^(p)- lÑU(x^(p))]=0         (4)

Наименьший положительный  корень уравнения (4) и даст нам значенияlp. Уравнения (4)  , нужно решать численно. Поэтому укажем метод приближенного  нахождения чисел lp.Будем считать, что l -малая величина, квадратом и высшими степенями которой можно  пренебречь. Имеем:

Ф(l)=

разлагая функции f_i по степеням l с точностью до линейных членов, получим: 

²,

где            

где

Отсюда 

Следовательно

    lp=

где   

Матрице Якоби  вектор функции f.

Далее имеем:

Отсюда

где W’(х)-транспонированная матрица Якоби.

Поэтому окончательно

               (5)

где для краткости положено

причем   х^(р+1)=х^(р)-m_рW­_р’f^(p) , P=0,1,2,.....         (6)

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

Ñх^(р)=х^(р+1)-х^(р).

{/spoilers}