Сделай Сам Свою Работу на 5

Метод деления отрезка пополам





 

Метод деления отрезка пополам является простейшим последовательным методом минимизации. Он позволяет для любой функции f(x)ÎQ[a, b] построить последовательность вложенных отрезков [a, b] É [a1,b1] É … É [an-1, bn-1] É [an, bn], каждый из которых содержит хотя бы одну из точек оптимума х* функции f(x).

Метод основан на делении текущего отрезка [а, b], где содер­жится искомый экстремум, на две равные части с последующим выбором одной из половин, в которой локализуется максимум в качестве следующего текущего отрезка. Экстремум локализуется путем сравнения двух значений критерия оптимальности в точ­ках, отстоящих от середины отрезка на e /2, где e — погрешность решения задачи оптимизации.

Если 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

n an bn f(an) f(bn) cn f(cn) |an-bn|
0 1,500 2,000 -89,438 -88,000 1,750 -92,121 0,500
1 1,500 1,750 -89,438 -92,121 1,625 -91,543 0,250
2 1,625 1,750 -91,543 -92,121 1,688 -92,033 0,125
3 1,688 1,750 -92,033 -92,121 1,719 -92,129 0,063
4 1,719 1,750 -92,129 -92,121 1,734 -92,138 0,031

В итоге получили: х* » 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

  n   an   bn     х1(n)   х2(n)   f(x1(n))   f(x2(n))   Примечания
0 1.5 2 0.25 1.74 1.76 -92.135 -92.096
1 1.5 1.76 0.13 1.62 1.64 -91.486 -91.696
2 1.62 1.76 0.07 1.68 1.70 -91.995 -92.084
3 1.68 1.76 0.04         точность достигнута

 

Следовательно, х* » 1,72, и f* » f (1.72) = - 92.13.

Пример 15.Методом деления отрезка пополам найти точку минимума х* функции

на отрезке [0.5; 1] с точностью e=0,05.

Решение. Сначала произведем вычисления, используя первый способ.

Таблица 8

 

n an bn f(an) f(bn) cn f(cn) |an-bn|
0 0,5 1 -3,591 -0,5 0,75 -2,439 0,5
1 0,5 0,75 -3,591 -2,439 0,625 -3,133 0,25
2 0,5 0,625 -3,591 -3,133 0,563 -3,395 0,125
3 0,5 0,563 -3,591 -3,395 0,531 -3,501 0,063
4 0,5 0,531 -3,591 -3,501 0,516 -3,548 0,031

 

Получаем, х* »0,516, и f* » f (0,516) = -3,548.

 

Решим этот же пример вторым способом. Для этого составим табл. 9:

Таблица 9

 

  n   an   bn     х1(n)   х2(n)   f(x1(n))   f(x2(n))   Примечания
0 0,5 1 0,25 0,74 0,76 -2,502 -2,374
1 0,5 0,74 0,12 0,61 0,63 -3,201 -3,109
2 0,5 0,63 0,065 0,555 0,575 -3,422 -3,448
3 0,5 0,575 0,0375         точность достигнута

 

Следовательно, х* »0,5375, и f* » f (0,5375) = -3,4814.

Пример 16. Дана функция f(x) = sin (x+1). Найти максимум на интервале [-1; 2] с точностью e=0,05.

Решение. Вычисления представим в виде табл. 10.

Таблица 10

n an bn f(an) f(bn) cn f(cn) |an-bn|
0 -1 2 0 0,1411 0,5 0,9975 3
1 0,5 2 0,9975 0,1411 1,25 0,7781 1,5
2 0,5 1,25 0,9975 0,7781 0,875 0,9541 0,75
3 0,5 0,875 0,9975 0,9541 0,6875 0,9932 0,375
4 0,5 0,6875 0,9975 0,9932 0,5938 0,9997 0,1875
5 0,5 0,5938 0,9975 0,9997 0,5469 0,9997 0,0938
6 0,5469 0,5938 0,9997 0,9997 0,5703 1 0,0469

 

Итак,

Решим этот же пример вторым способом. Для этого составим табл. 11:

Таблица 11

n an bn х1(n) х2(n) f(x1(n)) f(x2(n)) Примечания
0 -1 2 1,5 0,55 0,45 0,9998 0,9927
1 0,55 2 0,725 1,325 1,225 0,7288 0,7935
2 0,55 1,225 0,3375 0,9375 0,8375 0,9335 0,9646
3 0,55 0,8375 0,1438 0,7438 0,6438 0,9851 0,9997
4 0,55 0,6438 0,0469 точность достигнута

 

Следовательно, х* » 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] осуществляется двумя точками:

(3)

причем х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}, { }, n = 1, 2, …, следующим образом:

(5)

первая и вторая точки золотого сечения (3) отрезка [an-1; bn-1].

Для определения чисел an, bn, по найденным an-1, bn-1, необходимо выполнить следующие операции:

1) найти одну из точек золотого сечения отрезка [an-1; bn-1] по известной другой точке , используя формулы (4) или (3);

2) вычислить значение f(x) во вновь найденной точке золотого сечения;

3) сравнить значения и и найти an, bn, xn по формулам (5).

Таким образом, на каждом шаге определения an, bn и , n=2, 3, …, требуется вычисление одного значения f(x). Положив , найдем точку минимума х* с точностью en:

(6)

откуда следует, что число шагов n метода золотого сечения, обеспечивающее заданную точность e нахождения точки х*, должно удовлетворять неравенству:

(7)

Либо можно принять другое условие окончания поис­ка — величина отрезка, содер­жащего максимум, меньше за­данной погрешности.

Метод золотого сечения обеспечивает более быструю сходимость к реше­нию, чем многие другие ме­тоды, и применим, очевидно, только для одноэкстремальных функций, т.е. функций, содержащих один экстремум того типа, который ищется в задаче.

На рис. 18 приведены два этапа поиска максимума функ­ции методом золотого сече­ния: 1 – интервал, включающий в себя искомый максимум функции после первого этапа (первого золотого сечения в точках c и d); 2 – то же, после второго этапа (новая точка e и старая точка d).

 

Пример 17. Найти минимальное значение f* и точку минимума х* функции на отрезке [1.5; 2]. Точку х* найти с точностью e=0,05.

Решение.Вычисления проведем по формулам (5) представив результаты в табл. 12.

Таблица 12

 

n en an bn X1(n) x2(n) f(x1(n)) f(x2(n)) Примечание
1 0,309 1,500 2,000 1,691 1,809 -92,049 -91,814
2 0,191 1,500 1,809 1,618 1,691 -91,464 -92,049
3 0,118 1,618 1,809 1,691 1,736 -92,049 -92,138
4 0,073 1,691 1,809 1,736 1,764 -92,138 -92,084
5 0,045       1,736   -92,138

 

Первоначальные значения х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

n en an bn х1(n) x2(n) f(x1(n)) f(x2(n)) Примечание
1 0,309 0,5 1 0,691 0,809 -2,362 -2,287
2 0,191 0,5 0,809 0,618 0,691 -2,364 -2,362
3 0,118 0,5 0,691 0,573 0,618 -2,348 -2,364
4 0,073 0,573 0,691 0,618 0,646 -2,364 -2,368
5 0,045 0,646 -2,368

 

Следовательно, х* »0,646, и f* » f (0,646) = -2,368.

 

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.