Метод половинного деления. Цель работы: овладеть навыками решения задачи поиска экстремума целевой функции методом половинного деления

Цель работы: овладеть навыками решения задачи поиска экстремума целевой функции методом половинного деления.

Метод половинного деления - это метод, согласно которому исходная длинна интервала поиска экстремума [A,B] на каждой итерации уменьшается почти вдвое, что обеспечивает эффективный поиск хопт.

Алгоритм метода включает следующие этапы:

· Определяет координаты точек х1 и х2, лежащих вблизи середины исходного интервала[A,B]

Для этого исходный интервал исследования делят пополам и от него в разные стороны откладывают отрезок х/2. Полученные точки ибудут соответствовать искомым х1 и х2. Значения х определяет наименьшую величину изменения аргумента. Процесс поиска оптимума представлен на рис 1.

Искомые значения х1 и х2 :

 

Х1=А+(В-А)/2- х/2=А+(В-А- х)/2

Х2= А+(В-А)/2- х/2=А+(В-А+х)/2

 

· Определяют значения целевой функции у1 и у2 для двух точек х1 и х2:

 

Y1=f(x1) и Y2=f(x2)

 

· Ищут новый исходный интервал поиска, в котором находится искомый оптимум хопт. Для этого используют свойства унимодальной функции:

1. Если у2у1, то А=х1 – отбрасывается интервал [A,x1];

2. Если у2у1, то B=х1 – отбрасывается интервал [x2,B];

3. При этом ,если у21, то уmax=y1, ищется максимум функции у.

 

· Проверяют условия окончания процесса поиска оптимума:

· Если (В-А)< х, то процесс поиска заканчивается.

 

1.Проверяют число выполненных итераций i. Если число выполненных итераций I>N (максимальное допустимое), то процесс заканчивается, в противном случае переходят к началу алгоритма;

2. Если в методе прямого перебора эффективность поиска оптимума прямо пропорциональная числу расчетов, то по методу дихотомии она возрастает с ростом итераций экспоненциально. Отношения начального интервала поиска (В –А) к интервалу поиска (В-А)N после итераций приблизительно равна 2N/2, то есть

 

В-А/(В-А)N=2N/2

Если для метода прямого перебора требуется 1000 вычислений, то для метода дихотомии только 20

 

Программа

 

 

Функция и график 1 функция