Interpolarea Functiilor

Interpolarea funcțiilor

CUPRINS

Introducere

Capitolul 1: Polinom de interpolare. Definiție. Eroarea de interpolare

Capitolul 2: Polinomul Lagrange de interpolare

2.1 Prezentare teoretică

2.1.2 Algoritm pentru determinarea polinomului Lagrange

2.1.2 Exemple

Capitolul 3: Polinomul Newton de interpolare

3.1 Polinomul de interpolare de speța întâi al lui Newton

3.1.1 Algoritm pentru determinarea polinomului Newton de speța întâi. 1

3.1.2 Exemple

3.2 Polinomul de interpolare de speța a doua al lui Newton

III.2.1 Algoritm pentru determinarea polinomului Newton de de speța a doua. 2

3.2.2 Exemple

3.3 Polinomul lui Newton cu diferențe divizate

3.3.1 Algoritm pentru determinarea polinomului lui Newton cu diferențe divizate.

3.3.2 Exemple

Capitolul 4: Metoda lui Aitken de interpolare

4.1 Prezentare teoretică

4.2Algoritm Metoda lui Aitken

4.3 Exemple

Capitolul 5: Interpolarea cu funcții spline cubice

5.1 Prezentare teoretică

5.2 Algoritm pentru funcții spline cubice

5.3 Exemple

Concluzii

Bibliografie

Introducere

Problema aproximării funcțiilor intervine în situații diverse iar multitudinea formulărilor și metodelor de rezolvare corespunzătoare, constituie o reflectare directă a acestei diversități.

În acestă lucrarea î-mi propun o tratare a câtorva metode de interpolare a problemelor de o singură variabilă și câteva aplicații ale interpolării în rezolvarea unor probleme de aproximare ̧și calcul numeric.

În primul capitol se introduce noțiunea de polinom de interpolator și ̧se determină forma generală a polinomului de interpolare cu noduri simple și teorema care stabilește eroarea maximă cu care polinomul 𝑃𝑛 aproximează funcția f.

Capitolelel II ,III,IV,V cuprind o scurtă prezentare teoretică pentru identificarea formulelor de interpolare:

polinoamul lui Lagrange  polinomul lui Newton

 de speța întâi, de speța a doua, cu diferențe divizate

metoda lui Aitken de interpolare

interpolarea cu funcții spline cubice

Pe baza acestor formule se identifică pentru fiecare caz un algoritm în pseudocod, după care se trece in limbajul specific compilatorului din Maple. Pentru toate acestea este nevoie de anumite cunoștințe de programare și elemente specifice limbajului in care se implementează pseudocodului acesteia.

În cadrul fiecărui capitol sunt aplicații simple care sunt rezolvate atât prin calcul matematic cat și prin implementarea programului creat în Maple. Se compară in cele din urmă ambele cazuri atât numeric cât și grafic.

Exista doua seturi de probleme, în primul se cunosc valorile funcțiilor și trebuie identificată forma funcției iar în cel de al II-lea se cunoaște forma funcției și trebuie calculate valorile ei in anumite puncte. În urma rezolvări acestor probleme rezultă anumite concluzii specifice metodelor de interpolare.

Capitolul 1: Polinom de interpolare. Definiție. Eroarea de interpolare.

Capitolul 1: Polinom de interpolare. Definiție. Eroarea de interpolare.

În aplicațiile de calcul este necesară de multe ori utilizarea unor funcții tabelare, cum ar fi tabelele matematice, tabele ale unor mărimi fizice măsurate sau calculate e.t.c, în cele din urmă rezolvarea se limitează la cazul funcțiilor reale de o variabilă reală.

În toate aceste situații, funcția

𝑓: [𝑎, 𝑏] → 𝑅

este specificată prin valorile yi luate într-un număr de puncte 𝑥𝑖 ∈ ⌈𝑎,𝑏⌉, numite

puncte de rețea, adică 𝑓(𝑥𝑖) = 𝑦𝑖, i=1, 2,….,n

Deseori se impune prelucrarea numerică a acestor dependențe tabelate (subtabelare, derivare, integrare etc.), ceea ce implică cunoașterea valorilor funcției pentru argumente diferite de punctele de tabelare.

În multe din aceste situații, însă, obținerea unor informații suplimentare celor tabelate este foarte dificilă, dacă nu chiar imposibilă.

Chiar și în cazul dependențelor pentru care este cunoscut algoritmul de calcul, complexitatea acestuia poate face uneori ineficientă în utilizarea lui pentru detalierea informației asupra funcției.

Fie f : [a, b] → R o funcție. Se pune problema determinării unei funcții F care să aproximeze funcția f. O asfel de aproximație este necesară în următoarele situații:

Când nu se cunoaște expresia analitică a lui f, ci doar valorile sale întrun număr finit de puncte x0, x1, …, xn din intervalul [a, b].

Când expresia analitică a lui f este prea complicată și calculele efectuate cu ajutorul acesteia ar fi prea dificile.

F trebuie să fie o funcție simplă, ușor de evaluat, de diferențiat și de integrat. În cele ce urmează F va fi un polinom.

Fie x0, x1, …, xn n+1 puncte distincte din intervalul [a, b], și yi = f(x i) pentru orice i = 0,1,…n. Pentru ca polinomul de grad mai mic sau egal cu n, Pn, să fie un polinom de

interpolare pentru f trebuie satisfăcute relațiile:

