Лабораторная работа №2
Исследование метода локализации экстремума
Функции одной переменной
Описание метода
Предположим, что задача состоит в определении положения экстремума функции одной переменной на интервале [a, b]. Для решения этой задачи разобъем весь интервал на N равных частей. На рисунке 2 показано такое разбиение для N=4, где на границах всех подынтервалов, включая конечные точки интервала [a, b], вычисляются значения функции R(x).
Среди полученных значений R(x(k)) (k=0,…,4) находится то, которое соответствует типу отыскиваемого экстремума. Например, при отыскании минимума функции R(x) (рисунок 2) наименьшее значение R(x(k)) среди вычисленных значений R(x(k)) (k=0,…,4) будет в точке x(3).
Далее выбирается новый интервал, включающий два подынтервала с наименьшим вычисленным значением функции R(x(k)) на их общей границе. На рисунке 2 таким интервалом является [x(2), x(4)]. Очевидно, что поскольку на границах нового интервала значение функции R(x) больше, чем в его середине, минимум расположен в интервале [x(2), x(4)]. Тем самым искомый минимум локализован в интервале, размеры которого в 2 раза меньше исходного.
Применяя к новому интервалу тот же прием разбиения и вычисляя значение R(x) на границах полученных подынтервалов, можно еще более сузить интервал, где находится искомый минимум. Повторяя эту процедуру достаточное число раз, получим необходимую точность определения положения оптимума.
Нетрудно показать, что наилучшие результаты поиска могут быть достигнуты в том случае, если используется разбиение на четыре подынтервала (N=4). При этом для каждого разбиения нужно вычислять значения целевой функции только в двух новых точках, так как ее значения на концах нового интервала и в его середине известны из предыдущих расчетов.
Абсолютная ошибка в нахождении положения экстремума с увеличением числа точек, в которых вычисляется значение целевой функции, определяется выражением
,
причем s – число расчетов значений целевой функции, которое в используемом методе может быть только нечетным. Так, при s=21 относительная ошибка в нахождении положения экстремума составляет:
x(0) x(1) x(2) x(3) x(4)
Рис. 2. Одномерный поиск методом
локализации экстремума
2.2 Описание блок-схемы алгоритма локализации
экстремума функции одной переменной
Приразработке блок-схемы алгоритмаприняты следующие обозначения: х(1)=х(0), х(2)=х(1),…, х(5)=х(4). Это связано с тем, что при организации итерационных и циклических процедур невозможно использовать обозначение х(0) из-за равенства нулю индекса при х. В блок-схеме рассмотрен пример нахождения экстремума для параболической функции R = ах2 + вх + с, имеющей один экстремум.
Для запуска алгоритма в блоке 1 (см. рисунок 3) предусмотрен ввод следующих переменных: параметры функции – а, в, с; заданные (начальные) концы интервала — х(1) и х(4); заданная точность расчета — ? (для оценки критерия окончания поиска). Здесь же производится присваивание начального значения счетчика шагов — n (количество расчетов функции цели – R), равного 5, так на первом этапе производится расчет в пяти начальных точках х(1), х(2),…, х(5).
В блоке 3 осуществляется расчет величины начального подынтервала — ?, значение которого образуется при делении первоначального интервала [х(1),х(5)] на четыре равных участка.
Блоки 4 и 5 служит для организации цикла (i=1,2,…,5) расчетов функции цели R во всех пяти начальных точках исходного интервала. На этом подготовительный этап алгоритма поиска минимума завершается и управления передается на блоки 6-20, где осуществляются итерационные процедуры поэтапной локализации минимума целевой функции R(x) с постепенным сокращением величины подынтервала — ?.
В блоке 6 производится присвоение (условное) переменной Rmin значения R(1) – величины функции цели в первой точке. В блоках 7-10 в цикле (i=2,…,5) осуществляется выбор наименьшего значения целевых функций из всех пяти их значений, рассчитанных ранее. При этом, если значение Rmin будет меньше чем очередное значение R(i) в i-ой точке, то в блоке 9 производится переприсвоение переменной Rmin меньшего значения R(i), а в блоке 10 осуществляется запоминание номера точки k = I, в которой значение функции оказалось меньшим, чем Rmin.
После завершения цикла при i=5 управление передается на блоки 11 и 13, где проверяется номер точки минимальной функции цели – k на принадлежность его либо первой точке, либо пятой точке. Дело в том, что
Рис. 3. Блок-схема алгоритма локализации экстремума
минимум функции должен находится внутри интервала [х(1),х(5)]. Если же минимум находится на границах интервала (в первой или пятой точке), то это говорит о том, что первоначальный интервал выбран неверно, и его необходимо расширить либо влево при k=1, либо – вправо, при k=5.
Если первоначальный интервал выбран правильно, то в блоке 15 производится переприсвоение значений самих точек и значений функций в этих точках. Блок 15 является одним из ключевых в алгоритме, так как именно здесь производится «сужение» исходного интервала, вокруг точки x(k) с минимальным значением целевой функции — R(k). При этом центральной точке (точка с номером – 3) присваивается значение x(k), а первой и пятой точкам (т.е. новым концам интервала) присваиваются значения соседних точек. Таким образом, производится локализация минимума внутри «нового» интервала, меньшей длины.
В блоке 16 рассчитывается значение величины «нового» подынтервала — ?, которое должно быть меньше, чем значение подынтервала в предыдущей итерации. В блоке 17 проверятся критерий окончания поиска, если ???, то поиск завершается с выдачей на печать найденной координаты точки с минимальным значением целевой функции – x(k), самого ее значения – R(k) и количества шагов поиска – n.
Так как в блоке 15 были определены значения функций цели в трех точках нового интервала (в первой, пятой и третьей), то в блоке 19 производится расчет координат оставшихся двух точек — х(2) и х(4), а также значений целевых функций в этих точках — R(2) и R(4). В блоке 20 счетчик шагов n увеличивается на два шага, так как в блоке 19 функция цели рассчитывалась дважды – для второй и четвертой точек.
Таким образом, в результате операций переприсвоения в блоке 15 и расчета значений целевых функций для двух точек в блоке 19, нам стали известны координаты всех пяти точек нового «сокращенного» интервала и значения целевой функции в каждой из этих точек. Причем на каждой итерации значения целевых функций рассчитывается только для двух точек, а не для пяти, что значительно ускоряет поиск экстремума. После чего управление передается вновь на блок 6 и итерация локализации экстремума повторяется до тех пор, пока значение величины подынтервала (критерия окончания поиска) — ? в очередной итерации не станет меньше заданной точности – ?.
Задание
1. Возьмите у преподавателя исходные данные: а, в, с, ?, х(1) и х(5).
2. Составьте программу в среде Matlab, реализующую алгоритм метода локализации экстремума (см. рисунок 3).
3. Найдите с помощью программы минимальное значение функции – R(k) и ее координату – x(k), также скорость сходимости алгоритма, т.е. число шагов – n.
4. Дополните программу, реализующую алгоритм рисунка 3, фрагментами, позволяющими вывести кривую R(x) с найденными R(k) и x(k).
5. Измените начальный диапазон (задайте начальные координаты х(1) и х(5)), как в сторону его увеличения, так и в сторону уменьшения. Проанализируйте полученные при этом результаты поиска.
6. Попробуйте сместить начало или конец начального диапазона за точку экстремума – x(k). Проверьте сработают ли при этом блоки 11 и 13.
7. Измените значение величины критерия окончания поиска – ? сначала в два раза больше, а затем в два раза меньше. Повторите расчеты и сравните полученные результаты с результатами, полученными в п.3.
8. Подготовьте отчет с анализом полученных результатов.
Контрольные вопросы
1. Насколько уменьшается интервал после каждой итерации локализации экстремума целевой функции?
2. Что предусмотрено алгоритмом в случае, если экстремум будет расположен за пределами первоначального интервала?
3. Объясните механизм выбора минимальной функции R(k) и соответствующей координаты х(k) в блоках 6-10?
4. Объясните почему в результате переприсвоений в блоке 15 новый интервал будет в два раза меньше интервала, рассчитанного на предыдущей итерации?
5. Почему в блоке 20 значение счетчика шагов увеличивается на две единицы?
6. В чем принципиальное отличие значений величины подынтервала – ?, рассчитанных по одинаковым формулам в блоках 2 и 16?
7. Почему в каждой итерации необходимо рассчитывать функцию цели дважды?
8. В каком блоке алгоритма производится расчет значений двух новых функций цели?
Таблица 3
Диапазон изменения исходных данных для локализации
экстремума функции одной переменной
| a | b | c | x(1) | x(5) | ? |
| -10; +10 | -10; +10 | -10; +10 | -10; +10 | -10; +10 | 0,01;0,001 |
Примечание: Конкретные значения исходных данных каждому студенту дает преподаватель в пределах указанных диапазонов.
