Fenomenul Runge

În analiză numerică, fenomenul Runge este o problemă de oscilație la marginile de un interval care se produce la utilizarea unui polinom de interpolare de un grad ridicat. Acest fenomen a fost descoperit de către Carl David Tolmé Runge când explora comportamentul erorilor atunci când se utilizează polinoame de interpolare pentru aproximarea anumitor funcții. În examinarea acestui aspect, matematicianul David Carle Runge Tolmé a descoperit un rezultat contrar intuiției: există configurații în care diferența între funcția de interpolare și cea interpolată este mare și tinde la infinit odată cu n.

Curba roșie este funcția Runge, curba albastră este polinom de interpolare de gradul 5 și curba verde este polinom de interpolare de grad 9. Aproximarea este din ce în ce mai slabă

Introducere

Teorema de aproximare a lui Weierstrass prevede că fiecare funcție continuă f (x) definită pe un interval [a, b ] poate fi aproximată ca limita unui șir uniform convergent de polinoame de interpolare:

$\lim _{n\rightarrow \infty }\left(\max _{a\leq x\leq b}|f(x)-P_{n}(x)|\right)=0.$

Interpolarea cu puncte echidistante este o abordare naturală și binecunoscută pentru a construi polinoame aproximare. Fenomenul Runge demonstrează, totuși, că această interpolare poate fi divergentă.

Exemplu

Considerăm următoarea funcție:

$f(x)={\frac {1}{1+25x^{2}}}$

Având în vedere $(n+1)$ puncte uniform distribuite în segmentul $[-1,1]$:

$\scriptstyle x_{0}=-1,\;x_{1}=x_{0}+h,\;\cdots ,\;x_{k+1}=x_{k}+h=x_{0}+(k+1)h,\;\cdots ,\;x_{n}=1\ {\text{cu}}\ h=\textstyle {\frac {2}{n}}$

În cele din urmă, considerăm polinomul de interpolare $f$ în punctele $(x_{i})$, care este polinomul unic $P$de grad mai mic sau egal cu n astfel încât $P(x_{i})=f(x_{i})$ pentru orice i. Se notează cu $P_{n}$.

Runge a arătat că eroarea de interpolare între $P_{n}$ și $f$ tinde la infinit ca n crește. Formal:

$\lim _{n\rightarrow \infty }\left(\max _{-1\leq x\leq 1}|f(x)-P_{n}(x)|\right)=\infty$

De fapt, atunci când creșterea numărului de puncte, vom vedea că polinomul începe să oscileze puternic între punctele de $x_{i}$ cu amplitudinea în creștere.

Explicație

Aplicând în mod repetat teorema lui Rolle, putem arăta că în cazul interpolării celor $(n+1)$ puncte distribuite în mod egal, există un punct în intervalul $\xi \in [-1;1]$ încât eroarea dintre funcția generatoare și polinomul de interpolare de grad n este dată de

$f(x)-P_{n}(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\prod _{i=1}^{n+1}(x-x_{i})$

pentru $\xi$ între (−1, 1). Astfel,

$\max _{-1\leq x\leq 1}|f(x)-P_{n}(x)|\leq \max _{-1\leq x\leq 1}{\frac {|f^{(n+1)}(x)|}{(n+1)!}}\max _{-1\leq x\leq 1}\prod _{i=0}^{n}|x-x_{i}|.$

Rezultă că eroarea de aproximare crește la infinit odată cu n.

Într-un context mai larg, polinomul de interpolare cu noduri echidistante nu este o metodă stabilă. Într-adevăr, notând (l_i) , polinoamele Lagrange de bază corespunzătoare elementelor (x_i):

$l_{j}(x):=\prod _{\begin{smallmatrix}0\leq m\leq k\\m\neq j\end{smallmatrix}}{\frac {x-x_{m}}{x_{j}-x_{m}}}={\frac {(x-x_{0})}{(x_{j}-x_{0})}}\cdots {\frac {(x-x_{j-1})}{(x_{j}-x_{j-1})}}{\frac {(x-x_{j+1})}{(x_{j}-x_{j+1})}}\cdots {\frac {(x-x_{k})}{(x_{j}-x_{k})}}.$

avem:

$P_{n}(x)=\sum _{i=0}^{n}f(x_{i})l_{i}(x),$

care ne conduce la următoarea estimare:

$\left|P_{n}(x)\right|\leqslant \left(\sum _{i=0}^{n}\left|l_{i}(x)\right|\right)\|f\|_{\infty }\leqslant \sup _{x\in [a,b]}\left(\sum _{i=0}^{n}\left|l_{i}(x)\right|\right)\|f\|_{\infty }.$

Constanta $\Lambda _{n}=\sup _{x\in [a,b]}\left(\sum _{i=0}^{n}\left|l_{i}(x)\right|\right)$ este numită constanta Lebesgue asociată punctelor (xi)'. În caz de puncte echidistante, această constantă poate fi estimată prin:

$\Lambda _{n}\sim {\frac {2^{n+1}}{e\,n\ln(n)}},$

unde e este numărul lui Euler în valoare de 2.7183 ... . Vedem că, în acest caz, constanta Lebesgue tinde rapid la valori mari, mai repede decât poate converge la funcția polinomială de interpolaref.

Soluții la fenomenul Runge

Fenomenul Runge demonstrează că interpolarea polinomială nu este cea mai bună metodă de interpolare a funcțiilor.

Putem minimiza oscilațiile de polinoame de interpolare folosind polinomul Cebîșev de interpolare în loc de puncte distribuite în mod egal pentru a interpola. În acest caz, putem arăta că eroarea de interpolare $\max _{-1\leq x\leq 1}|f(x)-P_{n}(x)|$ descrește.

O metodă este utilizarea de noduri care sunt distribuite mult mai dens spre marginile intervalului.

O altă metodă este metoda celor mai mici pătrate.

O altă metodă foarte des întâlnită este aproximarea cu funcții spline (acestea sunt polinoame pe porțiuni; în acest caz, pentru a îmbunătăți aproximarea, vom crește numărul de bucăți și nu gradul de polinoame).

Bibliografie

• Jean Dieudonné, Calcul infinitésimal Format:Détail des éditions, chap. IX, appendice (pp. 319-320)

Legaturi externe

• http://an.lmn.pub.ro/lab/AN_Lab_4_v2.pdf
• www.ingineriebraila.ugal.ro/IngMec/An%20II-22-PA.doc