Calcul Numeric

Cursul 12

2015

Anca Ignat

1

Metoda lui Laguerre Fie polinomul:

0 1 2 0( ) ( )( ) ( ) , 0np x a x x x x x x a Metoda lui Laguerre propune construirea unui ir de numere care s convearg la una din rdcinile polinomului p. Considerm derivata polinomului p:

1 2

1 1 1'( ) ( )n

p x p xx x x x x x

Avem:

0 1 2ln | ( ) | ln | | ln | | ln | | ln | |np x a x x x x x x

2

dd 1 2

1 1 1 ( )ln | ( ) | ( )( )n

p xp x G xx x x x x x x p x

dd

2

2 2 2 21 2

2

2

1 1 1ln | ( ) |( ) ( ) ( )

'( ) ( ) ''( )( )

( )

n

p xx x x x x x x

p x p x p xH x

p x

Fie x1 rdcina pe care vrem s-o aproximm i yk valoarea aproximativ curent. Notm cu a = yk - x1 i facem presupunerea c yk se afl la acceeai distan de toate celelalte rdcini, adic:

2, ,k iy x b i n .

3

Prin urmare avem:

2

2 2 2

'( ) 1( )( )

'( ) ( ) ''( ) 1( )( )

kk

k

k k kk

k

p y nG yp y a b

p y p y p y nH ya bp y

Rezolvm acest sistem n raport cu a i obinem:

2max ( ) ( 1) ( ) ( )k k kna

G y n nH y G y

4

Semnul la numitor este ales astfel ca expresia s aib magnitudine maxim. Dac inem cont de expresiile pentru G i H obinem pentru a i urmtoarea expresie:

22

( )

max '( ) ( 1) '( ) ( 1) ( ) ''( )k

k k k k

n p yap y n p y n n p y p y

Urmtorul element din ir va fi:

1 2max ( ) ( 1) ( ) ( )k k k k k kny y a y

G y n nH y G y

1 22

( )

max '( ) ( 1) '( ) ( 1) ( ) ''( )k

k k

k k k k

n p yy yp y n p y n n p y p y

5

Procedeul se oprete cnd a devine suficient de mic. Metoda lui Laguerre se poate apl. i ptr. aprox. rd. complexe i de asemenea pentru polinoame cu coeficieni compleci. Pentru rdcini simple metoda lui Laguerre are ordinul de convergen 3.

6

Interpolare numeric

Presupunem c despre o funcie f cunoatem doar valorile ntr-un numr finit de puncte. Pornind de la aceste date, dorim s aproximm funcia f ntr-un alt punct.

x x0 x1 x2 ... xn-1 xn

f y0 y1 y2 ... yn-1 yn

n tabelul de mai sus f(xi) = yi , i=0,1,,n i xi xj , i j. Dat un punct x xi, i=0,1,,n dorim s aproximm f(x) cunoscnd cele (n+1) perechi (xi ,yi ), i=0,,n. Punctele xi se numesc noduri de interpolare.

7

Polinomul de interpolare Lagrange Notm cu n mulimea polinoamelor de grad cel mult n. Dimensiunea acestui spaiu este n+1, baza uzual fiind dat de polinoamele 1, x, x2,, xn. Vom considera o alt baz n acest spaiu. Se consider polinoamele pi:

pentruastfel ca

pentru0

( ) 0, , , 0, ,1i n i j

j ip p x j n i n

j i

Din relaia pi ( xj )=0, j i i faptul c pi este de grad n rezult c x0, x1,,xi-1, xi+1,,xn sunt cele n rdcini ale polinomului pi. Avem:

0 1 1( ) ( ) ( )( ) ( ),, 0, ,

i i i i n

i

p x c x x x x x x x xc i n

8

Constanta ci se determin din relaia pi ( xi ) = 1:

0 1 1

0 1 1

( ) 1 ( ) ( )( ) ( )1

( ) ( )( ) ( )

i i i i i i i i i n

ii i i i i i n

p x c x x x x x x x x

cx x x x x x x x

Polinoamele pi au forma:

0 1 1

00 1 1

( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )

0, ,

nji i n

iji i i i i i n i jj i

x xx x x x x x x xp xx x x x x x x x x x

