§ 3. Методы хорд и касательных

Следующие методы похожи на метод деления пополам, но имеют квадратичную сходимость за счёт более осмысленного выбора точки x_n+1 деления отрезка [_n ; _n].

1. М етод хорд. Если на отрезке [; ] нужно найти корень уравнения f(x) = 0 для непрерывной функции f со свойством f()·f() < 0, то можно действовать по аналогии с методом деления пополам: строим последовательность вложенных отрезков

[₀ ; ₀]  [₁ ; ₁]  …  [_n ; _n]  [_n+1 ; _n+1 ]  …,

на концах которых функция принимает значения противоположных знаков

1. полагаем x₀ =  = ₀, ₀ =  , ₀ = | – |, причём f(₀)·f(₀) < 0;

2. пусть уже известны x_n , _n , _n , _n , где f(_n)·f(_n)  0;

3. если f(_n) = 0 или f(_n) = 0, то корень найден, процесс завершён;

4. если _n   и |f(x_n)|  , то процесс завершён, x_n – приближённое значение корня;

5. если _n >  или |f(x_n)| >  , то x_n+1 = _n – – точка пересечения с осью абсцисс хорды с концами в точках (_n ; f(_n)) и (_n ; f(_n)). Полагаем

[_n+1 ; _n+1] = ,

_n+1 = _n+1 – _n+1 , возврат к шагу 2.

Приведённый выше рисунок показывает, что этот метод может привести к результату для функций весьма общего вида. Однако всегда нужно иметь в виду, что при f(_n) = f(_n) вычисления по методу хорд становятся невозможными. Таким образом, для беспечного применения метода хорд функция f на отрезке [; ] должна быть инъективной.

Если функция f не слишком патологическая, то после локализации корня можно считать отрезок [; ] настолько малым, что функция f на нём монотонна и даже выпукла или вогнута. Тогда метод хорд можно упростить:

Метод хорд для монотонных выпукло-вогнутых функций

1. положим  = , x₀ = , ₀ =  –  .

2. пусть уже известны x_n , _n .

3. если f(x_n) = 0, то корень найден, процесс завершён.

4. если _n   и |f(x_n)|  , то процесс завершён, x_n – приближённое значение корня.

5. если _n–1 >  или |f(x_n)| >  , то

– точка пересечения с осью абсцисс хорды с концами в точках ( ; f()) и (x_n ; f(x_n)), _n+1 = x_n+1 – x_n , возврат к шагу 2.

Здесь функция не предполагается дифференцируемой: символы f и f использованы лишь для удобного краткого обозначения знаков возрастания-убывания и выпуклости-вогнутости функции f (так, f > 0 обозначает возрастание, а f < 0 – убывание функции, f > 0 означает, что f выпукла вниз, а f < 0 – что f выпукла вверх). Таким образом, в случаях а), г) нужно положить  = , x₀ = , а в случаях б), в) – соответственно  = , x₀ = .

Теорема (о методе хорд). Пусть известен отрезок [; ], в котором заключён ровно один корень уравнения f(x) = 0, где функция f непрерывна, строго монотонна, всюду выпукла или вогнута на [; ] и f()·f() < 0. Тогда последовательность {x_n}_{n  N} , определённая по методу хорд, сходится к корню r  [; ]. При этих предположениях метод хорд имеет линейную скорость сходимости.

Доказательство. Для доказательства сходимости заметим, что последовательность {x_n}_{n  N} монотонна.

Для определённости проведём рассуждения в случае в): функция f убывает и выпукла вниз. Последнее означает, что любая хорда лежит выше графика функции. Согласно алгоритму,  = , x₀ = , f() > 0, f(x₀) < 0, т.е. x₁  [; x₀] и f(x₁) < 0. Предположим, что доказаны неравенства x₀  x₁  … …  x_k >  и f(x_i) < 0 (0  i  k). Тогда x_k+1 – точка пересечения с осью абсцисс хорды с концами (; f()) и (x_k ; f(x_k)) – лежит между  и x_k , т.е. x_k+1  x_k . Кроме того, поскольку хорда лежит выше графика функции, а в точке x_k+1 хорда пересекает ось абсцисс, то f(x_k+1) < 0.

Итак, последовательность {x_n}_{n  N} монотонна и ограничена (лежит на [; ]), поэтому она имеет предел x. Переходя к пределу в неравенстве f(x_n)·f() < 0, получим f(x)·f()  0, так что f(x)  f(), x   . Поэтому предельный переход в формуле x_n+1 = x_n – приводит к условиям x = x –  = 0, т.е. f(x) = 0 и x = r.