(1) Pn(xi) = yi, i = 0, 1, …, n .

Polinomul determinat de condițiile anterioare este unic. Într-adevăr fie

Pn(x) = anxn + a n-1Xn-1 + … + a1x+ a0

Relațiile anterioare conduc la sistemul:

Capitolul 1: Polinom de interpolare. Definiție. Eroarea de interpolare.

.

Determinatul acestui sistem este:

(fiind un determinant Vandermonde). Deci ∆ ≠ 0, și în consecință sistemul (2) este compatibil determinat, adică polinomul de interpolare Pn este unic determinat.

Coeficienții polinomului de interpolare pot fi determinați rezolvând sistemul (2), dar dacă n este mare, atunci volumul de calcul este mare.

De aceea se utilizează diferite forme comode ale polinoamelor care conduc la polinoame de interpolare Lagrange, Newton, etc.

Teorema următoare stabilește eroarea maximă cu care polinomul aproximează

funcția f:

Teoremă. Fie f : [a, b] → R o funcție de clasă . Fie puncte distincte din intervalul [a, b], și = f( ) pentru orice i = 0,1,…n.

Fie polinomul de interpolare, adică polinomul de gradul n ce satisface relațiile = pentru orice i = 0, 1, …, n . Atunci oricare ar fi x [a, b], avem:

.

Capitolul 2: Polinomul Lagrange de interpolare

2.1 Prezentare teoretică

Considerăm că funcția f este cunoscută pe baza unui ansamblu de valori într-o rețea de noduri x0,x1,…,xn nu neapărat echidistante:

yi  f(xi), i  0,n .

Se pune problema determinării unui polinom de grad n, de forma:

Ln(x)  y00(x) y11(x)… ynn(x)

care să coincidă cu funcția f în nodurile de interpolare:

Ln (xi)  f(xi)  yi, i  0,n .

Funcțiile 0,1,…,n sunt polinoame de grad n ce urmează a fi determinate, y0,y1,…,yn fiind valorile funcției în punctele x0,x1,…,xn .

Aceste relații pot fi puse sub forma:

n

ykk (xi)  yi, i  0,n . k0

Acest ansamblu de relații poate fi satisfăcut dacă:

0, i  k

k (xi)   . 1, i  k

Polinomul k se anulează în toate punctele xi, i  k , deci este de forma:

n

k (x)  ak (x  xi), k  0,n .

i0 ik

Determinarea coeficientului ak se poate face din condiția

k (xk ) 1

rezultând pentru k o expresie de forma:

k (x)  in0 xxkxxii , k  0,n .

ik

În aceste condiții, polinomul Lagrange capătă forma:

L n n xxi

n (x)  k0yki0 xk xi .

ik

2.1.2 Algoritm pentru determinarea polinomului Lagrange

Pentru generarea algoritmului vom scrie explicit formulele folosite pentru scrierea algoritmului:

Fie f : [a, b] → R o funcție, fie 𝑥0, 𝑥1, …, xn n+1 puncte distincte din intervalul [a, b],

și yi = f(xi) pentru orice i = 0,1,…n. Forma polinomului de interpolare Lagrange este:

Ln(x) = 𝑦0𝑏0(x) + 𝑦1𝑏1(x) + … + yn bn(x) unde bi sunt polinoame de grad n. Punând condițiile Ln(xi) = yi pentru orice i= 0, 1, …, n , se obține

𝑏 (𝑥) = (x − xi)(x − x1)…(x − xi−1)(x − xi+1)… (x − xn)

și deci

Procedura pentru calculul valorii polinomului Lagrange

real Lagrange

(

intreg n, // numărul de puncte cunoscute real x[ ], // vectorul absciselor punctelor cunoscute real y[ ], // vectorul ordonatelor punctelor cunoscute real xx, // punctul în care se calculează interpolarea

)

{ // declararea variabilelor locale intreg i, j ; // contori in buclele ‘for()’ real sum ; // variabilă ce reține suma real prod ; // variabilă ce reține produsul

// corpul de instructiuni al functiei sum=0; pentru i=0,n

{ prod=1; pentru j=0,n dacă j  i

xx x

j

prod  prod ;

x  x

i j

sum  sum yi  prod;

} returnează sum; // valoarea polinomului in punctul de interpolare cerut. }

Procedură MAPLE pentru calculul valorii polinomului Lagrange

lagrange := proc (n, x, y, xx) local sum, prod, i, j; sum := 0; for i from 0 to n do prod := 1; for j from 0 to n do if i <> j then

prod := prod*(xx-x[j])/(x[i]-x[j]) fi;

od;

sum := sum+y[i]*prod; od;

RETURN(simplify(sum)) end;

În cazul in care se cunoaște forma lui f(x) se apelează o procedură pentru a crea vectorul :

y f(x0), f(x1) f(x2), ……………… f(xi)…….. f(xn)

fx := proc (f, n, x) local yy, i; yy := array(0 .. n); for i from 0 to n do yy[i] := evalf(f(x[i]))

od; RETURN(yy) end

2.1.2 Exemple

Să se găsească polinomul de interpolare Lagrange pentru următorul set de date și să se compare cu rezultatul obținutn prin implementarea procedure in Maple:

a)

b)

În formula Ln (x)  n yk n xxk xxii se notează polinoamele de interpolare Lagrange

k 0 i 0 ik

fundamentale cu ln (x)  n xxkxxii

i 0 ik

Pentru punctul a).

Polinoamele de interpolare Lagrange fundamentale sunt:

-x

𝐿3(𝑥) =1-x

Pentru punctul b).

Polinoamele de interpolare Lagrange fundamentale sunt:

în urma calculelor rezultă:

Implementare procedurii Maple pentru punctele a) și b)

Se consideră funcțiile:

1+𝑥2

Să se calculeze polinomul lui Lagrange în anumite puncte.

Folosind implementarea proceduri Lagrange se vor compara valorile funciei f(x) atât numeric si grafic.

>

>

Capitolul 3: Polinomul Newton de interpolare

3.1 Polinomul de interpolare de speța întâi al lui Newton

Acest polinom de interpolare se exprimă funcție de diferențele finite.

Fie f:a,b R și rețeaua x0,x1,x2,…,xn cu pasul constant h.

Definiție. Se numește diferență finită (la dreapta) de ordinul întâi expresia : f x  f x  h f x unde h este pasul constant, iar diferența finită de ordinul n expresia : n f xn1 f x

Diferențele finite au următoarele proprietăți : 1. Operatorul diferență finită este liniar :

c1 f1  c2 f2 c1f1  c2f2

2. Diferența finită de ordinul n se calculează cu formula :

n k k f x n  kh n f x 1 Cn

k0

Diferențele finite la dreapta mai pot fi obținute și cu ajutorul tabelului.

Se numește putere generalizată de ordinul n a lui x expresia: xn xxhx 2h…xn1h

Pentru h=0 puterea generalizată coincide cu puterea obișnuită.

Diferența finită a puterii generalizate este:

xn nhxn1

Diferența finită de ordinul k a puterii generalizate este:

k xn nn1n2…nk1xnk

Fie funcția tabelată dată în tabelul de mai sus unde rețeaua x0,x1,x2,x3,…,xn este cu pasul constant h.

Prin cele n+1 puncte trece un polinom de gradul n pe care îl căutăm sub forma Pn(x) C0 C1(xx0)[1] C2(xx0)[2]…Cn(xx0)[n]

unde (xx0)[i]  (xx0)(xx1)…(xxi1) , i =1, 2, …n

și coeficienții C0,C1,…,Cn sunt necunoscute pe care le vom calcula. Se observă că

Pn(x0)  y0  C0

Se numește putere generalizată de ordinul n a lui x expresia: xn xxhx 2h…xn1h

Pentru h=0 puterea generalizată coincide cu puterea obișnuită.

Diferența finită a puterii generalizate este:

xn nhxn1

Diferența finită de ordinul k a puterii generalizate este:

k xn nn1n2…nk1xnk

Fie funcția tabelată dată în tabelul de mai sus unde rețeaua x0,x1,x2,x3,…,xn este cu pasul constant h.

Prin cele n+1 puncte trece un polinom de gradul n pe care îl căutăm sub forma Pn(x) C0 C1(xx0)[1] C2(xx0)[2]…Cn(xx0)[n]

unde (xx0)[i]  (xx0)(xx1)…(xxi1) , i =1, 2, …n

și coeficienții C0,C1,…,Cn sunt necunoscute pe care le vom calcula. Se observă că

Pn(x0)  y0  C0

Calculăm diferența finită de ordinul întâi :

Pn(x) C1h 2C2h(xx0)[1]…nCnh(xx0)[n1] Făcând substituția x x0 rezultă Pn(x0)  C11!h.

Se poate calcula C1 Pnx0 1!h

Se continuă calculul diferențelor finite în punctul x0 și se observă că :

Ck kPnkx0 k Pn x0k y0, k=0, 1, 2, … n.

, 

k!h

Ținând cont de formulele de calcul ale coeficienților, polinomul lui Newton de interpolare de speța întâi poate fi scris astfel:

y0 x x01  2!2hy20 x x02  n!nhyn0 x x0n

Pnx0 y0  

1!h

Deoarece în calculul coeficienților s-au utilizat diferențele finite la dreapta polinomul poartă denumirea de polinom a lui Newton de interpolare de speța întâi.

3.1.1 Algoritm pentru determinarea polinomului Newton de speța întâi.

Pentru generarea algoritmului vom scrie explicit formulele folosite pentru scrierea algoritmului:

Fie f : [a, b] → R o funcție, fie 𝑥0, 𝑥1, …, xn n+1 puncte distincte cu pasul constant h din intervalul [a, b], și yi = f(xi) pentru orice i = 0,1,…n. Forma polinomului Newton de speța I este:

y0 x

Pnx0 y0  1!h   x01  2y20 x x02  n!nhyn0 x x0n

2!h

Procedură pentru calculul valorii polinomului Newton de speța întâi.

)

{ // declararea variabilelor locale real sum ; // variabila ce reține sumele parțiale real prod ; // variabila ce reține produsele integ i, j ; // contoare in buclele ‘for()’ real y1[];//trebuie pastrate valorile inițiale ale lui y deoarece dacă se apelează funcția de mai multe ori atunci valorile initiale ale lui y devin valorile rezultate in urma prelucrari ultimului apel al proceduri

// corpul de instructiuni al functiei pentru i= 1,n y1i=yi;

sum = y10 ; // pornesc cu suma de la y0 prod = 1 ; pentru i= 1,n { // urmeaza sa se execute un corp de instructiuni pentru j=0, n-i y1j = y1j+1 – y1j ; // calculul diferentelor finite

prod  prod *xp x0  i 1*h* 1 *1;

h i

sum = sum + y10*prod ;

}

