42799

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

Курсовая

Физика

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

Русский

2015-08-30

3.14 MB

52 чел.

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

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

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

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

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

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

Выполнил:

студент 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


 

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

23880. Сказание об Индийском царстве 27 KB
  Сказание рисует сказочный образ далекой Индии.все о чем человек может мечтать в повседневной жизниобеспеченностьбогатсвообилие всего вокругуверенность в настоящем и будущемвсе это представлено в сказочнопреувеличенном видеИоанн пишетчто он царь над царямии ему подченено 3300царейцарские палаты грандиозны и с земными не могут вступать в сравнениеинд царство населяют не только обычные людино и самые невероятные человеч существарогатыетрехногиемногорукие и тдфантастичен животный мирв Индии есть все и при это нет ни тятяворани...
23881. Литературно-этикетный канун жития. Житие Феодосия Печерского 29 KB
  Житие Феодосия Печерского.Житие ФЕОДОСИЯ ПЕЧЕРСКОГОПмятник древнерусской литературы написанный преподобным Нестором Летописцем.Одним из древнейших русских монастырей был киевопечерскийбольшую роль в истории монастыря сыграл его постриженика затем игуменФеодосийПамятник рассказывает о жизни игумена КиевоПечерского монастыря преподобного Феодосия начиная от его рождения прихода в монастырь до игуменства и смерти.Житие Феодосия Печерского типичное монашеское житие рассказ о благочестивом кротком трудолюбивом праведнике вся жизнь...
23882. Творчество Епифания Премудрого. Житие Стефана Пермского 22.5 KB
  Житие Стефана ПермскогоЕпифаний родился в Ростове в первой половине 14века.Перу Епифания принадлежат 2 жития:Житиве Стефана Пермского и Житие Сергия Радонежского.доводит литературноэтикетный канон до совершенствау него 2ой этапа 1ый этапутверждение канонаЖития Феодосия Печерского и Алексияпышность языкамножество ярких деталейндивид стильЕпифаний неск раз определяет характер писательского труда как плетение словессближение звуковой формы слова и его смыслаМножество повторовпричастных оборотовритмика речитрадиционные метафорыЕпиф...
23883. Творчество Епифания Премудрого.Житие Сергия Радонежского 26.5 KB
  На сороковой день мальчика принесли в церковь крестили и дали ему имя Варфоломей. Они быстро научились грамоте а Варфоломей не мог. Варфоломей рассказал ему о своих неудачах в учебе и попросил помолиться о нем. Старец дал отроку кусок просфоры и сказал что отныне Варфоломей будет даже лучше знать грамоту чем его братья и сверстникитак потом все и будетмотив исполнения желания Мальчик уговорил священника зайти к его родителям.
23884. Хождение за три моря Афанасия Никитина 55 KB
  Билет 36Билет 38Повесть о Петре и ФевронииПовесть о ПиФ была написана в 16 векев век второго монументализма хотя по содержанию и духу она ближе к 15 веку веку русского предвозрождения когда осознавалась ценность человека единство человека и Бога. Жена так и сделала и змей проговорился: Смерть мне суждена от Петрова плеча и от Агрикова мечаБыл у Павла брат Петр и он согласился помочь точнее ему на роду написано сразиться со змеем но где найти Агриков меч они не знают. Один раз Петр в одиночестве пришел в церковь и отрок показал...
23885. Повесть о Горе Злочастии 28.5 KB
  Обобщенная судьба герояДобрый молодец Добрый молодец отказывается от родовой позиции хочет жить своим умом.представляениям только он может менять личинуДобрый молодец верит архангелу все пропиваетснова беден. ЧЕРТЫ лит повести: писалось когда РусьРоссия Родовая позиция уходитмолодец хочет жить своим умом Столкновение этих 2ух позиций Гуманистическая концепцияноваторствосочувствие падшему человеку Появляются: элементы психологизации характеровсочувствие падшему человеку ощущение непостоянства жизни и ее непрочности Боязнь...
23886. Повесть о Савве Грудцыне 27.5 KB
  Месть брошенной женщиныварит зельесавва выпивает и влюбляется и начинает ее домогаться. Савва заболеваетхочет исповедоватьсяно бес не отпускает егоа Савва не хочет отдавать ему душуЭпизод с царством Сатаны:золотой дворец и крылатые юноши вокруг него. Автор сочувствует: Бедныйбедный Савва.
23887. Повесть о Фроле Скобееве 23.5 KB
  Повесть о Карпе Сутулове Сюжет:ЖенаТатьяна. Жена организует свой позор самостоятельно.Воевода велит им выплатить штраф:50010001500половину себе забирает а вторую отдает Татьяны Жена стоит на позции своим умом комическая повесть автор смеется над героями и над Татьяной Сатирическому обличению подвергается распутное поведение духовенства и именитого купечества.
23888. Основные свойства художественного текста 15.33 KB
  Следовательно одним из основных свойств художественного текста является его цельность или целостность. Целостность определяет смысл и восприятие текста в целом его общее воздействие на читателя. Источником смысловой целостности текста по стилистическому энциклопедическому словарю русского языка является экстралингвистический фактор обусловливающий многоплановую смысловую структуру текста.