Методы одномерного поиска экстремума. Метод бисекции

Это один из простейших методов нахождения корней нелинейных уравнений. Он состоит в следующем. Допустим, что нам удалось найти отрезок [a,b], в котором расположено искомое значение корня x = c, т. е. a<c<b. В качестве начального приближения корня c принимаем середину этого отрезка, т. е. c0 = (a + b)/2. Далее исследуем значения функции F(x) на концах отрезков [a,c0] и [c0,b], т. е. в точках a, c0, b. Тот из них, на концах которогоF(x) принимает значения разных знаков, содержит искомый корень;

поэтому его принимаем в качестве нового отрезка. Вторую половину отрезка [a,b], на которой знак F(x) не меняется, отбрасываем. В качестве первой итерации корня принимаем середину нового отрезка и т. д. Таким образом, после каждой итерации отрезок, на котором расположен корень, уменьшается вдвое, т. е. после nитераций он сокращается в 2n раз.

Рис. 1.

Пусть для определенности F(a)<0, F(b)>0 (рис. 1). В качестве начального приближения корня примем c0 = (a + b)/2. Поскольку в рассматриваемом случае F(c0)<0, то c0 < c < b, и рассматриваем только отрезок[c0,b]. Следующее приближение: c1 = (c0 + b)/2. При этом отрезок [c1,b] отбрасываем, посколькуF(c1)>0 и F(b)>0, т. е. c0 < c < c1. Аналогично находим другие приближения: c2 = (c0 + c1)/2 и т. д.

Итерационный процесс продолжаем до тех пор, пока значение функции F(x) после n-й итерации не станет меньшим по модулю некоторого заданного малого числа e, т. е. . Можно также оценивать длину полученного отрезка: если она становится меньше допустимой погрешности, то счет прекращается.

Метод деления отрезка пополам довольно медленный, однако он всегда сходится, т. е. при его использовании решение получается всегда, причем с заданной точностью. Требуемое обычно большее число итераций по сравнению с другими методами не является препятствием к применению этого метода, если каждое вычисление значения функции F(x) несложно.

Поиск по сайту: