Контрольная работа: Интерполирование функций

где П_{n +1} (x ) = (x - x ₀ )(x - x ₁ )…(x - x_n ) - произведение элементов главной диагонали таблицы (эти элементы подчеркнуты). Тогда формула Лагранжапринимает вид:

Использование формулы (2) позволяет сократить значительную часть вычислений по определению лагранжевых коэффициентов L_i ^{(n )} (x )при различных значениях аргумента. Для этого произведение элементов i -й строки таблицы разностей представляется как K_i = (x – x_i )D_i , где D_i - произведение всех элементов строки, кроме расположенного на главной диагонали. Величина D_i (i= )не зависит от значения аргумента x и может быть вычислена для заданной функции только один раз.

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

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

В соответствии со схемой Эйткена линейная интерполяция по точкам 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.

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 .

Конечные разности первого порядка вычисляются как Dy_j = y_{j +1} – y_j , где

j = , для более высоких порядков используется известная формула

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

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

Таблица 1

x	y	Dy	D2 y	D3 y	D4 y
x 0	Y 0	Dy 0	D2 y 0	D3 y 0	D4 y 0
x 1	Y 1	Dy 1	D2 y 1	D3 y 1	D4 y 1
x 2	Y 2	Dy 2	D2 y 2	D3 y 2
x 3	Y 3	Dy 3	D2 y 3	-
x 4	Y 4	Dy 4	-	-
x 5	Y 5	-	-	-

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

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

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