C5&6_MN_2015-2016_Cristea

8/16/2019 C5&6_MN_2015-2016_Cristea

http://slidepdf.com/reader/full/c56mn2015-2016cristea 1/13

METODE NUMERICENotite de curs: 2015 – 2016, semestrul 2S.l. Dr. Ing. Anisoara-Gabriela CRISTEA

[email protected] Dunarea de Jos din Galati

Facultatea de Arhitectura NavalaGalati, 2015 – 2016

8/16/2019 C5&6_MN_2015-2016_Cristea


CURS 5&6 APROXIMAREA FUNCTIILOR DE O VARIABILA (I)

Problema aproximarii unei functii de o variabila se poate aplica in diferite situatii, douafiind mai frecvente:

functia este complet cunoscuta dar are o expresie complicata, dificil de manipulat incalcule (in operatii de derivare, de integrare etc.);

functia nu este complet cunoscuta, fiind date numai valorile acesteia pe o multimediscreta si finita de puncte.

Problema aproximarii poate fi formulata astfel:Fie f: [a,b] R, cunoscuta numai prin valorile sale si anume: f(x i) = y i, intr-un numar finitde puncte x i [a,b], numite noduri, cu x 1 = a si x 2 = b. Sa se determine o functie g(x), deexpresie cat mai simpla, care sa poata sa aproximeze cat mai bine functia f(x) peintervalul dat.

Introducere

y = g(x)

y = f(x)

x 1 = a x 2 x 3 Xn = bx k

8/16/2019 C5&6_MN_2015-2016_Cristea


Criterii de aproximare

a) Interpolarea

b) Minimizarea abaterii maxime

c) Minimizarea sumei patratelor abaterilor in noduri.

a) Aproximarea prin interpolare

Presupunand cunoscute valorile y i ale functiei f(x i) in nodurile x i distincte (x 1 < x 2 < … < x n),conditia de interpolare g(x i) = y i reprezinta un sistem de n ecuatii cu n necunoscute. Pentruaproximarea lui g(x) se utilizeaza relatia:

g(x) = a kgk(x)in care a k reprezinta un set de n parametri nedeterminati (scalari) , iar g k(x) un set de n functiisimple cunoscute, liniar independente (functii polinomiale, trigonometrice, exponentiale etc.).

a1) Interpolarea polinomialaUn set de functii despre care se stie ca sunt liniar independente il reprezinta sirul de monoamexk-1 , (k =1,2,…,n). In acest caz functia de interpolare devine un polinom de grad ( n-1 ), numitpolinom de interpolare.

g(x) = P n-1 (x) = a kx k-1 = a 1 +a 2x+a 3x 2+…+a nx n-1

k=1

n

8/16/2019 C5&6_MN_2015-2016_Cristea


Problema determinarii coeficientilor a K se rezolva folosind conditia de interpolare, adicagasind solutiile sistemului de ecuatii liniare:

a kx k-1 =y i

k=1

n

care poate fi scris printr-o ecuatie matriceala astfel:

1 x 2 x 22 … x2 n-1

…………………1 x n x n

2 … xn n-1

a 1

a 2

a n

.. =

y1

y2

yn

1 x 1 x 12 … x1 n-1

Nodurile x i fiind distincte, sistemul este de tip Cramer, cu determinant Vandermonde, avando solutie unica bine determinata pentru coeficientii a K. Metoda este foarte simpla, dar candnumarul de puncte x i este mare, rezolvarea sistemului este dificila sau mai putinconvenabila.

Metoda este simpla, dar cand numarul de noduri x i este mare, rezolvarea sistemului estedificila sau cel putin neconvenabila. De aceea, in aceste cazuri se prefera alte forme alepolinoamelor de interpolare.

8/16/2019 C5&6_MN_2015-2016_Cristea


a2) Forma Lagrange a polinomului de interpolare

In practica, pentru a evita rezolvarea sistemului de ecuatii

o forma mai convenabila pentru exprimarea functiei g(x) o constituie polinomul de interpolareLagrange. Acesta se scrie sub forma:

Pn-1 (x) = y kLk(x) = y 1L1 (x) + y 2L2(x) + … + y n Ln(x)

Coeficientii a K sunt chiar valorile y k ale functiei f(x) in noduri, iar functiile g k(x) din relatia g(x)

= a kgk(x) sunt scrise sub forma unor polinoame, denumite polinoame Lagrange si notate cu

Lk(x). Aceste polinoame, de grad (n-1

) au expresiile:

L1(x) =(x-x 2)(x-x 3)…(x-x n)

(x1-x2)(x1-x3)…(x 1-xn)

sau, intr-o forma concisa:

L2(x) =(x-x 1)(x-x 3)…(x-x n)

(x2-x1)(x2-x3)…(x 2-xn)

Lk(x) = i = 1i k

n

xk - x i

x - x i

Ln(x) =(x-x 1)(x-x 3)…(x-x n-1 )

(xn-x1)(xn-x2)…(x n-xn-1 )

Lk(x i) = 0 pentru k i

Lk(x i) = 1 pentru k = i

a kx k-1 =y i

k=1

n

8/16/2019 C5&6_MN_2015-2016_Cristea


a3) Forma Newton a polinomului de interpolare

O alta modalitate convenabila de construire a polinomului de interpolare o constituiepolinomul lui Newton cu diferente divizate.

Fiind date perechile de numere (x i, y i) se definesc urmatoarele rapoarte, denumite diferentedivizate , notate cu (DD) :

DD (x 2, x 1) =

DD(x 3, x 2, x 1) =

DD(x n, x n-1 ,…, x 1) =

y2 – y 1

x2 – x 1

DD(x 3, x 2) – DD(X 2, x 1)x3 – x 1

DD(x n ,…,x 2) – DD(x n-1 ,…,x 1 )xn – x 1

Diferentele divizate care se folosesc utilizand n puncte se numesc diferente divizate de ordinul ( n-1 )

DD(x 5, x 4, x 3, x 2, x 1)DD(x 4, x 3, x 2, x 1)

DD(x 5, x 4, x 3, x 2)

DD(x 3, x 2, x 1)

DD(x 4, x 3, x 2)

DD(x 5, x 4, x 3)

DD(x 2, x 1)

DD(x 3, x 2)

DD(x 4, x 3)

DD(x 5, x 4)

y1

y2

y3

y4

y5

x1

x2

x3

x4

x5

DD4DD3DD2DD1yx

8/16/2019 C5&6_MN_2015-2016_Cristea


P n-1 (x) = y 1 + (x-x 1) DD(x 2, x 1) + (x-x 1)(x-x 2) DD(x 3, x 2, x 1) + (x-x 1)(x-x 2)…(x-x n-1 ) DD(x n,…,x 1)

P n-1 (x) = polinomul de interpolare (polinomul lui Newton cu diferente divizate)

Rn-1 (x) = restul (eroarea de aproximare la interpolarea polinomiala)

Rn-1 (x) = (x-x i) DD(x, x n, x n-1 ,…,x 1) iar

F(x) = P n-1 (x) + R n-1 (x)

CONCLUZII

• Formula de interpolare Lagrange este aceeasi indiferent daca punctele de interpolaresunt egal distantate sau luate arbitrar pe scara absciselor. Relatia de recurenta estesimpla, usor de aplicat pe calculator, necesitand un spatiu de memorie mai redus.

• Interpolarea Newton permite trecerea cu usurinta la retele cu un numar mai mare depuncte, dar necesita alocarea unui spatiu de memorie mai mare decat in cazul interpolariiLagrange din cauza diferentelor divizate. La adaugarea unor puncte aditionale de

interpolare apar noi termeni in expresia polinomului de interpolare, fara insa a modifica pecei calculati anterior.

8/16/2019 C5&6_MN_2015-2016_Cristea


