4. Теоретические основы

4.1. Постановка задачи

Задача определения предела встречается в практике вычислений очень часто. При вычислении сумм сходящихся рядов, например

, (2.1)

мы имеем дело с последовательностью частичных сумм

, (2.2)

для которой требуется найти предел при n.

При вычислении определенного интеграла численным методом увеличивая число узловых точек сетки n, мы также приходим к некоторой последовательности

. (2.3)

Решение различных задач для дифференциальных уравнений методом конечных разностей (и другими методами) при увеличении числа узловых точек n приводит к последовательности.

Список примеров, в которых получается последовательность, предел которой желательно установить может быть продолжен. Это решение уравнений, систем уравнений, поиск экстремума функций итерационными методами и т.д.

Итак, в общем случае задача сводится к следующему. Имеется несколько членов последовательности , номера которых расположены, может быть, не подряд, а выборочно по какому-нибудь закону, либо произвольно. Необходимо по этим данным найти приближенно предел последовательности z. Тогда разность z_iz можно использовать для оценки погрешности приближенного значения z_i. Однако, поскольку само значение z получено прибли­женно, необходимо также иметь критерий, по которому можно судить о мере надежности этой оценки (или о ее точности). Совокупность оценки и критерия ее надежности позволяет принять решение об окончании расчетов, если можно утверждать, что заданная точность достигнута, или о необходимости продолжения исследований.

Из многообразия методов экстраполяции рассмотрим только такие, которые требуют знания численных значений z_i, а не их аналитического выражения через номер i.

4.2. Экстраполяция и оценка погрешности при известном порядке аппроксимации.

В качестве исходного положения будем считать, что известно некоторое число членов последовательности z_n.

Например, оценка по правилу Рунге основана на предположении, что известен порядок точности численного метода (или порядок аппроксимации), т.е. z_n можно представить в виде

, (2.4)

где z – точное значение; z_n – приближенный результат, полученный при числе узловых точек (или числе слагаемых суммы) равном n; c₁ – коэффициент, который предполагается не зависящим от n; k –порядок точности метода (или порядок аппроксимации); (n) – величина, полагаемая малой по сравнению с c₁n^-k при тех значениях n, которые использовались в данных конкретных расчетах.¹

Правила Рунге и Ричардсона. Одним из наиболее распространенных способов оценки погрешности численных методов с помощью экстраполяции, является правило Рунге [1].

В этом случае, уменьшив n в Q раз (предполагается, что Q>1 и n/Q - целое), отбросив малые, приходим к системе двух уравнений

(2.5)

Вычитая первое уравнение из второго, найдем

,

откуда нетрудно найти c₁ , а, тем самым и z:

, (2.6)

С помощью (2.6) определяется экстраполированное (по правилу Ричардсона) значение искомого параметра z, а с его помощью оценивается погрешность z_n‑z приближенного значения z_n. Этот способ оценки погрешности называется правилом Рунге.

Метод Ромберга. В некоторых случаях можно построить более подробную математическую модель погрешности, представив приближенный результат в виде суммы

. (2.7)

Тогда, чтобы найти неизвестные z, c₁,…,c_L нужно использовать L+1 значение z_i и записать задачу в виде системы линейных уравнений, пренебрегая малыми величинами:

(2.8)

Эта задачу можно решить путем построения интерполяционного многочлена Лагранжа [1,2] L-й степени

и экстраполяцией его до n

(2.9)

(в скобках перечислены числа z_i, которые использованы для получения экстраполированного значения z).

Интерполяционная формула обладает весьма полезным для практического применения свойством. Значение z, которое получается по формуле (2.9), может быть найдено путем последовательного применения рекуррентного соотношения Эйткена

, (2.10)

то есть для получения экстраполированного значения L+1-го порядка можно использовать два значения L-го порядка, вычисленные для двух наборов данных z_i, причем номер первой точки одного набора сдвинут на единицу относительно другого.

В случае если n_j=n₁Q ^j1, выражение (2.10) принимает вид

, (2.11)

что при L=1 совпадает с (2.6), а при L>1 представляет собой аналогичное выражение, в котором вместо вычисленных участвуют экстраполиро­ванные значения.

Повторное применение правила Рунге для оценки погрешности результата вычислений z_n при последовательном увеличении номера n в Q раз называют методом Ромберга [1].

Аналогичный подход имеет место и в случае, когда номер члена последовательности увеличивается на единицу (т.е. n_j+1=n_j+1). Для последовательности {z_n} строится таблица Нэвилла [7,8], представляющая собой матрицу z_jL ( , ), в которой нулевой столбец – исходная последовательность, а все остальные столбцы находятся по правилу

. (2.12)

В более общем случае приближенный результат представляется в виде

, (2.13)

где k₁,…, k_L – произвольные действительные числа. Тем не менее, при n_j=n₁Q ^j1 задача определения коэффициентов c_i и экстраполированного значения z решается аналитически. Подставив в (2.8) n_j=n₁Q ^j1 преобразуем систему уравнений:

Введя обозначения , получим

(2.14)

Вычитая в (2.14) предыдущее уравнение, умноженное на p₁, из последующего, будем иметь

Разделив все уравнения на 1p₁ и обозначив , , приходим к новой системе

(2.15)

которая по виду аналогична (2.14), но имеет на одно неизвестное меньше. Повторяя этот процесс L раз, можно найти z. Отметим, что представляют собой Ричардсоновские экстраполяции (2.6).

Таким образом, определение искомого значения z и в случае произвольных (в общем случае не целых) показателях k_i (но только при n_j=n₁Q ^j1) сводится к повторному использованию уточнения (2.6), то есть, к методу Ромберга.

В случае n_jn₁Q ^j1 задача экстраполяции сводится к решению системы L+1 линейных уравнений типа (2.13) численным методом.

Главным ограничением для применения рассмотренных методов, основанных на разложении по степеням n, является то, что показатели степеней k_j должны быть известны заранее.