i n

Propoziie Polinoamele p0, p1,, pn formeaz o baz n n.

9

Demonstraie: Vom arta c cele n+1 polinoame sunt liniar independente:

0 0 1 1

0 1

( ) ( ) ( ) ( ) 0 ,0

n n

n

q x a p x a p x a p x xa a a

Vom face pe rnd x = x0, x = x1,, x = xn n polinomul q:

0 0 0 0 0 1 1 0 0

0 1 0 0

( ) ( ) ( ) ( )1 0 0 0 0

n n

n

x x q x a p x a p x a p xa a a a a

1 1 1( 0x x q x a

0 0

0

( ) ( ) ( ) ( )0 0 0 0

k k k k k k n n k

k n k k

x x q x a p x a p x a p xa a a a a

( 0n n nx x q x a

10

Toate constantele ai sunt nule deci polinoamele ; 0, ,ip i n formeaz o baz n n. Pentru a aproxima funcia f pornind de la tabelul de mai sus, vom construi un polinom lnn a.. s satisfac condiiile de interpolare:

, ( ) , 0, ,n n n i il l x y i n (1) Odat construit acest polinom, vom aproxima f(x) prin ln(x).

( ) ( )nf x l x Vom scrie polinomul ln n raport cu noua baz ; 0, ,ip i n , deci exist constantele reale a0, a1,,an astfel ca:

0( ) ( )

n

n i ii

l x a p x

Constantele ak se determin astfel:

11

0 0

0

( ) ( ) ( ) ( )

0 1 0

k n k k k k k n n k

k n k k k

y l x a p x a p x a p x

a a a a a y

Prin urmare un polinom de grad n care ndeplinesc condiiile de interpolare (1) este:

0 1 1

0 0 0 1 1

0 0

( ) ( )( ) ( )( ) ( )

( ) ( )( ) ( )

( ) (2)

n ni i n

n i i ii i i i i i i i n

n nj

ii j i j

j i

x x x x x x x xl x y p x yx x x x x x x x

x xy

x x

Polinomul in formula (2) se numete polinomul de interpolare Lagrange.

12

Propoziie Polinomul ln dat de formula (2) este unicul polinom de grad n care ndeplinete condiiile de interpolare (1). Demonstraie: Presupunem c mai exist un polinom qn care ndeplinete condiiile (1):

, ( ) , 0, ,n i iq q x y i n Fie polinomul p(x)=ln(x)-q(x) n.

( ) ( ) ( ) 0 , 0, ,k n k k k kp x l x q x y y k n Polinomul p are ca rdcini toate nodurile de interpolare. Polinomul p este polinom de grad cel mult n i are (n+1) rdcini distincte (xi xj, i j). Acest polinom nu poate fi dect polinomul identic nul:

13

( ) ( ) ( ) 0 , ( ) ( )n np x l x q x x l x q x x

Polinomul ln este unicul care satisface (2). Fie wn+1 polinomul de grand (n+1) care are ca rdcini nodurile de interpolare:

1 0 1 1( ) ( )( ) ( )n n nw x x x x x x x Avem:

1 10 0 0

( ) ( ) ; ( ) ( )n n n

n j n k k ji j j

j i j k

w x x x w x x x

Putem rescrie polinomul ln i astfel:

14

1

0 1

( ) 1( ) [ ]( ( ))'

nn

n ii i n i

w xl x yx x w x

Fie a = min{x0, x1,, xn}, b = max{x0, x1,, xn}. Teorema restului Fie 1 ,nf C a b i , , , 0, , .ix a b x x i n Atunci exist un punct 0 1, , ( , , , , )ny a b y y x x x x (punctul y depinde de nodurile de interpolare xi i de punctul x ) astfel c eroarea la interpolarea numeric este dat de:

( 1)

1( )( ) ( ) ( )

( 1)!

n

n nf yf x l x w xn

(3)

15

Demonstraie: Considerm funcia F:

1( ) : ( ) ( ) ( )n nF x f x l x cw x Constanta real c este aleas astfel ca ( ) 0F x adic:

11

( ) ( ) , ) ( ) 0 )( )

ni n

n

f x l xc x x i w xw x

