Lucrarea de laborator nr.3Tema lucrrii: Aproximarea funciilor

III.1. ENUNUL LUCRRII

ntr-un sistem de calcul, funciile numerice se pot prezenta prin:

a) cod indicnd algoritmul de de evaluare a valorilor funciei n fiecare punct al domeniului de definiie;

b) date ndicnd valorile funciei ntr-un numr finit de noduri (puncte) din domeniul de definiie; Scopul acestei lucrri este de a evidenia cele mai eficiente metode de determinare ale valorilor unei funcii numerice reprezentate tabelar, efortul de calcul, erorile nregistrate i limitele acestor metode de aproximare.

III.2. MODELUL MATEMATIC I METODE DE SOLUIONARE

Seconsider o funcie , pentru care se cunosc doar valorile sale i ale unor derivate ale sale ntr-un numr finit de puncte din domeniul de definiie

Problema fundamental a aproximrii funciilor const n determinarea unei funcii astfel nct ,

cu ajutorul creia s se poat evalua valorila funciei f ct i a unor derivate ale acestora n orice punct al domeniului de definiie, dar s se poat studia i proprietile necesare n diverse situaii practice ale funciei f. Funcia f se construiete sub forma , unde

este o mulime liniar independent de funcii simple aparinnd clasei de funcii aproximante aleas ( de cele mai multe ori, clasa funciilor polinomiale), iar

Determinarea coeficienilor se face astfel nct aproximarea funciei F prin funcia F s fie ct mai bun ( s fie minim) , unde

este o funcie pondere Cele mai importante metode ale unor funcii definite tabelar sunt:a) Interpolarea utilizat dac datele cunoscute sunt exacte (neafectate de erori)

se refer la aproximarea valorilor funciei f n punctele din , (pentru i , procedeul de aproximare se numete extrapolare)b) Regresia (ajustarea prin metoda celor mai mici ptrate) utilizat dac datele sunt afectate de erori.

presupune determinarea parametrilor astfel nct s fie asigurat minimizarea ; curba determinat n urma aplicrii regresieu nu trece prin punctele cunoscute ca n cazul interpolrii ci prin barele de eroare ale acestora.III.2.1. INTERPOLARE POLINOMIAL

Fie pentru care sunt cunoscute:

n aceast situaie, un polinom de grad , notat cu: numit polinom de interpolare asociat funciei f i noduri de interpolare astfel nct

EMBED Equation.DSMT4 Cele mai cunoscute forme de prezentare a polinomuluisunt:III.2.1.1. FORMA LAGRANGE

III.2.1.1.a. Pentru noduri oarecare

, unde

Practice, evaluarea valorii funciei f ntr-un punct se poate obine astfel:

x0x1x2...xn-1xnDiyi

...

D0y0

...

D1y1

...

D2y2

.

.

..

.

..

.

.....

.

..

.

..

.

..

.

..

.

.

...

Dn-1yn-1

...

Dnyn

S

unde

sau se obine prin nmulirea elementelor liniei i a tabelului:

iar

Procedeul Aitken:

Conform formulei, aplicarea acestui procedeu presupune construirea tuturor polinoamelor de interpolare sub forma Lagrange, de grad ,Rezultatele se pot aranja tabelar astfel:

...

...

.....................................

.....................................................

.....................

unde

III.2.1.1.b. Pentru noduri echidistante

, unde

( h este ales astfel nct )

III.2.1.2. FORME NEWTON

III.2.1.2.a. Pentru noduri oarecare

unde reprezint diferena divizat de ordinul i corespunztoare funciei f i nodurilor

innd cont de faptul c diferenele divizate sunt introduce recursive (), valorile acestora se pot obine tabelar astfel:

Dif div IDif div IIDif div III...Dif div n-1Dif div n

Diferenele divizate sunt cele marcate cu rou n tabelul anterior.

III.2.1.2.b. Pentru noduri echidistante

cu

unde ky0 reprezint diferena finit progresiv de ordin k corespunztoare funciei f calcult n x0 (i.e.:

N1 se numete forma Newton de spea I a polinomului de interpolare asociat funciei f i nodurilor , echidistante.

De regul ,dac (sau dac mai apropiat de x0 dect de xn; n aceast ituaie se scrie N1 pentru nodurile ).

cu

unde reprezint diferena finit regresiv de ordin k corespunztoare funciei f calcult n xn (i.e.:

N2 se numete forma Newton de spea II i se utilizeaz de obicei pentru aproximarea lui cu ( i pentru , cu mai apropiat de ;n aceast situaie de scrie N2 pentru nodurile ).

Avnd n vedere legtura existent ntre cele dou categorii de diferene finite (, calculul acestora se poate face folosind acelai table:

Dif finit I

Dif finit II

...

Observaii

Diferenele finite pentru N1 (respectiv N2) sunt cele marcate cu rou

Presupunem c pentru o fucie

, n punctele se cunosc

.

Conform teoremei fundamentale a interpolrii polinnomiale, un polinom de grad care are aceleai valori n punctelecu ale funciei f ; de asemenea, valorile derivatei de ordinul I n punctelecoincide cu valorile .

Vom prezenta forma Hrmite (pentru noduri duble) a acestui polinom:

, unde

III.2.2. INTERPOLARE POLINOMIAL PE PORIUNI (FUNCII SPLINE)

Interpolarea cu funcii polinomiale pe poriuni (funcii spline) permite obinerea unor aproximri netede, fr oscilaii nedorite i fr a pierde avantajul evalurii simple.III.2.2.1. INTERPOLAREA CU FUNCII DE BAZ

Interpolarea liniar pe poriuni se realizeaz prin intermediul unei funcii obinut ca o combinaie liniar de funcii de baz (ce sunt continue i liniare pe poriuni)

Dintre principalele seturi de funcii de baz remarcm:

1) Funciile ramp.

Atunci :

, unde

se obine din condiiile de interpolare

,

i prin convenie

2) Funciile clopot.

sunt funcii continue cu suportul n i atunci:

Principalul dezavantaj: F nu este derivabil n nodurile de interpolareIII.2.2.2. INTERPOLAREA CU FUNCII CUBICE

Pentru evaluarea valorilor funciei cu se poate utilize o funcie splin curb (i.e. satisface urmtoarele condiii:

a) ;

b) ;

c) ;

d) ;

e) - condiie de frontier liber

sau

e) i - condiie de frontier impuns.

Conform condiiilor pe care le are de satisfcut, determinarea funciei S revine la calcularea coeficienilor , ntre care exist urmtoarele legturi (n care ):

de unde se obine sistemul de ecuaii liniare

cu:

Ambele sisteme obinute au matricele simetrice i pozitiv definite, sunt compatibil determinate i se rezolv numeric folosind o metod direct de rezolvare a sistemelor de ecuaii liniare.

III.2.3. PSEUDOCODUL ALGORITMILOR

III.2.3.1.REZOLVAREA PRIN FORMA LAGRANGE

Procedura de interpolare Lagrange admite urmtoarea reprezentare n pseudocod:

funcia interp_L(n, x, y, xcrt);evalueaz forma Lagrange a polinomului

;de interpolare n punctul xcrt

ntreg n;gradul polinomului

tablou real x(n), y(n);reeaua de interpolare

real xcrt, ;variabil independent

ycrt,;valoarea polinomului n xcrt

p;variabil intermediar

ycrt = 0

pentru k = 0,n

p = 1

pentru j = 0,n

dac j/ = k atunci

p = p(xcrt xj)/(xk xj)

ycrt = ycrt + ykp

ntoarce ycrt

III.2.3.2.REZOLVAREA PRIN FORME NEWTON

Procedura de interpolare Newton (pentru noduri oarecare) este dependent de calculul tabelar al diferenelor divizate : i se poate reprezenta n pseudocod astfel:procedura prep_(n, x, y, c);determin coeficienii polinomului

ntreg n;gradul polinomului

tablou real x(n), y(n);reeaua de interpolare

c(n);coeficienii polinomului

pentru i = 0,n

ai0 = yi

pentru j = 1,n

pentru i = 0,n j

