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

Метод дихотомии имеет свое название от древнегреческого слова , что в переводе означает деление надвое. Именно поэтому данные метод имеет еще второе название: метод половинного деления. Его мы используем довольно часто. Допустим, играя в игру "Угадай число", где один игрок загадывает число от 1 до 100, а другой пытается его отгадать, руководствуясь подсказками "больше" или "меньше". Логично предположить, что первым числом будет названо 50, а вторым в случае если оно меньше - 25, если больше - 75. Таким образом, на каждом этапе (иттерации) неопределенность неизвестного уменьшается в 2 раза. Т.е. даже самый невезучий в мире человек отгадает загаданное число в данном диапазоне за 7 предположений вместо 100 случайных утверждений.

Метод половинного деления в решении уравнения

Правильное решение уравнения методом половинного деления возможно лишь в том случае, если известно, что на заданном интервале имеется корень и он является единственным. Это совсем не означает что метод дихотомии может использоваться только для решения линейных уравнений. Для нахождения корней уравнений более высокого порядка методом половинного деления необходимо сначала отделить корни по отрезкам. Процесс отделения корней осуществляется путем отыскания первой и второй производной от функции и приравнивании их нулю f'(x)=0 и f''(x)=0. Далее определяются знаки f(x) в критических и граничных точках. Интервал, где функция меняет знак |a,b|, где f(a)*f(b)< 0.

Алгоритм метода дихотомии

Алгоритм метода дихотомии очень прост. Рассмотрим отрезок |a,b| в пределах которого имеется один корень x₁

На первой этапе вычисляется x₀=(a+b)/2

Далее определеяется значение функции в этой точке: если f(x₀)< 0, то [a,x₀], если наоборот, то [x₀,b],т.е происходит сужение интервала. Таким образом в результате формируется последовательность x_i, где i - номер иттерации.

Вычисления прекращаются, когда разность b-a меньше требуемой погрешности.

Метод дихотомии пример

В качестве примера использования метода половинного деления найдем корень на интервале [0;1] уравнения x³-3*x+1=0 с точностью в 10^-3

Как видно из таблицы корнем является 0,347. Колличество иттераций равно 10. Условие завершения: a-b=0,0009< 10^-3

Метод половинного деления или метод дихотомии является наиболее простым для решения уравнения в численных методах.

Скачать:

Решение уравнения методом дихотомии - Решение уравнения методом половинного деления в Паскале.