2015-04-01
655
Метод половинного деления (метод дихотомии), использующийся для решения задачи (1.1.1), относится к методам нулевого порядка и применяется для унимодальных на некотором начальном интервале (a, b) функций. Он предполагает выполнение двух этапов:
– отделение (локализация) положения локального минимума с целью построения начального интервала неопределенности D0 = (a, b) (в данной работе не рассматривается);
– последовательное уменьшение длины интервала неопределенности (этот этап отражает суть метода).
Уменьшение длины интервала неопределенности методом половинного деления осуществляется следующим образом. Пусть функция f (x) является унимодальной на интервале D0 = (a, b), содержащем х * Î (a, b) – точку искомого минимума функции f (x). Зададим достаточно малое число
e > 0, затем выберем симметрично относительно центра интервала D0 две пробные точки: x 1 = (b – a)/2 – e/2 и x 2 = (b – a)/2 + e/2. Число e определяет степень различимости этих точек. Построим очередной интервал неопределенности, который содержит точку минимума, используя свойства унимодальной на интервале D0 функции f (x). Очевидно, этот интервал неопределенности D1 будет совпадать с одним из интервалов: (а, x 2), (x 1, b) или (x 1, x 2). Следовательно, его возможная наибольшая длина êD1ê = (b – a)/2 + e/2.
|
|
|
Теперь приведем более формальное описание метода половинного деления. Пусть функция f (x) является унимодальной на интервале (a, b), заданы достаточно малые числа e > 0 и d > 0 – требуемая точность определения точки искомого минимума данной функции х * Î (a, b). Тогда метод половинного деления можно записать в виде следующего алгоритма.
1. Задать функцию f(x) и числа а, b, d > 0, e > 0.
2. Если b – a £ 2d Þ перейти к выполнению п. 8.
3. Вычислить с = (a + b)/2.
4. Задать х 1 = с – e/2 и х 2 = х 1 + e.
5. Вычислить f (x 1); f (x 2).
6. Если f (x 1) > f (x 2) положить a: = х 1.
Если f (x 1) < f (x 2) положить b:= х 2.
Если f (x 1) = f (x 2) положить a: = х 1; b: = х2;
7. Перейти к выполнению п. 2.
8. Положить х * = (a + b)/2. Процесс завершен.
Промежуточные результаты работы метода половинного деления удобно заносить в таблицу, аналогичную табл. 1.2.1.
Таблица 1.2.1
| Номер итерации | a | b | b – a | х 1 | х 2 | f (x 1) | f (x 2) |
| … | … | … | … | … | … | … | … |
| k |
Дадим общую характеристику метода половинного деления:
– всегда сходится к решению задачи (1.1.1);
– скорость сходимости метода практически линейная. На каждом шаге длина интервала неопределенности уменьшается, после k -го шага процесса она составляет не более (b – a)/2 k + (1 - 2 -k)e. Нетрудно подсчитать количество итераций, необходимых для уменьшения исходного интервала неопределенности в заданное количество раз. Например, чтобы уменьшить ее не менее чем в 100 раз, потребуется семь итераций;
|
|
|
– на каждом шаге требуется вычисление значений функции f (x)
в точках х 1 и х 2, которые расположены симметрично относительно центра текущего интервала неопределенности на расстоянии e друг от друга. Число e > 0 рекомендуется выбирать достаточно малым; практически оно ограничено снизу точностью производимых вычислений.
Таким образом, чтобы уменьшить длину исходного интервала неопределенности не менее чем в 100 раз, потребуется вычисление значения функции f (x) в 14 пробных точках. Для сравнения отметим, что можно
последовательно разместить внутри интервала неопределенности 99 точек с интервалом h = 0,01(b – a) и проанализировать значения функции в этих точках (так называемый пассивный поиск). В результате этих действий интервал неопределенности также будет уменьшен в 100 раз, но уже за счет 99 вычислений значений функции f (x). Следовательно, метод половинного деления является более эффективным, чем метод одновременного размещения большого количества пробных точек внутри исходного интервала неопределенности.
