Fenomen de Runge

De Viquipèdia
Dreceres ràpides: navegació, cerca
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ó[modifica | modifica el codi]

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

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

O el 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[modifica | modifica el codi]

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[modifica | modifica el codi]

Error de la interpolació de la funció de Runge respecte al nombre de nodes. L'error baixa degut als errors d'arrodoniment de l'ordinador.

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[modifica | modifica el codi]

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[modifica | modifica el codi]

Article principal: Interpolació per splines