returnează sum ; // valoarea interpolata

}

Procedură MAPLE pentru calculul valorii polinomului Newton de speța întâi.

newton1:=proc(n,x0,h,y, xp) local sum,prod,i,j,y1; for i from 0 to n do y1[i]:=y[i]; od; sum:=y1[0];

prod:=1; for i from 1 to n do for j from 0 to n-i do y1[j]:=y1[j+1]-y1[j]; od;

prod:=prod*(xp-(x0+(i-1)*h))*(1/h)*(1/i); sum:=sum+y1[0]*prod; od;

RETURN(simplify(sum)); end;

În cazul in care se cunoaste forma lui f(x) se apeleaza o procedura pentru a crea vectorul :

y f(x0), f(x1) f(x2), ……………… f(xi)…….. f(xn)

fx := proc (f, n, x) local yy, i; yy := array(0 .. n); for i from 0 to n do yy[i] := evalf(f(x[i])) od;

RETURN(yy)

End

3.1.2 Exemple

3. Să se găsească polinomului Newton de speța întâi pentru următorul set de date și să se compare cu rezultatul obținutn prin implementarea procedure in Maple:

a)

b)

Pentru punctul a).

Pnx0 y0  1!yh0 x x01  2y20 x x02  n!nhyn0 x x0n

2!h

h=1

Șirul diferențelor finite la stanga este șirul de pe prima linie, începând cu valorile funcției, adică:

2,-1,0,0

P(x)=

= 2 − 𝑥 + 1 = −𝑥 + 1

Pentru punctul b).

h=

Șirul diferențelor finite la stanga este șirul de pe prima linie, începând cu valorile funcției, adică:

1,-1,0,2,4

P(x)=

22

Implementarea procedurii Maple pentru punctele a) și b)

4. Se consideră func

Să se calculeze polinomului Newton de speța întâi în anumite pucte.

Folosind polinomului Newton de speța întâi se va compara cu valorile funcției f(x) atât numeric si grafic.

3.2 Polinomul de interpolare de speța a doua al lui Newton

Acest polinom de interpolare se exprimă în funcție de diferențele finite la stânga.

Fie f:a,b R și rețeaua x0,x1,x2,…,xn cu pasul constant h.

Definiție. Se numește diferență finită (la stânga) de ordinul întâi expresia :

f x f x f x  h

unde h este pasul constant, iar diferența finită de ordinul n expresia :

n f xn1 f x

Între cele două diferențe finite există următoarea legătură

f xf x h

Diferențele finite la stânga mai pot fi obținute și cu ajutorul tabelului.

Fie funcția tabelată dată în tabelul de mai sus unde rețeaua x0,x1,x2,x3,…,xn este cu pasul constant h.

Prin cele n+1 puncte trece un polinom de gradul n pe care îl căutăm sub forma:

Pn (x) C0 C1(xxn )[1] C2(xxn )[2] …Cn (xxn )[n]

unde (xxn)[i]  (xxn)(xxn1)…(xxni) , i =n, n-1, …i

și coeficienții C0,C1,…,Cn sunt necunoscute pe care le vom calcula diferență finită (la stânga)

Ck  kk!Phnkxn  , kPnxn k yn , k=n, n-1, n-2, … 0.

Ținând cont de formulele de calcul ale coeficienților, polinomul lui Newton de interpolare de speța a doua poate fi scris astfel:

Pnx  yn  yn x  xn1  2!2hy2n x  xn12  n!nhynn x  x1n 1!h

III.2.1 Algoritm pentru determinarea polinomului Newton de de speța a doua.

Pentru generarea algoritmului vom scrie explicit formulele folosite pentru scrierea algoritmului:

Fie f : [a, b] → R o funcție, fie 𝑥0, 𝑥1, …, xn n+1 puncte distincte cu pasul constant h din intervalul [a, b], și yi = f(xi) pentru orice i = 0,1,…n. Forma polinomului Newton de speța a doua este:

Pnx  yn  yn x  xn 1  2!2hy2n x  xn12  n!nhynn x  x1n 1!h

Procedură pentru calculul valorii polinomului Newton de speța a doua.

real Newton2(

intreg n, // numărul de puncte cunoscute real xn , // abcscisa maximă a punctelor cunoscute real h, // pasul constant între abscisele cunoscute real y[ ], // vectorul ordonatelor punctelor cunoscute real xp //abscisa punctului în care se face

// interpolarea

)

{ // declararea variabillelor locale real sum ; // variabila ce reține sumele parțiale real prod ; // variabila ce reține produsele intreg i, j ; // contoare

real y1[];//trebuie pastrate valorile inițiale ale lui y deoarece dacă se apelează funcția de mai multe ori atunci valorile initiale ale lui y devin valorile rezultate in urma prelucrari ultimului apel al proceduri

// corpul de instructiuni al functiei pentru i= 1,n y1i=yi; sum = y1n ; // valoarea interpolata porneste de la yn prod = 1; pentru i= 1,n {

pentru j= n,i y1j=y1j-y1j-1 ; // calculul diferentelor finite

1 1

prod  prod *xp xn i 1*h* h * i ;

sum = sum + y1n*prod ;

} returnează sum; // valoarea polinomului de interpolare in punctul // cerut. }

Procedură MAPLE pentru calculul valorii polinomului Newton de speța a doua.

newton2:=proc(n,xn,h,y,xp) local sum,prod,i,j,y1; prod:=1; y1:=array(0..n); for i from 0 to n do y1[i]:=y[i]; od; sum:=y1[n]; for i from 1 to n do for j from n by -1 to i do y1[j]:=y1[j]-y1[j-1]; od;

prod:=prod*(xp-(xn-(i-1)*h))*(1/h)*(1/i); sum:=sum+y1[n]*prod; od;

RETURN(simplify(sum)); end;

În cazul in care se cunoaște forma lui f(x) se apelează o procedura pentru a crea vectorul :

fx := proc (f, n, x) local yy, i; yy := array(0 .. n); for i from 0 to n do yy[i] := evalf(f(x[i]))

od; RETURN(yy)

End

3.2.2 Exemple

1. Să se găsească polinomului Newton de speța a doua pentru următorul set de date și să se compare cu rezultatul obținutn prin implementarea procedure in Maple:

a)

b)

Pnx  yn  yn x  xn1  2!2hy2n x  xn12  n!nhynn x  x1n 1!h

Pentru punctul a.

h=1

Șirul diferențelor finite la stanga este șirul de pe ultima linie, începând cu valorile funcției, adică:

-1,-1,0,0

P(x)=

= −1 − 𝑥 + 2 = −𝑥 + 1

Pentru punctul b).

𝜋

h=

2

Șirul diferențelor finite la stanga este șirul de pe prima linie, începând cu valorile funcției, adică:

1,1,0,-2-,2

P(x)=

Implementarea procedurii Maple pentru punctele a) și b)

Să se calculeze polinomului Newton de speța a doua în anumite puncte.

Folosind polinomului Newton de speța a doua se vor compara valorile funciei f(x) atât numeric si grafic.

>

>

3.3 Polinomul lui Newton cu diferențe divizate

Fie funcția f (x) dată sub forma celei prezentate mai sus, unde rețeaua x0,x1,x2,…,xn din domeniul de definiție al funcției nu are pas constant.

Se numește diferență finită de ordinul k+i a funcției f expresia : f xi1, xi , xi1,…, xik   f xi , xi1,…, xik  f xi1, xi ,…, xik1 (6.22)

xik  xi1

Se determină polinomul de gradul n, de forma :

Pn(x)  C0 C1(xx0)C2(xx0)(xx1)…Cn(xx0)(xx1)…(xxn1) (6.23) cunoscând n+1 puncte (xi,yi ), i=0, …,n , care verifică polinomul.

Se observă că Pn(x0)  y0  C0 .

Calculăm diferența divizată de ordinul întâi pentru polinomul Pn(x) și se facex  x1 Pn(x0,x1) C1 .

Calculând în continuare, se determină diferența divizată de ordinul k și luând pe x xk se obține valoarea coeficientului Ck :

Ck  Pn(x0,x1,x2,…,xk ), k=0, 1, …,n.

Polinomul se scrie acum sub forma:

Pn(x)  y0  Pn(x0, x1)(x x0) Pn(x0, x1, x2)(x x0)(x x1)…

 Pn(x0,…, xn)(x x0)(x x1)…(x xn1)

Polinomul obținut poartă numele de polinomul lui Newton de interpolare cu diferențe divizate.

3.3.1 Algoritm pentru determinarea polinomului lui Newton cu diferențe divizate.

Procedură pentru calculul valorii polinomului Newton cu diferențe divizate.

)

{ // declararea variabilelor locale

real y1[];//trebuie pastrate valorile iniiale ale lui y deoarece dacă se apelează funcia de mai multe ori atunci valorile initiale ale lui y devin valorile rezultate in urma prelucrari ultimului apel al proceduri

// corpul de instructiuni al functiei pentru i= 1,n y1i=yi; sum = y10 ; prod = 1 ;

pentru i= 0,n-1 { y1j1 y1j

Procedură Maple pentru calculul valorii polinomului Newton cu diferențe divizate.

newton3:=proc(n,x,y, xx) local sum,prod,i,j,y1; y1:=array(0..n); for i from 0 to n do y1[i]:=y[i];od; sum:=y1[0]; prod:=1;

for i from 0 to n-1 do for j from n-1 by -1 to i do y1[j+1]:=evalf(y1[j+1]-y1[j])/(x[j+1]-x[j-i]); od; od;

for i from 0 to n do prod:=prod*(xx-x[i-1]); sum:=sum+y1[i]*prod; od;

RETURN(simplify(sum)); end;

În cazul in care se cunoaste forma lui f(x) se apeleaza o procedura pentru a crea vectorul :

fx := proc (f, n, x) local yy, i; yy := array(0 .. n); for i from 0 to n do yy[i] := evalf(f(x[i]))

od; RETURN(yy)

End

3.3.2 Exemple

1. Să se găsească polinomul Newton cu diferențe divizate pentru următorul set de date și să se compare cu rezultatul obținutn prin implementarea procedure in Maple:

a)

b)

Pn (x)  y0 Pn (x0, x1)(xx0)Pn (x0, x1, x2)(xx0)(xx1)…

Pn (x0,…, xn )(xx0)(xx1)…(xxn1)

f xi1,xi,xi1,…,xik  f xi,xi1,…,xik  f xi1,xi,…,xik1

xik  xi1

Punctul a)

Șirul diferențelor divizate este șirul primelor valori de pe fiecare coloană, începând cu

valorile funcției, adică:

-1,-1,0,0

P(x)=2 − 1(𝑥 + 1) + 0(𝑥 + 1)(𝑥 − 0) + 0(𝑥 + 1)(𝑥 − 0)(𝑥 − 1) = 2 − 𝑥 − 1 = −𝑥 + 1 Punctul b).

Șirul diferențelor divizate este șirul primelor valori de pe fiecare coloană, începând cu valorile funcției, adică:

P(x)=

I

Implementarea procedurii Maple pentru punctele a) și b)

1. Se consideră funcțiile:

Să se calculeze polinomul Newton cu diferene divizate în anumite pucte.

Folosind polinomul Newton cu diferen e divizate se va compara cu valorile funciei f(x) atât numeric si grafic.

>

>

Capitolul 4: Metoda lui Aitken de interpolare

4.1 Prezentare teoretică

Metoda lui Aitken de interpolare dă același rezultat ca și metoda lui Lagrange de interpolare. Se realizează mai multe interpolări liniare. Cu fiecare interpolare, numărul punctelor rămase se micșorează cu o unitate, iar funcția ce trece prin două puncte de la etapa curentă crește în grad, astfel că în final, dacă sunt date n+1 puncte, se obține o funcție de gradul n.

Considerăm funcția dată în tabelul:

y0 j  x j  x y0  x  x0 y j j=1, 2, 3, …, n

xj  x0 xj  x0

y01j  x j  x I01 x  x1 I0 j j=2, 3, …, n x j  x1 x j  x1

– – – – – – – – – – – – – – – –––––-

y012…n  xnxn xx I012…n2n1  xxnxxnn11 I012…n2n

 n 1

Valoarea interpolată a funcției tabelate în punctul x este y012…n .

4.2 Algoritm Metoda lui Aitken

Procedură metoda lui Aitken

)

{ // declararea variabilelor locale intreg i, j ; // contoare

// corpul de instructiuni al functiei real y1[];//trebuie pastrate valorile iniiale ale lui y deoarece dacă se apelează funcia de mai multe ori atunci valorile initiale ale lui y devin valorile rezultate in urma prelucrari ultimului apel al proceduri

// corpul de instructiuni al functiei pentru i= 1,n y1i=yi;

pentru i= 1,n pentru j= i,n execută

returnează y1[n] ;

}

Procedură Maple (metoda lui Aitken)

aitken:=proc(n,x,y, xx) local i,j,y1; y1:=array(0..n); for i from 0 to n do y1[i]:=y[i];od;

for i from 1 to n do for j from i to n do y1[j]:=y1[i-1]*(xx-x[j])/(x[i-1]-x[j])+ y1[j]*(xx-x[i-1])/(x[j]x[i-1]);od;od;

RETURN(simplify(y1[n])); end;

În cazul in care se cunoaște forma lui f(x) se apelează o procedura pentru a crea vectorul :

fx := proc (f, n, x) local yy, i; yy := array(0 .. n); for i from 0 to n do

yy[i] := evalf(f(x[i])) od;

RETURN(yy)

End

4.3 Exemple

Să se găsească polinomul de interpolare folosind metoda lui Aitken pentru următorul set de date prin implementarea procedurii in Maple:

a)

b)

Implementarea procedurii Maple pentru punctele a) și b)

Se consideră funcțiile:

ln( )( 3 ) 8

Să se calculeze polinomul de interpolare prin metoda lui Aitken în anumite puncte.

Folosind polinomul de interpolare se vor compara valorile funcției f(x) atât numeric si grafic.

>

Capitolul 5: Interpolarea cu funcții spline cubice

5.1 Prezentare teoretică

Fie f :a,b R și nodurile ax1 x2 …xn1 b.

Definiție. Se numește funcție spline cubică asociată funcției f și nodurilor x1,…,xn1, o funție de clasă C2 , s :a,b R , astfel încât sxi  f xi  i1,…,n1 și restricția funcției s la fiecare interval xi ,xi1 este polinomială de grad cel mult 3.

Teoremă. Există și este unică o funcție spline cubică asociată funcției f și nodurilor x1,…,xn1, astfel încât s(a)  s(b)  0.

Să notăm hi  xi1  xi , ai  sxi , i1,…,n1. Atunci a1 an1  0. Se arată că pentru xxi ,xi1 avem:

s(x)  ai xi1  x3  ai1 x  xi 3 

6hi 6hi

hi2 a  xi 1  x  h2  x

 f xi  6 i  hi  f xi1 6i ai1 hi xi 

Se arată că necunoscutele rămase a2,…,an sunt soluțiile sistemului Ax b, unde

x  a2,…,an ,

h1 h2 h2



 3 6

 h2 h2 h3

1  1 1 

0 0 0 0 

 h3 0 0 0 

6

    

0 0 hn1 hn1 hn 

6 3 

1

b  b1,…,bn1, bi  h f xi hi  hi1  f xi1 hi1 f xi2 . i 

Matricea A este diagonal dominantă pe linii și deci sistemul Ax b are soluție unică, iar aceasta se poate aproxima cu metoda lui Jacobi.

Pe fiecare interval xi ,xi1 evaluarea erorii se face cu formulele stabilite la interpolare cu polinoame.

Fie

XgC[a2,b]gxi  f xi , i1,…,n1

și

b 2

:XR , (g)  a g(x) dx .

Are loc următoarea caracterizare variațională: Dacă sX este funcția spline cubică din teorema 1, atunci (s)  min g.