(4) Funcia f fiind de clas Cn+1 pe intervalul [a,b] rezult c i funcia F este din Cn+1[a,b]. Avem:

1( ) ( ) ( ) ( ) 0 0 , 0, ,i i n i n i i iF x f x l x cw x y y c i n Funcia F are (n+2) zerouri, 0 1, , , ,nx x x x . Aplicnd succesiv Teorema lui Rolle rezult c F are (n+1) zerouri, F are n zerouri,, F(n+1) are 1 zero n intervalul [a,b]. Vom nota aceast

16

rdcin a lui F(n+1) cu y. Punctul y depinde de zerourile iniiale 0 1, , , ,nx x x x i:

a.. ( 1)0 1( , , , , ) , ( ) 0.nny y x x x x a b F y (5) Derivata de ordinul (n+1) a funciei F se calculeaz astfel:

( 1) ( 1) ( 1) ( 1)1

( 1) ( 1)

( ) ( ) ( ) ( )

( ) 0 ( 1)! ( ) ( 1)!

n n n nn n

n n

F x f x l x c w x

f x c n f x c n

(6)

(derivata de ordin (n+1) a polinomului de grad n ln este 0). Din relaiile (4), (5) i (6) rezult c:

( 1) ( 1)

11

( ) ( )( ) ( )( ) ( ) ( )( 1)! ( ) ( 1)!

n nn

n nn

f x l xf y f yc f x l x w xn w x n

adic am obinut relaia (3).

17

Forma Newton a polinomului de interpolare Lagrange

Fie lk(x, x0, x1,, xk, f) polinomul de interpolare Lagrange pentru

funcia f pe sistemul de noduri distincte {x0, x1,, xk}.

Propoziie Fie lk-1(x, x0, x1,, xk-1, f), lk-1(x, x1, x2,, xk, f)k-1 polinoamele de interpolare Lagrange pentru funcia f pe sistemele de noduri {x0, x1,, xk-1} i respectiv {x1, x2,, xk}. Atunci:

0 1

1 0 1 1 0 1 1 2

0

( , , , , , )( ) ( , , , , , ) ( ) ( , , , , , )

k k

k k k k k

k

l x x x x fx x l x x x x f x x l x x x x f

x x

(1) Demonstraie: Exerciiu.

18

Considerm urmtoarele probleme de interpolare pentru f:

0 0 1 1 1 1 1 0 1 1

0 0 1 1 0 1

( , ),( , ), ,( , ) ( , , , , , )

( , ),( , ), ,( , ) ( , , , , , )k k k k

k k k k

x y x y x y l x x x x f

x y x y x y l x x x x f

Ne intereseaz s gsim o formul de trecere rapid de la polinomul de interpolare pe k noduri la cel care are un nod n plus. Deoarece polinomul de grad cel mult k:

0 1 1 0 1 1( ) ( , , , , , ) ( , , , , , )k k k k kq x l x x x x f l x x x x f are ca rdcini punctele x0,x1,,xk-1 (q(xi) = yi - yi = 0, i=0,...,k-1) avem relaia:

1

0 1 1 0 1 10

( , , , , , ) ( , , , , , ) ( )k

k k k k jj

l x x x x f l x x x x f A x x

19

n care A este dat de relaia:

0 1 1 0 1 11

0

( , , , , , ) ( , , , , , )

( )

k k k k k kk

k jj

l x x x x f l x x x x fAx x

(3)

1 1

0 0

1 1

0 0

1

1 10

0 0

( )

( ) ( )

( ) ( ) ( )

k kk j

ii j i j

j ikk k

k j k jj j

kk i

k ki

k j k i i jj j

j i

x xy

x xyAx x x x

y y

x x x x x x

20

0

0( )

ki

ki

i jjj i

yAx x

(4)

Considerm urmtoarele problemele de interpolare pentru f:

1 1 2 2 1 1 2

0 0 1 1 0 1

( , ),( , ), ,( , ) ( , , , , , )

( , ),( , ), ,( , ) ( , , , , , )

k k k k

k k k k

x y x y x y l x x x x f

x y x y x y l x x x x f

vom avea, analog ca mai sus

0 1 1 1 21

( , , , , , ) ( , , , , , ) ( )k

