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

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

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

Рис. 3. Схема рекурсивной процедуры PX

Интерполяционный полином Лагранжа.

Более удовлетворительный способ построения полинома состоит в использовании базиса так называемых лагранжевых полиномов

¡ Пусть функция f(x) задана таблично. Это могут быть, например, значения концентраций продуктов реакции в зависимости от времени, полученные экспериментально.

¡ Значения x ₀, x ₁,..., x _n называются узлами таблицы. Считаем, что узлы в общем случае не являются равноотстоящими (шаг таблицы неравномерный).

¡ Построим интерполяционный многочлен на отрезке [ x ₀, x _n]. Запишем искомый многочлен в виде:

P_m(x)=a ₀ +a ₁ x + a₂x² +... + a_mx^m.

¡ Геометрически задача интерполирования сводится к построению кривой через заданные точки.

¡ Аналитически задача сводится к решению системы уравнений

¡ Для определения коэффициентов многочлена P_n(x) необходимо располагать n +1 узловой точкой.

¡ Пусть в n +1-ой точках x ₀, x ₁,..., x _n определены значения y ₀, y ₁,..., y _n.

¡ Требуется построить многочлен P_n (x), принимающий в узловых точках заданные значения y_i, т.е. такой, что

P_n(x_i) = y_i i = 0,1,..., n.

¡ Лагранж предложил следующую форму интерполяционного полинома

,

¡ где L_i (x) - множитель Лагранжа, имеющий вид:

¡ Следовательно, формулу Лагранжа можно представить в виде:

¡ Числитель и знаменатель не должны включать в себя значения x = x_i, так как результат будет равен нулю.

¡ В развернутом виде формулу Лагранжа можно записать:

Пусть дана таблица значений

х	х1	х2	х3	............	хп
у	у1	у2	у3	............	уп

Требуется составить полином (функцию) y = f (x) степени m ≤ n – 1, который принимал бы заданные значения y_i при соответствующих значениях x_i: y_i = f (x_i) (i = 1, 2, 3, ………n). Иными словами график функции должен проходить через заданные точки M (x_i; y_i)

Данная задача выполнима при использовании интерполяционного полинома Лагранжа:

+

+......

.+ (1)

или

(2)

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

Дата добавления: 2015-07-24