Уточнение корней до заданной точности.

То есть сужение отрезка локализации корня [a,b]. Рассмотрим несколько методов.

1) Метод половинного деления (дихотомии).

Пусть корень отделён и принадлежит отрезку . Находим середину отрезка по формуле (рис.3). Если , то с – искомый корень.

Если , то в качестве нового отрезка изоляции корня выбираем ту половину или , на концах которой принимает значения разных знаков. Другими словами, если , то корень принадлежит отрезку , если - отрезку . Полученный отрезок снова делим пополам, находим ,

Рис. 3.

Рис.3

Вычисляем , выбираем отрезок и т.д. Как только будет выполнено , то в качестве приближенного значения корня, вычисленного с точностью , можно взять .

После каждой итерации отрезок, на котором расположен корень уменьшается вдвое, то есть после n итераций он сокращается в 2ⁿ раз. Таким образом, число итераций n в данном методе зависит от предварительно заданной точности ε и от длины исходного отрезка и не зависит от вида функции f(x). Это является важным преимуществом метода половинного деления по сравнению с другими методами. Метод, однако, медленно сходится при задании высокой точности расчёта.

2) Метод хорд.

Пусть на отрезке [a,b] функция f(x) непрерывна и принимает на концах отрезка значения разных знаков, а производные f ′(x) и f ″(x) сохраняют постоянный знак на интервале (a,b). Тогда возможны четыре случая расположения дуги кривой (рис.4).

Рис.4.

В методе хорд за очередное приближение берём точку пересечения с осью Х прямой (рис.5), соединяющей точки (a,f(a)) и (b,f(b))

Причём одна из этих точек фиксируется − та, для которой знаки f(x) и f ″(x) одинаковы.

Для рис.5 неподвижным концом хорды является х =a.

Уравнение хорды АВ:

Точка пересечения хорды с осью Х (у=0): .

Теперь корень находится на отрезке [a,c₁]. Заменяем b на с₁.

Рис.5. Иллюстрация метода хорд.

Применяя метод хорд к этому отрезку, получим:

.

Продолжим и т.д., получим: (2) Условие окончания вычислений:

│с_n+1 − c_n│< ε или │f(c_n)│< ε₁.

Для оценки погрешности можно пользоваться общей формулой:

, где

Итак, если f (x)∙f″(x) > 0, то приближённое значение корня находят по формуле (2), если f′(x)∙f″(x) < 0 (т.е. фиксируется х = b), то по формуле:

. (3)

2) Метод Ньютона (касательных).

Пусть на отрезке [a,b] функция f(x) непрерывна и принимает на концах отрезка значения разных знаков, а производные f ′(x) и f ″(x) сохраняют постоянный знак на интервале (a,b).

Геометрический смысл метода касательных состоит в том, что дуга кривой

y = f(x) заменяется касательной к этой кривой.

Рис.7. Иллюстрация метода касательных.

Выберем в качестве начального приближения х₀ = a и проведём в точке А₀(a,f(a)) касательную к графику функции f(x). Абсцисса пересечения касательной с осью Ох (у = 0) является первым приближением к корню (рси.7):

или х₀ = .

Через точку А₁(х₁;f(x₁)) снова проведём касательную, абсцисса точки пересечения которой даст второе приближение х₂ корня ξ и т.д. Очевидно, что в точке А_n(x_n;f(x_n)):

y − f(x_n) = f ′(x_n)(x−x_n)

и алгоритм метода Ньютона запишется так:

(4)

Заметим, что в нашем случае, если положить х₀ = b и провести касательную к кривой у = f(x) в точке b, то первое приближение не принадлежит отрезку [a,b].

Таким образом, в качестве начального приближения х₀ выбирается тот конец интервала [a,b], для которого знаки f(x) и f ″(x) одинаковы.

Условие окончания вычислений:

│с_n+1 − c_n│< ε или │f(c_n)│< ε₁.

Для оценки погрешности можно пользоваться общей формулой

, где