Метод половинного деления.
Метод половинного деления является процедурой последовательного поиска. Используется стратегия выбора точек x1 и y1 на интервале [a1, b1], направленная на минимизацию максимумов из x1 - a1 и b1 - y1. Это может быть достигнуто расчетом точек x1 и y1, симметрично расположенных на расстоянии > 0 от середины интервала каждая. Здесь число > 0 настолько мало, чтобы длина нового интервала + (b1 - a1)/2 являлась достаточно близкой к значению (b1 - a1)/2 и в то же время, чтобы значения функций f(x1), f(y1) были различны.
Алгоритм метода половинного деления.
Начальный этап. Выбрать константу 2 > 0, допустимую конечную длину интервала l > 0, начальный интервал [a1, b1]. Задать k = 1 и перейти к основному этапу.
Основной этап. Шаг 1. Если bk - ak < l то остановиться; точка минимума принадлежит интервалу [ak, bk], иначе вычислить
xk = 
yk = 
и перейти к шагу 2.
Шаг 2. Если f(xk) < f(yk) то ak+1 = ak и bk+1 = yk. В противном случае положить ak+1 = xk и bk+1 = bk . Заменить k = k + 1 и перейти к шагу 1.
Пример расчета экстремума функции методом половинного деления.
Постановка задачи. Определить экстремум функции f(x)=x2-3x+2 на интервале [-10;10] с точностью l=0,03 и константой различимости =0,005 .
Результаты расчета с применением табличного процессора ECXEL по алгоритму, рассмотренному выше, представлены в таблице 2.3.
Таблица 2.3
Расчет экстремума функции f(x)=x2-3x+2 методом половинного деления.
№ |
аk |
bk |
xk |
yk |
f(xk) |
f(yk) |
|b-a| |
Критерий |
1 |
-10.000 |
10.000 |
-0.005 |
0.005 |
2.015 |
1.985 |
20.000 |
не достигнут |
2 |
-0.005 |
10.000 |
4.993 |
5.003 |
11.948 |
12.018 |
10.005 |
не достигнут |
3 |
-0.005 |
5.003 |
2.494 |
2.504 |
0.738 |
0.758 |
5.008 |
не достигнут |
4 |
-0.005 |
2.504 |
1.244 |
1.254 |
-0.185 |
-0.190 |
2.509 |
не достигнут |
5 |
1.244 |
2.504 |
1.869 |
1.879 |
-0.114 |
-0.106 |
1.259 |
не достигнут |
6 |
1.244 |
1.879 |
1.557 |
1.567 |
-0.247 |
-0.246 |
0.635 |
не достигнут |
7 |
1.244 |
1.567 |
1.401 |
1.411 |
-0.240 |
-0.242 |
0.322 |
не достигнут |
8 |
1.401 |
1.567 |
1.479 |
1.489 |
-0.250 |
-0.250 |
0.166 |
не достигнут |
9 |
1.479 |
1.567 |
1.518 |
1.528 |
-0.250 |
-0.249 |
0.088 |
не достигнут |
10 |
1.479 |
1.528 |
1.498 |
1.508 |
-0.250 |
-0.250 |
0.049 |
не достигнут |
11 |
1.479 |
1.508 |
1.488 |
1.498 |
-0.250 |
-0.250 |
0.030 |
достигнут |
Таким образом, при поиске экстремума функции f(x)=x2 -3x+2 методом половинного деления после десяти итераций и одиннадцати вычислений значений функции интервал неопределенности составил [1,479; 1,508]. При этом |b11 – a11|=0,030, что равно заданной величине l=0,3. Следует отметить, что искомый минимум находится в точке х*=1,5.