Математическое описание методов нахождения корней уравнения, Метод дихотомии - Исследование функции и ее производной

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

Этот алгоритм основан на том наблюдении, что график непрерывной функции должен пересечь ось абсцисс между двумя точками a и b как минимум один раз, если значения функции имеют в этих точках разные знаки (рис. 1).

первая итерация метода дихотомии

Рисунок 1 - Первая итерация метода дихотомии: x1 - средняя точка отрезка [a, b]

На этом наблюдении, основан алгоритм решения уравнения, называющийся методом дихотомии или методом деления пополам. Начиная с отрезка [a, b] на концах которого f(x) имеет разные знаки, алгоритм вычисляет среднюю точку

Xmid=(a+b)/2.

Если f(xmid)=0, корень найден, и алгоритм завершает работу. В противном случае он продолжает поиск корня либо на отрезке [a, xmid], либо на отрезке [xmid, b] - в зависимости от того, на какой из двух половин отрезка функция f(x) имеет разные знаки на концах нового отрезка.

Поскольку мы не можем ожидать, что алгоритм "наткнется" на точное решение уравнения и завершит работу, нужен иной критерий для его завершения. Можно остановиться, когда отрезок [an, bn], содержащий некоторый корень x*, станет столь мал, что можно гарантировать, что абсолютная ошибка приближения x* величиной xn (средней точкой отрезка) меньше некоторого заранее выбранного значения е>0. Поскольку xn - средняя точка отрезка [an, bn] и x* лежит внутри этого отрезка мы имеем

Следовательно, мы можем завершать работу алгоритма, как только (bn - an)/2<е, или, что то же самое,

Нетрудно доказать, что

Из этого неравенства следует, что последовательность приближений {xn} может быть сделана сколь угодной близкой к x* выбором достаточно большого значения n. Другими словами, мы можем сказать, что {xn} сходится к корню x*.

С помощью неравенства (3) можно заранее определить количество итераций, достаточное для достижения требуемой степени точности. Выбрав n достаточно большим, что бы выполнялось неравенство (b1 - a1)/2n<е, т. е.

,

Мы получим достаточное для обеспечения заданной точности количество итераций.

Основной недостаток метода деления пополам в качестве алгоритма общего назначения для решения уравнений заключается в его низкой скорости сходимости по сравнению с другими известными методами. Кроме того, его нельзя распространить на уравнения более общего вида и на системы уравнений. Однако у этого метода имеются и сильные стороны. Он всегда сходится к корню, каким бы ни был начальный отрезок. Этот метод не использует производную функции f(x), как это делают некоторые более быстрые методы.

Похожие статьи




Математическое описание методов нахождения корней уравнения, Метод дихотомии - Исследование функции и ее производной

Предыдущая | Следующая