Метод дихотомии или метод половинного деления
Метод дихотомии имеет свое название от древнегреческого слова , что в переводе означает деление надвое. Именно поэтому данные метод имеет еще второе название: метод половинного деления. Его мы используем довольно часто. Допустим, играя в игру «Угадай число», где один игрок загадывает число от 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| в пределах которого имеется один корень x1
На первой этапе вычисляется x0=(a+b)/2
Далее определеяется значение функции в этой точке: если f(x0)< 0, то [a,x0], если наоборот, то [x0,b],т.е происходит сужение интервала. Таким образом в результате формируется последовательность xi, где i — номер иттерации.
Вычисления прекращаются, когда разность b-a меньше требуемой погрешности.
Метод дихотомии пример
В качестве примера использования метода половинного деления найдем корень на интервале [0;1] уравнения x 3 -3*x+1=0 с точностью в 10 -3
Как видно из таблицы корнем является 0,347. Колличество иттераций равно 10. Условие завершения: a-b=0,0009< 10 -3
Метод половинного деления или метод дихотомии является наиболее простым для решения уравнения в численных методах.
Решение уравнения методом дихотомии — Решение уравнения методом половинного деления в Паскале.
1.3 Метод половинного деления (метод дихотомии)
Метод половинного деления основан на последовательном делении отрезка локализации корня пополам. Для этого выбирается начальное приближение к отрезку [a, b], такое, что f(a)×f(b), затем определяется знак функции в точке 
— середине отрезка [a, b]. Если он противоположен знаку функции в точке a, то корень локализован на отрезке [a, c], если же нет – то на отрезке [c, b]. Схема метода дихотомии приведен на рисунке 2. 
Рисунок 2. Последовательное деление отрезка пополам и приближение к корню 
Алгоритм метода дихотомии можно записать так: 1. представить решаемое уравнение в виде 
2. выбрать a, b и вычислить 
3. если f(a)×f(с)
Пример решения уравнения методом дихотомии
Найти решение заданного уравнения методом дихотомии с точностью до 10 -5 . Пример создания расчетной схемы на основе метода дихотомии на примере уравнения: 
на отрезке [1, 2] Данный метод заключается в проверке на каждой итерации условия: если f(a)×f(с)и выбор соответствующего отрезка для следующей итерации.
 a) |
 |
| b) |
Рисунок 3. Последовательность итераций метода дихотомии при поиске корня уравнения 
на отрезке [1, 2] a) схема расчета (зависимые ячейки); b) режим отображения формул; Для нашего примера итерационная последовательность для нахождения решения принимает вид: 
Точность до пятой значащей цифры достигается за 20 итераций. Скорость сходимости этого метода является линейной. При выполнении начального условия он сходится к решению всегда. Метод половинного деления удобен при решении физически реальных уравнений, когда заранее известен отрезок локализации решения уравнения.
2 Решение уравнений, используя “Подбор параметра”
- Производится табулирование функции в диапазоне вероятного существования корней;
- По таблице фиксируются ближайшие приближения к значениям корней;
- Используя средство Excel Подбор параметра, вычисляются корни уравнения с заданной точностью.
2.1 Пример решения уравнения, используя “Подбор параметра”
Например, найдем все корни уравнения 2x3-15sin(x)+0,5x-5=0 на отрезке [-3 ; 3]. Для локализации начальных приближений необходимо определить интервалы значений Х, внутри которых значение функции пересекает ось абсцисс, т.е. функция меняет знак. С этой целью табулируем функцию на отрезке [–3; 3] с шагом 0,2, получим табличные значения функции. Из полученной таблицы находим, что значение функции трижды пересекает ось Х, следовательно, исходное уравнение имеет на заданном отрезке все три корня.
 |
 |
