 |
Метод хорд (метод линейной интерполяции)
|
|
|
|
Идея метода хорд для нахождения приближенного корня уравнения состоит в том, что по двум точкам 
и 
необходимо построить прямую 
(т. е. хорду, соединяющую две точки графика 
) и взять в качестве следующего приближения 
абсциссу точки пересечения этой прямой с осью 
.
Определение. Линейной интерполяцией функции 
назовём такую линейную функцию 
, значения которой совпадают со значениями в двух фиксированных точках, в данном случае – в точках 
и 
.
Иными словами, идея метода хорд состоит в приближённой замене на этом шаге функции её линейной интерполяцией, найденной по двум значениям и .
Рис. 2.2. Построение последовательного приближения по методу хорд
Итак, очередное последовательное приближение будет зависеть от двух предыдущих: 
. Найдём выражение для функции 
.
Интерполяционную линейную функцию будем искать как функцию с угловым коэффициентом, равным разностному отношению
,
построенному для отрезка между и , график которой проходит через точку 
:
.
Решая уравнение 
, находим
,
т. е.
.
Заметим, что величина 
может рассматриваться как разностное приближение для производной 
в точке . Тем самым полученная формула – это разностный аналог итерационной формулы метода Ньютона.
Вычисления ведутся непосредственно по данной формуле при 
, начиная с двух приближений 
и 
, взятых, по возможности, поближе к корню 
. При этом не предполагается, что лежит между и (и что значения функции 
в точках и , имеют разные знаки). При этом не гарантируется, что корень попадёт на отрезок между и на каком-либо следующем шаге (хотя это и не исключено). В таком случае затруднительно дать оценку погрешности, с которой приближает истинное значение корня , и поэтому довольствуются таким эмпирическим правилом: вычисления прекращают, когда будет выполнено неравенство 
, где 
– желаемая точность нахождения корня. При этом полагают приближённое значение корня равным 
.
|
|
|
Метод секущих
Идея метода секущих состоит в том, что выбирают любую постоянную 
, знак которой совпадает со знаком производной в окрестности 
(и в частности на отрезке, соединяющем и ). Постоянная не зависит также и от номера шага 
. Тогда формула итераций оказывается очень проста:
и на каждой итерации нужно один раз вычислить значение функции .
Выясним смысл этой формулы, а также смысл условия о совпадении знаков 
и . Рассмотрим прямую, проходящую через точку 
на графике с угловым коэффициентом 
. Тогда уравнением этой прямой будет
.
Найдём точку пересечения этой прямой с осью из уравнения
откуда 
. Следовательно, эта прямая пересекает ось как раз в точке следующего приближения. Тем самым получаем следующую геометрическую интерпретацию последовательных приближений. Начиная с точки , через соответствующие точки графика проводятся секущие с угловым коэффициентом 
того же знака, что производная 
.
Замечание. Значение производной вычислять не обязательно, достаточно лишь знать, убывает функция или возрастает. Прямые, проводимые при разных , имеют один и тот же угловой коэффициент 
и, следовательно, параллельны друг другу.
В качестве следующего приближения к корню берётся точка пересечения построенной прямой с осью .
Рис. 2.3. Последовательные итерации метода секущих
На чертеже изображены итерации. Мы видим, что последовательные точки приближаются к корню, оставаясь всё время с одной стороны от него.
Метод Ньютона
Рассмотрим эффективный метод решения нелинейных уравнений, носящий имя Ньютона. Вначале приведем некоторые наводящие рассуждения. Пусть функция 
, корень которой ищется, имеет производные до 2-го порядка в окрестности корня – точки 
. Пусть уже найдено 
-е приближение к корню (на -ой итерации) и требуется найти 
-е приближение. По формуле Тейлора имеем
|
|
|
.
Пренебрежем остаточным членом порядка 
в правой части формулы и будем считать, что 
, т.е. приближение номера 
найдено столь точно, что 
.
Тогда имеем приближенное равенство
.
Выражая отсюда 
при условии 
и переходя от приближенного равенства к точному, получим
Конечно, данные рассуждения не претендуют на роль строгого вывода и не могут служить обоснованием метода Ньютона. Перейдем к обоснованию метода Ньютона. Будем рассматривать лишь случай поиска вещественных корней.
Предположим, что уравнение
| (2.1) |
имеет простой вещественный корень 
, т.е.
, 
Будем предполагать, что 
дважды дифференцируема в некоторой окрестности точки , т.е. для всех , принадлежащих некоторому интервалу 
, где 
, причем 
непрерывна на отрезке 
, 
.
Исследуем сходимость метода Ньютона
| (2.2) |
Теорема 1. Пусть – простой вещественный корень уравнения (4.1) и пусть 
в окрестности точки
.
Пусть непрерывна на отрезке 
, причем
| (2.3) |
Тогда, если 
и
| (2.4) |
то метод Ньютона (2.2) сходится, и для погрешности справедлива оценка
| (2.5) |
Замечания.
Метод Ньютона имеет квадратичную сходимость, т.е. он сходится быстрее метода простой итерации, который имеет линейную сходимость. Однако метод Ньютона требует задания достаточно близкого к корню начального приближения, удовлетворяющего неравенству (2.4) при соблюдении соотношений (2.3).
|
|
|
