- •Методические указания к лабораторным работам по курсу лекций "методы оптимизации" Сост. К.В. Демидов, а. В. Духанов
- •Определение количества итераций при заданной точности
- •Метод золотого сечения Алгоритм
- •Определение количества итераций при заданной точности
- •Задание к лабораторной работе
- •Варианты заданий
- •Контрольные вопросы
- •Лабораторная работа №2. Метод ломаных
- •Постановка задачи
- •Теоретическая часть
- •Сходимость и оценка погрешности метода
- •Оценка константы Липшица
- •Задание к лабораторной работе
- •Варианты заданий
- •Сходимость и оценка погрешности метода
- •Метод условного градиента Алгоритм
- •Сходимость метода и оценка погрешности
- •Задание к лабораторной работе
- •Варианты заданий
- •Контрольные вопросы
- •Сходимость метода и оценка погрешности
- •Задание к лабораторной работе
- •Варианты заданий
- •Сходимость метода
- •Задание к лабораторной работе
- •Варианты заданий
- •Список литературы
Метод золотого сечения Алгоритм
Метод золотого сечения от рассмотренного ранее метода отличается тем, что он позволяет решить задачу минимизации унимодальной на отрезке функции с требуемой точностью при меньшем количестве вычислений значений функции.
Опр. 2. Золотым сечением отрезка называется деление отрезка на две неравные части так, чтобы отношение длины всего отрезка к длине большей части равнялось отношению длины большей части к длине меньшей части отрезка.
Нетрудно проверить, что золотое сечение отрезка производится двумя точками и , расположенными симметрично относительно середины отрезка, причем .
Точки золотого сечения обладают следующими свойствами, которые используются в методе золотого сечения:
1. Точка производит золотое сечение отрезка , так как и . Аналогично точка производит золотое сечение отрезка .
2. Для точек золотого сечения выполняется равенство:
(8)
Алгоритм метода золотого сечения заключается в следующем. Положим . На отрезке возьмем точки , производящие золотое сечение, и вычислим значения . Далее, если , то примем . Если же , то . Здесь важно то, что внутри нового отрезка уже содержится точка , которая производит золотое сечение этого отрезка. Причем, в этой точке уже известно значение функции . Длина отрезка
.
Опишем -й шаг алгоритма. Пусть уже определены точки , вычислены значения , найден отрезок такой, что , и известна точка , производящее золотое сечение отрезка , . Тогда в качестве следующей точки возьмем точку , которая в силу свойства (2) также производит золотое сечение отрезка . Вычислим значение . Пусть для определенности (случай рассматривается аналогично). Если , то полагаем ; если же , то . Новый отрезок таков, что , , точка производит золотое сечение отрезка и .
Определение количества итераций при заданной точности
После нахождения к-го отрезка в качестве приближенного значения к точке минимума можно взять точку . В этом случае погрешность решения, т.е. расстояние от точки до множества точек минимума оценивается сверху величиной, равной:
. (9)
Учитывая необходимость достижения заданной точности , получаем, что количество требуемых итераций должно удовлетворять неравенству:
(10)
или
(11)
Задание к лабораторной работе
Разработать программу, реализующую оба описанных метода для функции ; найти её минимальное значение на отрезке [-100,100].
Варианты заданий
№ вар. |
|
|
|
№ вар. |
|
|
|
1 |
|
1 |
-0.85 |
16 |
|
-0.3 |
3.5 |
2 |
2 |
-0.65 |
17 |
-0.1 |
4.0 |
||
3 |
3 |
-0.45 |
18 |
0.2 |
4.5 |
||
4 |
4 |
-0.25 |
19 |
0.4 |
5.0 |
||
5 |
5 |
-0.05 |
20 |
0.8 |
5.5 |
||
6 |
6 |
0.15 |
21 |
|
0.2 |
-4.0 |
|
7 |
7 |
0.35 |
22 |
0.4 |
-3.4 |
||
8 |
8 |
0.55 |
23 |
0.6 |
-2.8 |
||
9 |
9 |
0.75 |
24 |
0.8 |
-2.2 |
||
10 |
10 |
0.95 |
25 |
1.0 |
-1.6 |
||
11 |
|
-1.5 |
1.0 |
26 |
1.2 |
-1.0 |
|
12 |
-1.3 |
1.5 |
27 |
1.4 |
-0.4 |
||
13 |
-1.1 |
2.0 |
28 |
1.6 |
-0.2 |
||
14 |
-0.9 |
2.5 |
29 |
1.8 |
0.8 |
||
15 |
-0.7 |
3.0 |
30 |
2.0 |
1.4 |