APROXIMAREA FUNCTIILOR DE O VARIABILA (II)b) Interpolarea cu functii spline

Functiile spline constituie un instrument matematic de data relativ recenta, dar cu o largaaplicabilitate in procesarea pe calculator a datelor numerice. Termenul “ spline ” , de origineengleza, a fost adoptat ca atare in literatura de specialitate si reprezinta denumirea unei rigleflexibile prevazuta cu o serie de greutati de-a lungul ei, folosita de catre desenatori in trasareaunor curbe care trec printr-o serie de puncte.

Functia poligonala este unul din cele mai simple exemple de functii spline.

s(x)

f(x)

x1 = a x n = b

f(a)

f(b) Functiile spline sunt caracterizate prin formele lor pesubintervale dintre doua noduri (care pot fi diverse functiicunoscute) si prin anumite conditii de racordare in noduri.

Fie [a,b] R un interval din dreapta reala si x i o reteade puncte de diviziune (x 1 = a, x n = b). Se noteazacu I i subintervalele [x i, x i+1).

Prin definitie, functia s: [a,b] R se numeste functiespline polinomiala de ordinul m daca:

a) Restrictiile acesteia pe subintervalele I i suntpolinoame de gradul m ;

b) s este derivabila de ( m-1 ) ori pe intervalul (a,b).

A doua conditie contine conditiade racordare in noduri:

s m,i(xi+1) = s m,i+1 (xi+1) k = 0, 1,…, m-1(k) (k)

8/16/2019 C5&6_MN_2015-2016_Cristea


b1) Functia spline de ordinul 1 (linia poligonala)

Este functia cea mai simpla, formata din segmente de dreapta de ecuatie:

s 1,i(x) = m ix +n i , x [x i , x i+1 ), cu panta pe subintervalul I i: m i = .

In relatia respectiva h i = x i+1 – x i este marimea subdiviziunii. Cum s 1,i(x) = y i se obtine n i = y i – m ixi.

Asadar, s 1,i(x) = y i + m i (x – x i) , x [xi, x i+1), i = 1,…, n-1

yi+1 - y i

h i

b2) Functia spline de ordinul 2

Este formata din segmente de parabola racordate in noduri pana la derivata de ordinul intaiinclusiv, adica pentru doua intervale alaturate, atat valorile celor doua functii spline cat si

valorile derivatelor lor de ordinul intai, in nodul comun, sunt egale.

s 2,i(x) = y i + m i(x – x i) + a i(x – x i)2, x [xi, x i+1), i = 1,…, n-1

Cum s 2,i(x i+1) = y i+1 si s 2,i(xi+1) = s 2,i+1 (xi+1), rezultã urmatoarele valori pentru coeficientii a i:‘ ‘

m i

h i

yi+1 - y ia i = h i

2 - m i + m i+1 = 2yi+1 - y i

h ii = 1,…, n-1

pentru pantele in noduri.

8/16/2019 C5&6_MN_2015-2016_Cristea


b3) Functia spline de ordinul 3 (functia spline cubica)

Este una din cele mai utilizate functii ce are derivate continue pana la ordinul doi inclusiv,permitand astfel si calculul razei de curbura.

Aceasta are expresia: s 3,i(x) = y i + m i(x – x i) + b i(x – x i)2

+ a i(x – x i)3

, x [xi, x i+1), i = 1,…, n-1

Conditiile de continuitate in noduri sunt:s 3,i(xi+1) = y i+1 , s 3

',i(x i+1) = s 3

',i+1(xi+1) si s 3,

''i(xi+1) = s 3,

''i+1(x i+1) rezultand urmatoarele valori pentru

coeficientii a i si b i:‘ ‘ “ “

3

h i

- 2m i+1 + m ia i =

2 h i

yi+1 - y i3

b i = 2 h i

m i+1 + 2m i

3

yi+1 - y i

h i

+i = 1,…, n-1

