§ 3. Интерполяция по Эйткену. § 4. Интерполирование функии кубическими сплайнами §3. Интерполяция по эйткену

Для построения интерполяционногополинома Ла­­г­ран­жа по функцииy(x), заданной таблично {y_i,x_i}, весь­­ма эф­фек­тив­ной является итерационная схе­ма Эйт­ке­­на:

,i = 0, ...,m-1,

где m - количество итераций, символ равно означает опе­­­ра­тор при­сваивания. При этом для любого зна­­­че­­ния x = x_p из ин­тер­ва­ла [x₀, x_n] ордината y_p = y_m.

Рассмотренный алгоритм реализован в про­це­ду­­ре ait­ken,которую можно использовать как для рав­ных, так и не­равных интервалов [x_i, x_i+1]. Про­цедура стро­ит по­лином Ла­­гранжаL_n(x) сте­пе­ниnтаким образом, чтоL_n(x_i)ºy(x_i). По­скольку в про­це­ду­ре мас­сивyис­пользуется для хра­не­ния про­ме­жу­точ­ных зна­че­ний, его начальное зна­чение не со­храняется.

Формальные параметры про­цедуры.Входные:x[0:n],y[0:n] (типreal) - массивы абс­цисс и ординат таб­­лич­но за­данной функцииy= [y_i(x_i)];n(типin­te­ger) - ко­ли­чест­­во значений таб­лич­­­ной функции (ко­ли­­чество узлов ин­тер­­­по­ля­ции);xp(типreal) - абс­цис­са, для которой вы­чис­­ля­­ется интерполированноe зна­че­ние функции.Вы­ход­­ные:l(типre­al) - ин­­тер­по­ли­ро­ван­­­ное зна­че­ние функ­цииy(зна­че­ние полинома Ла­гран­­жа в точкеx_p).

procedure aitken(x:real;y:mas1;

n:integer;xp:real; var l : real);

var i,j,n1: integer;

begin

n1:=n-1;

for j:=0 to n1 do

for i:=j+1 to n do

y[i]:=((xp-x[j])*y[i]-(xp-x[i])*y[j])/(x[i]-x[j]); l:=y[n];

end { ****** aitken ******}.

Процедура aitkenполучена в результате со­кра­ще­ния за­­писи, оптимизации по временным за­тра­там и пе­­ре­во­да с язы­каALGOLна языкPASCALoд­но­и­мен­­ной про­це­дуры, ко­торая опубликована в работе Агеева (1976) и яв­ля­е­­т­ся, в своюочередь, результатом ис­прав­ле­­­ния, сокращенияи ор­динарной пере­ра­бот­ки ал­го­рит­­­­ма С.Дж. Мифсуда (1966). Процедура проверена для ря­да элементарных функ­ций на машине IBM PC/AT-286, некоторые при­ме­ры ре­зуль­­татов тес­ти­­рованияпред­ставлены в табл.2.3. По­­греш­ность ин­­тер­по­ли­ро­­­ваниявычис­ля­лась как мо­дуль раз­­нос­­ти ин­­тер­по­ли­­рованного значения функцииL(x) в точ­кеx_n = x_p и еезна­че­ния, рассчитанного на ЭВМ с точ­нос­тьюe= 10^-12.

Таблицa 2.3

Функция	Шаг аргумента	Значение x	Ln (x )	D
y = exp(x)	Dx = const	0.74	2.09593558	0
y = exp(x)	Dx № const	0.74	2.09593558	0
y = exp(x)	Dx = const	0.333	1.39514732	0
y = exp(x)	Dx № const	0.333	1.39514625	1.073e-62
y = cos(x)	Dx = const	0.74	0.73846864	1.192e-72
y = cos(x)	Dx № const	0.74	0.73846852	0
y = cos(x)	Dx = const	0.333	0.94506603	5.960e-82
y = cos(x)	Dx № const	0.333	0.94506591	5.960e-82