Interpolacja wielomianami Newtona opiera się na bazie wielomianów:
\(\displaystyle{ \mathcal{B} = \{1, \ \ x-x_{0}, \ \ (x-x_{0})(x-x_{1}) \ \ ,..., \ \ (x-x_{0})(x-x_{1})\cdot ... \cdot (x-x_{n-1}) \},}\) która stanowi podstawę
konstrukcji wielomianu Newtona:
\(\displaystyle{ p_{n}(x) = a_{0}\cdot 1 + a_{1}\cdot (x-x_{0}) + a_{2}\cdot (x-x_{0})(x-x_{1})+ \ \ ... \ \ a_{n}\cdot (x-x_{0})(x-x_{1})\cdot ... \cdot (x-x_{n-1}) }\)
Wprowadzając oznaczenia tzw. różnic dzielonych \(\displaystyle{ a_{j} = f[x_{0}, x_{1}, ..., x_{j}], \ \ j = 0,1,2,..., n }\) - możemy zapisać Wielomian
Interpolacyjny Newtona w postaci:
\(\displaystyle{ p_{n}(x) = f[x_{0}] + f[x_{0},x_{1}]\cdot (x-x_{0}) + \ \ ... \ \ + f[(x_{0},x_{1},\ \ ... \ \ x_{n}]\cdot (x-x_{0})(x-x_{1})\cdot ... \cdot (x-x_{n-1}).}\)
Można udowodnić [patrz np. Josef Stoer, Roland Bulirsch. Wstęp do analizy numerycznej, PWN Warszawa 1987], że między różncami dzielonymi
zachodzi rekurencja:
\(\displaystyle{ f[x_{0}, x_{1},\ \ ... \ \ x_{n}] = \frac{f[x_{0}, x_{1},\ \ ... \ \ x_{n-1}] - f[ x_{1},\ \ ... \ \ x_{n}]}{x_{0}-x_{n}} }\)
Relację tą wykorzystujemy, budując tablicę różnic dzielonych w celu obliczenia współczynników wielomianu Newtona.
Program w OCTAVE
Kod: Zaznacz cały
function newtondd(x,y)
disp('Różnice dzielone')
disp('___________________________________________________________')
disp(' x y f[,] f[,,] f[,,,] ...')
disp('___________________________________________________________')
n=length(x);
for k=1:n-1
% Obliczenie pierwszej różnicy dzielonej
d(k,1)=(y(k+1)-y(k))/(x(k+1)-x(k));
end
for i=2:n-1
for k=1:n-i
% Obliczenie i-tej różnicy dzielonej
d(k,i)=(d(k+1,i-1)-d(k,i-1))/(x(k+i)-x(k));
end
end
% Drukowanie wyników
if (rem(n,2)==0)
p=n/2;
else
p=fix(n/2);
m=fix(n/2)+1;
end
for i=1:p
fprintf('%8.2f %8.2f',x(i),y(i));
for k=1:i-1
fprintf(' %8.5f',d(i-k,2*k));
end
fprintf('\n ')
for k=1:i
fprintf(' %8.5f',d(i-k+1,2*k-1));
end
fprintf('\n')
end
j=p;
for i=m:-1:1
j=j+1;
fprintf('%8.2f %8.2f',x(j),y(j));
for k=1:i-1
fprintf(' %8.5f',d(j-k,2*k));
end
fprintf('\n ')
for k=1:i-1
fprintf(' %8.5f',d(j-k+1,2*k-1));
end
fprintf('\n')
end
Kod: Zaznacz cały
>> x=[1 2 3 5 7]';
>> y=[3 5 9 11 15]';
>> newtondd(x,y)
Różnice dzielone
___________________________________________________________________________
x y f[,] f[,,] f[,,,] ...
___________________________________________________________________________
1.00 3.00
2.00000
2.00 5.00 1.00000
4.00000 -0.50000
3.00 9.00 -1.00000 0.12500
1.00000 0.25000
5.00 11.00 0.25000
2.00000
7.00 15.00
[size=85][color=green]Dodano po 10 godzinach 15 minutach 40 sekundach:[/color][/size]
[b]Interpolacja wielomianami Newtona[/b]
Interpolacja wielomianami Newtona opiera się na bazie wielomianów:
[latex] \mathcal{B} = \{1, \ \ x-x_{0}, \ \ (x-x_{0})(x-x_{1}) \ \ ,..., \ \ (x-x_{0})(x-x_{1})\cdot ... \cdot (x-x_{n-1}) \},[/latex] która stanowi podstawę
konstrukcji wielomianu Newtona:
[latex] p_{n}(x) = a_{0}\cdot 1 + a_{1}\cdot (x-x_{0}) + a_{2}\cdot (x-x_{0})(x-x_{1})+ \ \ ... \ \ a_{n}\cdot (x-x_{0})(x-x_{1})\cdot ... \cdot (x-x_{n-1}) [/latex]
Wprowadzając oznaczenia tzw. różnic dzielonych [latex] a_{j} = f[x_{0}, x_{1}, ..., x_{j}], \ \ j = 0,1,2,..., n [/latex] - możemy zapisać Wielomian
Interpolacyjny Newtona w postaci:
[latex] p_{n}(x) = f[x_{0}] + f[x_{0},x_{1}]\cdot (x-x_{0}) + \ \ ... \ \ + f[(x_{0},x_{1},\ \ ... \ \ x_{n}]\cdot (x-x_{0})(x-x_{1})\cdot ... \cdot (x-x_{n-1}).[/latex]
Można udowodnić [patrz np. Josef Stoer, Roland Bulirsch. Wstęp do analizy numerycznej, PWN Warszawa 1987], że między różncami dzielonymi
zachodzi rekurencja:
[latex] f[x_{0}, x_{1},\ \ ... \ \ x_{n}] = \frac{f[x_{0}, x_{1},\ \ ... \ \ x_{n-1}] - f[ x_{1},\ \ ... \ \ x_{n}]}{x_{0}-x_{n}} [/latex]
Relację tą wykorzystujemy, budując tablicę różnic dzielonych w celu obliczenia współczynników wielomianu Newtona.
[b]Program w OCTAVE[/b]
[code]
function newtondd(x,y)
disp('Różnice dzielone')
disp('___________________________________________________________')
disp(' x y f[,] f[,,] f[,,,] ...')
disp('___________________________________________________________')
n=length(x);
for k=1:n-1
% Obliczenie pierwszej różnicy dzielonej
d(k,1)=(y(k+1)-y(k))/(x(k+1)-x(k));
end
for i=2:n-1
for k=1:n-i
% Obliczenie i-tej różnicy dzielonej
d(k,i)=(d(k+1,i-1)-d(k,i-1))/(x(k+i)-x(k));
end
end
% Drukowanie wyników
if (rem(n,2)==0)
p=n/2;
else
p=fix(n/2);
m=fix(n/2)+1;
end
for i=1:p
fprintf('%8.2f %8.2f',x(i),y(i));
for k=1:i-1
fprintf(' %8.5f',d(i-k,2*k));
end
fprintf('\n ')
for k=1:i
fprintf(' %8.5f',d(i-k+1,2*k-1));
end
fprintf('\n')
end
j=p;
for i=m:-1:1
j=j+1;
fprintf('%8.2f %8.2f',x(j),y(j));
for k=1:i-1
fprintf(' %8.5f',d(j-k,2*k));
end
fprintf('\n ')
for k=1:i-1
fprintf(' %8.5f',d(j-k+1,2*k-1));
end
fprintf('\n')
end
Kod: Zaznacz cały
>> x=[1 2 3 5 7]';
>> y=[3 5 9 11 15]';
>> newtondd(x,y)
Różnice dzielone
___________________________________________________________________________
x y f[,] f[,,] f[,,,] ...
___________________________________________________________________________
1.00 3.00
2.00000
2.00 5.00 1.00000
4.00000 -0.50000
3.00 9.00 -1.00000 0.12500
1.00000 0.25000
5.00 11.00 0.25000
2.00000
7.00 15.00