Din a treia conditie se obtine sistemul care da pantele pe noduri m i:

im i-1 + 2m i + im i+1 = d i , in care: h i

h i-1 + h i i =h i-1

h i-1 + h i i =

3h i-1 + h i

d i =yi – y i-1( h i-1

yi+1 - y i

h ih i )

h i-1+

Intrucat relatia in m i-1, m i, m i+1 reprezinta ( n-2 ) ecuatii cu n necunoscute, sistemul trebuiecompletat cu inca doua conditii pentru a suplini conditiile de racordare in prima si a doua derivatace nu mai pot fi scrise pentru nodul x n (spre exemplu se pot preciza pantele m 1 si m n).

8/16/2019 C5&6_MN_2015-2016_Cristea


c) Aproximarea prin metoda celor mai mici patrateSe stie ca datele obtinute prin masurarea cantitativa a variabilelor din fenomenele fizicestudiate sunt afectate de o serie de erori: erori de observatie, erori de masurare sau erori deinregistrare. In aceste situatii aproximarea functiei printr-un polinom de interpolare nu esterecomandata, deoarece polinomul se suprapune exact in toate punctele determinateexperimental si prin urmare erorile continute in datele masurate se vor pastra prin interpolare.

Aproximarea functiilor prin metoda celor mai mici patrate conduce la determinarea uneirelatii functionale care elimina intr-o oarecare masura erorile. Criteriul de aproximare ilreprezinta minimizarea sumei:

S = [yi – g(x i)]2 = minimi=1

m

valorile x i si y i fiind date. Aproximanta g(x) se scrie sub forma: g(x) = a kg k(x)

k=1

n

k = 1, 2…, n

gk(x) sunt functii cunoscute, liniar independente, iar a k – parametri nedeterminati.

8/16/2019 C5&6_MN_2015-2016_Cristea


c1) Aproximarea liniara a functiilor prin metoda celor mai mici patrate

In acest caz polinomul g(x) se ia de forma:

g(x) = P 1(x) = a 1 + a 2x

Problema revine la minimizarea functiei:

S(a 1, a 2) = [yi – (a 1+a 2xi)]2

i=1

m

in raport cu parametrii a 1 si a 2.

Pentru aceasta este necesar ca derivatele partiale sa se anuleze: Sa 1

= 0 S

a 2= 0si

Acest sistem este echivalent cu:

xiyii = 1

m

a 1m + a 2 xi =i = 1

m

yii = 1

m

xii = 1

ma 1 xi =

i = 1

m2a 2+

si permite determinarea unica a coeficientilor a 1 si a 2 daca se cunosc valorile (x i, y i), i = 1,…, m,unde m reprezinta numarul punctelor citite (numarul masuratorilor).

8/16/2019 C5&6_MN_2015-2016_Cristea


c2) Aproximarea functiilor printr-un polinom de grad (n-1) utilizand metodacelor mai mici patrate

Judecand intr-un mod similar aproximarii liniare expuse, se obtine cazul aproximarii functieinecunoscute printr-un polinom de gradul ( n-1 ), cu n < m:

g(x) = P n-1 (x) = a kxk-1 = a 1 + a 2x + a 3x2 + …+ a nxn-1

k =1

n

sistem cu n ecuatii si n necunoscute, exprimat matriceal prin urmatoarea ecuatie:

i =1

m x

i

2

i =1

m xi

2

…

……………

…

…m

i =1

m xi

3

i =1

m xi

n-1

i =1

m xi

n-1

i =1

m xi

n

i =1

m xi

n+1

i =1

m xi

2n-2

i =1

m xi

n

i =1

m xi

i =1

m xi

a 1

a 2

……

a n

=

i =1

m yi

i =1

m xiyi

i =1

m xi yin-1

…

permitandu-se determinarea coeficientilor a k.

C5&6_MN_2015-2016_Cristea

Documents

Transcript of C5&6_MN_2015-2016_Cristea