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

1. положим g = , x₀ = , D₀ = b – a.

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

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

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

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

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

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

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

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

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

Итак, последовательность {x_n}_{n Î N} монотонна и ограничена (лежит на [a; b]), поэтому она имеет предел x. Переходя к пределув неравенстве f(x_n)·f(g) < 0, получим f(x)·f(g) £ 0, так что f(x) ¹ f(g), x ¹ g. Поэтому предельный переход в формуле 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 j_n, f(g) = (x_n+1 – g)× tg j_n, откуда, вычитая, f(x_n) – f(g) = –(x_n – g)× tg j_n. Поэтому

,

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

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

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

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

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

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

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

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

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

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

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

[a₀; b₀] É [a₁; b₁] É … É [a_n; b_n] É [a_n+1; b_n+1 ] É …,

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

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

2. пусть уже известны x_n, a_n, b_n, D_n, где f(a_n)·f(b_n) £ 0;

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

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

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

[a_n+1; b_n+1] = ,

D_n+1 = b_n+1 – a_n+1 , возврат к шагу 2.

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