Файл: Определение максимального и минимального значения функции двух переменных методом градиентного спуска.doc
Добавлен: 29.10.2018
Просмотров: 457
Скачиваний: 11
Определение максимального и минимального значения функции двух переменных методом градиентного спуска (подъема).
При определении максимального или
минимального значений функции двух или
более переменных используется понятие
«Градиента». Градиентом функции
называется вектор, компоненты которого
являются частными производными функции
по соответствующим координатам. Так,
например, для функции двух переменных
f(x,y)
градиент определяется как вектор с
компонентами: 
и 
.
Обозначается градиент функции 
либо без значка вектора .
Градиент функции f(x1, x2,..., xn) в каждой точке направлен в сторону наискорейшего локального возрастания (убывания) этой функции. Для поиска минимума необходимо спускаться в противоположном направлении.
При численных расчетах градиент функции
можно вычислить приближенно 
,
где
,
– единичные вектора по направлениям
осей x и y,
,
,
-
приращение x, 
- приращение y.
Вектор градиента 
указывает, подобно производной одномерной
функции, направление на ближайший
локальный максимум функции в данной
точке, вектор 
–
направление на ближайший локальный
минимум.
Параметр а определяет длину шага в направлении спуска. Длину шага можно выбирать из условия минимизации функции вдоль направления, противоположного градиенту. Такой метод называют методом наискорейшего спуска. В другом методе градиентного спуска длина шага а выбирается методом дробления.
Рассмотрим многомерную функцию, имеющую вид колокола:
,
(1)
где точка 
– точка максимума функции.
В области изменений 
функция имеет вид:
Аналогичные функции можно построить в многомерном пространстве. Например, если размерность пространства n, то функция «n-мерный колокол» будет иметь вид:
. (2)
Точка максимума этой функции - 
.
Функция «n-мерного колокола»
(2) при n=2 превращается в
(1).
Описание алгоритма нахождения максимального (минимального) значения функции двух переменных методом градиентного спуска (подъема):
-
Задаем размерность n массива аргументов минимизируемой (максимизируемой) многомерной функции, погрешность вычислений ε, начальные значения шага d по x, y, координаты начальной точки поиска x0, y0, определяем вспомогательный массив для запоминания значений аргументов при дроблении шага х1, y1, массив для составляющих градиента функции df.
-
Вычисляем значение функции в точке с координатами (x0, y0).
-
Вычисляем х и y компоненты вектора градиента функции по формулам gx=(f(x0+dx, y0)-f(x0,y0))/dx; gy=(f(x0, y0+dy)-f(x0,y0))/dy.
-
Вычисляем модуль градиента функции.
-
Вычисляем новое значение функции и сравниваем с предыдущим. Если максимум (минимум) не найден, продолжаем итерации.
-
Если второе условие не выполнилось, уменьшаем шаг.
Алгоритм на естественном языке приведем для функции «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