Вычислительный алгоритм метода "Наискорейшего спуска" с тестированием на функции Розенброка - Отчет по практике

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


Аннотация к работе
Целью работы является создание программы, находящей экстремум функции с помощью метода наискорейшего спуска. Для минимизации функции в направлении градиента используются методы одномерной оптимизации, например, метод золотого сечения. Сходимость метода градиентного спуска зависит от отношения максимального и минимального собственных чисел матрицы Гессе в окрестности минимума (максимума). Алгоритм наискорейшего спуска реализует итерационную процедуру движения к минимуму из произвольно выбранной точки начального приближения в направлении наиболее сильного уменьшения функции, определенном в окрестности текущего значения аргумента минимизируемой функции. Такое направление противоположно направлению, задаваемому вектором градиента минимизируемой функции F(x1, . .В общем случае критерий выбора представляет собой компромисс между точностью приближения к точке экстремума, затратами ресурсов ЭВМ для этой цели и простотой требуемых аналитических выкладок (от которой зависят затраты времени разработчика на отладку). С целью сравнения эффективности различных алгоритмов разработаны специальные (т.наз. тестовые) функции, имеющие "неприятные" для методов поиска экстремума особенности.Общий алгоритм работы программы представлен в виде блок-схемы на рисунке 3.До начала работы программы нужно выбрать, каким методом будет находиться экстремум, далее ввести начальные значения: начальный шаг, необходимую точность и начальное приближение X01 и X02 (рисунок 3). Для вывода расчетных данных следует нажать кнопку «Показать расчет».При выполнении индивидуального задания была разработана программа нахождения экстремума параболоида и функции Розенброка.begin alpha:=(25*pi)/180; if f(x01,x02)<f(x1,x2) then begin chp1:=chp1-tmp1; chp2:=chp2-tmp2; d:=-d; x1:=x01 d*chp1; x2:=x02 d*chp2; end else begin x01:=x1; x02:=x2; x1:=x01 d*chp1; x2:=x02 d*chp2; end; if x1<x01 then begin a1:=x1; b1:=x01; end else begin a1:=x01; b1:=x1; end; if x2<x02 then begin a2:=x2; b2:=x02; end else begin a2:=x02; b2:=x2; end; begin if form2.Visible=false then begin form2.Visible:=true; button2.Caption:="Убрать рассчет"; end else begin form2.Visible:=false; button2.

План
Содержание

Введение

1. Математическая часть задачи

2. Тестовый расчет

2.1 Назначение тестовой функции и ее форма

3. Алгоритм работы программы

4. Руководство пользователя

Заключение

Список использованных источников

Приложение А

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

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

Сходимость метода градиентного спуска зависит от отношения максимального и минимального собственных чисел матрицы Гессе в окрестности минимума (максимума). Чем больше это отношение, тем хуже сходимость метода.

Методом наискорейшего спуска может быть найден минимум функции n переменных F(x1, . . . ,xn) или найдены решения системы уравнений вида: Fi(x1,x2, . . .,xn)=0, i=1, . . ,n.

Алгоритм наискорейшего спуска реализует итерационную процедуру движения к минимуму из произвольно выбранной точки начального приближения в направлении наиболее сильного уменьшения функции, определенном в окрестности текущего значения аргумента минимизируемой функции. Такое направление противоположно направлению, задаваемому вектором градиента минимизируемой функции F(x1, . . . ,xn)

1. Математическое описание

Основной целью программы является вычисление экстремума функции.

В методе наискорейшего спуска в качестве направления поиска минимума заданной функции выбирается вектор, направление которого противоположно направлению вектора градиента функции F(X), где X={x1, x2, x3, … xn}. Координаты этого вектора :

В математическом анализе доказывается, что вектор GRADF(X) характеризует направление наиболее быстрого возрастания функции. Поэтому вектор - GRADF(X) (антиградиента) является направлением наиболее быстрого ее убывания. Каждое последующее приближение получается из предыдущего смещением в направлении антиградиента функции F(X) (смотри рис.1).

Рис. 1

Задавшись начальным приближением X0, ищется следующее приближение с помощью реккурентного соотношения вида: , i=0,1,2…

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

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

Поиск прекращается при выполнении условия

, так как градиент в точке минимума функции = 0, а при приближенных вычислениях .

Вывод
При выполнении индивидуального задания была разработана программа нахождения экстремума параболоида и функции Розенброка.

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

Список литературы
Б. Банди, «Методы оптимизации» стр. 51 - 56.

В.В. Салмин, «Методы оптимального управления».

СТО СГАУ 02068410-004-2007. Общие требования к учебным текстовым документам. Самара 2007
Заказать написание новой работы



Дисциплины научных работ



Хотите, перезвоним вам?