aij = (ai + 1, j 1 - ai , j 1 )/(xj + i xi)

pentru i = 0,n

ci = a0i

retur

funcia eval_N;evalueaz forma Neuton al polinomului de

;interpolare

tablou real x(n);abscisele reelei de interpolare

c(n);coeficienii polinomului

real xcrt, ;variabil independent

ycrt = cn

pentru k = n 1, 0, 1

ycrt = ck + (xcrt xk) ycrt

ntoarce ycrt

Interpolarea polinomial pe poriuni un rol important l joac algoritmul de identificare a intervalului n care se afl valoarea x . urmtoarea funcie folosete ca scop algortmul cutrii binare:funcia caut_seg(n, x,xcrt)

ntreg n;numr de segmente

tablou real x(n), ; abscisele nodurilor

real xcrt;valoarea variabilei independente

ntreg k;numr segment

dac xcrt xn 1 atunci ntoarce (n 1)

dac xcrt x 1 atunci ntoarce (0)

k1 = 1

k2 = n 1

repet

k = (k1 + k2)/2

dac xk > xcrt atunci

k2 = k

astfel

k1 = k

Pn cnd

ntoarce k1

Interpolarea liniar pe poriuni este evaluat de urmtoarea funcie:

funcia ilpp(n, x, y, xcrt)

ntreg n;numr de segmente

tablou real x(n),y(n) ; date de interpolare

real xcrt;valoarea variabilei independente

real ycrt;valoare interpolat

k = caut_seg(n, x, xcrt)

ycrt = yk + (yk+1 - yk)(x xk)/ (xk+1 - xk)

ntoarce ycrt

Interpolarea cu funcii spline cu condiii la limit naturale se realizeaz astfel:

procedura prep_spline(n, x, y, yd);pregtete datele yd, pentru interpolarea

;spline cu n intervale a unei funcii

;descris prin tabele x,y

pentru k = 0,n 1

pk = (xk+1 - xk);subdiagrama principal

qk = (yk+1 - yk)/pk

pentru k = 1,n 1 ; date de interpolare

sk = 3(qk-1pk + q1pk-1);termenul liber

s0 = 3q0

sn = 3qn-1

pentru k = 1,n 1

qk = 2(xk+1 - xk);diagonala principal

rk = pk-1;supradiagonala principal

q0 = 2

r0 = 1

pn = 1

qn = 2

trida(n, p, q, r, s, yd);rezolv sistemul tridiagonal i determin

;derivatele n noduri

retur

III.2.4. PROGRAM MATLAB

III.2.4.1. APROXIMAREA LAGRANGE

Acest pogram evalueaz valorile formei Lagrange a polinomului de interpolare corespunztoare funciei f i nodurile (unde )function [C,L]= lagran ( X,Y )

%Input X este un vector ce conine abcisele nodurilor

% Y este un vector ce conine valorile funciei n noduri

%Output C este o matrice ce conine coeficienii formei Lagrange a polinomului

%;de interpolare

% L este o matrice ce conine coeficienii Lagrange

w = leght (X);

n = w 1 ;

1 = zeros(w,w)

%Formeaz coeficienii polinomiali Lagrange

fork = 1: n + 1

v = 1;

for j = 1: n +1

if ~ = j

v = conv(v, poly(x(j)))/X(k) X(j));

end

end

L(k,: ) = v;

%Determin coeficienii formei Lagrange a polinomului de interpolare

C = Y*L;

III.2.4.2. APROXIMAREA NEWTON( cu diferene divizate)

Construiete i evalueaz forma Newton de grad a polinomului de interpolare corespunztor unei funcii f i punctelor function [C,D]= newpoly ( X,Y )

%Input X este un vector ce conine abcisele punctelor date

% Y este un vector ce conine ordonatele punctelor cunoscute

%Output C este un vector ce conine coeficienii formei Newton a polinomului de

%;de interpolare

% D este tabelul diferenelor divizate

n = leght (X);

O = zeros(n,n) ;

D (:,1) = X;

%Formeaz tabloul cu diferene divizate

forj = 2 : n

for k = j : n