Рисунок 4. Поиск приближенных значений корней уравнения Выполните команду меню Сервис/Параметры, во вкладке Вычисления установите относительную погрешность вычислений E=0,00001, а число итераций N=1000, установите флажок Итерации. Выполните команду меню Сервис/Подбор параметра. В диалоговом окне (рисунок 9) заполните следующие поля:
- Установить в ячейке: в поле указывается адрес ячейки, в которой записана формула правой части функции;
- Значение: в поле указывается значение, которое должен получить полином в результате вычислений, т.е. правая часть уравнения (в нашем случае 0);
- Изменяя значение: в поле указывается адрес ячейки (где записано начальное приближение), в которой будет вычисляться корень уравнения и на которую ссылается формула.
Рисунок 5. Диалоговое окноПодбор параметрадля поиска первого корня После щелчка на ОКполучим значение первого корня-1,65793685. Выполняя последовательно операции аналогичные предыдущим, вычислим значения остальных корней: -0,35913476 и 2,05170101.
Метод дихотомии в Excel
Чтобы отыскать предварительные интервалы, строим график функции.
Как видно, первый корень лежит в интервале [-2;2], второй корень функции находится в интервале [2;4].
Уточним интервалы, в которых будут находиться корни уравнения. Для этого исходный интервал [2;4] разобьем на 10 подынтервалов.
h5 = 2 + 5*(4-2)/10 = 3
h6 = 2 + (5+1)*(4-2)/10 = 3.2
Поскольку F(3)*F(3.2)Итерация 1.
Находим середину отрезка: c = (3 + 3.2)/2 = 3.1
F(c) = 0.13
F(x) = 0.42
Поскольку F(c)•F(x) > 0, то a=3.1
Итерация 2.
Находим середину отрезка: c = (3.1 + 3.2)/2 = 3.15
F(c) = -0.0265
F(x) = 0.13
Поскольку F(c)•F(x) < 0, то b=3.15
Итерация 3.
Находим середину отрезка: c = (3.1 + 3.15)/2 = 3.13
F(c) = 0.0518
F(x) = 0.13
Поскольку F(c)•F(x) > 0, то a=3.13
Итерация 4.
Находим середину отрезка: c = (3.13 + 3.15)/2 = 3.14
F(c) = 0.0128
F(x) = 0.0518
Поскольку F(c)•F(x) > 0, то a=3.14
Остальные расчеты сведем в таблицу.
| N | c | a | b | f(c) | f(x) |
| 1 | 3.1 | 3 | 3.2 | 0.1289 | 0.1289 |
| 2 | 3.15 | 3.1 | 3.2 | 0.1289 | -0.02648 |
| 3 | 3.125 | 3.1 | 3.15 | 0.05185 | 0.05185 |
| 4 | 3.1375 | 3.125 | 3.15 | 0.01284 | 0.01284 |
| 5 | 3.1438 | 3.1375 | 3.15 | 0.01284 | -0.00678 |
| 6 | 3.1406 | 3.1375 | 3.1438 | 0.00304 | 0.00304 |
| 7 | 3.1422 | 3.1406 | 3.1438 | 0.00304 | -0.00187 |
| 8 | 3.1414 | 3.1406 | 3.1422 | 0.000586 | 0.000586 |
Ответ: x = 3.14; F(x) = 0.000586
Количество итераций, N = 8
Параметр сходимости.
Метод половинного деления (метод дихотомии или метод бисекции)
Данный метод описывает алгоритм нахождение корней (нулей) функции. Чтобы найти минимум целевой функции методом дихотомии используйте этот калькулятор.
Считаем, что отделение корней произведено и на интервале [a,b] расположен один корень, который необходимо уточнить с погрешностью ε.
Итак, имеем f(a)f(b)1. Если |f(c)| < ε, то c – корень. Здесь ε - заданная точность.
2. Если f(c)f(a)3. Если f(c)f(b)Продолжая процесс половинного деления в выбранных подынтервалов, можно дойти до сколь угодно малого отрезка, содержащего корень ξ.
Так как за каждую итерацию интервал, где расположен корень уменьшается в два раза, то через n итераций интервал будет равен:
при этом an≤ξ≤bn, , .
В качестве корня ξ. возьмем =½(bn+an). Тогда погрешность определения корня будет равна (bn – an)/2. Если выполняется условие (bn–an)/2n+an).
см. более подробный алгоритм метода бисекции.
Теорема 2. Итерационный процесс половинного деления сходится к искомому корню ξ с любой наперед заданной точностью ε.
Доказательство: Рассмотрим последовательность чисел ξi являющихся приближением корня на i -ом шаге.
ξi=½(bi+ai), i=0,1.
где a0=a; b0=b; ai;bi — границы подынтервалов, в которых f(ai)f(bi)|ξ1— ξ0|, |ξ2— ξ1|, …, |ξn— ξn-1|.
Имеем |ξ1-ξ0|=½(b1+a1-b0-a0). Так как всегда имеем либо b1=b0, a1=½(b0+a0), либо a1=a0, b1=½(a0+b0), поэтому , если, b1=b0
либо , если a1=a0.
Повторяя аналогичные рассуждения и учитывая, что всегда выполняется соотношение либо bi=bi-1, ai=½(bi-1+ai-1), либо bi=½(bi-1+ai-1), ai=ai-1. Получим
;
;
, где a0=a, b0=b.
Отсюда видно, что какое бы малое число ε>0 мы ни задали, всегда можно найти такое n , что ч.т.д.
Графически метод дихотомии выглядит следующим образом
Сходимость метода дихотомии линейная с коэффициентом α=0,5. Покажем это.
Если в качестве xn брать an, то из формулы (6) мы можем записать , . Отсюда следует .
Отметим, что за 10 итераций (n=10) интервал уменьшается в 2 10 = 1024 ≈ 10 3 раз. За 20 итераций (n=2) уменьшается в 2 20 ≈ 10 6 раз.
- Решение
- Видео решение
Находим производную функции: y ‘ = 10x-4. Найдем нули функции методом дихотомии: y’=0.
Поскольку F(0)*F(10) Пример №2 . Методом дихотомического поиска найдите максимумы функций, пологая, что Δ=0,05.
f(x) = x*cos(x), 0 ≤x≤ π
Пример №3 . Методом бисекции найти решение нелинейного уравнения на отрезке [a,b] с точностью ε = 10 -2 . Выбрав полученное решение в качестве начального приближения, найти решение уравнения методом простой итерации с точностью ε = 10 -4 . Для метода простой итерации обосновать сходимость и оценить достаточное для достижения заданной точности число итераций.
sqrt(t)+x 2 = 10, a = 2.6, b = 3
Найдем корни уравнения: 
Используем для этого Метод половинного деления (метод дихотомии)..
Считаем, что отделение корней произведено и на интервале [a,b] расположен один корень, который необходимо уточнить с погрешностью ε.
Итак, имеем f(a)f(b) 1 /2(a+b) и вычисляем f(c). Проверяем следующие условия:
1. Если |f(c)| 1 /2 n (b-a)
В качестве корня ξ. возьмем 1 /2(an+bn). Тогда погрешность определения корня будет равна (bn – an)/2. Если выполняется условие:
(bn – an)/2 1 /2(an+bn).
Решение.
Поскольку F(2.6)*F(3) 0, то a=2.8
Итерация 2.
Находим середину отрезка: c = (2.8 + 3)/2 = 2.9
F(x) = 0.113
F(c) = -0.487
Поскольку F(c)•F(x) 0, то a=2.825
Остальные расчеты сведем в таблицу.
| N | c | a | b | f(c) | f(x) |
| 1 | 2.6 | 3 | 2.8 | -1.6275 | -0.4867 |
| 2 | 2.8 | 3 | 2.9 | -0.4867 | 0.1129 |
| 3 | 2.8 | 2.9 | 2.85 | 0.1129 | -0.1893 |
| 4 | 2.8 | 2.85 | 2.825 | -0.1893 | -0.3386 |
| 5 | 2.825 | 2.85 | 2.8375 | -0.3386 | -0.2641 |
| 6 | 2.8375 | 2.85 | 2.8438 | -0.2641 | -0.2267 |
Ответ: x = 2.8438; F(x) = -0.2267
Решение было получено и оформлено с помощью сервиса Метод Ньютона онлайн
Пример №2 . Локализовать корень нелинейного уравнения f(x) = 0 и найти его методом бисекции с точностью ε1 = 0,01. Выбрав полученное решение в качестве начального приближения, найти решение уравнения методом простой итерации с точностью ε2 = 0,0001. Для метода простой итерации обосновать сходимость и оценить достаточное для достижения заданной точности ε2 число итераций.