k k k k jj

l x x x x f l x x x x f B x x

(5)

21

Dac nmulim relaia (2) cu (x-xk) iar relaia (5) cu (x-x0) i scdem aceste relaii obinem:

0 0 1 1 0 1 1

0 1 1 20

( ) ( , , , , , ) ( ) ( , , , , , )

( ) ( , , , , , ) ( ) ( )

k k k k k kk

k k jj

x x l x x x x f x x l x x x x f

x x l x x x x f A B x x

innd seama de relaia (1) rezult c:

adic0

( ) ( ) 0k

jj

A B x x A B

Vom nota n cele ce urmeaz:

0 1, , , k fA x x x numit diferen divizat de ordin k a funciei f pe nodurile 0 1, , , kx x x .

Vom nlocui n formula (2) lk-1(x, x0,, xk-1, f) cu:

22

1 0 1 2 1 11

0 1 11

( , , , , ) ( , , , , )

, , , ( )

k k k kk

k jfj

l x x x f l x x x f

x x x x x

iar n formula (5) lk-1(x, x1 ,, xk , f ) cu:

1

1 1 2 1 1 1 21

( , , , , ) ( , , , , ) , , , ( )k

k k k k k lfl

l x x x f l x x x f x x x x x

i apoi scdem membru cu memebru cele dou relaii. Obinem:

1 1

0 1 01 0

1

1 01 1

, , ( ) , , ( )

, , ( ) , , ( ) 0

k k

k j k jf fj j

k k

k l k lf fl l

x x x x x x x x

x x x x x x x x

Putem scrie:

23

1 0 1 11

1

0 00

( ) , , , ,

, , ( )

k

j k kf fj

k

k j nfj

x x x x x x

x x x x x x x x

relaie din care obinem: 1 2 0 1 1

0 10

, , , , , ,, , , k kf fk f

k

x x x x x xx x x

x x

(6)

Relaia (6) justific denumirea de diferen divizat. Se introduce i noiunea de diferen divizat de ordinul 0: ( ) ,k k kfx y f x (7)

24

Diferenele divizate se pot obine folosind definiia direct (4) sau folosind definiia recursiv (7), (6). Cele 2 definiii sunt echivalente: Propoziie

0 1 0 0 10

, , ,( ) '( )

k ki i

k kfi i n k

i jjj i

y yx x xw xx x

(8)

pentru orice sistem de noduri 0 1, , , kx x x i orice k. Demonstraie: Se face prin inducie. Pentru k=1 avem:

1 00 10 1

0 1 1 0 1 0

, f ff

x xy yx xx x x x x x

25

Presupunem c relaia (8) este valabil pentru orice k i pentru orice sistem de noduri 0 1, , , kx x x . Pentru k+1 folosim relaia de recuren i apoi aplicm ipoteza inductiv:

1 1 1 0 20 1 1

1 0

1

11 01 0

1 0

, , , , , ,, , ,

( )( ) ( )

k kf fk f

k

k ki i

k ki ik

i j i jj jj i j i

x x x x x xx x x

x x

y yx x x x x x

26

0 11

1 00 1

0 10 1

1 1 0

1

( ) ( )

1 1[ ( )] }( )

kk k

kj k j

j jj j k

ki

ki i k i

i jjj i

y yx x x x x x

yx x x xx x

0 11 1 1

10 1

0 0 00 1

1

10

0

( ) ( ) ( )

( )

kk i

k k ki

j k j i jj j jj j k j i

ki

ki

i jjj i

y y y

x x x x x x

y

x x

Inducia este complet.

27

Din definiie se observ c diferena divizat 0 1, , , k fx x x nu depinde de ordinea nodurilor 0 1, , , kx x x . Vom nota n continuare cu lk(x) polinomul de interpolare Lagrange pe nodurile 0 1, , , kx x x pentru funcia f. Avem:

0 1 0 1 1

0 0 1 0 0 1 0 1

0 1 0 1

( ) ( ) ( ) ( )] ( ) ( )] ( ) ( )]

, ( ) , , , ( ) ( )

, , , ( ) ( )

n k k n n

k kf f

n nf

l x l x l x l x l x l x l x l x

y x x x x x x x x x x x

