Extrapolarea Richardson#

Acest concept va fi util și în momentul în care se va discuta despre integrarea numerică, așadar necesită o atenție deosebită.

Din punct de vedere numeric, dacă suntem interesați să evaluăm o funcție matematică într-un punct:

• Putem face evaluarea propriu-zisă - aceasta este metoda obișnuită, însă impractică în situația în care funcția descrisă este foarte complicată (greu de evaluat numeric);

• Putem să extrapolăm rezultatul.

Vom explica o modalitate de a extrapola rapid evaluarea căutată, minimizând eroarea introdusă și timpul de execuție.

Explicația matematică#

Fie \(\Psi(h)\), unde \(\Psi:\mathbb{R}\rightarrow\mathbb{R}\), o aproximare a unei valori exacte \(\Psi^*\in\mathbb{R}\). Atunci, valoarea \(\Psi^*\) se poate scrie:

\[ \boxed{ \begin{split} \Psi^*&=\Psi(h)+K_0h^{\lambda_0}+K_1h^{\lambda_1}+K_2h^{\lambda_2}+\dots\\ &=\Psi(h)+\sum_{i\geq0}K_ih^{\lambda_i} \end{split} } \]

Considerăm constante valorile \(K_i\) și \(\lambda_i\), \(\forall i\in\mathbb{N}\), cu proprietatea că \(h^{\lambda_i}\gt h^{\lambda_{i+1}}\) (deoarece ne dorim ca seria să conveargă).

Folosind această notație, \(\Psi^*\) poate fi scris în următoarea formă:

\[ \Psi^*=\Psi(h)+K_0h^{\lambda_0}+O(h^{\lambda_1}) \]

Să considerăm acum o constantă \(t\in\mathbb{R}_+\) ce va fi folosită în evaluarea funcției \(\Psi\). Avem deja o ecuație pentru \(\Psi^*\), dar vom mai forma una pentru \(h\to\dfrac{h}{t}\):

\[ \Psi^*=\Psi\left(\frac{h}{t}\right)+K_0\left(\frac{h}{t}\right)^{\lambda_0}+O(h^{\lambda_1}) \] \[ \Rightarrow t^{\lambda_0}\Psi^*=t^{\lambda_0}\Psi\left(\frac{h}{t}\right)+K_0h^{\lambda_0}+ t^{\lambda_0}O(h^{\lambda_1}) \]

Scâzând din acest rezultat \(\Psi^*=\Psi(h)+K_0h^{\lambda_0}+O(h^{\lambda_1})\), se obține:

\[ \Psi^*=\frac{t^{\lambda_0}\Psi\left(\frac{h}{t}\right)-\Psi(h)}{t^{\lambda_0}-1}+O(h^{\lambda_1}) \]

Ce au rezolvat toate aceste operații? Tocmai am transformat o modalitate de a aproxima \(\Psi^*\) cu o eroare de \(O(h^{\lambda_0})\) într-o aproximare de eroare \(O(h^{\lambda_1})\)!

Ce este cel mai impresionant este că nu am avut nevoie să cunoaștem informații precum originea lui \(\Psi^*\), ci numai o aproximare de eroare \(O(h^{\lambda_0})\) a acestuia.

Recurența Richardson#

Ne exprimăm dorința de a construi o funcție \(\Psi_i(h)\) astfel încât valoarea exactă \(\Psi^*\in\mathbb{R}\) să ia forma:

\[ \Psi^*=\Psi_i(h)+O(h^{\lambda_{i+1}}) \]

Atunci, în baza ecuației \(\Psi^*=\frac{t^{\lambda_0}\Psi\left({h}/{t}\right)-\Psi(h)}{t^{\lambda_0}-1}+O(h^{\lambda_1})\), se poate scrie următoarea formulă recursivă:

\[ \boxed{ \Psi_i(h)=\frac{t^{\lambda_{i-1}}\Psi_{i-1}\left(\frac{h}{t}\right)-\Psi_{i-1}(h)}{t^{\lambda_{i-1}}-1}}\,,\,\,\forall i\in\mathbb{N}^* \]

Această recurență va simplifica notațiile și calculele ulterioare.

Derivarea numerică#

Algoritmul explicat anterior poate fi utilizat pentru calcularea rapidă a derivatelor numerice.

Fie \(f:\mathbb{R}\rightarrow\mathbb{R}\) o funcție derivabilă pentru care se dorește evaluarea derivatei în punctul \(x_0\in\mathbb{R}\). Amintim că demonstrația aproximării derivatei folosind metoda celor trei puncte implică utilizarea seriilor Taylor (Maclaurin):

\[ f'(x)=\frac{f(x+h)-f(x-h)}{2h}-\frac{f^{(3)}(x)}{3!}h^2-\frac{f^{(5)}(x)}{5!}h^4-\dots,\,\forall x\in\mathbb{R} \]

În acest context, putem observa că prin \(f'(x_0)\) se înțelege \(\Psi^*\), iar astfel \(\Psi_0(h)=\dfrac{f(x_0+h)-f(x_0-h)}{2h}\). Observăm deci că are loc relația:

\[ \Psi^*=\Psi_0(h)-\frac{f^{(3)}(x_0)}{3!}h^2-O(h^4) \]

Bineînțeles, putem aplica direct formula de recurență descrisă, dar vom prefera o metodă mai naturală. Ne amintim că scopul acestei metode este de a îmbunătăți eroarea, anume \(O(h^2)\rightarrow O(h^4)\) (acceptăm această simplificare pentru a mai ușura din calcule). În acest scop, facem înlocuirea \(h\to\dfrac{h}{2}\):

\[ \Psi^*=\Psi_0\left(\frac{h}{2}\right)-\frac{f^{(3)}(x_0)}{3!}\left(\frac{h}{2}\right)^2-O(h^4) \] \[\Rightarrow 4\Psi^*=4\Psi_0\left(\frac{h}{2}\right)-\frac{f^{(3)}(x_0)}{3!}h^2-4O(h^4) \]

Scăzând aceste două ecuații, se obține:

\[ 3\Psi^*=4\Psi_0\left(\frac{h}{2}\right)-\Psi_0(h)-3O(h^4) \]

Amintim însă că \(\Psi^*\) reprezintă \(f'(x_0)\), deci am reușit să găsim o modalitate de a scrie cu o eroare de \(O(h^4)\) derivata de ordin întâi a funcției \(f\):

\[ \boxed{f'(x)=\frac{8f\left(x+\dfrac{h}{2}\right)+f(x-h)-f(x+h)-8f\left(x-\dfrac{h}{2}\right)}{6h}+O(h^4)}\,,\,\,\forall x\in\mathbb{R} \]

O scriere alternativă, folosind diferențe finite, ar putea fi:

\[ \boxed{f'(x)=\frac{8\delta_h^n[f](x)-\delta_{2h}^n[f](x)}{6h}+O(h^4)}\,,\,\,\forall x\in\mathbb{R} \]

Bineînțeles, algoritmul poate fi repetat pentru a obține o eroare și mai favorabilă, utilizând recurența deja descrisă anterior.

Licență#

The book "Metode Numerice", written by Valentin-Ioan Vintilă, is licensed under CC BY-NC-SA 4.0