Метод половинного деления

Самый простой из них – метод половинного деления, или иначе метод дихотомии. Метод дихотомии получил свое название от древнегреческого слова διχοτομία, что в переводе означает деление надвое. Его мы используем довольно часто. Допустим, играя в игру "Угадай число", где один игрок загадывает число от 1 до 100, а другой пытается его отгадать, руководствуясь подсказками "больше" или "меньше". Логично предположить, что первым числом будет названо 50, а вторым, в случае если оно меньше - 25, если больше - 75. Таким образом, на каждом этапе неопределенность неизвестного уменьшается в 2 раза. Т.е. даже самый невезучий в мире человек отгадает загаданное число в данном диапазоне за 7 предположений вместо 100 случайных утверждений.

Алгоритм метода половинного деления основан на теореме Больцано - Коши о промежуточных значениях непрерывной функции и следствии из неё.

Теорема Больцано - Коши: если непрерывная функция принимает два значения, то она принимает любое значение между ними.

Следствие (теорема о нуле непрерывной функции): если непрерывная функция принимает на концах отрезка положительное и отрицательное значения, то существует точка, в которой она равна 0.

Алгоритм:

1. Задать отрезок [a,b] и погрешность e.

2. Вычислить c=(a+b)/2

3. Определить интервал дальнейшего поиска: если f(a) и f(c) имеют разные знаки, т.е. f(a)*f(c)<0, то b:=c, в противном случае a:=c.

f(a)*f(c)<0 (да)	f(a)*f(c)<0 (нет)

4. Если длина нового отрезка , то вычислить значение корня c=(a+b)/2 и остановиться, в противном случае перейти к шагу 2.

Блок-схема метода половинного деления

Поиск по сайту: