Fenomen de Runge

La corba vermella és la funció de Runge. La corba blava és el polinomi interpolador de grau 5 (utilitzant sis nodes equiespaiats). La corba verda és el polinomi interpolador d'ordre 9 (utilitzant 10 nodes equiespaiats).

En anàlisi numèrica, el fenomen de Runge és un problema que apareix en la interpolació polinòmica de funcions quan s'utilitzen un alt nombre de nodes. És un resultat important perquè demostra que no sempre augmentar el nombre de nodes d'una interpolació millora la precisió d'aquesta, la qual cosa promou la creació de dos camins diferents en l'anàlisi numèrica, la interpolació no equiespaiada i la interpolació per splines.

Introducció

El teorema d'aproximació de Weierstrass ens diu que si $\,f(x)$ és una funció contínua, llavors

$\forall \varepsilon >0,\quad \exists p(x):\;|f(x)-p(x)|<\varepsilon$

O cosa que és el mateix, sigui $\,P_{n}(x)$ un polinomi interpolador (desconegut) d'ordre $\,n$ , es compleix que:

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

Des d'un punt de vista teòric, això ens diu que és possible trobar un polinomi interpolador de grau suficientment alt de manera que aproximi qualsevol funció contínua. Això no obstant, a la pràctica trobar aquest polinomi és impossible, perquè no podem calcular polinomis de grau infinit i als errors d'arrodoniment dels ordinadors.

Explicació del fenomen

Suposem que volem interpolar la funció $f(x)={\frac {1}{1+25x^{2}}}$ en l'interval $\,[-1,1]$ . Podem triar una distribució equiespaiada dels nodes de la interpolació. És a dir:

$x_{j}=-1+{\frac {2j}{n}},\quad j=0,1,\ldots ,n$

Anomenarem $P_{n}(x)$ al polinomi que passa per aquests punts i per les seves respectives abscisses. Runge va demostrar que l'error d'aquesta interpolació quan n tendeix a infinit és també infinit. És a dir, que:

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

Possibles solucions

Hem vist analíticament que si augmentem el nombre de nodes per interpolar la funció de Runge l'error tendeix a l'infinit. A la figura de la dreta es pot veure l'error respecte del nombre de nodes. És important notar que:

L'error arriba fins aproximadament 1e10 amb tan sols 55 nodes d'interpolació.
A partir d'aquí l'error disminueix degut als errors d'arrodoniment de l'ordinador.
L'error "s'estabilitza" en aproximadament 1e3.

En definitiva, arribem a la conclusió que la interpolació equiespaiada és numèricament inestable. Cal, doncs, trobar mètodes alternatius per tal de solucionar aquest problema. A continuació explicarem alguns dels remeis més habituals.

Interpolació no equiespaiada

Els nodes d'interpolació de Txebixev són numèricament estables i permeten interpolar la funció de Runge amb errors propers a l'epsilon de la màquina.

Aquest mètode consisteix, en resum, en utilitzar una distribució de nodes més densa en els extrems dels intervals d'interpolació. Això es fa de la següent manera: suposem que volem interpolar una funció amb n+1 nodes. Aquests nodes els trobarem de la següent manera:

$x_{j}=\cos \left({\frac {\pi j}{n}}\right),\;j=0,1,\ldots ,n$

Com es veu al gràfic de l'esquerra, aquesta distribució dels nodes permet arribar a errors de 1e-15 (és a dir, molt propers a l'epsilon de la màquina) utilitzant 175 nodes. Des d'aquest punt, veiem que augmentar el nombre de nodes amb prou feines augmenta l'error de la interpolació. Els nodes de Chebyshev són, per tant, numèricament estables.

Interpolació per splines