|
|
Метод деления отрезка пополам
Метод деления отрезка пополам является простейшим последовательным методом минимизации. Он позволяет для любой функции f(x)ÎQ[a, b] построить последовательность вложенных отрезков [a, b] É [a1,b1] É … É [an-1, bn-1] É [an, bn], каждый из которых содержит хотя бы одну из точек оптимума х* функции f(x).
Если f(х + e /2) > f(х - e /2), то максимум располагается на правой половине текущего отрезка [а, b] , в противном случае — на левой. Процесс поиска завершается при достижении отрезком [а, b] величины заданной погрешности e. К недостаткам метода относится его работоспособность только для одноэкстремальных функций f(х) (т.е. таких, которые содержат один экстремум того типа, который мы ищем в задаче), так как в других случаях при сравнении двух критериев в соседних точках невозможно правильно выбрать следующий интервал, где находится максимум. На рис. 17 приведены три этапа метода половинного деления. Сплошными вертикальными линиями отмечены середины отрезков, а пунктирными — вычисляемые значения критерия оптимальности слева и справа на e /2 от середин. Иллюстрация метода заключается в следующем: 1 – интервал, включающий в себя искомый максимум функции после первого этапа (первого деления пополам); 2, 3 – то же соответственно после второго и третьего этапов. Существует и другой вариант алгоритма, заключающийся в следующем. После нахождения середины отрезка (например, точка с1) в одной из половинок (допустим, в левой) находят среднюю точку (точка с2) и, сравнивая значения функции в этих точках, определяют, в какой из половинок находится экстремум. Если f(c1)<f(c2), то в качестве следующего отрезка выбираем отрезок [а, с1], если же f(c1)>f(c2), то берут новую точку в середине правой половины (точка с3) и в ней вычисляют функцию. В зависимости от сравнения значений функции в точках с3 и с1 выбирают новый отрезок [с1, b] или [с2, с3] и т.д. Второй вариант метода не имеет с точки зрения эффективности принципиального отличия от первого, так как эффективность принято оценивать по наихудшему варианту (т.е. по двум вычислениям f(x) на каждом шаге). В первом варианте метода есть одна особенность, которая его делает очень эффективным при экспериментальном отыскании экстремума (например, при автоматической настройке технических систем или при практическом поиске наилучших условий деятельности экономического объекта). Малые отклонения от текущей точки обеспечивают в процессе поиска отсутствие "шараханий", сопровождающихся резкими отклонениями состояния системы. Пример 14. Найти минимальное значение f* и точку минимума х* функции f(x)=x4+8x3-6x2-72х на отрезке [1.5; 2]. Точку х* найти с погрешностью e=0,05. Решение.1 способ. Вычисления представим в виде табл. 6. Таблица 6
В итоге получили: х* » 1.734 и f* » f (1.734) = - 92.138. В таблице an и bn являются концами отрезков, а сn – середина соответствующего отрезка, то есть Полагая Используя условие en ? e , из последнего выражения можно найти необходимое число шагов n для обеспечения требуемой точности e. Однако на практике часто поступают иначе: определив границы отрезка [an; bn], вычисляют en по формуле (**) и сравнивают с заданной точностью e. В нашем случае положим d=0,02 < 2e=0,1. Построим последовательность вложенных отрезков [an; bn] по рекуррентным формулам, записывая результаты вычислений в табл. 7: Таблица 7
Следовательно, х* » 1,72, и f* » f (1.72) = - 92.13. Пример 15.Методом деления отрезка пополам найти точку минимума х* функции Решение. Сначала произведем вычисления, используя первый способ. Таблица 8
Получаем, х* »0,516, и f* » f (0,516) = -3,548.
Решим этот же пример вторым способом. Для этого составим табл. 9: Таблица 9
Следовательно, х* »0,5375, и f* » f (0,5375) = -3,4814. Пример 16. Дана функция f(x) = sin (x+1). Найти максимум на интервале [-1; 2] с точностью e=0,05. Решение. Вычисления представим в виде табл. 10. Таблица 10
Итак, Решим этот же пример вторым способом. Для этого составим табл. 11: Таблица 11
Следовательно, х* » 0,5969, f* » 0.9997.
Метод золотого сечения
Метод золотого сечения также является последовательным методом минимизации. Опираясь на свойства золотого сечения отрезка, этот метод использует найденные значения f(x) более рационально, чем метод деления отрезка пополам, что позволяет переходить к очередному отрезку, содержащему точку х* после вычисления одного, а не двух значений f(x). Метод основан на делении текущего отрезка [a; b],где содержится искомый экстремум, на две неравные части, подчиняющиеся правилу золотого сечения, для определения следующего отрезка, содержащего максимум. Правило золотого сечения: отношение всего отрезка к большей его части равно отношению большей части отрезка к меньшей. Ему удовлетворяют две точки с и d, расположенные симметрично относительно середины отрезка: Путем сравнения f(с) и f(d) определяют следующий отрезок, где содержится максимум. Если f(d) > f(с), то в качестве следующего отрезка выбирается отрезок [с, b], в противном случае — отрезок [а, d]. Новый отрезок снова делится на неравные части по правилу золотого сечения. Следует отметить, что точка d является и точкой золотого сечения отрезка [с, b], т.е. Поэтому на каждой следующей итерации (кроме "запуска" метода на исходном отрезке) нужно вычислять только одно значение критерия оптимальности. Существуют аналитические формулы для расчета новой точки на отрезке, где находится максимальное значение f(x). Золотое сечение отрезка [a; b] осуществляется двумя точками: причем х1 есть вторая точка золотого сечения отрезка [a; x2], а х2 – первая точка золотого сечения отрезка [x1; b]. Зная одну из точек золотого сечения отрезка [a; b], другую можно найти по одной из формул x1 = a + b - x2, x2 = a + b – x1. (4) Пусть f(x) Î Q[a; b] и требуется найти точку минимума х* функции f(x) на [a; b]. Построим последовательности {an}, {bn}, { первая и вторая точки золотого сечения (3) отрезка [an-1; bn-1]. Для определения чисел an, bn, 1) найти одну из точек золотого сечения отрезка [an-1; bn-1] по известной другой точке 2) вычислить значение f(x) во вновь найденной точке золотого сечения; 3) сравнить значения Таким образом, на каждом шаге определения an, bn и откуда следует, что число шагов n метода золотого сечения, обеспечивающее заданную точность e нахождения точки х*, должно удовлетворять неравенству: Либо можно принять другое условие окончания поиска — величина отрезка, содержащего максимум, меньше заданной погрешности. Метод золотого сечения обеспечивает более быструю сходимость к решению, чем многие другие методы, и применим, очевидно, только для одноэкстремальных функций, т.е. функций, содержащих один экстремум того типа, который ищется в задаче.
Пример 17. Найти минимальное значение f* и точку минимума х* функции Решение.Вычисления проведем по формулам (5) представив результаты в табл. 12. Таблица 12
Первоначальные значения х1 и х2 находим по формулам (3), а значения точности e по формуле (6). Из таблицы получаем Заметим, что если воспользоваться формулой (7), то необходимое число шагов n можно определить заранее. В нашем случае n ? 4,79, т.е. n = 5, и отпадает необходимость во втором столбце табл. 12. Пример 18. Найти точку минимума х*и минимум f* функции f(x)=x2+3x(lnx-1) на отрезке [0.5; 1] с точностью e=0,05. Решение. Вычисления представим в табл. 13. Таблица 13
Следовательно, х* »0,646, и f* » f (0,646) = -2,368.
Не нашли, что искали? Воспользуйтесь поиском по сайту: ©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|
Метод основан на делении текущего отрезка [а, b], где содержится искомый экстремум, на две равные части с последующим выбором одной из половин, в которой локализуется максимум в качестве следующего текущего отрезка. Экстремум локализуется путем сравнения двух значений критерия оптимальности в точках, отстоящих от середины отрезка на e /2, где e — погрешность решения задачи оптимизации.
, находим х* с абсолютной погрешностью, не превосходящей величины
(**)
точность достигнута
на отрезке [0.5; 1] с точностью e=0,05.
точность достигнута
(3)
}, n = 1, 2, …, следующим образом:
(5)
необходимо выполнить следующие операции:
, используя формулы (4) или (3);
и 
и найти an, bn, xn по формулам (5).
, найдем точку минимума х* с точностью en:
(6)
(7)
На рис. 18 приведены два этапа поиска максимума функции методом золотого сечения: 1 – интервал, включающий в себя искомый максимум функции после первого этапа (первого золотого сечения в точках c и d); 2 – то же, после второго этапа (новая точка e и старая точка d).
на отрезке [1.5; 2]. Точку х* найти с точностью e=0,05.
