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

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

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

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

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

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

Искомые значения х₁ и х₂:

 

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

Х₂₌ А+(В-А)/2- Δх/2=А+(В-А+Δх)/2

 

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

 

Y₁=f(x₁) и Y₂=f(x₂)

 

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

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

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

3. При этом,если у₂>у₁, то у_max=y₁, ищется максимум функции у.

 

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

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

 

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

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

 

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

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

 

Программа

 

 

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