Обзор возможностей математических пакетов MathCAD 2000, MathLAB 5.0, Mathematica (стр. 9 )

(2.8)

И при условии её сходимости корень уравнения равен (с учётом погрешности)

(2.9),

тогда вычитая (2.8) из (2.9), имеем

а уменьшив здесь индекс на единицу, получаем

К правым частям этих равенств применим формулу Лагранжа, согласно которой найдутся точки ck и ck-1 такие, что

Таким образом, имеют место следующие связи между ошибками соседних приближений:

Предположим, что в той окрестности корня ξ, в которой находятся точки xk-1 и xk, производная меняется не очень быстро. Это допущение позволяет считать, что

, где η – некоторое число,

и значит,

, .

Беря отношение этих приближённых равенств, избавляемся от η:

, (2.10)

и разрешаем полученное приближённое уравнение относительно ξ:

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

Более коротко это записывается так:

, (2.11)

где - так называемые конечные разности первого и второго порядков соответственно. Отсюда название (2.11) Δ2 – преобразование или Δ2 – процесс Эйткена [1].

Примером реализации такого метода может служит следующий алгоритм.

Δ2 – алгоритм Эйткена

Шаг 0. Ввод x0 (начального приближения), φ(x) (исходной функции), q (оценки модуля производной), ε (допустимой абсолютной погрешности).

Шаг 1. Вычисление значений .

НЕ нашли? Не то? Что вы ищете?

Шаг 2. Δ2 – ускорение: .

Шаг 3. Вычисление контрольного значения: .

Шаг 4. Проверка на точность: если , то положить , вычислить и вернуться к шагу 2.

Шаг 5. Положить (с точностью до ε).

Применяя метод Эйткена, не следует забывать о проблеме своевременного прерывания счёта из-за потерь точности при вычитании близких чисел. Подключение Δ2 – ускорения на ранней стадии МПИ, когда x0 далеко от ξ, может привести к расходимости процесса, по крайней мере, в случае, когда [1].

2.4.2. Метод Вегстейна.

При выводе метода Вегстейна решения задачи о неподвижной точке x=φ(x) будем использовать как аналитические, так и геометрические соображения [1].

Пусть уже найдены: - элемент строящейся здесь последовательности, и - точка, соответствующая одному шагу МПИ, применённого к точке . Независимо от того, сходится начатый с МПИ (рис. 2.5, где ) или расходится (рис. 2.6 с ), отрезок AB, параллельный оси Ox и имеющий концами точки и , можно разделить точкой С так, чтобы она принадлежала прямой x = ξ (при этом во втором случае речь идёт о делении отрезка внешним образом) [1].

Рис. 2.5, 2.6. К построению метода Вегстейна.

При любых комбинациях направлений возрастания и выпуклости графика функции y=φ(x) в окрестности неподвижной точки ξ имеет место равенство длин отрезков BC = PC. Различаются два случая: когда и когда . По формуле Лагранжа соответственно имеем

или

В любом случае можно утверждать, что существует точка или такая, что

Разрешая это линейное уравнение относительно ξ, находим

. (2.12)

Если бы значение было известно, то тем самым задача о неподвижной точке x=φ(x) была бы решена точно. Заменим это неизвестное значение аппроксимирующим его разностным отношением:

Подставляя приближённое значение в (2.12), вместо корня ξ получаем приближение к нему

. (2.13)

Эта итерационная формула, где k = 1,2,3,…, совместно с формулой

(k = 0, 1, 2, …) (2.14)

и начальными значениями полностью определяет метод Вегстейна для задачи x=φ(x) [1].

Значение , получаемое по формуле Вегстейна (2.13) при заданных начальных значениях и , совпадает со значением , вычисляемым Δ2 – процессом Эйткена. Далее, т. е. при k ≥ 2, процессы (2.11) и (2.13) различаются. Учитывая, что МПИ является составной частью метода Вегстейна, в случаях, когда , можно заканчивать процесс вычислений, как и в методе Эйткена.

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

Алгоритм Вегстейна.

Шаг 1. Вычислить ; положить .

Шаг 2. Вычислить .

Шаг 3. Проверить на точность: если , то вычислить ; переприсвоить значения и вернуться к шагу 2.

Шаг 4. Положить (с точностью ε).

Разумеется, проверку на точность в подобном алгоритме можно устраивать иную (что просто необходимо, если метод Вегстейна применяется в случаях, когда ). Если нет угрозы большой потери точности из-за вычитания близких чисел, то заканчивать работу алгоритма Вегстейна лучше выводом значения . Для вычисления значения в этом алгоритме применена равносильная (2.13) формула [1]