Интерполирование по схеме Эйткена

Итерационные методы интерполирования основаны на повторном применении некоторой простой интерполяционной схемы. Наиболее известным из итерационных методов является метод Эйткена, в основе которого лежит многократное применение линейной интерполяции.

В соответствии со схемой Эйткена линейная интерполяция по точ­кам M_i (x_i, y_i) и M_{i +1}(x_{i +1}, y_{i +1}) сводится к вычислению определителя второго порядка

При интерполировании по трем и более точкам последовательно вычисляются многочлены

В общем случае интерполяционныймногочлен n -й степени, прини­мающий в точках x_i значения y_i (i = ), записываются следующим образом:

(3)

Основным достоинством схемы Эйткена является возможность постепенного увеличения числа используемых значений x_i до тех пор, пока последовательные значения P _{0,1,2,…, n} (x) и P _{1,2,…, n -1}(x) не совпа­дут в пределах заданной точности. Иначе говоря, вычисления прекращаются при выполнении условия

| P _{0,1,2,…, n} (x) - P _{1,2,…, n -1}(x)| < e (k £ n).

При использовании ЭВМ вычисления по формуле (3) реализуются в виде рекурсивной подпрограммы - функции РХ(I, J) с формальными параметрами I, J, определяющими индексы крайних узлов интерполирования, которые используются для получения значения соответствующего многочлена P_{i , i +1,…, j} (x).

Для хранения вычисленных значений P (x) используется двумерный массив M размером N*N элементов, где N - максимальное число узлов интерполирования. Каждому возможному значению P (x) соответствует один из элементов M(I, J), расположенный выше главной диагонали (I < J) и определяемый сочетанием индексов крайних узлов интерполирования.

Например, значению многочлена P _1,2(x) соответствует элемент M(1,2), значению P _2,3,4(x) - элемент M(2, 4) и т.д. Симметричные элементы M(J, I), расположен­ные ниже главной диагонали (J > I), показывают, вычислены ли соот­ветствующие значения P (x) на данный момент, и определяются как

Схема рекурсивной процедуры PX приведена на рис. 1, где Х- массив значений узлов интерполирования, Y- массив значений функциивузлах интерполирования, Z- значение аргумента. Пара­метры X, Y, Z, M должны быть описаны как общие для главной про­граммы и подпрограммы PX.

1.3. Интерполяционные формулы Ньютона

для равноотстоящих узлов

Узлы интерполирования x ₀, x ₁,..., x_n называются равноотстоящими, если , где h - шаг интерполирования. При этом для некоторой функции f (x) таблично задаются значения y_i = f (x_i), где x_i = x ₀ + ih.

Существуют две формулы Ньютона для случая равноотстоящих узлов интерполирования, которые называются соответственно первой и второй интерполяционными формулами Ньютона и имеют вид:

;

,

В этих формулах D ⁱy_j - конечные разности, где i - порядок разности, j - ее порядковый номер, а параметры t и q определяются следующим образом:

t = (x - x ₀) / h; q = (x - x_n) / h.

Конечные разности первого порядка вычисляются как D y_j = y_{j +1} – y_j, где
j = , для более высоких порядков используется известная формула

(i = 2, 3,...; j = ).

Получаемые конечные разности удобно представлять в табличной форме записи, например, в виде табл. 1, которая называется горизонтальной таблицей ко­нечных разностей.

Таблица 1

x	y	D y	D2 y	D3 y	D4 y
x 0	Y 0	D y 0	D2 y 0	D3 y 0	D4 y 0
x 1	Y 1	D y 1	D2 y 1	D3 y 1	D4 y 1
x 2	Y 2	D y 2	D2 y 2	D3 y 2	-[s1]
x 3	Y 3	D y 3	D2 y 3	-	-[s2]
x 4	Y 4	D y 4	-	-	-[s3]
x 5	Y 5	-	-	-	-[s4]

Пepвая формула Ньютона применяется для интерполирования впе­ред и экстраполирования назад, т.е. в начале таблицы разностей, где строки заполнены и имеется достаточное число конечных разностей. При использовании этой формулы для интерполирования значение аргумента x должно лежать в интервале [ x ₀, x ₁]. При этом за x ₀может приниматься любойузел интерполяции x_k с индексом , где m - максимальный порядок конечных разностей.

Вторая формула Ньютона применяется для интерполирования назад и экстраполирования вперед, т.е. в конце таблицы конечных разностей. При этом значение аргумента x должно находиться в интервале [ x_{n -1}, x_n ], причем за x_n может приниматься любой узел интерполирования .

Одно из важнейших свойств конечных разностей заключается в следующем. Если конечные разности i –го порядка (i < n) постоянны, то функция представляет собой полином i –й степени. Следовательно, фор­мула Ньютона должна быть не выше i -й степени. При использовании ЭВМ вычисление конечных разностей завершается при выполнении условий

где L - число значащих цифр после запятой в представлении значений функции.

Необходимо отметить, что формулы Ньютона являются видоизменениями формулы Лагранжа. Однако в формуле Лагранжа нельзя пренебречь ни одним из слагаемых, так как все они равноправны и пред­ставляют многочлены
n -й степени. В формулы Ньютона в качестве слагаемых входят многочлены повышающихся степеней, коэффициентами при которых служат конечные разности, разделенные на факториалы. Конечные разности, как правило, быстро уменьшаются, что позволяет в формулах Ньютона пренебречь слагаемыми, коэффициенты при кото­рых становятся малыми. Это обеспечивает вычисление промежуточных значений функции достаточно точно спомощью простых интерполяционных формул.