Метод хорд (метод линейной интерполяции)

Идея метода хорд состоит в том, что по двум точкам и построить прямую (то есть хорду, соединяющую две точки графика ) и взять в качестве следующего приближения абсциссу точки пересечения этой прямой с осью . Иными словами, приближённо заменить на этом шаге функцию её линейной интерполяцией, найденной по двум значениям и . (Линейной интерполяцией функции назовём такую линейную функцию , значения которой совпадают со значениями в двух фиксированных точках, в данном случае – в точках и .)

Рис 2.2. Построение последовательного приближения по методу хорд

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

Интерполяционную линейную функцию будем искать как функцию с угловым коэффициентом, равным разностному отношению

,

построенному для отрезка между и , график которой проходит через точку :

Решая уравнение , находим

то есть

Заметим, что величина может рассматриваться как разностное приближение для производной в точке . Тем самым полученная формула – это разностный аналог итерационной формулы метода Ньютона.

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

Метод секущих

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

и на каждой итерации нужно один раз вычислить значение функции .

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

Найдём точку пересечения этой прямой с осью из уравнения

откуда . Следовательно, эта прямая пересекает ось как раз в точке следующего приближения. Тем самым получаем следующую геометрическую интерпретацию последовательных приближений. Начиная с точки , через соответствующие точки графика проводятся секущие с угловым коэффициентом того же знака, что производная . (Заметим, что, во-первых, значение производной вычислять не обязательно, достаточно лишь знать, убывает функция или возрастает; во-вторых, что прямые, проводимые при разных , имеют один и тот же угловой коэффициент и, следовательно, параллельны друг другу.) В качестве следующего приближения к корню берётся точка пересечения построенной прямой с осью .

Рис.2.3 Последовательные итерации метода секущих

На чертеже изображены итерации. Мы видим, что последовательные точки приближаются к корню, оставаясь всё время с одной стороны от него.

Метод Ньютона

Рассмотрим эффективный метод решения нелинейных уравнений, носящий имя Ньютона. Вначале приведем некоторые наводящие рассуждения. Пусть функция y = F(x), корень которой ищется, имеет производные до 2-го порядка в окрестности корня - точки . Пусть уже найдено приближение номера n к корню (n-ая итерация) и требуется найти приближение номера n+1. По формуле Тейлора имеем

F(x_n+1) = F(x_n) + F’(x_n) × (x_n+1 – x_n) + O(x_n+1 – x_n)².

Пренебрежем остаточным членом порядка O(x_n+1 – x_n)² в правой части формулы и, будем считать, что x_n+1» , т.е. приближение номера n+1 найдено столь точно, что F(x_n+1)» 0.

Тогда имеем приближенное равенство

0» F(x_n) + F'(x_n) (x_n+1 – x_n).

Выражая отсюда x_n+1 при условии F'(x_n) ¹ 0, и, переходя от приближенного равенства к точному, получим

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

Предположим, что уравнение

имеет простой вещественный корень x_*, т.е.

F(x_*) = 0,

Будем предполагать, что F(x) дважды дифференцируема в некоторой окрестности точки x_*, т.е. для всех х принадлежащих некоторому интервалу (x_* - r₁, x_* + r₁), где r₁ > 0, причем F"(x) непрерывна на отрезке [x_* - r, x_* + r], 0 < r £ r₁.

Исследуем сходимость метода Ньютона

(2.2)

Теорема 1. Пусть x_* - простой вещественный корень уравнения (4.1) и пусть F'(x) ¹ 0 в окрестности точки. x_*

= {x:½x - x_*½ < r}.

Пусть, что F"(x) непрерывна на отрезке [x_*-r, x_*+r] Ì Ì , причем

(2.3)

Тогда, если и

(2.4)

то метод Ньютона (2.2) сходится, и для погрешности справедлива оценка

(2.5)

Замечания.

Метод Ньютона имеет квадратичную сходимость, т.е. он сходится быстрее метода простой итерации, который имеет линейную сходимость. Однако, метод Ньютона требует задания достаточно близкого к корню x_* начального приближения, удовлетворяющего неравенству (2.4) при соблюдении соотношений (2.3).