D(k,j) = (D(k,j 1) D(k 1, j 1)/(X(k) X(k j + 1));

end

end

%Determin coeficienii formei Newton a polinomului de interpolare

C = D(n,n);

for k = (n 1): 1: 1

C = conv (C, poly(X(k)));

m = lenghth (C);

C(m) = C(m) + D(k,k);

end

III.2.4.3. APROXIMAREA CEBEV

Construiete i evalueaz polinomul de interpolare Cebev de grad pe , unde corespunztoare nodurilor function [C,X,Y]= cheby ( fun,n,a,b)

%Input fun este funcia band ce trebuie aproximat

% N este gradul polinomului de interpolare Cebev

% a este extremitatea stng

% b este extremitatea dreapt

%Output C este lista coeficienilor pentru polinom

% X conine abcisele

% Y conine ordonatele

if margin = = 2, a = -1; b = 1; end

d = pi/(2*n + 2);

C = zeros(i, n+i);

for k = 1 : n+1

X(k) = cos((2*k-1)*d);

end

X = (b a)*X/2 + (a + b)?2;

x = X;

Y = eval(fun);

for k = 1 : n + 1

z = (2*k-1)*d;

for j = 1 : n + 1

C(j) = C(j) + Y(k)*cos((j 1)*z));

end

end

C = 2*C n +1;

C(1) = C(1) 2;

III.2.4.4. APROXIMAREA CU FUNCII SPLINE CUBICE

Construiete i evalueaz un interpelant splin cubic pentru puncte function S= esfit ( X, Y, dx0, dxn)

%Input X este vectorul 1xn ce conine abscisele

% Y este vectorul 1xn ce conine abscisele

% este condiia de frontier impus

% este condiia de frontier impus

%Output S: liniile ale lui S sunt coeficienii, n ordine descresctoare, a polinomului cubic

N = length(X) 1;

H = diff(X);

D = dif(X)./H;

A = H(2:N 1);

B = R*(H(1:M 1) + H(2:N));

C = H(2:N);

U = 6*diff(D);

%Condiiile de frontier

B(1) = B(1) H(1)/2;

U(1) = U(1) 3*(D(1) + dxo);

B(N 1) = B(N 1) H(N)/2;

U(N 1) = U(N 1) 3*(dxn D(N));

for k = 2:N 1

temp = A(k 1)/B(k 1);

B(k) = B(k) temp*C(k 1);

U(k) = U(k) temp*U(k 1);

end

M(N) = U(N 1)/B(N 1);

for k = N 2: 1:1

M(k + 1) = (U(k) C(k)*M(k + 2))/B(k);

end

M(1) = 3*(D(1) dxo)/H(1) M(2)/2;

