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

Пусть дано уравнение

(14.7)

и при непрерывности .

Для нахождения корня уравнения (14.7), делим отрезок пополам.

Далее выбираем ту из половин , на концах которой функция имеет противоположные знаки. Новый отрезок

снова делим пополам и проводим то же рассмотрение.

В результате на каком-то этапе получаем или точный корень уравнения (14.7)

или бесконечную последовательность вложенных друг в друга отрезков ,

таких, что . (14.8) Очевидно, что . (14.9)

Так как левые концы образуют монотонную неубывающую ограниченную последовательность, а правые концы - монотонную не возрастающую ограниченную последовательность, то

.

.

корень уравнения.

Т.к. ,

то очевидно, что .

Метод половинного деления удобно применять для нахождения грубого значения корня данного уравнения. При увеличении точности значительно возрастает объем вычислительной работы.

Метод половинного деления легко реализуется на электронных счетных машинах. Программа вычисления составляется так, чтобы машина находила значение в середине каждого из отрезков и выбирала соответствующую его половину.

Пример. Методом половинного деления уточнить корень уравнения

, лежащий на отрезке .

Решение. Последовательно имеем:

За можно принять .

Метод хорд (метод пропорциональных частей)

Для нахождения корня уравнения , лежащего на заданном отрезке и удовлетворяющего условию имеется более быстрый способ.

Пусть . Заменим кривую на участке хордой, проходящей через точки

Из аналогичной геометрии мы знаем уравнение прямой проходящей через

точки : . У нас (см. рис. 13.8)

.

Точка пересечения хорды с кривой с осью имеет координаты

.

Подставим их в уравнение хорды при .

. (14.10)

Применяя этот метод к отрезку , получаем формулу

Многократное повторение приема приводит к итерационной формуле

Следует обратить внимание на то, что здесь неподвижен конец , а левые концы отрезков образуют ограниченную монотонно возрастающую последовательность

.

В случае же, когда неподвижен конец , последовательные приближения

образуют монотонно убывающую последовательность.

Сами приближения имеют вид

Т.е. итерационная формула сохраняет симметричный относительно неподвижного конца вид.

Существует такое правило:

1) неподвижен тот конец, для которого знак функции совпадает

со знаком ее второй производной ;

2) последовательные приближения лежат по ту сторону корня ,

где функция имеет знак, противоположный знак ее второй производной .

(Из математического анализа вспоминаем, что если , то функция обращена в точке выпуклостью вниз, если - то выпуклостью вверх).

Для оценки погрешности метода хорд можно воспользоваться формулой (14.6)

, где .

Можно привести еще одну оценку погрешности метода хорд:

.

Следовательно, как только будет обнаружено, что

< ,

где - заданная предельная абсолютная погрешность, то гарантировано, что

< .

Пример. Найти положительный корень уравнения

с точностью до 0, 002.