Метод деления отрезка пополам

Метод секущих

Этот метод является модификацией метода Ньютона в плане его реализации, т. е. задача поиска корня связана лишь с вычислением значения функции f(x). Заменив производную f '(x_n) в методе Ньютона так называемой разделенной разностью по двум точкам x_n и x_n + h_n, где h_n – некоторый малый параметр, получим итерационную формулу

, n = 0, 1, 2, …, (3.9)

которая называется методом секущих.

Приближение x_n+1 является абсциссой точки пересечения секущей прямой, проведенной через точки (x_n, f(x_n)) и (x_n + h_n , f(x_n + h_n)) с осью х (рис. 3.6).

Имеются другие интерпретации формулы (3.9). В частности, метод Вегстейна,в котором для выбора параметра h используют предыдущую расчетную точку, т. е. берут h_n = x_n–1 – x_n, тогда (3.9) имеет вид

, n = 0, 1, 2, … . (3.10)

Рис. 3.6

Метод Вегстейна, очевидно, двухшаговый (m = 2), т. е. для вычисления требуется задать две начальные точки приближения, лучше всего x₀ = а; x₁ = b. Данный метод медленнее метода секущих, однако требует в два раза меньше вычислений f(x) и поэтому оказывается более эффективным.

Целесообразным является использовать подходы к уточнению корня, не выпускающие корень из выделенной «вилки» (отрезка [a, b]).

Так, если f(b)×f "(x) > 0 для x Î [a, b], берут в качестве x₀ = a, и уточнение ко­рня производится по формуле

, n = 0, 1, 2, …, (3.11)

а если f(a)×f "(x) > 0 для x Î [a, b], берут в качестве x₀ = b, и уточнение корня производится по формуле

, n = 0, 1, 2, … . (3.12)

Все вышеизложенные методы могут работать, если функция f(x) из (3.1) является непрерывной и дифференцируемой вблизи искомого корня, в противном случае решение не гарантируется. Данный метод может быть использован даже для разрывных функций.

Его алгоритм реализовывается согласно следующей рекуррентной последовательности: для x^*Î [a, b]; x₀ = a; x₁ = b, находится x₂ = (a + b) / 2.

Очередная точка x₃ выбирается, как середина того из смежных с x₂ интервалов [x₀, x₂] или [x₂, x₁], на котором находится корень. В результате получается следующий алгоритм метода деления отрезка пополам:

1) вычисляем y₀ = f(x₀);

2) вычисляем x₂ = (x₀ + x₁) / 2, y₂ = f(x₂);

3) если y₀ × y₂ > 0, то x₀ = x₂, иначе x₁ = x₂; (3.13)

4) если x₁ - x₀ > e, то повторяем с п. 1;

5) вычисляем x^* = (x₀ + x₁) / 2.

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

Немного подкорректировав, алгоритм (3.13) более наглядно можно представить в виде блок-схемы (рис. 3.7).

Рис. 3.7