2.3.1. Приближённое решение уравнения f(x) = 0 методом деления пополам (методом бисекций).
Пусть задана непрерывная функция f(x) и требуется найти корень уравнения f(x) = 0. Предположим, что найден отрезок [a,b], такой, что f(a)f(b)<0. Тогда согласно теореме Больцано-Коши внутри отрезка [a,b] существует точка c, в которой значение функции равно нулю, т.е. f(с) = 0, сÎ(a,b). Итерационный метод бисекций состоит в построении последовательности вложенных отрезков.{[an,bn]| [an,bn]Ì [an-1,bn-1]Ì [a,b]}, на концах которых функция принимает значения разных знаков. Каждый последующий отрезок получают делением пополам предыдущего. Процесс построения последовательности отрезков позволяет найти нуль функции f(x) (корень уравнения f(x) = 0) с любой заданной точностью [10].
Опишем один шаг итераций. Пусть на (n-1)-м шаге найден отрезок [an-1,bn-1]Ì[a,b], такой, что f(an-1)f(bn-1) < 0. Делим его пополам точкой x = (an-1 + bn-1)/2 и вычисляем f(x). Если f(x) = 0, то x = (an-1 + bn-1)/2 – корень уравнения. Если f(x) ¹ 0, то из двух половин отрезка выбираем ту, на концах которой функция имеет противоположные знаки, так как один из корней лежит на этой половине. Таким образом,
an = an-1, bn = x, если f(x)f(an-1) < 0,
an = x, bn = bn-1, если f(x)f(an-1) > 0.
Если требуется найти корень с точностью до e, то деление пополам продолжается до тех пор, пока длина отрезка не станет меньше 2e. Тогда координата середины отрезка и есть значение корня с требуемой точностью e.
Метод бисекций – простой и надежный метод поиска простого корня (корень x = c называют простым корнем дифференцируемой функции f(x), если f(c) = 0 и f¢(c) ¹ 0) уравнения f(x) = 0. Он сходится для любых непрерывных функций f(x), в том числе и недифференцируемых. Скорость сходимости невелика. Для достижения точности e необходимо совершить N итераций, где N » log2((b-a)/e).
Это означает, что для получения каждых трёх верных десятичных знаков необходимо совершить около 10 итераций.
Если на отрезке [a,b] находится несколько корней уравнения f(x) = 0, то процесс сходится к одному из них. Метод неприменим для отыскания кратных корней чётного порядка. В случае корней нечётного порядка он менее точен [10].
Используя данный алгоритм легко написать функцию Bisect (f, a, b, eps, k) вычисления корня уравнения f(x) = 0, используя пакет MathCAD 2000.
f – искомая функция,
a, b – начало и конец интервала [a,b] соответственно,
eps – погрешность,
k – количество итераций.