3. Метод Ньютона (метод касательных или метод линеаризации).

Одним из лучших общих методов решения уравнения f(x)=0 является метод Ньютона. Если есть некоторое приближение x_i к решению x^*, то метод Ньютона аппроксимирует функцию f(x) касательной к ее графику в точке x_i . Точка пересечения касательной с осью абсцисс принимается за новое приближение. Метод Ньютона часто работает так, как показано на рис. 2 и приближения быстро сходятся к решению.

Рис. 2

Для вывода формул метода Ньютона разложим функцию f(x) в ряд Тейлора в точке x_i:

f(x) =f (x_i) + f’(x_i)(x - x_i ) +…

Касательная задается при помощи первых двух членов ряда

Y = f(x_i) + f’(x_i)( x- x_i )

Полагая y=0, получаем: x_i+1 = x_i - f(x_i)/f’(x_i).

В качестве начальной точки в зависимости от свойств функции берется или левая точка х₀ =a, (если f(a) f’’(a) > 0),

или правая точка x₀=b, (если f(b) f’’(b) > 0)., т.е. итерации сходятся к корню с той стороны, с которой f(x) f’’(x) > 0.

Метод Ньютона хорош тем, что быстро сходится, точнее, имеет квадратичную скорость сходимости.

Однако метод Ньютона не всегда работает так хорошо. Он может и не сходиться, например, если f’(x_i)=0, метод не определен.

Если f’(x_i)»0, могут возникнуть трудности, так как новое приближение x_i+1 может оказаться значительно худшим, чем x_i.

Еще одним недостатком метода Ньютона является необходимость вычисления f’(x). В ряде случаев можно применять упрощенный алгоритм – вместо вычисления производной в каждой точке f’(x_i) использовать значение в начальной точке f’(x₀).

4. Метод итераций (задача о неподвижной точке).

Дано уравнение

f(x)=0, (1)

заменим его равносильным уравнением

х=j(х) (2)

итерации образуются по правилу

х_i+1 = j ( х_i ), i=0,1,2,…, (3)

причем задается начальное приближение х₀.

Если полученная последовательность сходящаяся, т. е. существует предел , то, переходя к пределу в равенстве (3) и предполагая функциюj(х) непрерывной, найдем:

(5)

Таким образом, предел x является корнем уравнения (2) и может быть вычислен по формуле (3) с любой степенью точности.

Геометрическая интерпретация метода состоит в следующем:

построим на плоскости графики функций y=x и y=j(х). Каждый действительный корень уравнения (2) является абсциссой точки пересечения кривой y=j(х) и y=x. Возможен вид ломаной – “лестница'' (рис.3) и “спираль” (рис.4) - производная j’(х)>0 и j’(х)<0 (соответственно).

Рис.3

Рис. 4

Теорема (о сходимости метода итераций). Пусть функция j(х) определена и дифференцируема на отрезке. [a, b]. Тогда, если существует правильная дробь q такая, что

|j’(х)| £ q < 1 (6)

при a<x<b, то

1) Процесс итераций х_i+1=j(х_i), i=0,1,2,…, (7)

сходится независимо от начального значения х₀Î[a, b].

2) Предельное значение

является единственным корнем уравнения

х=j(х) (8) на отрезке [a, b].

Доказательство:…………………………………………………...

Замечание: В условиях теоремы метод итераций сходится при любом выборе начального значения х₀ из [a, b]. Метод является самоисправляющимся, т. е. Отдельная ошибка в вычислениях не повлияет наконечный результат, так как ошибочное значение можно рассматривать как новое начальное значение х₀.