Acest subcapitol este, momentan, o schiță și/sau necesită modificări semnificative.
Suplimentar, acesta este prevăzut să se schimbe în edițiile următoare astfel încât să se adapteze mai bine nevoilor întâlnite în cadrul materiei de Metode Numerice.
Polinoame ortogonale#
Înainte de a continua cu metodele de aproximare, este necesară introducerea conceptului de polinom ortogonal, întrucât acestea cu siguranță nu au fost explicate pe la cursurile de matematică.
Acestea au o aplicabilitate foarte mare în tot ceea ce înseamnă metode numerice, așadar considerăm că necesită să fie tratate separat!
Într-adevăr, în această ediție a cărții, mă voi focaliza în mod special pe cazul continuu, urmând ca, poate în edițiile viitoare, să vă explic mai în detaliu și cazul discret.
Funcția pondere#
Ponderile apar peste tot - că vorbim de metode numerice sau de rețele neurale, fiți siguri că veți da de ele!
Fie \(\omega:D\subseteq\mathbb{R}\rightarrow(0,+\infty)\) o funcție oarecare. Atunci când \(\omega\) este folosită alături de o sumă, serie, integrală etc., aceasta poartă denumirea de funcție pondere.
Vom folosi astfel de funcții pentru a controla importanța sau influența unor elemente în operația pe care vrem să o executăm.
Spre exemplu, funcția:
\[ \omega(x)=\exp\left\{\frac{-x^2}{2}\right\},\,\forall x\in\mathbb{R} \]va pune accent pe elementele cât mai aproapiate de \(0\) și aproape că le va "ignora" pe celelalte - acest lucru se întâmplă fiindcă \(\omega(x)\) este o exponențială cu exponent negativ.
Ca să arătăm acest lucru, să evaluăm funcția în câteva puncte:
-
\(\omega(0)=1\) - acesta este chiar maximul funcției noastre;
-
\(\omega(1)=0.6\) - nici nu am trecut bine de o valoare unitară că aproape ne-am înjumătățit ponderea; mai precis, aceasta va fi chiar jumătate în punctul \(\omega(1.1174)\approx0.6\);
-
\(\omega(3.7169)\approx0.001\) - ponderea ajunge extrem de mică până ca variabila noastră să atingă valoarea \(4\); în \(5\), am obține \(\omega(5)\approx0.000004\).
Funcții ortogonale#
Dacă ar fi să definiți conceptul de "funcții ortogonale", cum ați începe? Ce legătură există între funcții oarecare și ortogonalitate?
Ei bine, putem pleca de la produsul scalar a doi vectori. În cazul acestora, \(\bm{x},\bm{y}\in\mathbb{R}^n\), \(n\in\mathbb{N}^*\), sunt ortogonali dacă și numai dacă produsul lor scalar este nul, adică:
\[\left\langle\bm{x},\bm{y}\right\rangle=0\]Dacă am putea defini produsul scalar al două funcții, atunci, folosindu-ne de aceeași idee, am putea defini și ortogonalitatea acestora.
Fie \(f,g:[a,b]\subset\mathbb{R}\rightarrow\mathbb{R}\) două funcții oarecare, respectiv \(\omega:[a,b]\rightarrow\mathbb{R}\) o funcție pondere. Atunci, produsul scalar dintre funcțiile \(f\) și \(g\) în raport cu funcția pondere \(\omega\) este, prin definiție:
\[\boxed{\left\langle f_i,f_j\right\rangle_{\omega}=\int_a^bf_i(x)\cdot f_j(x)\cdot\omega(x)\,dx}\]Spunem că acestea sunt ortogonale dacă și numai dacă produsul lor scalar este nul, adică \(\left\langle f_i,f_j\right\rangle_{\omega}=0\).
Generalizat, fie \(\left\{f_0,\dots,f_n\,|\,f_k:[a,b]\subset\mathbb{R}\rightarrow\mathbb{R},\,\forall k\in\overline{0,n}\right\}\) o mulțime de \(n+1\) funcții, unde \(n\in\mathbb{N}^*\). Spunem că funcțiile din mulțime sunt ortogonale între ele în raport cu o funcție pondere \(\omega:[a,b]\rightarrow\mathbb{R}\) dacă și numai dacă:
\[ \boxed{ \left\langle f_i,f_j\right\rangle_{\omega}=\int_a^bf_i(x)\cdot f_j(x)\cdot\omega(x)\,dx=\begin{cases} 0,&\text{dacă } i\neq j\\ \alpha_i,&\text{dacă } i=j \end{cases} } \]unde \(\alpha_0,\dots,\alpha_n\in(0,+\infty)\). Suplimentar, dacă \(\alpha_k=1\), \(\forall k\in\overline{0,n}\), atunci funcțiile se consideră ortonormate între ele.
Deoarece este greu să lucrăm cu funcții oarecare, ne vom ocupa exclusiv de înțelegerea polinoamelor, în mod special a familiilor de polinoame predefinite, adică cele pe care nu trebuie să le calculăm noi de la zero, precum Cebâșev sau Legendre.
(Bonus) Construirea polinoamelor ortogonale#
În general, proveniența polinoamelor ortogonale (așa cum au fost definite anterior, considerate polinoame ortogonale clasice) este atribuită soluționării unei ecuații diferențiale de forma:
\[ Q(x)\frac{d^2f}{dx^2}(x)+L(x)\frac{df}{dx}+\lambda f=0 \]unde \(Q\) și \(L\) sunt alese astfel încât:
-
\(Q:\mathbb{R}\rightarrow\mathbb{R}\) să fie un polinom de grad \(2\) sau mai puțin;
-
\(L:\mathbb{R}\rightarrow\mathbb{R}\) să fie un polinom de grad \(1\).
Funcția (polinomul) \(f:\mathbb{R}\rightarrow\mathbb{R}\), respectiv constanta \(\lambda\in\mathbb{R}\) trebuie calculate. Menționăm că gradele lui \(Q\) și ale lui \(L\) sunt limitate pentru ca ecuația finală să conțină un polinom de cel mult același grad precum \(f\).
Vom demonstra că ecuația diferențială anterioară este suficientă pentru a genera polinoame ortogonale. Înainte de a continua, definim funcția \(R(x)\), pe care o vom și deriva:
\[ R(x)=\exp\left\{\int\frac{L(x)}{Q(x)}\,dx\right\}\Rightarrow R'(x)=\frac{L(x)}{Q(x)}R(x) \]Să considerăm acum polinoamele \(f_i\) și \(f_j\) provenite din aceeași ecuație diferențială. Atunci, dacă păstrăm implicită dependența față de \(x\):
\[ Qf_i''+Lf_i'+\lambda_if_i=0 \]Vom înmulți ecuația anterioară cu \(\frac{R}{Q}f_j\):
\[ Rf_jf_i''+\frac{R}{Q}Lf_jf_i'+\frac{R}{Q}\lambda_if_jf_i=0 \]Alternativ, prin simpla inversare a indicilor, obținem formula:
\[ Rf_if_j''+\frac{R}{Q}Lf_if_j'+\frac{R}{Q}\lambda_jf_if_j=0 \]Aceste două ecuații se pot scădea între ele:
\[ \left(Rf_jf_i''+\frac{R}{Q}Lf_jf_i'+\frac{R}{Q}\lambda_if_jf_i\right)-\left(Rf_if_j''+\frac{R}{Q}Lf_if_j'+\frac{R}{Q}\lambda_jf_if_j\right)=0 \]Vom grupa acum termenii convenabil:
\[ \left[R\left(f_jf_i''-f_if_j''\right)+\frac{R}{Q}L\left(f_jf_i''-f_if_j''\right)\right]+\left[\left(\lambda_i-\lambda_j\right)\frac{R}{Q}f_jf_i\right]=0 \]Putem acum să integrăm în ambele părți pentru a obține
\[ \int_a^bR\left(f_jf_i''-f_if_j''\right)+\frac{R}{Q}L\left(f_jf_i''-f_if_j''\right)\,dx+\left(\lambda_i-\lambda_j\right)\int_a^b\frac{R}{Q}f_jf_i\,dx=0 \]Integrala din stânga poate însă să fie mult simplificată - putem observa cum, derivând funcția \(R\cdot(f_jf_i'-f_if_j')\), obținem chiar ceea ce se află în interiorul prime integrale, adică:
\[\begin{split} \frac{d}{dx}\Big[R(f_jf_i'-f_if_j')\Big]&=R\left(f_jf_i''-f_if_j''\right)+R'\left(f_jf_i''-f_if_j''\right)\\ &=R\left(f_jf_i''-f_if_j''\right)+\frac{R}{Q}L\left(f_jf_i''-f_if_j''\right) \end{split}\]Utilizând această formulă, putem reveni în egalitatea anterioară:
\[ \Big[R(f_jf_i'-f_if_j')\Big]_a^b+\left(\lambda_i-\lambda_j\right)\int_a^b\frac{R}{Q}f_jf_i\,dx=0 \]Așadar, dacă se construiesc polinoamele astfel încât \(f_jf_i'-f_if_j'=0\), se va respecta condiția de ortogonalitate:
\[ \int_a^b\frac{R}{Q}f_jf_i\,dx=0 \]Polinoame algebrice ortogonale#
Amitim conceptul de polinoame monice - acele polinoame ale căror coeficient din fața termenului cel mai semnificativ este egal cu \(1\).
De exemplu, polinomul \(x^4+7x^3-x\) este monic, în timp ce polinomul \(10x+5\) nu este.
Fără a ne complica să arătăm o demonstrație, acceptăm ca atare următoarea recurență ce poate fi utilizată în contextul oricărei familii de polinoame ortogonale monice[2][39]:
\[ \boxed{ \begin{cases} P_{-1}(x)=0\\ P_0(x)=1\\ P_{k+1}(x)=(x-\alpha_{k})P_{k}(x)-\beta_{k}P_{k-1}(x),&k\geq0 \end{cases}} \]unde prin \(\alpha_k\), \(\forall k\geq0\), se înțelege:
\[ \boxed{\alpha_k=\frac{\left\langle xP_k,P_k\right\rangle_{\omega}}{\left\langle P_k,P_k\right\rangle_{\omega}} =\frac{\int_a^bxP_k^2(x)\cdot\omega(x)\,dx}{\int_a^bP_k^2(x)\cdot\omega(x)\,dx}}\,,\,\,\forall k\geq0 \]respectiv, prin \(\beta_k\), \(\forall k\geq1\), se înțelege:
\[ \boxed{\beta_k=\frac{\left\langle P_k,P_k\right\rangle_{\omega}}{\left\langle P_{k-1},P_{k-1}\right\rangle_{\omega}} =\frac{\int_a^bP_k^2(x)\cdot\omega(x)\,dx}{\int_a^bP_{k-1}^2(x)\cdot\omega(x)\,dx}}\,,\,\,\forall k\geq1 \]Această recurență se va afla la baza calculării polinoamelor ortogonale monice, întrucât, din punct de vedere numeric, se consideră suficient de stabilă. Vom observa în paragrafele următoare cum poate fi aceasta utilă.
Începem acum discuția care ne interesează de fapt în acest subcapitol, anume familiile consacrate de polinoame ortogonale.
Polinoame Cebâșev#
Polinoamele Cebâșev (matematicianul rus Pafnuty Lvovich Chebyshev - Пафну́тий Льво́вич Чебышёв) au la bază următoarea funcție pondere:
\[ \boxed{\omega(x)=\frac{1}{\sqrt{1-x^2}}} \]Alături de aceasta, se vor seta și capetele integralei ce stă la baza produsului scalar: \(a=-1\), respectiv \(b=1\). În acest context, produsul scalar dintre două polinoame ortogonale Cebâșev \(T_i\) și \(T_j\) este dat de relația particularizată:
\[ \left\langle T_i,T_j\right\rangle_{\omega}=\int_{-1}^1T_i(x)\cdot T_j(x)\cdot\frac{1}{\sqrt{1-x^2}}\,dx \]Generarea acestor polinoame ortogonale se va face utilizând o formulă de recurență extrasă din cea generală - cu alte cuvinte, orice polinom ortogonal Cebâșev respectă recurența[39]:
\[ \begin{cases} T_0(x)=1\\ T_1(x)=x\\ T_{k+1}(x)=2xT_k(x)-T_{k-1}(x) \end{cases} \]În situația în care \(|x|\leq1\) (cazul de care suntem interesați pentru metodele numerice), recurența anterioară se traduce în formula:
\[ \boxed{T_k(x)=\cos\left(k\arccos x\right)}\,,\,\,\forall k\in\mathbb{N} \]Suplimentar, utilizând această formulă, putem obține o formulă mai practică de calcul a produsului scalar între două polinoame ortogonale monice Cebâșev:
\[ \boxed{ \left\langle T_i,T_j\right\rangle=\begin{cases} 0,&i\neq j\\ \pi,&i=j=0\\ \dfrac{\pi}{2},&i=j\neq0 \end{cases} } \]Fie \(T_i\) și \(T_j\) două polinoame Cebâșev. Atunci:
\[\begin{split} T_i(x)\cdot T_j(x)&=\cos\left(i\arccos x\right)\cdot\cos\left(j\arccos x\right)\\ &=\frac{1}{2}\Big[\cos\big((i+j)\arccos x\big)+\cos\big((i-j)\arccos x\big)\Big] \end{split}\]Acum, pentru a calcula produsul scalar, obținem:
\[\begin{split} \left\langle T_i,T_j\right\rangle&=\frac{1}{2}\int_{-1}^1\frac{\cos\big((i+j)\arccos x\big)+\cos\big((i-j)\arccos x\big)}{\sqrt{1-x^2}}\,dx \end{split}\]Putem face schimbarea de variabilă \(u=\arccos x\), \(u'=-\frac{1}{\sqrt{1-x^2}}\):
\[\begin{split} \left\langle T_i,T_j\right\rangle&=-\frac{1}{2}\int_{\arccos(-1)}^{\arccos(1)}\cos\big((i+j)u\big)+\cos\big((i-j)u\big)\,dx \end{split}\]Dacă \(i\neq j\), atunci integrala anterioară se dovedește a fi:
\[\left\langle T_i,T_j\right\rangle=\frac{1}{2}\left[\frac{\sin\big((i+j)u\big)}{i+j}+\frac{\sin\big((i-j)u\big)}{i-j}\right]_{0}^{\pi}\]Cum \(\sin(k\pi)=0\), \(\forall k\in\mathbb{Z}\), realizăm că \(\left\langle T_i,T_j\right\rangle=0\).
Dacă însă \(i=j\neq0\), atunci:
\[\left\langle T_i,T_i\right\rangle=\frac{1}{2}\left[\frac{\sin\big((i+j)u\big)}{i+j}+u\right]_{0}^{\pi}=\frac{\pi}{2}\]Nu în ultimul rând, dacă \(i=j=0\), atunci:
\[\left\langle T_0,T_0\right\rangle=\frac{1}{2}\Big[u+u\Big]_{0}^{\pi}=\pi\]Primele polinoame#
În tabelul de mai jos, voi ilustra primele câteva polinoame Cebâșev - acestea reies din recurența pe care am descris-o în paragrafele anterioare. Așadar, primele polinoame Cebâșev sunt:
| Indicele polinomului | Polinomul Cebâșev | |
| \(T_0(x)\) | \(1\) | |
| \(T_1(x)\) | \(x\) | |
| \(T_2(x)\) | \(2x^2-1\) | |
| \(T_3(x)\) | \(4x^3-3x\) | |
| \(T_4(x)\) | \(8x^4-8x^2+5x\) | |
| \(T_5(x)\) | \(16x^6-20x^3+5x\) |
Acestea se vor dovedi utile atât în cadrul exercițiilor din carte, cât și în cadrul celor ce se dau la examenul de Metode Numerice.
Polinoame Legendre#
Polinoamele Legendre au la bază următoarea funcție pondere:
\[ \boxed{\omega(x)=1} \]Ce se poate mai simplu de atât? Cu toate acestea, ele dau naștere unor polinoame ce nu au o formulă la fel de simplă precum polinoamele Cebâșev. Utilizând capetele de integrare \(a=-1\), respectiv \(b=1\), se obține următorul produs scalare între două polinoame ortogonale Legendre, \(L_i\) și \(L_j\):
\[ \left\langle L_i,L_j\right\rangle_{\omega}=\int_{-1}^1L_i(x)\cdot L_j(x)\,dx \]Generarea acestor polinoame ortogonale se va face utilizând o formulă de recurență extrasă tot din cea generală - cu alte cuvinte, orice polinom ortogonal Legendre va respecta recurența[39]:
\[ \boxed{\begin{cases} L_0(x)=1\\ L_1(x)=x\\ L_{k+1}(x)=\dfrac{2k+1}{k+1}xL_k(x)-\dfrac{k}{k+1}L_{k-1}(x) \end{cases}} \]Forma generală a polinoamelor Legendre este mult mai complexă decât forma polinoamelor Cebâșev. Cu toate acestea, vom prezenta și noi câteva variante de a le reprezenta:
-
Folosind formula lui Rodrigues:
\[ L_n(x)=\frac{1}{2^nn!}\frac{d^n}{dx^n}\left(x^2-1\right)^n \] -
Folosind sume de combinări:
\[ L_n(x)=\frac{1}{2^n}\sum_{k=0}^n(C_n^k)^2(x-1)^{n-k}(x+1)^k \]
Alte metode de reprezentare pot fi găsite pe pagina de Wikipedia dedicată.
Suplimentar, se poate determina o formulă mai practică pentru produsul a două astfel de polinoame:
\[ \boxed{ \left\langle L_i,L_j\right\rangle=\begin{cases} 0,&i\neq j\\ \dfrac{2}{2i+1},&i=j\neq0 \end{cases} } \]Primele polinoame#
În tabelul de mai jos, vom ilustra primele câteva polinoame Legendre - acestea reies din recurența pe care am descris-o în paragrafele anterioare. Așadar, primele polinoame Legendre sunt:
| Indicele polinomului | Polinomul Legendre | |
| \(L_0(x)\) | \(1\) | |
| \(L_1(x)\) | \(x\) | |
| \(L_2(x)\) | \(\dfrac{1}{2}(3x^2-1)\) | |
| \(L_3(x)\) | \(\dfrac{1}{2}(5x^3-3x)\) | |
| \(L_4(x)\) | \(\dfrac{1}{8}(35x^4-30x^2+3)\) | |
| \(L_5(x)\) | \(\dfrac{1}{8}(63x^5-70x^3+15x)\) |
Polinoame Jacobi#
Polinoamele ortogonale explicate anterior fac parte dintr-o familie mai mare de polinoame, cunoscută sub umbrela de polinoame Jacobi. Studiul acestora nu face obiectul acestei cărți, însă se pot găsi oricând detalii suplimentare în subcapitolul dedicat.
Polinoame trigonometrice#
Vom abstractiza acum puțin noțiunile învățate în cadrul polinoamelor algebrice ortogonale. Considerăm o funcție \(T:\mathbb{R}\rightarrow\mathbb{C}\) un polinom trigonometric dacă acesta are forma:
\[ T(x)=a_0+\sum_{k=1}^na_n\cos(nx)+\sum_{k=1}^nb_n\sin(nx) \]unde \(a_0,\dots,a_n,b_1\in\mathbb{C}\) și \(\dots,b_n\in\mathbb{C}\) sunt constante, iar \(n\in\mathbb{N}\).
Polinoame trigonometrice Fourier#
Polinoamele trigonometrice Fourier au la bază următoarea funcție pondere:
\[ \boxed{\omega(x)=1} \]Alături de aceasta, se vor seta capetele integralei \(a=0\), respectiv \(b=2\pi\). În acest context, produsul scalar dintre două polinoame ortogonale trigonometrice \(u_i\) și \(u_j\) este dat de relația particularizată:
\[ \langle u_i, u_j\rangle=\int_{0}^{2\pi}u_i(x)\cdot u_j(x)\,dx \]Polinoamele trigonometrice Fourier se definesc foarte simplu drept (în scrierea lor originală, se utilizează formula lui Euler, însă voi încerca să evit pe cât posibil lucrul cu numere complexe):
\[ \boxed{u_n=\begin{cases} 1,&n=0\\ \sin(kx),&n=2k+1,k\in\mathbb{N}\\ \cos(kx),&n=2k,k\in\mathbb{N}^* \end{cases}}\,,\,\,\forall n\in\mathbb{N} \]Folosind această formulă, prin simplu calcul brut, se obține o formă mai utilă a produsului scalar:
\[ \boxed{ \left\langle u_i,u_j\right\rangle=\begin{cases} 0,&i\neq j\\ 2\pi,&i=j=0\\ \pi,&i=j\neq0 \end{cases} } \]Polinoame ortogonale discrete#
Toate polinoamele ortogonale ce au fost descrise anterior au reprezentat situația continuă, în care se utilizează integrale definite pentru calculul produsului scalar între acestea. Există însă posibilitatea discretizării, prin utilizarea sumelor.
Definim așadar produsul a două polinoame ortogonale, \(f_i\) și \(f_j\), în raport cu ponderea \(\omega\) conform relației:
\[ \boxed{\langle f_i,f_j\rangle_{\omega}=\sum_{k=0}^nf_i(x_k)\cdot f_j(x_k)\cdot \omega(x_k)} \]Observăm că, pentru a avea sens, operația presupune cunoscute evaluările funcțiilor \(f_i\) și \(f_j\) în punctele \(x_0,\dots,x_n\). În rest, toate informațiile acumulate până la acest moment rămân valabile.
Detalii suplimentare despre acestea se pot găsi în subcapitolul dedicat.
Licență#
The book "Metode Numerice", written by Valentin-Ioan Vintilă, is licensed under CC BY-NC-SA 4.0 
