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


 

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

24537. Системы программирования: состав систем программирования. Этапы разработки ПО 124.23 KB
  Современные системы программирования как правило представляют собой интегрированную среду разработки integrated development environment – IDE к компонентам которой относятся следующие программные средства: текстовый редактор editor предназначенный для создания текстов исходной программы на языке высокого уровня ЯВУ или ассемблере макроассемблере; компилятор compiler – составитель предназначенный для трансляции перевода исходного текста входной программы в эквивалентную ей выходную программу объектный код на языке нижнего...
24538. Виды ресурсов вычислительной системы 14.16 KB
  Ресурсы запрашиваются используются и освобождаются процессами. По форме реализации различают: аппаратные ресурсы Hard; программные ресурсы Soft; информационные ресурсы. По способу выделения ресурса различают: неделимые ресурсы – предоставляются процессу в полное распоряжение; делимые ресурсы – предоставляются процессу в соответствии с запросом на требуемое количество ресурса. Делимые ресурсы в свою очередь можно разделить на те которые могут использоваться процессами одновременно или попеременно.
24539. Структура и виды программного обеспечения (ПО). Характеристика системного ПО 15.33 KB
  ПО Прикладное Операционные системы Система управления файлами Операционные оболочки Утилиты Системы программирования Базы данных САПР Электронные таблицы Издательские системы ПО для математических расчетов Системное Рис. Cистемное ПО можно разделить на следующие группы: операционные системы ОС; системы управления файлами; операционные оболочки; утилиты; системы программирования. Современные системы программирования представляют собой интегрированную среду разработки IDE объединяющую редактор текста компилятор языка...
24540. Классификация ОС 13.63 KB
  Примером таких ОС является семейство Windows и Linux. Среди ОС специального назначения можно выделить следующие разновидности: ОС для карманных компьютеров сотовых телефонов и другой бытовой техники например PalmOS и Windows CE Consumer Electronics – бытовая электроника; ОС для встроенных систем телевизоров СВЧ печей стиральных машин и т. По режиму обработки задач различают однозадачные например MSDOS MSX и многозадачные ОС OC EC OS 2 UNIX Windows. По способу взаимодействия пользователя с системой различают...
24541. Назначение и основные функции операционной системы (ОС) для автономного компьютера 13.74 KB
  Назначение и основные функции операционной системы ОС для автономного компьютера.2 Операционные системы для автономного компьютера Операционная система компьютера представляет собой комплекс взаимосвязанных программ который действует как интерфейс между приложениями и пользователями с одной стороны и аппаратурой компьютера с другой стороны. В соответствии с этим определением ОС выполняет две группы функций: предоставление пользователям и программистам вместо реальной аппаратуры компьютера расширенной виртуальной машины с которой удобней...
24542. Сетевые операционные системы: функциональные компоненты и варианты построения 46.02 KB
  Сетевые операционные системы: функциональные компоненты и варианты построения.3 Сетевые операционные системы. Различают сетевые и распределенные ОС. Распределенная ОС предоставляет пользователю сетевые ресурсы в виде ресурсов единой централизованной виртуальной машины.
24543. Одноранговые и серверные операционные системы 79.16 KB
  В зависимости от того как распределены функции между компьютерами сети они могут выступать в трех разных ролях: выделенный сервер сети – компьютер обслуживающий запросы других компьютеров т. В одноранговых сетях рабочих группах на все компьютеры устанавливается такая ОС которая предоставляет всем компьютерам в сети потенциально равные возможности. Схема одноранговой сети При потенциальном равноправии всех компьютеров в одноранговой сети часто возникникает функциональная несимметричность которая обусловлена тем что одни компьютеры...
24544. Принципы построения ОС 15.76 KB
  Принципы построения ОС.1 Принципы построения ОС. Однако в их основу положены общие принципы перечисленные ниже. Принцип модульности.
24545. Виды программных модулей 48.36 KB
  никакие внешние события не могут прервать работу модуля и он непрерывно выполняется от начала до конца. Структура привилегированного модуля приведена на рис. Структура привилегированного модуля Непривилегированные модули – это обычные программные модули которые могут быть прерваны во время своей работы.2 приведен пример использования реентерабельного модуля В процессами А и С.