 |
Определение количества итераций при заданной точности
|
|
|
|
Сост. К.В. Демидов, А. В. Духанов
Владимир 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)
|
|
|
