Download - CN - curs 11 - 2015
-
Calcul Numeric
Cursul 11
2015
Anca Ignat
-
1
Problema celor mai mici ptrate
, , ,m n m nA b Ax b x (1)
11 1 12 2 1 1
21 1 22 2 2 2
1 1 2 2
1 1 2 2
==
=
=
n n
n n
i i in n i
m m mn n m
a x a x a x ba x a x a x b
a x a x a x b
a x a x a x b
-
2
Sistemul are soluii clasice dac:
rang A = rang [A | b] m < n - o infinitate de soluii m n
- dac rang A = rang [A | b] soluii clasice - dac rang A rang [A | b] soluii n sensul celor mai mici
ptrate Vectorul reziduu:
( ) mr x b Ax
-
3
Vectorul nx se numete soluie n sensul celor mai mici ptrate pentru sistemul (1) dac este soluia urmtoarei probleme de optimizare: 2 22 2min{ ( ) ; }
nr x b Ax x (LSP)
3 2
1 4 02 5 , 0 , 3, 23 6 1
A b m n
rang A = 2 rang [A | b] = 3
-
4
Sistemul:
1 2
1 2
1 2
4 02 5 03 6 1
x xx xx x
(2)
nu are soluie clasic (nu exist x1 , x2 care s satisfac toate cele 3 ecuaii simultan). Vectorul reziduu are forma:
1 2
11 2
21 2
0 1 4 4( ) 0 2 5 2 5
1 3 6 1 3 6
x xx
r x b Ax x xx
x x
Soluia n sensul celor mai mici ptrate a acestui sistem este definit ca soluia problemei de optimizare:
-
5
22 21 2 1 2 1 2 1 2min{( 4 ) ( 2 5 ) 1 3 6 ; , }x x x x x x x x
2 2
1 2 1 2 1 2 1 2min{1 6 12 64 14 77 ; , }x x x x x x x x Aceast problem de minimizare are soluia:
1 213 2 1, , ( )18 9 6
x x r x
i este soluia n sensul celor mai mici ptrate a sistemului (2). 1 21 2range A { y ; , , 1, }m nn iy a A a A a A a i n
-
6
1 2 , sunt coloanele matricii n i mA A A A A A Teorem Fie ( ) ,m n mA m n b . Un vector nx minimizeaz norma euclidian a vectorului reziduu ||r(x)||2=||b-Ax||2, rezolvnd problema (LSP), dac i numai dac:
( ) range( ) ( ) 0Tr x A A r x sau echivalent T TA Ax A b (3)
-
7
Sistemul (3) poart numele de sistemul de ecuaii normale i
este un sistem ptratic de dimensiune n, matricea sistemului T n nA A este simetric. Sistemul de ecuaii normale (3) este
nesingular dac i numai dac rang A = n, n acest caz soluia x
a sistemului (3) este unic.
det 0 rangTA A A n
1 414 32 3
2 5 , ,32 77 6
3 6
T TA A A A b
-
8
1 21 2
1 2
14 32 3 13 2,32 77 6 18 9
x xx x
x x
Pseudo-inversa matricii A Presupunem c A are rang A = n. Atunci pseudo-inversa poate fi definit ca:
1T T n mA A A A ( ?)IA A
114 32 1 2 3*
32 77 4 5 6A
-
9
Rezolvarea sistemului de ecuaii normale
1) Folosind factorizarea Cholesky (descompunere LU) pentru
matrici simetrice:
, matrice inferior triunghiularT T n nA A LL L Se calculeaz matricea ATA i vectorul ATb; Se calculeaz factorizarea Cholesky a matricii ATA=LLT; Se rezolv sistemul inferior triunghiular Ly= ATb pentru y; Se rezolv sistemul superior triunghiular LTx= y pentru x;
-
10
2) Se calculeaz descompunerea QR (cu algoritmul lui
Householder adaptat) pentru matricea A:
( )
, matrice ortogonal , ,
, matrice superior triunghiular0
m m m n
n n
m n n
A QR Q R
RR R
Se calculeaz factorizarea QR modificat a matricii A; Se calculeaz vectorul QTb ; Se rezolv sistemul sup. triunghiular
1,
T
i nRx Q b ;
-
11
3) Se folosete desc. dup valori singulare a matricii A
, , ,T m n m m n nA U V U V Se calculeaz SVD pentru matricea A=UVT; Se calculeaz vectorul UTb; Se rezolv sistemul diagonal w = UTb pentru w; Soluia este x=Vw;
1), 2) sau 3) ? se recomand 2)
-
12
Rezolvarea ecuaiilor neliniare
Fie :[ , ]f a b o funcie continu pe intervalul [a,b] astfel ca f(a)f(b) < 0. n aceste condiii, exist x*(a,b) astfel ca f(x*)=0. n cele ce urmeaz ne propunem s aproximm soluia x*
a ecuaiei neliniare f(x)=0.
-
13
Metoda biseciei (a njumtirii intervalului)
Pp. f(a)f(b) < 0!!! Pentru a aproxima soluia x* cutat, vom
construi un ir de intervale {[ , ]; 0}k ka b k ce satsifac:
1 1
1 1
,
, ,
2
k k
k k k k
k kk k
x a b
a b a bb ab a
Pentru primul interval vom considera: 0 0, , 0a a b b k .
-
14
Considerm punctul c de mijloc al intervalului [ak,bk]:
k ka bc Avem urmtoarele 3 variante:
1. f(c)=0 - soluia cutat este x*=c, algoritmul se oprete;
2. f(ak)f(c) < 0 soluia se gsete n intervalul (ak,c), continum procedeul cu intervalul [ 1 1,k k ka a b c ];
3. f(bk)f(c) < 0 soluia se gsete n intervalul x*(c,bk) procedeul continu cu intervalul [ 1 1,k k ka c b b ].
-
15
Dat > 0 exist un interval ,k ka b astfel ca ,k kx a b i k kb a ( 2log b ak
). Pentru suficient de mic att ka ct i kb pot fi considerate aproximri ale soluiei x
* ( ka x prin
lips iar kb x prin adaos).
-
16
Metoda tangentei (Newton-Raphson) Vom presupune c funcia 1 ,f C a b este derivabil pe [a,b] cu derivata continu n acest interval i satisface relaia f(a)f(b) < 0. Pentru a aproxima soluia x* a ecuaiei f(x)=0 vom construi un ir kx care s convearg la x*,
pentru,kx x k . Primul element din ir, x0, considerm
c este dat. Urmtorul element din ir se construiete ca fiind punctul de intersecie al tangentei la graficul funciei f n punctul ( x0 , f(x0) ) cu axa absciselor. Procedeul se repet cu x1 pentru a-l obine pe x2, .a.m.d.
-
17
.
1 0 0
2 1 1
1
O tangenta la graficul func iei n punctul , ( )
O tangenta la graficul func iei n punctul , ( )
O tangenta la graficul fc n pt. , ( ) , 0,1,2,k k k
x x f x f x
x x f x f x
x x f x f x k
Ecuaia tangentei la graficul funciei f ntr-un punct (a, f(a)) este urmtoarea (pentru o funcie derivabil):
( ) ( )( )y f a f a x a
Pentru a calcula xk+1 din xk vom considera ecuaia tangentei:
( ) ( )( )k k ky f x f x x x
-
18
unde lum y = 0. Avem:
1 0( ) , 0,1,2, , dat( )
kk k
k
f xx x k xf x
Formula de mai sus poate fi folosit doar dac la fiecare pas
( ) 0kf x . Dac la un pas avem ( ) 0kf x putem calcula cteva iteraii xk (k k ) folosind 1( )kf x .
-
19
Teorem de convergen Fie 2 ,f C a b , cu ( ) ( ) 0f a f b , ( ) 0f x i ( ) 0f x
,x a b . Dac alegem 0
pentru ( ) ( ) 0pentru ( ) ( ) 0
a f a f ax
b f b f b
atunci irul ; 0kx k construit cu metoda tangentei este monoton, mrginit i convergent la unica soluie x* a ecuaiei
f(x)=0. Ordinul de convergen este mai mare dect 2.
-
20
Metoda falsei poziii (a coardei) Presupunem c funcia f este continu, ,f C a b i satisface relaia ( ) ( ) 0f a f b . Vom construi un ir kx care s convearg la soluia cutat x*, pentru,kx x k
. Considerm date primul element din ir, x0 i un alt punct x . Procedeul de construire a irului este urmtorul:
1 0 0
2 1 1
1
O dreapta ce une te punctele , ( ) , ( )
O dreapta ce une te punctele , ( ) , ( )
O dreapta ce une te pt. , ( ) , ( ) , 0,1,2,k k k
x x x f x x f x
x x x f x x f x
x x x f x x f x k
-
21
Ecuaia dreptei ce trece prin punctele (a, f(a)) cu (b, f(b)) este:
( )( ) ( )y f a x a
f a f b a b .
Pentru a-l obine pe 1kx din kx avem:
cu
dat
1
0
( ) 0( ) ( )
( )( ) ( ) ( ) ,( ) ( ) ( ) ( )
0,1,2, ,
k k
k k
k k k kk k
k k
y f x x x yf x f x x x
f x x x xf x x f xx xf x f x f x f x
k x
-
22
Teorem de convergen Fie 2 ,f C a b , cu ( ) ( ) 0f a f b , ( ) 0f x i ( ) 0f x ,x a b . Dac alegem
i pentrui pentru
0
0
( ) ( ) 0( ) ( ) 0
x a x b f a f ax b x a f b f b
atunci irul ; 0kx k construit cu metoda falsei poziii este monoton, mrginit deci convergent la unica soluie x* a ecuaiei f(x)=0.
-
23
Metoda secantei
Presupunem c funcia f este continu, ,f C a b i satisface relaia ( ) ( ) 0f a f b . Vom construi un ir kx care s convearg la soluia cutat x*, pentru,kx x k
. Considerm date primele dou elemente din ir, x0 i x1. Procedeul de construire a irului este urmtorul:
2 0 0 1 1
3 1 1 2 2
1 1 1
O dreapta ce une te punctele , ( ) , , ( )
O dreapta ce une te punctele , ( ) , , ( )
O dreapta ce une te pct. , ( ) , ( ) ,k k k k k
x x x f x x f x
x x x f x x f x
x x x f x x f x
1,2,k
-
24
Obinem elementul xk+1 din xk i xk-1 astfel:
1 1
( ) cu 0( ) ( )
k k
k k k k
y f x x x yf x f x x x
11
1
1 1
1
0 1
( )( )( ) ( )
( ) ( ) ,( ) ( )
1,2, , , da i
k k kk k
k k
k k k k
k k
f x x xx xf x f x
x f x x f xf x f x
k x x
-
25
Teorem de convergen Fie x* o soluie a ecuiei f(x)=0. Pp. c 2 * *,f C x r x r ,
( ) 0f x i ( ) 0f x * *,x x r x r . Atunci exist 0 < r0 r pentru care, dac 0 1 0 0, [ , ]x x x r x r atunci
0 0[ , ], 2kx x r x r k i pentru,kx x k . Ordinul
de convergen este 1 5 1.618032
q .
-
26
Metoda lui Muller irul kx de aproximare a unei rdcini a ecuaiei neliniare f(x)=0 se construitete astfel:
- x0, x1, x2 date - urmtorul element din ir x3 se construiete astfel:
se construiete parabola care trece prin ultimele trei elemente calculate ale irului (x0,f (x0)), (x1, f(x1)) , (x2,f(x2))
22 2( ) ( ) ( )P x a x x b x x c .
Constantele a, b i c se gsesc rezolvnd sistemul de ecuaii:
-
27
20 0 2 0 2 0
21 1 2 1 2 1
22 2 2 2 2 2
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
P x a x x b x x c f x
P x a x x b x x c f xP x a x x b x x c c f x
de unde obinem:
1 0
1 1 21 0
, , ( )a b ah c f xh h
0 1 0 1 2 1
1 0 2 10 1
0 1
, ,( ) ( ) ( ) ( ),
h x x h x xf x f x f x f x
h h
-
28
Pentru stabilitate numeric se consider urmtoarea formul de calcul a soluiei ecuaiei de gradul 2, 2 0az bz c
1,2 2
24
czb b ac
.
Rdcina cea mai apropiat de x2 a ecuaiei P(x)=0 este noul element x3 al irului. Obinem formula:
3 2 2 22max 4 , 4cx x b b ac b b ac
-
29
Sisteme de ecuaii neliniare Consider sistemul neliniar:
1 1 2 1 1
2 1 2 2 2
1 2
( , , , ) 0( , , , ) 0
( ) 0 ,
( , , , ) 0
n
n
n nn n
f x x x f xf x x x f x
F X F X
f xf x x x
Fie matricea jacobian asociat funciei F (presupunem c funciile fi sunt difereniabile):
-
30
1 1 1
1 2
2 2 2
1 2 1 2
1 2
( ) ( , , , )
n
n n
n n n
n
f f fx x xf f fx x xF X x x x
f f fx x x
Pentru a gsi soluia X* a sistemului de ecuaii neliniare F(X)= 0 se construiete un ir de vectori ( )k nX astfel:
-
31
dat(0)1( 1) ( ) ( ) ( ) ( ) ( )
1( ) ( ) ( )
( ) ( ) ,
( ) ( ) , 0,1,
k k k k k k
k k k n
X
X X F X F X X
F X F X k
Vectorul de corecie (k) poate fi calculat i ca soluie a sistemului liniar:
( ) ( )( ) ( )k kF X F X unde matricea sistemuui este matricea jacobian calculat n punctul ( )kX iar vectorul termenilor liberi este ( )( )kF X . Metoda descris mai sus poart numele de metoda Newton. Pentru n=1 metoda Newton este chiar metoda tangentei descris anterior.
-
32
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:
-
33
0 1 2ln | ( ) | ln | | ln | | ln | | ln | |np x a x x x x x x
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
-
34
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 . 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
-
35
Rezolvm acest sistem n raport cu a i obinem:
2max ( ) ( 1) ( ) ( )k k kna
G y n nH y G y
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:
-
36
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
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.
-
37
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.
-
38
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.
-
39
Avem:
0 1 1( ) ( ) ( )( ) ( ),, 0, ,
i i i i n
i
p x c x x x x x x x xc i n
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
-
40
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. Demonstraie: Vom arta c cele n+1 polinoame sunt liniar independente:
-
41
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
-
42
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
-
43
Constantele ak se determin astfel:
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.
-
44
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.
-
45
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:
( ) ( ) ( ) 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
-
46
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:
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}.
-
47
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)
a = min{x0, x1,, xn}, b = max{x0, x1,, xn}. Demonstraie: Considerm funcia F:
1( ) : ( ) ( ) ( )n nF x f x l x cw x
-
48
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
-
49
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:
-
50
( 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).
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}.
-
51
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. 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
-
52
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
n care A este dat de relaia:
-
53
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
-
54
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)
-
55
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
-
56
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:
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.
-
57
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:
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
-
58
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) Diferenele divizate se pot obine folosind definiia direct (4) sau folosind definiia recursiv (7), (6). Cele 2 definiii sunt echivalente:
-
59
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
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:
-
60
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
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
-
61
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. Din definiie se observ c diferena divizat 0 1, , , k fx x x nu depinde de ordinea nodurilor 0 1, , , kx x x .
-
62
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
-
63
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 .
-
64
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
-
65
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:
[ ,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:
-
66
1
for 1, ,for , ,
i ii
i i k
k ni n k
y yyx x
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).
-
67
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
. 1 1
11
( ) ( ),( )
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
-
68
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
.
-
69
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
-
70
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
-
71
Consider c punctul de interpolare este de forma: 0x x t h
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
20 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
-
72
Aceast relaie poart numele de formula lui Newton progresiv pe noduri echidistante. 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:
-
73
2
1 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