Работа №2 Метод делением отрезка пополам
Задание
1. Ознакомиться с методом и машинным алгоритмом метода одномерной оптимизации делением отрезка пополам.
2. Составить программу метода и отладить ее на контрольном примере.
3. Рассчитать по программе метода делением отрезка пополам экстремум заданной функции по варианту.
4. Произвести расчет экстремум функции для двух различных значений точности.
Методические указания
1. Описание метода оптимизации делением отрезка пополам приведено в разделе 3, тема 3. Согласно алгоритму метода начальный отрезок (а,b) делится пополам, определяется, в каком из полученных отрезков содержится экстремум целевой функции, и этот отрезок принимается за начальный, затем расчет повторяется. Особенностью метода является то, что величина шага меняется на каждом расчетном цикле, уменьшаясь в два раза.
Блок-схема расчетного алгоритма метода делением отрезка пополам приведена на рис. 25. В блок-схеме используются вспомогательные машинные переменные: h - текущее значение шага, логическая переменная – i, и рабочие ячейки x1 , x2 , x3 , xi , F1 , F2 , F3 , Fi , в которых хранятся текущие значения параметра оптимизации и значения целевой функции.
Ввести
F(х),
a, b,
е
Присвоить
х:=
a;
x1:=
a.
Вычислить
h:=
(в–а)/4;
х2
:=(а+в)/2;
F:=
F(х)
;
F2
:=F(x2
)
Вычислить
х1
:=
x2
– h,
х3
:=
x1
[2]+ h,
F1
:=F1
(x1
) F[3]=F(x[3])
Присвоить
i:=
1
Если
F1
[2] < F1
[i],
то присвоить i:=
2
Если
F1
[3] < F1
[i],
то присвоить i:=
3
Да
Нет
Если
h
> е
/2, то присвоить h:=
h/2,
x2
:=
x1
, F2
:=
Fi
Да
Печать
x[i],
F[i].
Конец
Рис. 25. Блок-схема расчетного алгоритма метода деления отрезка пополам.
2. На основании блок-схемы алгоритма составляется программа в Mathcad. Текст программы и отладочный пример приведены на рис. 26 (скриншот). Программа вводится согласно правилам, приведенным в разделе 3, и далее производится её отладка на примере целевой функции и параметров, приведенных на рис. 25. Также на рисунке дана графическая интерпретация целевой функции с целью контроля точки оптимума, полученного по расчетной программе и на графике.
3. Для выполнения задания по варианту ввести в программу функцию, соответствующую варианту задания, заданный интервал и точность, и затем произвести расчет точки минимума. Целевые функции и интервалы, на которых определяются экстремумы, а также заданное значение точности расчета приведены в таблице вариантов задания (см. табл.3).
Рассчитанное значение экстремума функции необходимо сопоставить (координаты точки экстремума) с точкой минимума на графике функции.
4. С целью оценки влияния точности на значение координаты точки минимума используется та же программа оптимизации методом делением отрезка пополам в MathCad, приведенная на рис.25. Необходимо увеличить на порядок значение точности, произвести расчет экстремума функции и сопоставить значение точки экстремума для двух различных значений точности.
Рис. 26. Программа и расчет оптимума целевой функции делением отрезка пополам.
Работа №3. Метод «золотого сечения»
Задание
1. Ознакомиться с алгоритмом машинного метода одномерной оптимизации метода «золотого сечения».
2. Составить программу метода и отладить ее на контрольном примере.
3. Рассчитать по программе метода «золотого сечения» экстремум заданной функции согласно варианту.
Методические указания
1. Метод одномерной оптимизации «золотого сечения» описан в разделе 3, тема3. В нем используется разбиение интервала области допустимых значений параметра оптимизации в пропорции «золотого сечения», которая определяется числами Фибоначчи – Ф1 Ф2. Расчет коэффициентов разбиения (чисел Фибоначчи) также приведен в разделе 3.
Пусть заданы параметр оптимизации х, область допустимых значений параметра (a,b), целевая функция F(x) и точность отыскания эстремума – e. Известно, что F(x) унимодальна на заданном интервале. Требуется найти экстремум (условились, что это минимум, п. 3) с заданной точностью.
Блок- схема машинного алгоритма метода «золотого сечения» приведена на рис. 27
2. Для выполнения задания ввести в программу функцию, соответствующей варианту задания и заданному интервалу, и произвести расчет точки экстремума с заданной точностью. Целевые функции и интервалы, на которых определяются экстремумы приведены в таблице вариантов задания (табл. 3). Рассчитанное значение точки минимума необходимо сопоставить с точкой минимума на графике функции.
3. С целью оценки влияния точности на точку минимума необходимо, увеличив точности на порядок, произвести расчет экстремума функции и сопоставить значение точки минимума для двух различных значений точности.
Ввести
F(х),
a, b,
е, Ф1,
Ф2
Присвоить
x1
:=
a
;
х4
:= b.
Вычислить
F1
= F(x2)
; F4
= F(x3)
Вычислить
x2
= x1
+ Ф1(x4
– x1)
, x3
= x1
+ Ф2(x4
– x1)
Вычислить
F2
= F(x2)
; F3
= F(x3)
Если
F2
> F3
?,
то
присвоить x1:=
x2
; F1:=
F2
Нет
Присвоить
x3:=
x4
; F3:=
F4
Если
(x3
– x2)
< е
/2, ?
Нет
Да
Печать
Xmin
= x3,
F(Xmin).
Конец
Рис. 27. Блок-схема расчетного алгоритма метода «золотого сечения».
Программа алгоритма метода в MathCad и расчета оптимума целевой функции для отладочного примера приведены на рис. 28.
Рис. 28. Программа алгоритма метода «золотого сечения» и отладочный пример.
Заметим, что в программе использованы вспомогательные рабочие ячейки f1 и f2 (см. рис. 28).