x x x x x x x

Am obinut forma Newton a pol. de interpolare Lagrange:

0 0 1 0 0 1 2 0 1

0 1 0 1

( ) , ( ) , , ( )( )

, , , ( ) ( )

n f f

n nf

l x y x x x x x x x x x x x

x x x x x x x

28

Schema lui Aitken de calcul a diferenelor divizate Ne propunem s calculm diferenele divizate

0 1, fx x , 0 1 2, , fx x x , , 0 1, , , n fx x x necesare construirii polinomului de interpolare Lagrange n forma Newton. Procedeul folosete definiia recursiv a diferenelor divizate i se desfoar n n pai. La pasul 1 se calculeaz numai diferene divizate de ordinul 1:

0 1, fx x , 1 2, fx x ,, 1 ,n n fx x . n general, la pasul k se calc. diferene divizate de ordin k:

0 1, , , k fx x x , 1 2 1, , , k fx x x ,, 1, , ,n k n k n fx x x . La pasul n se calculeaz o singur diferen divizat de ordin n i anume 0 1, , , n fx x x .

29

0 0

1 1 0 1

2 2 1 2

1

Pas 1 Pas Pas

,

,

,

f

f

k k k k f

k nx y

x y x x

x y x x

x y x x

0 1

1 1 2 1 1 1

1

, , ,

, , ,

,

k f

n n n n n k nf f

n n n n f

x x x

x y x x x x

x y x x

1 0 1, , , ,n k n nf fx x x x x

Notm dd[i,k]= 1, , ,i i i k fx x x diferena divizat de ordin k, pe nodurile consecutive 1, , ,i i i kx x x i=0,,n-k, k=1,,n, cu dd[i,0]=yi, i=0,,n. Schema lui Aitken se implementeaz astfel:

30

[ ,0] , 0, , ;

for 1, ,for 0, ,

[ 1, 1] [ , 1][ , ]

i

i k i

dd i y i nk n

i n kdd i k dd i kdd i k

x x

Putem face aceleai calcule folosind un singur vector, de exemplu rescriind vectorul y astfel:

1

for 1, ,for , ,

i ii

i i k

k ni n k

y yyx x

31

La finalul acestei secvene de program, vectorul y va conine elementele:

y0 , 0 1, fx x , 0 1 2, , fx x x ,, 0 1, , , n fx x x ( 0 1, , ,k k fy x x x , k=0,...,n).

Interpolare Newton pe noduri echidistante Pp. c nodurile de interpolare sunt echidistante:

0 , 0,1, ...,ix x i h i n n relaia de mai sus fie se d h distana ntre 2 noduri succesive, fie se precizeaz primul i ultimul nod, x0 i xn i h se calculeaz:

0( )nx xhn

.

32

1 11

1

( ) ( ),( )

i i i ii i f

i i

f x f x y yx xx x h

Se introduce noiunea de diferen finit de ordinul 1:

( ) ( ) ( )f x f x h f x Pornind de la aceast definiie se pot introduce i diferene finite de ordin superior:

2 ( ) ( ( )) ( ( ) ( ))( 2 ) 2 ( ) ( )

f x f x f x h f xf x h f x h f x

i n general se pot introduce recursiv diferenele finite de ordin k:

1 1 1( ) ( ( )) ( ) ( )k k k kf x f x f x h f x . Prin inducie dup k, se poate deduce formula de calcul a diferenelor finite de ordin k folosind doar valorile funciei f:

0( ) ( 1) ( )

kk k i i

ki

f x C f x i h

.

33

Observaie: Dac funcia f este polinom de grad m atunci ( )f x este polinom de grad m-1, 2 ( )f x este polinom de grad m-2, .a.m.d. Prin urmare:

( ) 0 , pentru , polinom de grad k f x k m f m . Legtura ntre diferenele divizate i cele finite:

11

1

( ) ( ) ( ),( )

i i ii i f

i i

f x f x f xx xx x h

2

1 2 11 2 2

2

, , ( ), ,( ) 2

i i i if f ii i i f

i i

x x x x f xx x xx x h

34

Prin inducie se poate arta urmtoarea legtur ntre diferenele divizate de ordin k i cele finite:

1( ), , , .

