Типы сходимостей итерационных последовательностей

Чтобы более объективно судить о скорости сходимости тех или иных итерационных методов, введем следующие понятия.

Пусть некоторый итерационный процесс генерирует последовательность , имеющую пределом x*.

Определение 1. Линейная и сверхлинейная сходимость.

Сходимость последовательности (x_k) к x* называется линейной (соответственно, итерационный процесс — линейно сходящимся), если существует такая постоянная C  (0; 1) и такой номер k₀, что

|x* – x_k+1|  C|x* – x_k|  k  k₀ (5)

и сверхлинейной, если существует такая положительная последовательность , что и

|x* – x_k+1|  C_k|x* – x_k|  k  N₀ (6)

Определение 2. Сходимость порядка p.

Говорят, что последовательность (x_k) сходится к x* по меньшей мере с p-м порядком (соответственно, итерационный процесс имеет по меньшей мере p-й порядок), если найдутся такие константы C > 0 и p  1, что

|x* – x_k+1|  C|x* – x_k|^p (7)

при всех k  N₀, начиная с некоторого k = k₀.

Фиксируя в Определение 2 значение p = 1, видим, что линейно сходящийся процесс можно называть процессом первого порядка, значению p = 2 в (7) соответствует квадратично сходящийся процесс, p = 3 означает кубическую сходимость.

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

Для простоты будем считать, что функция f(x) дважды дифференцируема на отрезке [а, b], содержащем корень ξ уравнения (1).

Пусть x_k  [a; b] — уже известный член последовательности приближений к ξ, полученный конструируемым методом (или заданное начальное приближение x₀ при k = 0). Для любого x из [а, b] можно записать формальное представление f(x) по формуле Тейлора

, (8)

где _k  [a;b] — некоторая точка между x и x_k.

Так как корень ξ — потенциально произвольная точка отрезка [а, b], то разложение (8) справедливо и для x = ξ, т. е. существует точка такая, что

.

Но f(ξ) = 0, и если точка известна, то корень ξ можно точно найти из квадратного уравнения

(9)

Считая, что значение x_k близко к ξ, т.е. разность ξ – x_k по модулю достаточно мала, можно рассчитывать, что величина (ξ – x_k)² будет тем более малой. На этом основании отбросим в (9) последнее слагаемое и подменим квадратное уравнение (9) линейным уравнением. Естественно, что при этом будет найден не корень ξ, а некоторая другая точка, которую обозначим x_k+1.

Таким образом, итерационный процесс Ньютона определяется линейным уравнением

f(x_k) + f'(x_k)(x_k+1 – x_k) = 0 (10)

или в явном виде формулой

, (11)

где k = 0, 1, 2, ... и предполагается, что по крайней мере на элементах последовательности (x_k) первая производная данной функции в нуль не обращается.

Если в равенстве (10) фиксированную точку x_k+1 заменить переменной x, а 0 в правой части — переменной у, то в полученном легко узнать уравнение касательной к кривой y = f(x), проведенной к ней в точке (x_k; f(x_k)). Отсюда геометрический смысл метода Ньютона: приближения к корню ξ совершаются по абсциссам точек пересечения касательных к графику данной функции, проводимых в точках, соответствующих предыдущим приближениям (Рис. 2).

Рис. 2. Геометрический смысл метода Ньютона

Теорема 2. Апостериорная погрешность метода Ньютона.

Пусть функция f(x) удовлетворяет условиям

x  [a; b] (12)

Тогда, если члены последовательности (x_k), определяемые методом Ньютона (11), при любом фиксированном k  N₀ принадлежат отрезку [а, b] и эта последовательность сходится на [а, b] к корню ξ уравнения (1), то справедливы неравенства (k  N₀):

(13)

(14)

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

Теорема 3. Априорная погрешность метода Ньютона.

Пусть для функции f(x) на отрезке [а, b] выполнены условия (12).

Тогда, если интервал содержится в [а, b], то при произвольном выборе x₀ из J для определяемой методом Ньютона (11) последовательности (x_k):

1) x_k  J k  N;

2) и f(ξ) = 0;

3) справедливо утверждение Теорема 2 и оценка

. (15)

Теорема 4. Условия сходимости метода Ньютона.

Пусть на отрезке [а,b] функция f(x) имеет первую и вторую производные постоянного знака и пусть

f(а)f(b) < 0.

Тогда, если точка x₀ выбрана на [а, b] так, что

f(x₀)f"(x₀) > 0, (16)

то начатая с нее последовательность (x_k), определяемая методом Ньютона (11), монотонно сходится к корню ξ  (a; b) уравнения (1).

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

На получение сверхлинейной скорости сходимости при видоизменении метода Ньютона (11) можно надеяться в случае, когда f'(x_k) при каждом k  N подменяется некоторым близким к f'(x_k) значением, которое может быть найдено (при каждом k свое) через значения данной функции. Для таких аппроксимаций f'(x_k) можно использовать, например, определение производной. Имеем:

,

и при малых h (произвольного знака) получаем приближенное равенство

, (17)

позволяющее производную приближенно подменять так называемым разностным отношением. Подстановка (17) в (11) приводит к итерационной формуле

(18)

где k = 0, 1, 2, ..., a h — малый параметр, которым должен распорядиться вычислитель.

Ясно, что при каждом k в формуле (17) может быть свое значение h, т.е. в формуле (18) вместо постоянного параметра h имеет смысл использовать связанный с номером итерации параметр h_k, т.е. вести вычисления по формуле

(19)

Итерационный метод, определяемый формулами (18) или (19), назовем разностным методом Ньютона.

Так как равенство (17) можно сделать сколь угодно точным за счет малости шага h разностного отношения (теоретически; практически это далеко не так из-за потерь точности при вычитании близких чисел), то по непрерывности можно утверждать асимптотически квадратичную скорость сходимости разностного метода Ньютона при определенных условиях.

Опираясь на то, что необходимым условием сходимости некоторой последовательности x_k к пределу ξ является сходимость к нулю последовательности разностей x_k – x_k–1 (причем с той же скоростью), положим в (19)

h_k = x_k–1 – x_k, откуда x_k–1 = x_k + h_k. В результате этого из (19) получаем итерационный процесс

, (20)

где k = 1, 2, 3, ..., а x₀ и x₁ должны задаваться.

Формула (20) определяет новый метод как двухшаговый (результат (k + 1)-го шага зависит от результатов k-гo и (k – 1)-го шагов) и на каждой итерации требует вычисления только одного значения функции, другое же значение, фигурирующее в этой формуле, передается с предыдущего шага. Сравнив (20) с формулой (4), полученной из геометрических соображений, легко понять, что x_k+1 есть абсцисса точки пересечения с осью Ox прямой, проведенной через точки (x_k–1, f(x_k–1)) и (x_k; f(x_k)), т.е. секущей (Рис. 3). Отсюда название этого метода — метод секущих.

Рис. 3. Приближения к корню методом секущих