M(N + 1) = 3*(dxn - D(N)/H(N) M(N)/2;

for k = 0,N 1

S(k + 1,1) = (M(k +2) M(k + 1))/(6*H(k + 1));

S(k + 1,2) = M(k + 1)/2;

S(k + 1,3) = D(k +2) N(k + 1)*(2*N(k + 1) + M(k + 2))/6;

S(k + 1,4) = Y(k + 1);

end

_1309513705.unknown

_1309527610.unknown

_1309538646.unknown

_1309679726.unknown

_1309684901.unknown

_1309690685.unknown

_1309697893.unknown

_1309707196.unknown

_1309710765.unknown

_1309711734.unknown

_1309716222.unknown

_1310016310.unknown

_1310016419.unknown

_1309716197.unknown

_1309710818.unknown

_1309708974.unknown

_1309709043.unknown

_1309707269.unknown

_1309702722.unknown

_1309703932.unknown

_1309700591.unknown

_1309691310.unknown

_1309696096.unknown

_1309697463.unknown

_1309691436.unknown

_1309691029.unknown

_1309691076.unknown

_1309690881.unknown

_1309688153.unknown

_1309688824.unknown

_1309690391.unknown

_1309690448.unknown

_1309690293.unknown

_1309688620.unknown

_1309688664.unknown

_1309688273.unknown

_1309687314.unknown

_1309687881.unknown

_1309687963.unknown

_1309687734.unknown

_1309685567.unknown

_1309687200.unknown

_1309685023.unknown

_1309681121.unknown

_1309683191.unknown

_1309684294.unknown

_1309684719.unknown

_1309683222.unknown

_1309681494.unknown

_1309683056.unknown

_1309681267.unknown

_1309680274.unknown

_1309680502.unknown

_1309681070.unknown

_1309680353.unknown

_1309679985.unknown

_1309679986.unknown

_1309679768.unknown

_1309679811.unknown

_1309675229.unknown

_1309678583.unknown

_1309679629.unknown

_1309679681.unknown

_1309679704.unknown

_1309679652.unknown

_1309679241.unknown

_1309679399.unknown

_1309679435.unknown

_1309679257.unknown

_1309679327.unknown

_1309678992.unknown

_1309679125.unknown

_1309678930.unknown

_1309676152.unknown

_1309676295.unknown

_1309676448.unknown

_1309676259.unknown

_1309675751.unknown

_1309676108.unknown

_1309675594.unknown

_1309673493.unknown

_1309674933.unknown

_1309675203.unknown

_1309675213.unknown

_1309675031.unknown

_1309674529.unknown

_1309674608.unknown

_1309674716.unknown

_1309674386.unknown

_1309538752.unknown

_1309539895.unknown

_1309538668.unknown

_1309537585.unknown

_1309538606.unknown

_1309538618.unknown

_1309538633.unknown

_1309537796.unknown

_1309538040.unknown

_1309538271.unknown

_1309538586.unknown

_1309537892.unknown

_1309537599.unknown

_1309536233.unknown

_1309536257.unknown

_1309536278.unknown

_1309536286.unknown

_1309536269.unknown

_1309536236.unknown

_1309536249.unknown

_1309536235.unknown

_1309536234.unknown

_1309536037.unknown

_1309536133.unknown

_1309536232.unknown

_1309536097.unknown

_1309535520.unknown

_1309517330.unknown

_1309517953.unknown

_1309518534.unknown

_1309518806.unknown

_1309527199.unknown

_1309518638.unknown

_1309518242.unknown

_1309518321.unknown

_1309517954.unknown

_1309517621.unknown

_1309517672.unknown

_1309517783.unknown

_1309517826.unknown

_1309517630.unknown

_1309517387.unknown

_1309517545.unknown

_1309517602.unknown

_1309517396.unknown

_1309517351.unknown

_1309517375.unknown

_1309517341.unknown

_1309515264.unknown

_1309517281.unknown

_1309517300.unknown

_1309517312.unknown

_1309517290.unknown

_1309515887.unknown

_1309516717.unknown

_1309516784.unknown

_1309515604.unknown

_1309514789.unknown

_1309515046.unknown

_1309515119.unknown

_1309515011.unknown

_1309513820.unknown

_1309514681.unknown

_1309513818.unknown

_1309513819.unknown

_1309513817.unknown

_1309511182.unknown

_1309513013.unknown

_1309513297.unknown

_1309513326.unknown

_1309513351.unknown

_1309513536.unknown

_1309513316.unknown

_1309513177.unknown

_1309513284.unknown

_1309513285.unknown

_1309513283.unknown

_1309513282.unknown

_1309513166.unknown

_1309513167.unknown

_1309513049.unknown

_1309512638.unknown

_1309512829.unknown

_1309512931.unknown

_1309512960.unknown

_1309512982.unknown

_1309512947.unknown

_1309512871.unknown

_1309512687.unknown

_1309512709.unknown

_1309512730.unknown

_1309512673.unknown

_1309511916.unknown

_1309512328.unknown

_1309511764.unknown

_1309506998.unknown

_1309510498.unknown

_1309511000.unknown

_1309511099.unknown

_1309510645.unknown

_1309508434.unknown

_1309510159.unknown

_1309510469.unknown

_1309508399.unknown

_1309502482.unknown

_1309506280.unknown

_1309506535.unknown

_1309503267.unknown

_1309506073.unknown

_1309506212.unknown

_1309505926.unknown

_1309503054.unknown

_1309501750.unknown

_1309502385.unknown

_1309500072.unknown