!

ki

i i i k kf

f xx x xk h

Polinoame de interpolare pe noduri echidistante

0 0 1 0 0 1 2 0 1

0 1 0 1 1

0 1 0 1 1

( ) , ( ) , , ( )( )

, , ..., ( )( ) ( )

, , ..., ( )( ) ( )

n f f

k kf

n nf

l x y x x x x x x x x x x x

x x x x x x x x x

x x x x x x x x x

Consider c punctul de interpolare este de forma:

0x x t h

35

i nlocuim diferenele divizate cu diferene finite n forma Newton a polinomului de interpolare:

0 1 0 0 0 0( ) ( ) ( ) ( ( 1) )

( 1) ( 1)k

k

x x x x x t h x x t h x k h

h t t t k

2

0 0 0 0

0

0

( 1)( ) ( ) ( ) ( )2

( 1) ( 1)( )!

( 1) ( 1)( )!

n n

k

n

t tl x l x th y f x t f x

t t t kf xk

t t t nf xn

Aceast relaie poart numele de formula lui Newton progresiv pe noduri echidistante.

36

Considerm polinomul de interpolare Lagrange pe nodurile n ordine invers 1 0{ , , ..., }n nx x x :

1 1 2 1

1 0 1 0

( ) , ( ) , , ( )( )

, , ..., ( )( ) ( )

n n n n n n n n n nf f

n n n nf

l x y x x x x x x x x x x x

x x x x x x x x x

Dac punctul de interpolare este de forma: nx x th

analog ca mai sus obine formula lui Newton regresiv pe noduri echidistante:

21 2

0

( 1)( ) ( ) ( ) ( )2

( 1) ( 1)( )!

( 1) ( 1)( )!

n n n n n n

kn k

n

t tl x l x th y f x t f x

t t t kf xk

t t t nf xn

37

Funcii spline Fie nodurile: , , 0,1, , ,ix a b i n cu

0 1 2 1n na x x x x x b Se consider funcia continu polinomial pe poriuni:

1( ) ( ) pentru [ , ] 0, ..., 1i i iS x P x x x x i n 0 0 1

1 1 2

2 2 3

2 2 1

1 1

( ) , [ , ],( ) , [ , ],( ) , [ , ],

( )

( ) , [ , ],( ) , [ , ] .

n n n

n n n

P x x x xP x x x xP x x x x

S x

P x x x xP x x x x

38

Pi(x), i=0,...,n sunt polinoame. O asemenea funcie poart numele de funcie spline.

Funcii spline liniare continue Definiie Funcia S(x) definit mai sus se numete funcie spline liniar continu dac polinoamele , 0, , 1iP x i n sunt polinoame de gradul 1 i S(x)C[a,b], adic:

lim lim( ) ( ) 1, , 1.i i

i i

x x x xx x x x

S x S x i n

Fie funcia :[ , ]f a b pentru care se cunosc valorile: , 0, ,i iy f x i n .

39

Funcia spline liniar de interpolare S pentru funcia f ndeplinete

condiiile de interpolare:

( ) , 0, , .i iS x y i n innd seam c polinoamele Pi(x) sunt polinoame de gradul 1 i S(x) este continu vom avea condiiile:

1 1

( ) ,( ) 0, , 1,( ) polinom de gradul 1.

i i i

i i i

i

P x yP x y i nP x

Din aceste condiii rezult:

11

1 1

( ) , 0, , 1i ii i ii i i i

x x x xP x y y i nx x x x

1

0 0 0 0 1

( ) , 1, , 1,

( ) , .k k k k k k

n n n n

S x P x P x y k n

S x P x y S x P x y

40

Funcii spline cubice de clas C2 Se consider sistemul de noduri distincte din intervalul [a,b]:

0 1 1{ }n na x x x x b Funcia S(x) asociat divizrii D care ndeplinete condiiile :

2( ) [ , ] ,polinoamele ( ) au gradul 0, , 1,i

S x C a bP x i n

se numete funcie spline cubic. Dat fiind o funcie :[ , ]f a b cu valorile:

i iy f x , 0, ,i n , se consider funcia spline cubic S(x) de interpolare ce satisface