Оценим скорость сходимости:

Достаточно понять, что величины ограни­чены: если  с > 0 ( n  N M_n  c), то  n  N |x_n+1 – r|  c·|x_n – r| , что и требуется.

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

И меем, f(x_n) = –(x_n – x_n+1)tg _n , f() = (x_n+1 – )tg _n , откуда, вычитая, f(x_n) – f() = –(x_n – )tg _n . Поэтому

,

что и требовалось.

Теорема доказана.

Следствие (о методе хорд для дифференцируемых функций). Пусть известен отрезок [; ], в котором заключён ровно один корень уравнения f(x) = 0, где функция f дважды непрерывно дифференцируема со знакопостоянными на этом отрезке производными f(x) и f(x), причём f()·f() < 0. Тогда последовательность {x_n}_{n  N} , определённая по методу хорд, сходится к корню r  [; ]. При этих предположениях метод хорд имеет линейную скорость сходимости.

Примеры: 1. Уточнить значение корня (точное его значение 0,25) для многочлена f(x) = 32·x³ – 48·x² + 22·x – 3 на отрезке [0; 0,34] с точностью  = 0,01.

Здесь f(x) = 22 – 96·x + 96·x², f(x) = –96 + 192·x . Легко понять, что f < 0 и f > 0. Применяем метод хорд, беря  = 0, x₀ = 0,34.

Таким образом, приближённое значение корня 0,25 : ₁₁ < 0,01 и f(x₁₁)  0,01.

2. Уточнить корень функции f(x) = с точностью до 0,001 на отрезке [–1,3; 0,05].

Здесь функция f(x) непрерывно дифференцируема дважды: f(0) = –1, f(0) = 0. Функция убывает, выпукла вниз, т.е. имеет случай в) :  = –1,3, x₀ = 0,05. Точное значение корня, очевидно, равно нулю.

Видно, что универсальной константы c со свойством квадратичной сходимости |x_n+1 – r|  c·|x_n – r|² не существует. В то же время, конечно, имеет место линейная сходимость. Поэтому квадратичная сходимость метода хорд, о которой, как ни странно, говорится во многих учебниках (например, [7, стр. 95]) имеет место только для очень хороших ситуаций, в общем случае можно рассчитывать только на сходимость первого порядка.

Краткая характеристика метода хорд для монотонных выпукло-вогнутых функций приведена в приложении (таблица II) .

2. М етод касательных. Если на отрезке [; ] требуется найти корень уравнения f(x) = 0 для непрерывно дифференцируемой функции f со свойством f()·f() < 0, то можно действовать как в методе хорд: строим последовательность вложенных отрезков

[₀ ; ₀]  [₁ ; ₁]  …  [_n ; _n]  [_n+1 ; _n+1 ]  … ,

на концах которых функция принимает значения противоположных знаков

1. полагаем в зависимости от ситуации либо x₀ =  = ₀ , ₀ = , либо x₀ =  = ₀ , ₀ = , ₀ = | – |, причём f(₀)·f(₀) < 0;

2. пусть уже известны x_n , _n , _n , _n , где f(_n)·f(_n)  0;

3. если f(_n) = 0 или f(_n) = 0, то корень найден, процесс завершён;

4. если _n   и |f(x_n)|   , то процесс завершён, x_n – приближённое значение корня;

5. если _n >  или |f(x_n)| > , то x_n+1 = x_n – – точка пересечения с осью абсцисс касательной y = f(x_n) + f(x_n)·(x – x_n) к графику функции в точке (x_n ; f(x_n)),

[_n+1 ; _n+1] = ,

_n+1 = _n+1 – _n+1 , возврат к шагу 2.

П риведённый выше рисунок показывает, что этот метод может привести к результату для функций весьма общего вида. Однако нужно иметь в виду, что иногда вычисления по методу касательных становятся некорректными: например, точка x_n+1 не всегда принадлежит отрезку [; ] или процесс “зацикливается” (см. рис. слева). Таким образом, для беспечного применения метода касательных функция f на отрезке [; ] должна удовлетворять дополнительным ограничениям.

Е сли функция f не слишком патологическая, то после локализации корня можно считать отрезок [; ] настолько малым, что функция f монотонна на нём и даже выпукла или вогнута. Тогда метод касательных можно упростить: