Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Определение количества итераций при заданной точности




Сост. К.В. Демидов, А. В. Духанов

 

Владимир 2003


Сост: доц. Демидов, асс. Духанов

 

Методические указания к лабораторным работам по курсу лекций "Методы оптимизации" /Владим. гос. ун-т; Сост: К.В. Демидов, А.В. Духанов. Владимир, 2003.

 

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

Пособие предназначено для студентов, обучающихся по специальности «Прикладная математика».

 


Содержание

Лабораторная работа № 1. Минимизация функций одной переменной методами дихотомии и золотого сечения. 3

Лабораторная работа №2. Метод ломаных. 3

Лабораторная работа №3. Метод касательных. 3

Лабораторная работа №4. Градиентные методы.. 3

Лабораторная работа №5. Метод покоординатного спуска. 3

Лабораторная работа №6. Метод штрафных функций. 3

Список литературы.. 3

 

Лабораторная работа № 1. Минимизация функций одной переменной методами дихотомии и золотого сечения

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

Используя методы дихотомии и золотого сечения, найти на отрезке точку , в которой достигается минимальное значение унимодальной функции . Вычислить минимальное значение .

Теоретическая часть

Опр. 1. Функция является унимодальной на отрезке , если непрерывна на и , такие, что

1) строго монотонно убывает при (если );

2) строго монотонно возрастает при (если );

3) , при .

Случаи, когда один или два из отрезков вырождаются в точку, не исключаются.

Метод дихотомии (деления отрезка пополам)

Алгоритм

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

Определим точки по формулам:

(1)

Рис. 1. Определение точек и .

 

Найдем и сравним значения функции в точках . Здесь возможны два случая:

1) (см. рис. 1);

2) .

Определим новый отрезок в зависимости от того, какой из этих случаев имеет место. В первом случае концы отрезка (рис. 1) определяются следующим образом:

, (2)

во втором случае

(3)

Для нового отрезка заново вычисляются точки по формуле (1) и определяется очередной отрезок меньшей длины при помощи формул (2) или (3). Дальнейшие итерации выполняются аналогично. При этом в силу унимодальности функции искомая точка минимума принадлежит каждому из построенных отрезков.

Итерации по определениию отрезков продолжаются до тех пор, пока не будет достигнута заданная точность .

Определение количества итераций при заданной точности

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

. (5)

Учитывая необходимость достижения заданной точности , получаем, что количество требуемых итераций должно удовлетворять неравенству:

(6)

или

(7)

Метод золотого сечения

Алгоритм

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

Опр. 2. Золотым сечением отрезка называется деление отрезка на две неравные части так, чтобы отношение длины всего отрезка к длине большей части равнялось отношению длины большей части к длине меньшей части отрезка.

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

Точки золотого сечения обладают следующими свойствами, которые используются в методе золотого сечения:

1. Точка производит золотое сечение отрезка , так как и . Аналогично точка производит золотое сечение отрезка .

2. Для точек золотого сечения выполняется равенство:

(8)

Алгоритм метода золотого сечения заключается в следующем. Положим . На отрезке возьмем точки , производящие золотое сечение, и вычислим значения . Далее, если , то примем . Если же , то . Здесь важно то, что внутри нового отрезка уже содержится точка , которая производит золотое сечение этого отрезка. Причем, в этой точке уже известно значение функции . Длина отрезка

.

Опишем -й шаг алгоритма. Пусть уже определены точки , вычислены значения , найден отрезок такой, что , и известна точка , производящее золотое сечение отрезка , . Тогда в качестве следующей точки возьмем точку , которая в силу свойства (2) также производит золотое сечение отрезка . Вычислим значение . Пусть для определенности (случай рассматривается аналогично). Если , то полагаем ; если же , то . Новый отрезок таков, что , , точка производит золотое сечение отрезка и .

Определение количества итераций при заданной точности

После нахождения к-го отрезка в качестве приближенного значения к точке минимума можно взять точку . В этом случае погрешность решения, т.е. расстояние от точки до множества точек минимума оценивается сверху величиной, равной:

. (9)

Учитывая необходимость достижения заданной точности , получаем, что количество требуемых итераций должно удовлетворять неравенству:

(10)

или

(11)

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...