gX

Reciproc, dacă uX și (u)  min x, atunci u este funcția spline cubică din teorema 1.

gX

5.2 Algoritm pentru funcții spline cubice

Date de intrare : x – lista argumentelor funcției, f – lista valorilor funcției, xx – variabila

Date de ieșire : dacă z este număr, atunci returnează valoarea funcției spline în acel număr, dacă z este simbol, atunci returnează expresiile pe subintervale ale funcției spline.

n = numărul de puncte, A – matrice pătratică de ordinul n−2, b – vector cu n–2 linii

pentru i = 1, n − 1 hi = xi+1 − xi pentru i = 1, n − 2

Ai,i = 2(hi + hi+1)

pentru i = 2, n − 2

Ai,i−1 = hi Ai−1,i = hi

pentru i = 1, n − 2

c1 = 0 cn = 0 pentru i = 2, n − 1

ci = a i − 1-a soluție a sistemului tridiagonal Ac = b

pentru i = 1, n − 1

𝑠𝑖0 = 𝑓𝑖

Procedură Maple pentru funcții split cubice

cubicspline:=proc(x::list, f::list, xx) local n,i,h, A, b,c,aa,bb,cc,dd; n:=nops(x);

A:=matrix(n-2, n-2, 0); b:=vector(n-2); for i from 1 to n-1 do h[i]:=x[i+1]-x[i]; od;

for i from 1 to n-2 do A[i,i]:=2*(h[i]+h[i+1]); od;

for i from 2 to n-2 do

A[i,i-1]:=h[i]; A[i-1,i]:=h[i]; od;

for i from 1 to n-2 do

b[i]:=6*((f[i+2]-f[i+1])/h[i+1]-(f[i+1]-f[i])/h[i]); od;

c:=linsolve(A,b); c:=[0,seq(c[i],i=1..n-2),0]; for i from 1 to n-1 do aa[i]:=f[i]; bb[i]:=(f[i+1]-f[i])/h[i]-(2*c[i]*h[i]+c[i+1]*h[i])

/6;

cc[i]:=c[i]/2;

dd[i]:=(c[i+1]-c[i])/(6*h[i]); od;

if type(xx,numeric) then

if evalb(evalf(xx)<evalf(x[1]) or evalf(xx)>evalf(x[n])) then

WARNING(“rezultatele interpolarii nu sunt exacte decat pentru x in intervalul [%1,%2]”, x[1],x[n]) fi;

if (evalf(xx)<evalf(x[1])) then

RETURN(aa[1]+bb[1]*(xx-x[1])+cc[1]*(xx-x[1])^2+dd[1]*(xxx[1])^3); else i:=1;

while evalb(evalf(x[i])<=evalf(xx) and i<n) do i:=i+1; od; if i>=n then

RETURN(aa[n-1]+bb[n-1]*(xx-x[n-1])+cc[n-1]*(xx-x[n-1])^2+ dd[n-1]*(xx-x[n-1])^3);

else i:=i-1; fi;

RETURN(aa[i]+bb[i]*(xx-x[i])+cc[i]*(xx-x[i])^2+dd[i]*(xxx[i])^3); fi; fi;

if type(xx, name) then printf(“Functia spline cubice care interpoleaza datele x=%a si f(x)=%a este\n”, x, f);

for i from 1 to n-1 do

printf(“ %a+%a*(%a-%a)+%a*(%a-%a)^2+%a*(%a-%a)^3 , pentru %a in intervalul [%a,%a] \n”, aa[i],bb[i],xx,x[i],cc[i], xx,x[i],dd[i],xx,x[i],xx,x[i],x[i+1]); od; fi;

RETURN(seq(simplify(f[i]+bb[i]*(xx-x[i])+cc[i]*(xxx[i])^2+dd[i]*(xx-x[i])^3), i=1..n-1));

end:

5.3 Exemple

1. Să se găsească funcțiile split cubice pentru următorul set de date prin implementarea procedurii in Maple:

a)

b)

Implementarea procedurii Maple pentru punctele a) și b)

Warning, rezultatele interpolarii nu sunt exacte decat pentru x in

Functia spline cubice care interpoleaza datele x=[0, 1/2*Pi, Pi, 3/2*Pi,

2*Pi] si

f(x)=[0, 1, 0, -1, 0] este

0+3/Pi*(xx-0)+0*(xx-0)^2+-4/Pi^3*(xx-0)^3 , pentru xx in intervalul [0,1/2*Pi]

1+0*(xx-1/2*Pi)+-6/Pi^2*(xx-1/2*Pi)^2+4/Pi^3*(xx-1/2*Pi)^3 , pentru xx in intervalul [1/2*Pi,Pi]

0+-3/Pi*(xx-Pi)+0*(xx-Pi)^2+4/Pi^3*(xx-Pi)^3 , pentru xx in intervalul [Pi,3/2*Pi]

-1+0*(xx-3/2*Pi)+6/Pi^2*(xx-3/2*Pi)^2+-4/Pi^3*(xx-3/2*Pi)^3 , pentru xx in intervalul [3/2*Pi,2*Pi]

Functia spline cubice care interpoleaza datele x=[0, 1/2*Pi, Pi, 3/2*Pi,

2*Pi] si

f(x)=[0, 1, 0, -1, 0] este

