C08-Aproximarea functiilor_1.pdf
Transcript of C08-Aproximarea functiilor_1.pdf
-
Cursul 8
Aproximarea funciilor
-
Aproximarea functiilor
Fie o funcie real f:[a,b]R, cunoscut numai ntr-un numr limitat de puncte numite noduri, (ansamblul acestora constituind suportul interpolrii): x1,x2,,xn prin valorile y1=f(x1), y2=f(x2),, yn=f(xn).
O multime F de functii reale este
interpolatoarea de ordin n daca pentru orice
sistem de n puncte distincte x1,x2,,xn din
X si oricare ar fi numerele reale y1,y2,,yn
exista in F o singura functie care in punctele xi ia valorile yi.
-
Interpolare
Problema de interpolare: Dandu-se multimea
interpolatoare F de de ordin n in X si perechile
(xi,yi) XxR cu proprietatea ca ij xixj sa
se determine aceea functie jF care in
punctele xi ia valorile yi.
Se aproximeaza comportarea funciei n afara
acestor puncte printr-un polinom generalizat de
interpolare, de forma:
Pn(x)=a1u1(x)+a2u2(x)++anun(x)
n care funciile liniar independente
u1(x),u2(x),,un(x)
sunt cunoscute i constituie baza interpolrii.
-
Interpolare
Aceasta poate fi format din funcii simple:
polinoame, funcii trigonometrice,
exponeniale, etc.
Determinarea polinomului generalizat de interpolare (a coeficienilor ai) se face,
impunnd ca pe suportul interpolrii
polinomul de interpolare s coincid cu funcia f.
Pn(xi)=f(xi), i=1:n
numite condiii de interpolare.
-
Interpolare
Condiiile de interpolare conduc la sistemul
de ecuaii liniare
scris matriceal
U.a=f
n:1i,xfxua in
1k
ikk
-
Interpolare
S-au folosit notatiile
cu uij=uj(xi), fi=f(xi)
n
2
1
n
2
1
nn2n1n
n22221
n11211
f
f
f
f
a
a
a
a
uuu
uuu
uuu
U
-
Interpolare
Polinomul de interpolare este
cu
Introducand conditiile de interpolare se obtine
xlxlxl
UxuxuxuUxuxl
n21
1
n21
1TT
fxlfUxuaxuxuaxP T1TTn
1k
kkn
k
n
1k
kn xfxlxP
.1xl
,ki,0xl
kk
ik
-
Interpolarea polinomiala
Pentru baza polinomial
u1(x)=1, u2(x)=x,,u(x)=xn-1
Funciile lk(x) sunt polinoame de grad n-1, cu rdcinile xi, i=1:n, ik:
Deci polinoamele lk(x) pot fi scrise
n1k1k1kk xxxxxxxxCxl
nk1kk1kk1k
kxxxxxxxx
1C
n
ki,1i ik
i
kxx
xxxl
-
Interpolare
Polinomul de interpolare poart n acest caz numele de polinom de interpolare Lagrange i are
forma
Sistemul determinat de condiiile de interpolare
este
n
ki,1i ik
i
n
1k
knxx
xxxfxP
n
1k
i
k
ik n:1i,xfxa
-
Interpolare
Acesta are determinant Vandermonde, care este nenul dac punctele xi sunt distincte, caz n care sistemul este compatibil determinat, cu soluie unic, ceea ce implic un polinom de interpolare unic.
n
2
1
n
2
1
1n
n
2
nn
1n
2
2
22
1n
1
2
11
y
y
y
a
a
a
xxx1
xxx1
xxx1
-
Interpolare
Alte forme ale polinomului de interpolare Lagrange
kk
kx
x
xx
1xl
n
1i
ixxx
n
ki,1i
ikk
n
1k
n
ki,1i
i xxxxxx
n
ki,1i
ik
n
1i
i
k
n
ki,1i ik
i
k
xx
xx
xx
1
xx
xxxl
n
1k kk
kn
1k
kkxxx
xfxxlxfxP
-
Interpolare
Se observ c multiplicatorii Lagrange reprezint raportul produselor pe coloane ale celor dou matrice:
1xaxa
xa1xa
xaxa1
V
nn
22
11
1xxxx
xx1xx
xxxx1
U
n2n1
2n21
1n12
Uprod/VprodlllL n21
-
Interpolare
Valoarea polinomului Lagrange ntr-un punct de
abscis a
U=diag(x)*ones(n)-ones(n)*diag(x)+eye(n)
y*Uprod/Vprodylbn
1i
ii
n
n21
n21
n21
nnn
222
111
I
xxx
xxx
xxx
xxx
xxx
xxx
U
n
n
2
1
n
2
1
I
x00
0x0
00x
111
111
111
111
111
111
x00
0x0
00x
U
-
Interpolare
V=(a-diag(x))*~eye(n)+eye(n)
n
nn
22
11
I
0xx
x0x
xx0
0aa
a0a
aa0
V
n
n
2
1
I
011
101
110
x00
0x0
00x
011
101
110
*aV
-
Interpolare
function b = Lagrange(a, x, y)
% valoare polinom Lagrange in a
n = length(x);
V=(a-diag(x))*~eye(n)+eye(n);
U=diag(x)*ones(n)-ones(n)*diag(x)+eye(n);
b=prod(V)./prod(U)*y;
function a = coefLagr(x, y)
% Intrri:
% x = tabloul absciselor celor n puncte
% y = tabloul ordonatelor celor n puncte
% Ieiri:
% a = coeficienti polinom Lagrange
-
Interpolare
a=zeros(n,1);
z=zeros(n,1);
% calcul coeficieni c din (x-x(1))...(x-x(n))
c=poly(x);
for i = 1 : n
% calcul coeficieni b ai mpririi
% polinomului prin x-x(i)
[b,r]=deconv(c,[1 -x(i)]);
% calcul p=(x(i)-x(1))...(x(i)-x(i-1))(x(i)-x(i+1))(x(i)-x(n))
z=x(i)-x;
z(i)=1;
p=prod(z);
a(1:n)=a(1:n)+y(i)*b(1:n)/p;
end
-
Interpolarea Lagrange-Exemplu
Sa se calculeze polinomul de interpolare Lagrange corespunzator datelor:
-
Interpolarea Lagrange-Exemplu
Solutie:
4 3 2 4 3 2
4 3 2 2
1 1 2 2 1 2( ) 6 2
2 1 2 2 1 2 2 1 2 1 1 1 1 2
2 1 1 1 12 2 2 4 4
2 2 2 1 2 2 1 4 3
12 2
12
x x x x x x x xP x
x x x xx x x x x x x x
x x x x x x
-
Interpolare
Polinomul de interpolare de grad poate fi calculat
prin recuren, folosind polinoame de interpolare de
grad mai mic.
Dac se noteaz ={i1,i2,,ip} i
P - polinomul de interpolare ce trece prin punctele
(xi1,yi1),(xi2,yi2),,(xip,yip)
atunci polinomul de interpolare definit pe ansamblul
extins de puncte +j+k= {j,k}
jk
jkkj
kjxx
xPxxxPxxxP
-
Interpolare
Metoda Neville are forma:
n care s-a notat Qij=Pi-j,,i polinomul de
interpolare prin punctele (xi-j,yi-j),,(xi,yi) Se pornete cu polinoamele de interpolare de grad 0, reprezentate prin y1,y2,,yn, formndu-se polinoamele de interpolare de grad 1, 2, ..., .a.m.d.
conform tabloului x1 y1 = Q11 Q12 Q13 Q1n
x2 y2 = Q21 Q22 Q23 Q2,n-1
x3 y3 = Q31 Q32 Q3,n-2
xn yn = Qn1
, 1 1, 1i j i j i i j
ij
i i j
x x Q x x x Q xQ x
x x
-
Interpolare
b = Neville (x, y, a)
% Intrri:
% a = abscisa n care se calculeaz polinomul
% x = tabloul absciselor celor n+1 puncte
% y = tabloul ordonatelor celor n+1 puncte
% Ieiri:
% b = valoare polinom de interpolare
n = length(x);
q = y
for i = 1 : n
for j = 1 : n
q(j)=((a-x(j+i))*q(j)-(a-x(j))*
q(j+i))/(x(j)-x(j+i));
end
end
b = q(n);
-
Metoda Neville-exemplu
Sa se calculeze polinomul de interpolare Lagrange (folosind metoda Neville de recuren) corespunzator datelor:
-
Interpolarea Lagrange-Exemplu
(folosind metoda Neville de recuren)
Solutie:
2 1,0 1 2,01,1
1 2
1 6 2 24 2
2 1
x x Q x x Q x xQ x
x x
3 2,0 2 3,02,1
2 3
0 2 1 02
1 0
x x Q x x Q x xQ x
x x
-
Interpolarea Lagrange-Exemplu
(folosind metoda Neville de recuren)
Solutie:
4 3,0 3 4,03,1
3 4
1 0 0 00
0 1
x x Q x x Q x xQ
x x
5 4,0 4 5,04,1
4 5
2 0 1 22 2
1 2
x x Q x x Q x xQ x
x x
3 1,1 1 2,1 21,2
1 3
0 4 2 2 2
2 0
x x Q x x Q x x x xQ x x
x x
4 2,1 2 3,1 22,2
2 4
1 2 1 0
1 1
x x Q x x Q x x xQ x x
x x
-
Interpolarea Lagrange-Exemplu
(folosind metoda Neville de recuren)
Solutie:
5 3,1 3 4,1 23,2
3 5
2 0 0 2 2
0 2
x x Q x x Q x x xQ x x
x x
2 24 1,2 1 2,2 21,3
1 4
1 2
2 1
x x x x x xx x Q x x QQ x x
x x
2 25 2,2 2 3,2 22,3
2 5
2 1
1 2
x x x x x xx x Q x x QQ x x
x x
2 25 1,3 1 2,3 21,4
1 5
2 2
2 2
x x x x x xx x Q x x QQ x x
x x
-
Diferene divizate
111 xfxF
21
2111
212xx
xFxFx,xF
p1
p21p1p11p
p1pxx
x,,xFx,,xFx,,xF
Diferentele divizate ale unei functii f n raport cu xi pot fi introduse prin recuren cu relaiile:
-
Diferene divizate
p
1k
p
1i
ik
k
p
1k k
k
p1p
xx
xf
x
xfx,,xF
,xfxx
xfxflimx,xFlimx,xF 1
10
10
xx101
xx111
1010
i
1p
p
ii1p xfx,,xF
Ele se pot calcula cu relatia:
Se introduce diferenta divizat de argument repetat:
pe baza creia se deduce:
-
Diferene divizate
function a = DifDiv(x, y)
% Intrri:
% x = abscisele celor n puncte
% y = ordonatele celor n puncte
% Ieiri:
% y =diferene divizate de ordin
1:n
n = length(x);
for k = 1 : n-1
y(k+1:n)=(y(k+1:n)-y(k))./
(x(k+1:n)-x(k));
end
-
Identitatea lui Newton
0010 xfxfx,xFxx
1010110210 x,xFx,xFx,x,xFxxxx
21021022103210 x,x,xFx,x,xFx,x,x,xFxxxxxx
n10n1n0n
n01nn1n0
x,x,xFx,,x,xF
x,,x,xFxxxxxx
Pornind de la relatia de recurenta a diferentelor divizate se va stabili o alta forma a polinomului de interpolare Lagrange care pune in evidenta expresia erorii.
-
Identitatea lui Newton
n01nn0n0n1n0
21021010100
x,,x,xFxxxxx,,xFxxxx
x,x,xFxxxxx,xFxxxfxf
xRxPxf nn
Prin adunarea lor se ajunge la:
relatie denumita Identitatea lui Newton.
Aceasta relatie contine atat polinomul de interpolare Lagrange cat si restul interpolarii:
-
Identitatea lui Newton
are n+1 rdcini
are n rdcini are o rdcin
Prin derivarea de n ori a polinomului de interpolare se obtine:
n01nn0n x,,x,xFxxxxxR
xRxPxf nn
xPxf n xPxf nnn
n10n
n
n x,,x,xF!nxP
-
Identitatea lui Newton
De unde:
n101nn0n x,,x,x,xFxxxxxR
0x,,x,xF!nxf n10nn
!n
fx,,x,xF
)n(
n10n n0 x,x
!n
fx,,x,xF
)n(
n10n
!1n
fMxxxxxR 1nn0n
ffM 1n1n
-
Identitatea lui Newton
Dac funcia f este nedefinit derivabil fC atunci
Mn+1(f) crete foarte repede, deci majorarea este
grosier. function b = Newton(a, x, y)
% Intrri:
% a = abscisa n care se calculeaz polinomul
% x = tabloul absciselor celor n puncte
% y = tabloul ordonatelor celor n puncte
% Ieire:
% valoarea polinomului de interpolare n a
n = length(x);
a = DifDiv(x, y);
b = a(n);
for i = n-1:-1:1
b = (a - x(i-1)).*b + a(i);
end
-
Diferente divizate-exemplu
Sa se calculeze polinomul de interpolare Lagrange folosind identitatea lui Newton cu diferente divizate corespunzatoare datelor:
-
Interpolarea Lagrange-Exemplu
(folosind identitatea lui Newton cu diferente divizate)
Solutie:
1 1 1 22 1 2
1 2
( ) ( ) 6 2( , ) 4
2 1
F x F xF x x
x x
1 2 1 32 2 3
2 3
( ) ( ) 2 0( , ) 2
1 0
F x F xF x x
x x
-
Interpolarea Lagrange-Exemplu (folosind identitatea lui Newton cu diferente
divizate) Solutie:
1 3 1 3
2 3 4
3 4
( ) ( ) 0 0( , ) 0
0 1
F x F xF x x
x x
1 4 1 52 4 5
4 5
( ) ( ) 0 2( , ) 2
1 2
F x F xF x x
x x
2 1 2 2 2 33 1 2 3
1 3
( , ) ( , ) 4 2( , , ) 1
2 0
F x x F x xF x x x
x x
2 2 3 2 3 43 2 3 4
2 4
( , ) ( , ) 2 0( , , ) 1
1 1
F x x F x xF x x x
x x
-
Interpolarea Lagrange-Exemplu (folosind identitatea lui Newton cu diferente
divizate) Solutie:
2 3 4 2 4 5
3 3 4 5
3 5
( , ) ( , ) 0 2( , , ) 1
0 2
F x x F x xF x x x
x x
3 1 2 3 3 2 3 44 1 2 3 4
1 4
( , , ) ( , , ) 1 1( , , , ) 0
2 1
F x x x F x x xF x x x x
x x
3 2 3 4 3 3 4 54 2 3 4 5
2 5
( , , ) ( , , ) 1 1( , , , ) 0
1 2
F x x x F x x xF x x x x
x x
2 2
( ) ( 2) 2 ( 4) 2 ( 1) 1
6 4 8 3 2
F x f x x x
x x x x x