Krzysztof Demiańczuk grupa MD-A0-11

Praca domowa z metod numerycznych.

Zadanie 13:

Wyznacz wielomiany interpolacyjne Lagrange’a oraz Newtona dla funkcji określonej tablicą:

x	0.0	0.1	0.3	0.6	1.0
f(x)	-6.0000	-5.89483	-5.65014	-5.17788	-4.28172

Wyznacz i porównaj błędy interpolacji.

Opis zastosowanych metod:

Interpolacja Lagrange’a:

Metoda polega na wyznaczeniu wielomianu interpolacyjnego zgodnie z wzorem:

$$\text{Wn}\left( x \right) = \sum_{j = 1}^{n}{f(x_{j})\frac{\left( x - x_{0} \right)\left( x - x_{1} \right)\ldots\left( x - x_{j - 1} \right)\left( x - x_{j + 1} \right)\ldots(x - x_{n})}{\left( x_{j} - x_{0} \right)\left( x_{j} - x_{1} \right)\ldots\left( x_{j} - x_{j - 1} \right)\left( x_{j} - x_{j + 1} \right)\ldots(x_{j} - x_{n})}}$$

Interpolacja Newtona:

Metoda polega na wyznaczeniu wielomianu interpolacyjnego na podstawie kolejnych pochodnych funkcji interpolowanej:

f(x) = b₀ + b₁(x−x₀) + … + b_n(x−x₀)(x−x₁)…(x−x_n)

gdzie:

b₀ = y₀ = f(x₀)

$$b_{1} = f\left( x_{1},x_{0} \right) = \frac{f\left( x_{1} \right) - f(x_{1})}{\left( x_{1} - x_{0} \right)}$$

$$b_{2} = f\left( x_{2},\ x_{1},x_{0} \right) = \frac{\frac{f\left( x_{1} \right) - f(x_{1})}{\left( x_{2} - x_{1} \right)} - \frac{f\left( x_{1} \right) - f(x_{1})}{\left( x_{1} - x_{0} \right)}}{\left( x_{2} - x_{0} \right)}$$

.

.

.

b_n = f(x_n, x_n − 1,…,x₀)

Wartość błędu interpolacji wyznaczana jest jako suma różnic wartości zadanej węzła interpolacyjnego i wartości wielomianu interpolacyjnego w każdym punkcie dziedziny.

$\varepsilon = \sum_{i = 1}^{n}\left| f\left( x \right) - \ W(x) \right|$

W procesie interpolacji dążymy do minimalizacji powyższej wartości.

Interpolacja Lagrange’a – skrypt lagranp

function [wsp,L] = lagranp(x,y)

%dane wejsciowe: x = [x0,x1,...,xN], y = [y0,y1,...yN]

%dane wynikowe: wsp - wspolczynniki wielomianu Lagrange'a stopnia n

% L = wspolczynniki Lagrange'a

N = length(x) - 1;

wsp = 0;

for j=1:N+1

wmn = 1;

for i=1:N+1

if i ~= j, wmn = conv(wmn,[1 -x(i)])/(x(j) - x(i));

end

end

L(j,:) = wmn; %wspolczynniki wielomianowe Lagrange'a

wsp = wsp + y(j) * wmn; %wielomian Lagrange'a

end

Interpolacja Newtona – skrypt newtonp

function [cn,DD] = newtonp(x,y)

%gotowy algorytm z materiałów do wykładu- opracował Pan Andrzej Kosior PWR

%parametry wejsciowe: x=[x0,x1,...,xN]

%y=[y0,y1,...,yN]

%wyjscie cn = wspolczynniki wielomianu Newtona

N = length(x) - 1;

DD = zeros(N+1,N+1);

DD(1:N+1,1)=y';

%w pierwsza kolumne macierzy kwadratowej N+1xN+1

%podstaw wartosc y, apostrof oznacza transpozycje

for k=2:N+1

for m=1:N+2-k %tworzenie tablicy roznic dzielonych

DD(m,k) = (DD(m+1,k-1) - DD(m,k-1))/(x(m+k-1)-x(m));

end

end

r = DD(1,:);

cn = r(N+1);

for k=N:-1:1

cn = [cn r(k)] - [0 cn*x(k)];

%czyli cn(c)*(x-x(k-1))+r_k-1

end

Skrypt zadaniowy

x = [0.0 0.1 0.3 0.6 1.0];

y = [-6.0000 -5.89483 -5.65014 -5.17788 -4.28172];

[wsp,L] = lagranp(x,y); %wyznacza wielomian Lagrange'a

xmin = min(x);

xmax = max(x);

xx = linspace(xmin,xmax,100); %dziedzina doprecyzowana na potrzeby kreślenia wykresów wielomianów

yl = polyval(wsp,xx); %interpolacja do zadanych punktow

clf

subplot(3,1,1)

plot(xx,yl,'k-',x,y,'r*') %wykres wielomianu Lagrange'a

grid on

title('interpolacja metodą Lagrangea')

[cn,DD] = newtonp(x,y);

yn = polyval(cn,xx);

subplot(3,1,2)

plot(xx,yn,'k-',x,y,'r*') %wykres wielomianu Newtona

grid on

title('interpolacja metodą Newtona')

%porównanie wartości w węzłach interpolacji

y

ybl=polyval(wsp,x) %interpolacja do zadanych punktow dziedziny x

ybn=polyval(cn,x) %interpolacja do zadanych punktow dziedziny x

blad_lagr=ybl-y %wartość błędu

blad_newt=ybn-y %wartość błędu

subplot(3,1,3)

plot (x,blad_lagr,'k*-',x,blad_newt,'kx-')%wykres błędów

title ('* -błąd interp. Lagrange, + -błąd interp. Newtona')

wartości węzłów interpolacji:
y – dane z zadania

ybl – wartości dla metody Lagrange’a

ybn – wartości dla metody Newtona

y =

-6.000000000000000 -5.894830000000000 -5.650140000000000 -5.177880000000000 -4.281720000000000

ybl =

-6.000000000000000 -5.894829999999999 -5.650139999999996 -5.177879999999981 -4.281719999999931

ybn =

-6.000000000000000 -5.894830000000000 -5.650140000000000 -5.177880000000000 -4.281720000000000

Porównanie błędów:

blad_lagr =

1.0e-013 *

0 0.008881784197001 0.044408920985006 0.195399252334028 0.692779167366098

blad_newt =

0 0 0 0 0

Wizualizacja wyników:

WNIOSKI

Przy podstawowej konfiguracji Matlaba wartości wielomianów interpolacyjnych podane wyliczane były na jednakowym poziomie. Jedynie funkcja błędu wskazywała, że jest to wyłącznie złudzenie. Przy zmianie wyświetlanej dokładności wyników wartości okazały się różnić na poziomie rzędu 10^-13.

Metoda interpolacji Newtona jest bardziej dokładna i lepiej dopasowuje wielomian interpolacyjny do zadanego zbioru punktów niż metoda Lagrange’a.