( ) , 0, , .i iS x y i n Pentru determinarea funciei spline cubice de interpolare observm c polinoamele:

3 21( ) , [ , ] , 0, , 1,i i i i i i iP x x x x x x x i n

41

implic determinarea a 4n necunoscute { , , , 0, , 1}i i i i i n pentru care se impun:

' ''

1 condi ii din rela iile de interpolare ( ) , 0, , ,

3( 1) condi ii de continuitate pentru ( ), ( ) i ( )n nodurile , 1, , 1 ,

i i

i

n S x y i n

n S x S x S xx i n

n total 4n-2 condiii. Se pot avea n vedere pentru adugarea a dou condiii suplimentarea urmtoarele abordri : fixarea pantelor n extremitile intervalului [a,b]. Se presupune

c funcia f este derivabil i se cunosc valorile f(a), f(b). Se impun condiiile:

0 0 0 1( ) ( ) ( ) , ( ) ( ) ( );n n nS x P x f a S x P x f b

42

periodicitatea primelor dou derivate:

0 0 0 1

0 0 0 1

( ) ( ) ( ( ) ( ) ( ) ( ) ,( ) ( ) ( ( ) ( ) ( ) ( ))

n n n

n n n

f a f b S x P x P x S xf a f b S x P x P x S x

;

anularea derivatei secunde n capetele intervalului:

0 0 0 1( ) ( ) 0

( 0 , 0).n n n

f a f bS x P x S x P x

Funciile spline care ndeplinesc aceste condiii se numesc funcii spline cubice normale. derivata de ordinul al treilea a funciei S este continu n

punctele x1 i xn-1 . Aceasta nseamn c polinoamele P0, P1 respectiv Pn-2, Pn-1 coincid. Acest tip de funcie spline se numete not a knot i este utilizat n MATLAB.

43

Vom calcula n cele ce urmeaz funcia spline cubic n cazul n care cunoatem suplimentar valorile primei derivate a funciei f n capetele intervalului de interpolare:

( ), ( )a bd f a d f b . Recapitulnd, vom avea urmtoarele condiii :

1

1

1

1

( ) , 0, , 1, ( ) interpolare ,( ) ( ) , 1, , 1, continuitatea func iei ,( ) ( ) , 1, , 1, continuitatea primei derivatei,( ) ( ) , 1,

i i i n n n

i i i i

i i i i

i i i i

P x y i n P x yP x P x i n SP x P x i nP x P x i

0 0 1

, 1, continuitatea derivatei secunde,( ) ( ), ( ) ( ).a n n b

nP x d f a P x d f b

Vom nota: ( ) , 0, .i iS x a i n

innd seama de faptul c funcia SC[a,b] este o funcie liniar pe fiecare din intervalele [xi, xi+1] rezult c:

44

11 1

1

( ) , [ , ] , 0, , 1

, 0, , 1

i ii i i i

i i

i i i

x x x xS x a a x x x i nh h

h x x i n

iar din

( ) ( ) , ( ) ( )S x S x dx S x S x dx rezult:

3 311

1

( ) ,6 6

[ , ] , , , 0, 1,

i ii i i i

i i

i i i i

x x x xS x a a b x c

h hx x x b c i n

3 31

1( ) ,6 6, , 0, 1,

i ii i i i i

i i

i i

x x x xP x a a b x c

h hb c i n

45

Vom calcula funcia spline pentru cazul:

0 0

1

( ) ( ) ( ,( ) ( ) (

a

n n b

S a P x f a dS b P x f b d

Impunnd condiiile de interpolare i de continuitate vom obine: 2

2

1 1 1 1

( ) ,6

( ) 0, 1.6

ii i i i i i i

ii i i i i i i

hP x a b x c y

hP x a b x c y i n

Din aceste relaii calculm i n funcie de 1 1, , ,i i i i i ib c a a y y :

11

1 11 1

,6

, 0, 1.6

i i ii i i

i

i i i i ii i i i i

i

y y hb a ah

x y x y hc x a x a i nh

46

Avem:

2 20 1

0 1 0 00 0

2 21

1 1 11 1

( )2 2

( )2 2

n nn n n n

n n

x x x xP x a a b

h h

x x x xP x a a b

h h

Din condiia 0 0( ) ( ) aS a P x d avem 0 0 0 1 0

0 0 0 0 0 10

2( )2 6 6 ah h h y yP x a b a a d

h

1 00 0 0 1

0

2 6 ay yh a h a d

h

(1)

Din condiia 1( ) ( )n n bS b P x d avem

47

1 1 1 11 1 1

1

( )2 6 6n n n n n

n n n n n n bn

h h h y yP x a b a a dh

11 1 1

1

6 n nn n n n bn

y yh a h a dh

(2)

Din condiia de continuitate a primei derivate a funciei spline cubice

1( ) , 1, ..., 1i i i iP x P x i n , innd seama de: 2 21

1 1 11 1

( ) ,2 2

i ii i i i

i i

x x x xP x a a b

h h

2 211( ) ,2 2

i ii i i i

i i

x x x xP x a a b

h h

rezult, utiliznd formulele pentru bi-1 i bi deduse mai sus:

48

1 1 11 1

1

11

( )2 6

( )2 6

i i i ii i i i i

i

i i i ii i i i i

i

h y y hP x a a ah

h y y hP x a a ah

sau

1 11 1

1

( ) 6 , 1, , 1.i i i ii i i i ii i

y y y yh h a h a i nh h

(3)

Sistemul liniar format din ecuaiile (1), (3), (2) cu necunoscutele

0 1, , , na a a are forma: cu ( 1) ( 1) 1, ,n n nHa f H f

49

1 00 0 0 1

0

1 11 1

1

11 1 1

1

2 6

( ) 6 1, , 1

6

a

i i i ii i i i i

i i

n nn n n n b

n

y yh a h a dh

y y y yh h a h a i nh h

y yh a h a dh

50

0 0

0 0 1 1

1 1 2 2

2

2 0 0 0 0 02( ) 0 0 0 0

0 2( ) 0 0 0

0 0 0 0 n

h hh h h h

h h h hH

h

2 1 1

1 1

2( )0 0 0 0 0 2

n n n

n n

h h hh h

1 0

0

1 1

1

1

1

6

6 1, , 1

6

a

i i i i

i i

n nb

n

y y dh

y y y yf i nh h

y ydh

51

Matricea H are diagonala dominant att pe linii ct i pe coloane,

este simetric i pozitiv definit prin urmare putem utiliza metoda

Gauss-Seidel sau o metod de relaxare pentru rezolvarea sistemului

Ha=f.

Interpolare n sensul celor mai mici ptrate

x x0 x1 x2 ... xn-1 xn

f y0 y1 y2 ... yn-1 yn

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

f(x) Sf (x; a0, a1, ..., am ) Sf (x; a0, a1, ..., am ) = amxm + am-1xm-1 + + a1x + a0

52

Coeficienii a0, a1, ..., am se gsesc rezolvnd problema de minimizare n sensul celor mai mici ptrate:

20 1 0 10

min{ ( ; , , ..., ) ; , , ..., } (LSP)n

f r m r mr

S x a a a y a a a

1

2

0 1 0 10

: ,

( , , ..., ) ( ; , , ..., )

m

n

m f r m rr

g

g a a a S x a a a y

20 1 1 00

( , , ..., )n

m km m r k r r r

rg a a a a x a x a x a y

0 1 1 00

( , , ..., ) 2n

m k km m r k r r r r

rk

g a a a a x a x a x a y xa

Soluia problemei de minimizare a problemei (LSP) este obinut rezolvnd sistemul de ecuaii liniare, de dimensiune (m+1):

53

0 1( , , ..., ) 0 , 0,1, ...,mk

g a a a k ma

1 00 0

, 0, ...,n n

m k k km r k r r r r r

r ra x a x a x a x y x k m

1 1

0 1 10 0 0 0 0

,

0, ...,

n n n n nk k k m k m kr r m r m r r r

r r r r ra x a x a x a x y x

k m

Constantele { a0, a1, ..., am } sunt soluia sistemului liniar:

( 1) ( 1) ( 1), 0 0

,, ( ) , ( )m m m m mkj k j k k

Ba zB B b z z z

0 0, , , 0, ...,

n nk j k

kj r k r rr r

b x z y x k j m