Уточнение корней.

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

1. Метод деления пополам (метод бисекций).

Пусть корень уравнения отделен и находится на отрезке . Итерационный метод бисекций состоит в построении последовательности вложенных отрезков , на концах которых функция принимает значения разных знаков. Каждый последующий отрезок получают делением пополам предыдущего. Процесс построения последовательности отрезков позволяет найти корень уравнения с любой заданной точностью.

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

, если ,

, если .

Если требуется найти корень с точностью , то деление пополам продолжается до тех пор, пока на каком-то n-ом этапе середина отрезка будет точным корнем уравнения, т.е. (случай, весьма редко встречающиеся на практике), либо будет получен отрезок , длина которого меньше . Тогда координата середины этого отрезка и есть значение корня с требуемой точностью.

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

.

2. Метод простых итераций (метод последовательных приближений).

Обычно в итерационных методах уравнение (1) сводят к равносильному ему уравнению вида

(2)

таким образом, что искомый корень уравнения (1) является и корнем уравнения (2). Затем на отрезке выбирается - начальное приближение, и строится последовательность

(3)

При определенных условиях эта последовательность сходится к корню .

Определение. Если существует некоторая окрестность (круг) корня , такая, что для любых и

(4)

где , то говорят, что удовлетворяет условию Липшица.

Замечание. Условие Липшица с константой M будет иметь место, если в некоторой окрестности корня производная

(5)

Теорема (без доказательства). Каково бы ни было , последовательность сходится к корню уравнения , если только в круге корня удовлетворяет условию Липшица с константой . При этом скорость сходимости характеризуется неравенством

(6)

На практике для выполнения этого условия достаточно оценить . Если , то такая окрестность, в которой существует.

Рис. 1

Для случая, когда - действительная функция переменной , описанный метод простых итераций имеет ясную геометрическую интерпретацию. Построим графики функций и . Корнем уравнения является абсцисса точки пересечения кривой с прямой (рис.1). Взяв в качестве начальной произвольную точку , строим ломаную линию (рис.1 а, б).

Абсциссы вершин этой ломаной представляют собой последовательные приближения корня . Из рис. видно, что если на отрезке , то последовательные приближения колеблются около корня , если же производная положительна, то последовательные приближения сходятся к корню монотонно.

3. Метод хорд (метод секущих).

Рассмотрим вопрос о способах построения функции . Поступают следующим образом. Если уравнение имеет корень , а функция непрерывна и не обращается в 0 в окрестности , то очевидно, что уравнение

(8)

также имеет единственный корень . Обозначая

, (9)

получаем требуемый вид уравнения (2). Различные итерационные методы различаются выбором функции .

Рассмотрим метод хорд. Пусть - действительная непрерывная функция действительной переменной, имеющая в интервале непрерывные производные первого и второго порядка, не меняющие своего знака в этом интервале. (Будем считать, что корень уравнения (1) - простой и находится на отрезке ). Пусть - произвольная точка из , в которой (например, в качестве можно выбрать одну из границ отрезка ). В качестве функции возьмем функцию

(10)

Тогда

, (11)

и уравнение

(12)

также имеет корень . За начальное приближение примем любую точку из , в которой имеет знак, противоположный знаку (например, за можно взять другую границу отрезка ). Последующие приближения строим обычным образом:

(13)

Геометрическая интерпретация этого метода состоит в том, что через точки и проводится прямая (т.е. дуга кривой заменяется стягивающей ее хордой на малом отрезке ). За следующее приближение берется точка пересечения этой прямой с осью абсцисс (см. Рис.2).

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

В методе Ньютона в качестве выбираем

(14)

Тогда

(15)

При этом полагаем, что функция удовлетворяет тем же условиям, что и в предыдущем случае. Начальное приближение целесообразно выбирать так, чтобы , хотя это и не обязательно. Итерационная последовательность строится обычным образом:

, (16)

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

[1] Рассматривается случай действительной функции.