42799

Метод Флетчера-Ривса

Курсовая

Физика

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

Русский

2015-08-30

3.14 MB

55 чел.

Государственное образовательное учреждение высшего профессионального образования «Пермский государственный университет»

Механико-математический факультет

Кафедра процессов управления и

информационной безопасности

Курсовая работа по методам оптимизиции

Метод Флетчера-Ривса

Выполнил:

студент III курса

очной формы обучения

группы

Научный руководитель:

к.ф.-м.н., доцент кафедры ПУиИБ

Лутманов Сергей Викторович


Введение

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

Все описываемые градиентные методы основаны на итерационной процедуре, реализуемой в соответствии с формулой

Где  - текущее приближение к решению  ; - параметр, характеризующий длину шага; - направление поиска управляемых переменных x.Способ определения  и  на каждой итерации связано с особенностями применяемого метода. Рассмотрим простейшие градиентные методы.

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

Второйметод наискорейшего градиентного спуска, где величина шага  определяется для каждого значения k из условия:

,  .

Есть еще градиентные методы со своими особенностями определения направления поиска и величины шага на каждой итерации.

Более подробно рассмотрим метод Флетчера-Ривса. Относительно невысокий уровень требований к объему памяти ЭВМ делает метод Флетчера-Ривса и его модификации особенно полезным при решении задач большой размерности.

1. Градиентный метод Флетчера-Ривса

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

Пусть дана функция f(x), ограниченная снизу на множестве Rn и имеющая непрерывные частные производные во всех его точках.

Требуется найти локальный минимум функции f(x) на множестве допустимых решений X=Rn, т.е. найти такую точку , что f(x*)=min f(x).

Стратегия поиска

Стратегия метода Флетчера-Ривса состоит в построении последовательности точек {xk}, k=0,1,, таких, что f (xk+1)< f (xk), k=0,1,. Точки последовательности {xk} вычисляются по правилу:

x k + 1 = x k +t d k, k = 0,1,…;

d k =  +βk-1 d k -1;

d0 = ;

βk-1 = ;

Точка x0 задается пользователем, величину шага t выбираем постоянной.

Вычисление величины βk -1 обеспечивает для квадратичной формы построение последовательности Н-сопряженных направлений d0, d1,.., dk,. При этом в точках последовательности {xk} градиенты функции f(x) взаимно перпендикулярны.

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

Алгоритм

Шаг 1. Задать x0, ε1>0, ε2>0, M –предельное число итераций, t - длина шага. Найти градиент ;

Шаг 2. Положить k = 0;

Шаг 3. Вычислить ;

Шаг 4. Проверить выполнение критерия окончания ;

Шаг 5. Проверить условие :

  1.  если неравенство выполняется, то расчет окончен и  ;

б) если нет, то при k = 0 перейти к шагу 6, а при  перейти к шагу 7.

Шаг 6. Определить 

Шаг 7. Определить .

Шаг 8. Определить 

Шаг 9. Вычислить 

Шаг 10. Проверить выполнение условий

,  :

а) в случае выполнения обоих условий в двух последовательных итерациях с номерами k и k - 1 расчет окончен, найдена точка  ;

б) если не выполняется хотя бы одно из условий, полагаем  и переходим к шагу 3.

Тестовый пример

Применим градиентный метод Флетчера-Ривса для нахождения локального минимума функции:

Задаем начальные условия:

Величину шага  на каждой итерации определяем из следующего условия:

,  .

Текст программы, выполненной в системе Wolfram Mathematica,

Тестовый пример:

Найти локальный минимум функции  .

Задача оптимизации

Исследовать величину скорости и ускорения точки С на минимум по параметрам a, b, t.


Скорость:

Ускорение:


Литература

1. Лутманов С.В. Курс лекций по методам оптимизацииРХД Ижевск, 2001.

2. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. М: Высш. шк., 2005


 

А также другие работы, которые могут Вас заинтересовать

73194. Математические понятия 112.5 KB
  Понятия, которые изучаются в начальном курсе математику, обычно представляют в виде четырех групп. В первую включаются понятия, связанные с числами и операциями над ними: число, сложение, слагаемое, больше и др. Во вторую входят алгебраические понятия: выражение, равенство, уравнение и др.
73195. Охорона і захист права власності 85.33 KB
  Охорона власності - це вжиття власником різноманітних заходів, спрямованих на забезпечення цілісності свого майна, його схоронності від найрізноманітніших небажаних обставин: негоди, стихійного лиха, нападу зловмисника, дикого звіра тощо.
73196. Экология микроорганизмов 34.63 KB
  Данные биоценозы характеризуются относительным постоянством однако качественный и количественный состав микрофлоры организма человека меняется в течение жизни и зависит от пола возраста питания климата и др.
73197. Реальные газы и фазовые переходы 834 KB
  Учёт конечных размеров молекул и сил взаимодействия между ними позволяет ввести поправки в уравнение Менделеева-Клапейрона и получить уравнение состояния идеальных газов. Пересечение изобары с изотермой даёт точки с соответствующими параметрами состояния.
73198. Физика атомного ядра. Радиоактивность 290 KB
  Как уже известно современная физика установила что атом состоит из положительно заряженного ядра и окружающих его электронов. Каково же строение атомного ядра Ключом к изучению атомного ядра послужило открытие французского ученого А.
73199. Ядерные реакции. Искусственная радиоактивность. Элементарные частицы 272.5 KB
  Ядра атомов нельзя разрушить ни нагреванием до многих тысяч градусов, ни охлаждением до самых низких температур. Для разрушения ядер нужны значительные затраты энергии. Как же это осуществить? Чтобы ответить на этот вопрос, необходимо уяснить смысл ядерных реакций.
73200. Основы молекулярно-кинетической теории. Термодинамические параметры. Масса и размеры молекул 348 KB
  Все тела -– твёрдые жидкие и газообразные –- представляют собой совокупность большого числа атомов и молекул. При изучении свойств тел и физических явлений происходящих с телами возможны два направления исследований: а молекулярно-кинетическое устанавливает законы протекания различных...
73201. Идеальные газы 136.5 KB
  Используя выводы рассмотренных вопросов разберем основные законы для газов. Основные газовые законы. Из основного уравнения кинетической теории газов можно вывести все газовые законы ранее установленные экспериментально.
73202. Основы термодинамики, Связь теплоты и работы. Механический эквивалент тепла 134.5 KB
  Термодинамика, в отличие от статистической физики, не рассматривает конкретные молекулярные картины. На основании опытных данных формулируются основные законы (принципы или начала). Эти законы и их следствия применяются к конкретным физическим явлениям, связанным с превращением энергии...