Lucrarea 2. Criteriul de aproximare prin interpolare: polinoame Newton si Lagrange.
Tema A - Polinoame Newton cu diferente divizate Tema B - Polinoame Lagrange
Formularea
cea mai generala a problemei de aproximare cere ca, pornind de la o functie
f(x) definita pe un anumit domeniu, sa se determine o alta functie
F(x), avand o forma cat mai simpla, care sa aproximeze cat mai bine
functia f(x) pe intregul domeniu de definitie. Evident, o data aproximatia
F(x) stabilita, ea va inlocui functia originara f(x) in toate
calculele ulterioare.
Cel mai frecvent, problemele de aproximare apar in cazul
unor functii definite tabelar. Functia f(x) este descrisa de un set de
"puncte" definite de perechi de forma (valoare variabila - valoare functie).
Despre o asemenea functie se spune ca este definita sub forma tabelara,
conform urmatorului model:
x_k | x_1 | x_2 | ... | x_i | ... | x_(n+1) |
f(x_k) | f_1 | f_2 | ... | f_i | ... | f_(n+1) |
Tabelul de definitie contine n+1 puncte (x_k , f_k), pentru care f_k = f (x_k). In multe situatii practice nu se urmareste determinarea explicita a unei expresii pentru functia de aproximare F(x), ci numai a valorii sale intr-un punct oarecare x. Daca acest punct se gaseste in interiorul domeniului de definitie al functiei f(x), se vorbeste de interpolare, iar daca se afla in afara domeniului de definitie, se vorbeste de extrapolare. Punctele x_k in care este cunoscuta functia f(x) se numesc noduri de interpolare, iar multimea lor (x_1 , x_2 , ... , x_n) formeaza suportul de interpolare.
Tema A - Polinoame Newton cu diferente divizate
Polinomul de interpolare Newton de grad n cu diferente divizate, notat N_n(x), se exprima in functie de distantele dintre punctul de calcul x si nodurile de interpolare. Se poate folosi polinomul de interpolare Newton de speta intai:
sau polinomul de interpolare Newton de speta a doua:
Interpolarea folosind polinomul Newton de speta intai este eficienta mai ales pentru puncte de interpolare/extrapolare situate catre inceputul, respectiv la stanga intervalului de definitie [x_1 , x_(n+1)]. Pentru puncte de calcul situate la extremitatea opusa a intervalului [x_1 , x_(n+1)] se recomanda folosirea polinomului Newton de speta a doua.
In expresiile polinoamelor Newton marimile notate cu se numesc diferente divizate de un anumit ordin si definite in raport cu un anumit nod de interpolare. Diferentele divizate se pot construi pornind de la urmatoarea structura tabelara (in continuare ne vom referi numai la polinomul Newton de speta intai):
si relatia de recurenta:
unde j indica ordinul diferentei, iar i nodul de interpolare de la care incolo se defineste diferenta divizata. Astfel, diferenta divizata este definita intre nodurile de interpolare x_i si x_(i+1). Se mentioneaza ca diferentele divizate de ordin 1 sunt egale cu valorile functiei de aproximat in nodurile respective:
Pentru memorarea diferentelor divizate care intervin in expresia polinomului Newton se poate folosi un singur vector D, dupa urmatoarea schema:
Initial, vectorul D contine valorile functiei in nodurile de interpolare, identice cu diferentele divizate de ordin unu. Se calculeaza succesiv diferentele divizate de ordin crescator in raport cu primul nod de interpolare. In vectorul D, calculul diferentelor divizate se face de jos în sus.
Folosind acest algoritm functia este aproximata cu un polinom de grad fix, a carui valoare este impusa de numarul nodurilor de interpolare folosite (n-1). Daca tabelul de definitie al functiei f(x) contine un numar mare de noduri de interpolare, rezulta un polinom de grad mare, ceea ce genereaza riscul aparitiei unor oscilatii puternice intre nodurile de interpolare. Pentru a evita aceste oscilatii se poate folosi interpolarea cu polinoame Newton de grad liber. In acest caz, pentru un punct de calcul x* se folosesc numai cateva noduri din tabelul de definitie a functiei f(x), si anume nodurile cele mai apropiate de punctul de calcul x*.
Pornind de la functia f(x) definita tabelar, polinomul de interpolare Lagrange de grad n, notat L_n(x) se defineste ca o combinatie liniara de polinoame k=1,...,n+1, care formeaza baza de interpolare. Coeficientii combinatiei liniare sunt tocmai valorile functiei de aproximat in nodurile de interpolare:
Pentru a evita aparitia oscilatiilor intre nodurile de interpolare - oscilatii care apar in special in cazul unui numar mare de noduri de interpolare - se poate folosi interpolarea cu polinoame Lagrange de grad liber. Pentru un punct de calcul x* se folosesc numai o parte din nodurile din tabelul de definitie a functiei f(x), si anume nodurile cele mai apropiate de punctul de calcul x*.
Polinomului de interpolare Lagrange i se poate asocia un tablou asemanator celui al diferentelor divizate (vezi polinomul de interpolare Newton), format insa din polinoame Lagrange calculate pe o multime de noduri de interpolare diferite de la un element la altul. In continuare se folosesc notatiile:
Intre aceste polinoame exista relatia:
Dintre polinoamele L_i,j din acest tablou, cele care intereseaza sunt cele care folosesc succesiv 1, 2, ... , n+1 noduri de interpolare. Aceste polinoame sunt L_1,1 , L_1,2 , ... , L_1,n+1, adica prima linie din tabloul de mai sus. Pentru a putea calcula insa polinomul L_1,n+1 este necesar calculul in prealabil al tuturor celorlalte polinoame din tablou.
Se constata existenta unei similitudini formale cu polinoamele Newton care folosesc diferente divizate. Si in acest caz este necesara renumerotarea nodurilor de interpolare in raport cu punctul de calcul x*. De asemenea, valorile polinoamelor L_i,j pot fi memorate intr-un singur vector, dupa un model asemanator celui prezentat in cazul polinoamelor Newton.
Pentru alte variante de implementare a modelului de aproximare cu polinoame
Lagrange, se poate consulta cartea "Calcul numeric cu aplicatii in Turbo Pascal".