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


 

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

66399. ГЕНДЕРНА СПЕЦИФІКА СТАНОВЛЕННЯ ПРОФЕСІЙНОГО ІНТЕЛЕКТУ У СТУДЕНТІВ ВИЩОГО ТЕХНІЧНОГО НАВЧАЛЬНОГО ЗАКЛАДУ 183 KB
  Сучасному молодому фахівцю інженерної галузі необхідно вміти продуктивно та творчо розвязувати завдання й вирішувати виробничі проблеми виявляти здатність професійно інтелектуально розвиватися....
66400. РОЗВИТОК ТЕХНІЧНОГО МИСЛЕННЯ У МАЙБУТНІХ ВЧИТЕЛІВ ТЕХНОЛОГІЙ В ПРОЦЕСІ ВИВЧЕННЯ СПЕЦІАЛЬНИХ ДИСЦИПЛІН 252.5 KB
  Характер технічної оснащеності і наявних технологій у їх сукупності відображають рівень інтелектуального, духовного потенціалу суспільства, можливості самореалізації кожної людини. Безперечно, що підростаючому поколінню потрібно оволодівати знаннями про сутність технологічних перетворень навколишньої дійсності.
66401. КОНЦЕПТ ПРИРОДИ В ПОЕЗІЇ ВІЛЬЯМА БЛЕЙКА ТА ФЕДОРА ТЮТЧЕВА 157 KB
  Якщо йдеться про порівняння художніх світів англійця Блейка вільного митця й принципового нонконформіста та російського аристократа-царедворця Тютчева який намагався щиро сповідувати офіційну ідеологічну доктрину царату більше того порівняння письменників...
66402. СОЦІАЛЬНО-ПЕДАГОГІЧНА ПІДТРИМКА ОБДАРОВАНИХ ДІТЕЙ У ШКОЛАХ США 163 KB
  Проблема навчання й виховання обдарованих дітей набула особливого значення на порозі ХХІ століття. Навчання й виховання обдарованих дітей є надзвичайно важливими для створення підґрунтя розвитку інтелектуальних та творчих ресурсів суспільства будьякої держави зокрема України.
66403. Система самостійної роботи студентів-заочників філологічних факультетів педагогічних університетів 181 KB
  Упровадження інноваційних педагогічних технологій вимагає змін у підходах до організації навчального процесу вищої школи які передусім стосуються самостійної роботи студентів навчальних закладів ІІІ-ІV рівня акредитації.
66404. Теоретичне та експериментальне обґрунтування застосування сучасних гелеутворювачів природного та синтетичного походження у технології м’яких лікувально-косметичних засобів 1.71 MB
  Однак відомостей щодо її складу біологічної дії у науковій літературі практично немає що робить актуальним комплексне дослідження бодяги та розробку засобів місцевої дії на її основі для специфічного догляду та корекції патологічних станів шкіри.
66405. КЛЕЮЧІ РОЗЧИНИ НА ОСНОВІ СУХИХ ЗОЛОВМІСНИХ БУДІВЕЛЬНИХ СУМІШЕЙ З ДОБАВКАМИ ОРГАНО-МІНЕРАЛЬНИХ МОДИФІКАТОРІВ 2.25 MB
  Тонкошарова технологія нанесення клеючих розчинів і необхідність надання їм комплексу поліпшених будівельно-технічних властивостей обумовили їхнє модифікування добавками найбільш поширеними з яких є водоутримуючі та добавки редиспергованих полімерів.
66406. САНАТОРНО-КУРОРТНА РЕАБІЛІТАЦІЯ ХВОРИХ ПІСЛЯ ЕНДОПРОТЕЗУВАННЯ КУЛЬШОВОГО СУГЛОБА 1.99 MB
  Одним із найбільш актуальних та таких що швидко розвиваються методів лікування остеоартрозу є ендопротезування ЕП суглобів застосування якого призводить до запобігання стійкої втрати та більш повного відновлення працездатності хворих підвищення якості їх життя...
66407. ІНСТИТУТ АДВОКАТУРИ НА ЗАХІДНОУКРАЇНСЬКИХ ЗЕМЛЯХ ДРУГОЇ ПОЛОВИНИ ХІХ – ПОЧАТКУ ХХ СТОЛІТТЯ (НА МАТЕРІАЛАХ ГАЛИЧИНИ) 170.5 KB
  Зокрема проблеми функціонування інституту адвокатури а також права і обовязки адвокатів відображено у законі України Про адвокатуру від 19 грудня 1992 р. постанові Кабміну Про порядок оплати праці адвокатів з надання громадянам правової допомоги в кримінальних справах за рахунок держави від 14 травня 1999 р.