2. Метод половинного деления

Метод половинного деления является более универсальным, всегда приводит к искомому результату, хотя и требует большого объема вычислений. Для нахождения корня уравнения f(x)=0, принадлежащего отрезку [a, b], делим отрезок пополам z = (a+b)/2 (см. рис. 5.12,а). Далее рассмотрим значения функции y = f(x) в точках x = a и x = z. Если значения f(a) и f(z) разных знаков, т. е. f(a) f(z) < 0, то исходный отрезок [a, b] уменьшим в два раза путем переноса точки x = b в точку x = z. Новый отрезок [a, b] вновь делим пополам (см. рис. 5.12,б) и так как f(a) f(z) < 0, то переносим точку x = a в точку x = z, уменьшая [a, b] в два раза. Повторяем указанную процедуру до тех пор, пока длина отрезка, содержащего корень, не станет меньше заданной погрешности ε. Любое значение является искомым значением корня, однако на практике в качестве корня выбирают середину отрезка, т. е.x = (a+b)/2.

При организации итерационного цикла вычисляется последовательность отрезков

[a₀, b₀], [a₁, b₁], …, [a_n, b_n], … ,

для которой

Для контроля точности вычисления корня можно использовать следующую последовательность значений

поэтому условие выхода из цикла

или условие продолжения цикла

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

y

f(z)

1. a

x^* z b

f(a)

a)

y

y=f(x)

0 a x^*

f(z) z b x

f(a)

b)

Рис. 5.12 Графическая иллюстрация

метода половинного деления

3. Метод касательных

Для обеспечения сходимости метода касательных (метода Ньютона) необходимо, чтобы производные f' (x) и f" (x) были определены, непрерывны и сохраняли постоянные знаки на отрезке [a, b]. На рис. 5.14 представлена геометрическая интерпретация метода Ньютона.

Выберем некоторую точку x₀ на отрезке [a, b] и проведем касательную к кривой y=f(x) в точке P₀(x₀, y₀). Ее уравнение

y = y₀ + f' (x₀)(x–x₀),

где y₀ = f(x₀).

Новое приближение корня х₁, равно абсциссе точки пересечения касательной с осью абсцисс, т. е.

y

y₀

y₁

y₂

Выберем некоторую точку x₀ на отрезке [a, b] и проведем касательную к кривой y=f(x) в точке P₀(x₀, y₀). Ее уравнение

y = y₀ + f' (x₀)(x–x₀),

где y₀ = f(x₀).

Новое приближение корня х₁, равно абсциссе точки пересечения касательной с осью абсцисс, т. е.

Проведя касательную через точку P₁(x₁, y₁), получим второе приближение корня x₂. Вычисление приближений корня по формуле

продолжается до выполнения неравенства

,

где ε – абсолютная погрешность определения корня уравнения.

Начальное приближение х₀ выбирают таким образом, чтобы выполнялось условие

В противном случае сходимость метода Ньютона не гарантируется. На практике выбирают x₀ = a или x₀ = b, в зависимости от того, в какой из этих точек выполняется указанное условие. Схема алгоритма уточнения корня методом Ньютона (методом касательных) приведена на рис. 5.15.