1.      »нтерполирование функций многочленами Ќьютона

 

ћногочлен Ћагранжа неудобен из-за своей громоздкости дл€ практического использовани€. –ассмотрим более простую схему построени€ интерпол€ционного многочлена.

ѕусть ln(x) - интерпол€ционный многочлен Ћагранжа с равноотсто€щими узлами. ѕредставим в виде:

ln(x) = l0(x) + (l1(x) - l0(x)) + (l2(x) - l1(x)) +Е+ (ln(x) - ln-1(x)).††††††††††††††††††††† †††††(4.1)

–азности lk(x) - lk-1(x) есть многочлены k-ой степени, обращающиес€ в ноль в точках x0, x1,Е,xk-1, поскольку lk(xj) - lk-1(xj) при j = 0,1,Е, k-1. —ледовательно,

lk(xj) - lk-1(xj) = ak(x - x0) (x - x1)Е (x - x k -1).

ѕодставл€€ эти выражени€ в (4.1) (дл€ k =1,Е, k-1) находим:

ln(x) = a0 + a1(x - x0) + a2(x - x0) (x - x1) +Е+ an(x - x0) (x - x1(x - x n -1).

 оэффициенты a0, a1,Е,an определ€ютс€ из условий:

ln(xj) = f(xj) при j = 0,1,Е, k-1,

lk(xj) - lk-1(xj) = ak(x - x0) (x - x1)Е (x - x k -1).

“ак как мы предполагали, что у нас равноотсто€щие узлы, то x k = x0+ kh, lk(xk) = f(xk). ќтсюда

.

ѕокажем, что f(xk) - lk-1(xk) есть k - € разность в точке x0, т.е.она равна Dkf(x0).

ћетодом математической индукции можно доказать, что

Dkf(x0) = f(xk) - k1 f(xk - 1) + k2 f(xk - 2) +Е+ (-1)iki f(xk - i) +Е+ (-1)k f(x0).

¬ычислим разность f(xk) - lk-1(xk). »меет место равенство

f(xk) - lk-1(xk) = ,

где

.

 

“аким образом,

f(xk) - lk-1(xk) = f(xk)-= Dkf(x0).

—ледовательно

.

ѕоэтому

, (4.2)

»нтерпол€ционный многочлен, записанный в таком виде, называетс€ интерпол€ционным многочленом Ќьютона (с равноотсто€щими узлами интерпол€ции).

Ћинейный интерпол€нт по Ќьютону имеет вид

.

¬вод€ обозначение, получим

 

.

ѕри вычислении разностей удобно пользоватьс€ таблицей

xi

f(xi)

D f(xi)

D2 f(xi)

Е

Dn f(xi)

x0

x1

Е

xn- 1

xn

f(x0)

f(x1)

Е

f(xn- 1)

f(xn)

Df(x0)

Df(x1)

Е

Df(xn- 1)

 

D2f(x0)

D2f(x1)

Е

 

 

Е

Е

Dnf(x0)

 

 

ѕри проверке вычислений используетс€ условие, что сумма всех чисел столбца должна быть равна разности первого и последнего чисел столбца.

»нтерпол€ционна€ формула Ќьютона имеет место и в случае, если узлы не равноотсто€т друг от друга. ¬ этом случае она принимает вид:

,†††††††††††† (4.3)

где коэффициенты

-         разделенные разности.

 

xi

f(xi)

xi+1- xi

d1 f(xi)

xi+2- xi

d2 f(xi)

Е

xn- x0

dn f(xi)

x0

x1

Е

xn- 1

xn

f(x0)

f(x1)

Е

f(xn- 1)

f(xn)

x1-x0

x2-x1

Е

xn - xn- 1

d1f(x0)

d1f(x1)

Е

d1f(xn- 1)

 

x2-x0

x3-x1

Е

 

d2f(x0)

d2f(x1)

Е

 

Е

Е

xn- x0

 

 

dnf(x0)

 

 

 

јлгоритм интерпол€ции функции многочленом Ќьютона (произвольные узлы).

¬вод: ”злы интерпол€ции X[i], Y[i]' i = 0,1,Е, n.

¬ывод: ¬ычислить c:= f(х).

d:= 1; с:= X[0];p:=1;

÷икл по j:= 1Е n выполнить

†††††† с:= Y[0];

÷икл по i:= 0Е n-j выполнитьY[i]:= (Y[i+1]- Y[i])/ (X[i+j]- X[i]);конец цикла по i;

p:= p*( x- X[j-1]); c:= c+p*Y[j])

конец цикла по j;

конец.

јлгоритм интерпол€ции функции многочленом Ќьютона (равноотсто€щие узлы).

¬вод: ”злы интерпол€ции X[i], Y[i]' i = 0,1,Е, n.

¬ывод: ¬ычислить c:= f(х).

h:= X[1]- X[0]; с:= X[0];p:=1;

÷икл по j:= 1Е n выполнить

†††††† с:= Y[0];

÷икл по i:= 0 Е n-j выполнитьY[i]:= (Y[i+1]- Y[i]);/ (X[i]- X[i-1]); X[i]:= X[i]- X[i-1]); конец цикла по i;

p:= p*( x- X[j-1])/(j*h); c:= c+p*Y[i]);

конец цикла по j;

конец.

 

ѕример. ѕо таблице значений функции вычислить f(10)

x

2

5

7

8

12

f(x)

12

33

-12

2

20

 

 

xi

f(xi)

xi+1- xi

d1 f(xi)

xi+2- xi

d2 f(xi)

xi+3- xi

d3 f(xi)

xi+4- xi

Dnxi

x - xi

2

5

7

8

12

12

33

-12

2

3

3

2

1

4

7

-22,5

14

0,25

5

3

5

-5,9

12,2

9,3

6

7

3,0

0,4

10

-0,3

8

5

3

2

f(10) = 120.

 

ѕогрешность при интерпол€ции многочленом Ќьютона та же, что и при интерпол€ции многочленом Ћагранжа. Ќаибольша€ точность при заданных узлах интерпол€ции достигаетс€ дл€ , расположенных к середине отрезка.