Метод градиентного спуска в среде Maple

Размещено на http://www.allbest.ru/

ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

КАФЕДРА ВЫСШЕЙ И ПРИКЛАДНОЙ МАТЕМАТИКИ

Контрольная работа по теме:

“Метод градиентного спуска в среде Maple”

Введение

Цель работы: Реализовать метод градиентного спуска в среде Maple.

Постановка задачи:

Пусть целевая функция имеет вид:

И задача оптимизации задана следующим образом:

Основная идея метода заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом :

где л[j] выбирается

постоянной, в этом случае метод может расходиться;

дробным шагом, т.е. длина шага в процессе спуска делится на некое число;

наискорейшим спуском:

Теоретическая часть

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

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

(B)

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

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

Пусть x - вектор системы (А) и x0 - его нулевое приближение. Через точку x0 проведем поверхность уровня функции U(x). Если точка x0 довольно близка к корню x, то при наших предположениях поверхность уровня

U(x)= U(x0)

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

Из точки x0 движемся по нормали к поверхности U(x)= U(x0) до тех пор, пока эта нормаль не затронет в некоторой точке x1 какой-то другой поверхности уровня U(x)= U(x1).

Потом, отправляясь от точки x1, снова движемся по нормали к поверхности уровня U(x)= U(x1) до тех пор, пока эта нормаль не затронет в некоторой точке x2 новой поверхности уровня U(x)= U(x2), и т.д.

Поскольку U(x0)>U(x1)>U(x2)>..., то, двигаясь таким путем, мы быстро приближаемся к точке с наименьшим значением U ("дно ямы"), что отвечает искомому решению исходной системы. Обозначим через

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

Находить нужное решение будем по формуле:

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

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

.

Наименьший положительный корень этого уравнения и даст нам значение .

Будем считать, что - малая величина, квадратом и высшими степенями которой можно пренебрегать. Имеем:

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

, .

Где матрица W - Якоби вектор-функции f.

Дальше, имеем:

.

Отсюда,

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

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

,

.

Описание алгоритма решения задачи:

1. Задают начальное приближение и точность расчёта

2. Рассчитывают

где

Проверяют условие остановки:

Если или (выбирают одно из условий), то j = j + 1 и переход к шагу 2.

Иначе и останов.

Применим градиентный метод к функции

. Тогда последовательные приближения будут выглядеть так:

Рис. 1

Рис. 2

Результат работы программы для модельной задачи:

Задаем функцию, а так же шаг и необходимую точность

Находим градиент функции

Задаем начальное приближение

Далее строим итерационную последовательность и находим значения переменных с необходимой степенью точности

Как мы видим, программа работает верно. Для наглядности построим график функции:

Рис. 3

Результат работы программы для функции

Задаем функцию, а так же шаг и необходимую точность

Находим градиент функции

Задаем начальное приближение

Далее строим итерационную последовательность и находим значения переменных с необходимой степенью точности

Результат работы программы для функции

Задаем функцию, а так же шаг и необходимую точность

Находим градиент функции

Задаем начальное приближение

Далее строим итерационную последовательность и находим значения переменных с необходимой степенью точности

Результат работы программы для функции

Задаем функцию, а так же шаг и необходимую точность

Находим градиент функции

градиентный метод листинг программа

Задаем начальное приближение

Далее строим итерационную последовательность и находим значения переменных с необходимой степенью точности

Листинг программы

> restart;

U:=x^2+y^2;

lambda:=0.1;

epsilon:=0.0001;

> Ux:= diff(U,x);

Uy:= diff(U,y);

> x:=1;

y:=2;

> N1:=Ux;

N2:=Uy;

> x:=x-lambda*N1;

y:=y-lambda*N2;

i:=1:

> N1:=Ux;

N2:=Uy;

x:=x-lambda*N1;

y:=y-lambda*N2;

> Nx:=max(N1,N2);

while (abs(lambda*Nx)>epsilon) do

N1:=Ux;

N2:=Uy;

x:=x-lambda*N1:

y:=y-lambda*N2:

Nx:=max(N1,N2);

i:=i+1:

end do:

> print(X=x,Y=y);

print(`kolli4estvo iteraciy`); i;

print(`zna4enie funkcii`); U;

Выводы

Численное решение нелинейных алгебраических уравнений является сложной и не до конца разрешимой задачей вычислительной математики.

При решении систем нелинейных уравнений иногда поступают следующим образом. Строится функционал, минимум которого достигается в решении системы. Затем, задавши начальное приближение к точке минимума, проводят итерации каким-либо из методов спуска. И таким путём получают удовлетворительное приближение к решению системы. Исходя из этого приближения, проводят уточнения при помощи какого-либо итерационного метода.

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

Список используемой литературы

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. - М.: Высш. шк., 1986.

2. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. - М.: Мир, 1985.

3. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. - М.: Энергоатомиздат, 1972.

4. Максимов Ю.А., Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. - М.: МИФИ, 1982.

5. Максимов Ю.А. Алгоритмы линейного и дискретного программирования. - М.: МИФИ, 1980.

6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - М.: Наука, 1970. - С. 575-576.

Размещено на Allbest.ru