2. Интерполяционный многочлен Ньютона для системы произвольно расположенных узлов

Данный многочлен строится с помощью аппарата разделенных разностей (табл. 2) в виде (17) на основании имеющего места соотношения (21)

N_n(x) = f(x₀) + (x–x₀) f(x₀,x₁) + (x–x₀)(x–x₁) f(x₀, x₁, x₂) +…+

+ (x–x₀)(x–x₁)…(x–x_n–1) f(x₀, x₁,…, x_n) (27)

Здесь, как и раньше, N_n(x_k) = f(x_k), (k = 0, 1, 2,…,n).

Остаточный член

R_n(x) = f(x) – N_n(x) = f(x, x₀, x₁,…, x_n) (x–x₀)(x–x₁)… (x–x_n).

При n = 1 – это линейная интерполяция, при n = 2 – квадратичная.

Замечания

1. Разные способы построения многочленов Лагранжа и Ньютона дают тождественные рабочие формулы при заданной таблице f(x). Это следует из единственности интерполяционного многочлена заданной степени на упорядоченной системе узлов.

2. Повышение точности интерполирования предположительно проводить за счет увеличения числа узлов n и соответственно степени полинома P_n(x). Однако при таком подходе увеличивается погрешность из-за роста | f ⁽ⁿ⁾(x) | и, кроме того, увеличивается вычислительная погрешность.

Эти соображения приводят к другому способу приближения функций с помощью сплайнов (будет рассмотрено дальше).

3. Повышение точности интерполирования осуществляется и посредством специального расположения узлов интерполяции на рассматриваемом отрезке [a, b] области определения функции f(x). Известно, что если сконцентрировать узлы x_i вблизи одного конца отрезка [a, b], то погрешность R_n(x) при длине отрезка l = b – a > 1 будет велика в точках x_i близких к другому концу. Поэтому всегда возникает задача о наиболее рациональном выборе x_i (при заданном числе узлов n).

Эта задача была решена Чебышевым, т.е. оптимальный выбор узлов нужно производить по формуле:

x_i = ,

где (i = 0,1,2, ..., n) – есть нули полинома Чебышева T_n+1(x).

Пример. Найти значение y = f(x) при x = 0,4 заданной таблично:

i	0	1	2	3
xi	0	0,1	0,3	0,5
yi	–0,5	0	0,2	1

3. Локальная интерполяция

3.1. Линейная интерполяция

y = a_ix + b_i

a_i = (y_i – y_i–1)/(x_i – x_i–1), b_i = y_i–1 – a_ix_i–1.

x_t = 0,4; 0,3  x_t 0,5; x_i–1 = 0,3; x_i = 0,5

y_i–1 = 0,2; y_i = 1

a₃ = (1 – 0,2)/(0,5 – 0,3) = 0,8/0,2 = 4; b₃ = –1;

y = 4x–1, при x = 0,4; y = 40,4 – 1 = 0,6. (28)

3.2. Квадратичная интерполяция

y=a_ix²+b_ix+c_i

Выбираем три ближайшие точки к x_t = 0,4

x_i–1 = 0,1; x_i = 0,3; x_i+1 = 0,5.

y_i–1 = 0; y_i = 0,2; y_i+1 = 1.



A = ; = ; = =A^–1 .

Найдем A^–1 = ;

= =  ;

a = 0 – = 7,5; b = –2; c = 0,125;

y = 7,5x² – 2x + 0,125; при x = 0,4; y = 0,525. (29)

4. Глобальная интерполяция

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

L(x) = ;

при x = 0,4; y  L(x) = 0,3999.

Найдем выражение для полинома Лагранжа для данной таблицы при n=1 и для x_T = 0,4;

это соответствует (28).

Для n = 2 при x_T = 0,4 y  L(x) =

Для рассматриваемого интервала [x₁, x₃], берем x₀ = 0,1; x₁ = 0,3; x₂ = 0,5; y₀ = 0; y₁ = 0,2; y₂ = 1. Тогда

y  L(x) = 0,2 ;

что соответствует (29).

Алгоритм расчета интерполяционного многочлена Лагранжа, реализованный в виде функции PL с параметрами:

x_T – значение текущей точки;

, – одномерные массивы известных значений x и f(x);

n – размер массивов , ;

представлен на рис. 5.1.

В схеме введены следующие обозначения:

p – значение накапливаемой суммы, результат которой равен L(x_Т);

e – значение очередного члена произведения;

Результатом функции PL является значение p.

Рис. 5.1. Схема расчета интерполяционного многочлена Лагранжа