8.3.4. Метод деления отрезка пополам (вилки, дихотомии)

Идея метода состоит в том, что на каждой итерации в качестве очередного приближения к корню выбирается середина отрезка [a,b](рис. 52), а в качестве нового отрезка для выбора следующего приближения принимается та половина исходного, на концах которого функцияf(х)имеет разные знаки:

[a, x], если sign (f(x))  sign (f(а)), т. е. f(x) f(a) < 0,

[x, b], если sign (f(x))=sign (f(а)), т. е. f(x)  f(a) > 0.

Рис. 52. Метод дихотомии

Таким образом, получается последовательность вложенных отрезков, левые границы которых образуют неубывающую последовательность а_k, правая – невозрастающую последовательностьb_k. При неограниченном увеличении числа итерацийkэти последовательности сходятся к общему пределу: последовательностьa_k слева и последовательностьb_k– справа. Значение предела является точным значением корнях*.

Сужение исходного отрезка до размеров требуемой точности b_k – a_k2 позволяет определить приближенное значение корня:

.

Метод половинного деления требует только информации о значении функции. Для него не нужно условие сходимости, но метод дихотомии относительно медленный, т. е. заданную степень точности можно получить за большее количество итераций, чем при использовании других методов. Блок-схема метода представлена на рис. 53.

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

Общая стратегия метода состоит в замене на каждой итерации функции f(x)приближенной линейной зависимостью.

Замена функции прямой, т. е. её линеаризация, проводится следующим образом. Пусть имеется такое приближение х^(k-1)к корню уравнения, что оно отличается от точного решения на достаточно малую величинуh^(k):

x*=x^(k-1) + h^(k) ,

тогда функция f(x)в окрестности точких^(k-1) может быть разложена в ряд Тейлора

Т. к. f(x*)0, то, ограничиваясь линейными относительноhчленами разложения, можно получить формулу для приближенного расчета шагаh^(k):

. (61)

Значение h^(k)не точно. Тем не менее, оно дает новое приближение

х^(k)=x^(k-1) + h^(k) , (62)

которое расположено ближе к корню, чем предыдущее. Тогда из новой точки x^(k)можно сделать еще один шаг для дальнейшего уточнения значения корня по той же методике. В результате организуется итерационный алгоритм поиска корня уравнения из выбранной некоторым образом точки начального приближениях⁽⁰⁾.

Рис. 53. Алгоритм поиска корня уравнения методом дихотомии

Вычисления заканчиваются тогда, когда два последовательных приближения различаются на величину, не превышающую заданной точности , т. е.

или . (63)

В геометрической интерпретации производная определяет тангенс угла наклона касательной к функции (рис. 54). Поэтому значениеh^(k)(61) можно также получить из прямоугольного треугольника, образующегося с помощью касательной.

Рис. 54. Геометрическая интерпретация метода Ньютона

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

Однако если касательные проводить из точки a, то уточнение корня не будет происходить.

Рассмотрим другой возможный график функции (рис. 55). В этом случае проводить касательные нужно из точки a.

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

Если f’(x)_* f (x) > 0 илиf(b)_* f(x) > 0, где x [a, b], то процесс поиска начинается с точкиb.

Если f’(x)_* f (x) < 0  xилиf(а)_* f(x) > 0, то процесс поиска начинается с точкиа.

Рис. 55. Возможное поведение функции

Метод Ньютона требует информации о значении функции, ее первой и второй производной, т. е. большей, чем метод дихотомии. Но метод Ньютона теоретически обладает самой высокой скоростью сходимости. Кроме того, метод Ньютона не требует выполнения каких-либо условий сходимости последовательности x_k. Блок-схема реализации метода приведена на рис. 56.