0+3/Pi*(xx-0)+0*(xx-0)^2+-4/Pi^3*(xx-0)^3 , pentru xx in intervalul [0,1/2*Pi]

1+0*(xx-1/2*Pi)+-6/Pi^2*(xx-1/2*Pi)^2+4/Pi^3*(xx-1/2*Pi)^3 , pentru xx in intervalul [1/2*Pi,Pi]

0+-3/Pi*(xx-Pi)+0*(xx-Pi)^2+4/Pi^3*(xx-Pi)^3 , pentru xx in intervalul [Pi,3/2*Pi]

-1+0*(xx-3/2*Pi)+6/Pi^2*(xx-3/2*Pi)^2+-4/Pi^3*(xx-3/2*Pi)^3 , pentru xx in intervalul [3/2*Pi,2*Pi]

2. Se consideră funcțiile:

pentru x=0.4,0,6,0.8,1,1.2

pentru x=1,2,3,4,5

Să se calculeze funcțiile split cubice în punctele stabilite mai sus și să se compare cu valorile lui f(x).

Concluzii

Concluzii

Polinoamele de interpolare Newton și Lagrange diferă numai prin formă, restul este același în ambele cazuri, dacă se consideră aceeași rețea de noduri.

Din punct de vedere al calculului numeric, este de preferat folosirea polinomului

Newton deoarece acesta necesită un număr de operații aritmetice mai mic față de polinomul Lagrange.

Pentru o funcție tabelată, dată prin lista ordonată a valorilor, [x1 =xa, x2, …, xn =xb], și

lista valorilor sale, [f1, f2, …, fn].

Se constată că polinomul de interpolare Lagrange și Newton nu aproximează bine funcția, pentru valori ale lui x în afara intervalului [xa, xb].

Dacă notăm cu xa și xb cel mai mic, respectiv cel mai mare dintre nodurile de interpolare, atunci din punct de vedere computațional, sunt convenabile următoarele polinoame de interpolare: pentru x apropiat de xb este convenabilă utilizarea polinomului

Newton de spețea a doua (la stânga); pentru x apropiat de xa este convenabilă utilizarea polinomului Newton de speța întâi (la dreapta).

Necesarul de memorie este același pentru ambii algoritmi.

Polinomul de interpolare dă rezultate exacte pentru funcții polinomiale de grad maxim n, unde n este numărul de puncte în care se cunoaște valoarea funcției căutate.

Deoarece interpolarea polinomială pe tot intervalul [xa,xb ] (polinoamele de interpolare

Lagrange și Newton) nu converg în totdeauna, apare ideea de interpolare polinomială pe porțiuni (interpolare spline cubică), la care pe fiecare subdiviziune a intervalului [xa, xb] definim un alt polinom de interpolare.

Bibliografie

Bibliografie

Dumitru Ebanca – Metode de calcul numeric pentru algebra Editura: SITECH Craiova 2005

Rusu, Metode numerice în electronică.Aplicații în limbaj C, Editura Tehnică, București, 1997

Andrei Neculai – Convergența algoritmilor de optimizare, Editura Tehnică, București, 2004.

Andrei Neculai – Metode de punct interior în optimizarea convexă, Editura

MatrixRom, București, 2000.

Andrei Neculai – Optimizare fără restricții, Editura MatrixRom, București, 2000.

Andrei Neculai – Teorie versus empirism în analiza algoritmilor de optimizare,

Editura Tehnică, București, 2004.

Bradu Adrian – Analiză numerică. Exerciții și probleme, Editura Universității “Al.

I. Cuza”, Iași, 2001.

Calude Cristian – Complexitatea calculului, Editura Științifică și Enciclopedică, București, 1982.

Corduneanu Adrian – Ecuații diferențiale cu aplicații în electrotehnică, Editura

Facla, Timișoara, 1981.

Dodescu Gh., Toma M. – Metode de calcul numeric, Editura Didactică și

Pedagogică, București, 1976.

Dodescu Gheorghe – Metode numerice în algebră, Editura Tehnică, București, 1979.

Ichim I., Marinescu G. – Metode de aproximare numerică, Editura Academiei, București, 1986.

Bibliografie

Dumitru Ebanca – Metode de calcul numeric pentru algebra Editura: SITECH Craiova 2005

Rusu, Metode numerice în electronică.Aplicații în limbaj C, Editura Tehnică, București, 1997

Andrei Neculai – Convergența algoritmilor de optimizare, Editura Tehnică, București, 2004.

Andrei Neculai – Metode de punct interior în optimizarea convexă, Editura

MatrixRom, București, 2000.

Andrei Neculai – Optimizare fără restricții, Editura MatrixRom, București, 2000.

Andrei Neculai – Teorie versus empirism în analiza algoritmilor de optimizare,

Editura Tehnică, București, 2004.

Bradu Adrian – Analiză numerică. Exerciții și probleme, Editura Universității “Al.

I. Cuza”, Iași, 2001.

Calude Cristian – Complexitatea calculului, Editura Științifică și Enciclopedică, București, 1982.

Corduneanu Adrian – Ecuații diferențiale cu aplicații în electrotehnică, Editura

Facla, Timișoara, 1981.

Dodescu Gh., Toma M. – Metode de calcul numeric, Editura Didactică și

Pedagogică, București, 1976.

Dodescu Gheorghe – Metode numerice în algebră, Editura Tehnică, București, 1979.

Ichim I., Marinescu G. – Metode de aproximare numerică, Editura Academiei, București, 1986.