Файл: Определение максимального и минимального значения функции двух переменных методом градиентного спуска.doc

Добавлен: 29.10.2018

Просмотров: 390

Скачиваний: 10

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Определение максимального и минимального значения функции двух переменных методом градиентного спуска (подъема).


При определении максимального или минимального значений функции двух или более переменных используется понятие «Градиента». Градиентом функции называется вектор, компоненты которого являются частными производными функции по соответствующим координатам. Так, например, для функции двух переменных f(x,y) градиент определяется как вектор с компонентами: и . Обозначается градиент функции либо без значка вектора .

Градиент функции f(x1, x2,..., xn) в каждой точке направлен в сторону наискорейшего локального возрастания (убывания) этой функции. Для поиска минимума необходимо спускаться в противоположном направлении.


При численных расчетах градиент функции можно вычислить приближенно , где , – единичные вектора по направлениям осей x и y, , , - приращение x, - приращение y.

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


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


Рассмотрим многомерную функцию, имеющую вид колокола:

, (1)

где точка – точка максимума функции.

В области изменений функция имеет вид:



Аналогичные функции можно построить в многомерном пространстве. Например, если размерность пространства n, то функция «n-мерный колокол» будет иметь вид:


. (2)


Точка максимума этой функции - . Функция «n-мерного колокола» (2) при n=2 превращается в (1).

Описание алгоритма нахождения максимального (минимального) значения функции двух переменных методом градиентного спуска (подъема):

  1. Задаем размерность n массива аргументов минимизируемой (максимизируемой) многомерной функции, погрешность вычислений ε, начальные значения шага d по x, y, координаты начальной точки поиска x0, y0, определяем вспомогательный массив для запоминания значений аргументов при дроблении шага х1, y1, массив для составляющих градиента функции df.

  2. Вычисляем значение функции в точке с координатами (x0, y0).

  3. Вычисляем х и y компоненты вектора градиента функции по формулам gx=(f(x0+dx, y0)-f(x0,y0))/dx; gy=(f(x0, y0+dy)-f(x0,y0))/dy.

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

  5. Вычисляем новое значение функции и сравниваем с предыдущим. Если максимум (минимум) не найден, продолжаем итерации.

  6. Если второе условие не выполнилось, уменьшаем шаг.


Алгоритм на естественном языке приведем для функции «n-мерного колокола».

Строки «комментарии» будем начинать с символа «*».


Для функции с координатами точки максимума: (2, 3, 4, …, n+1) для пространства размерности n.

Определить n как целое, где n – количество аргументов функции.

n=2

Определить массивы x0(n), x1(n) , x2(n), df(n), h(n)

* массивы x0, x1, х2 – рабочие массивы координат точек (0), (1),

* (2). Массивы df – компоненты вектора градиента функции,

* h – компоненты векторов шага

Определить глобальный массив xс(n)

* массив xс-массив координат точки максимума функции


eps=0.01

d=0.01


* в данном цикле задаются координаты точки максимума

цикл по i от 1 до n

xc(i)=1+i

конец цикла


* здесь задаются координаты начальной точки для определения

* максимума

цикл по i от 1 до n

x0(i)=0.1+i

конец цикла


h0=0.5


f0=колокол(@x0,n)


цикл по k от 1 до 10000

печать "k=",x0(1),x0(2),f0,h0


цикл по j от 1 до n

цикл по i от 1 до n

x1(i)=x0(i)

конец цикла

x1(j)=x0(j)+d

f1=колокол(@x1,n)

df(j)=(f1-f0)/d

конец цикла

* нормирование градиента

lendf=0

цикл по i от 1 до n

lendf = lendf + df(i)^2

конец цикла

lendf = Корень(lendf)

цикл по i от 1 до n

df(i)=df(i)/lendf

конец цикла


цикл по i от 1 до n

x0(i)=x0(i)+df(i)*h0

конец цикла


f0_1=колокол(@x0,n)


если f0_1=<f0

печать " нашли max"


если h0<eps

печать "найден max x0=(",

цикл по i от 1 до n

печать x0(i)

конец цикла

печать ")"

печать " f0= ", f0

печать "за ",k," итераций"

выход из программы

конец если


h0=h0/2


конец если


f0=f0_1


конец цикла


печать "максимум не найден x="

цикл по i от 1 до n

печать x0(i)

конец цикла


ОПРЕДЕЛИТЬ ФУНКЦИЮ колокол

параметры x, n

определить массив x(n)

определить локальную переменную r2

r2=0

цикл по i от 1 до n

r2=r2+(x(i)-xc(i))^2

конец цикла

если r2>10

r2=10

конец если

вернуть 5*(EXP(-0.1*r2))


Пример решения на языке VFP:


CLEAR

SET DECIMALS TO 15

n=100

DIMENSION x0(n), x1(n), df(n), h(n), x2(n)

PUBLIC ARRAY xc(n)


FOR i=1 TO n

xc(i)=1+i

ENDFOR


eps=0.01

d=0.01


FOR i=1 TO n

x0(i)=1.1+i

ENDFOR


h0=0.5


f0=функция(@x0,n)


FOR k=1 TO 10000

? "k=",STR(x0(1),5,2),STR(x0(2),5,2),f0,h0


FOR j=1 TO n

FOR i=1 TO n

x1(i)=x0(i)

ENDFOR

x1(j)=x0(j)+d

f1=функция(@x1,n)

df(j)=(f1-f0)/d

ENDFOR

* нормирование градиента

lendf=0

FOR i=1 TO n

lendf = lendf + df(i)^2

ENDFOR

lendf = SQRT(lendf)

FOR i=1 TO n

df(i)=df(i)/lendf

ENDFOR


FOR i=1 TO n

x0(i)=x0(i)+df(i)*h0

ENDFOR


f0_1=функция(@x0,n)


IF f0_1=<f0

? " нашли max"


IF h0<eps

? "найден max x0=(",

FOR i=1 TO n

??x0(i)

ENDFOR

??")"

?" f0= ", f0

? "за ",k," итераций"

RETURN

endif


h0=h0/2


ENDIF


f0=f0_1


endfor


? "максимум не найден x="

FOR i=1 TO n

??x0(i)

ENDFOR


FUNCTION функция

LPARAMETERS x, n

DIMENSION x(n)

LOCAL r2

r2=0

FOR i=1 TO n

r2=r2+(x(i)-xc(i))^2

ENDFOR

IF r2>10

r2=10

ENDIF

RETURN 5*(EXP(-0.1*r2))


Пример решения на языке VBA:


Sub grd()

Dim z(8), y(8), p(8)

n = 2

e = 0.0001

a = 0.2

For i = 1 To n

Debug.Print z(i)

z(i) = 0

Next

GoSub 1


For i = 1 To n

Debug.Print z(i)

Next

Debug.Print f, k


1: k = 1

GoSub 2

4: f1 = f

GoSub 3

For i = 1 To n

y(i) = z(i)

Next

5: l = 1

For i = 1 To n

r = a * p(i)

z(i) = y(i) - r

If Abs(r) > e Then

l = 0

End If

Next

k = k + 1

GoSub 2

If l = 1 Then Return


If f < f1 Then GoTo 4


a = a / 2

GoTo 5

Return

2: r = Exp(z(1) ^ 2 + z(2) ^ 2)

f = r + 2 * z(1) - 3.5 * z(2)

Return

3: r = 2 * r

p(1) = z(1) * r + 2

p(2) = z(2) * r - 3.5

Return

End Sub