Interpolació polinòmica i splines: Lagrange, Newton, error i fenomen de Runge

Interpolar és construir una funció que passi exactament pels punts que et donen. És una cosa diferent d'ajustar per mínims quadrats, que busca la millor aproximació però no obliga a passar per cap punt. Quina de les dues vols depèn de si les teves dades són exactes (valors tabulats d'una funció) o sorolloses (mesures experimentals): interpolar dades amb soroll és una mala idea, perquè obligues la corba a seguir l'error.

Existència i unicitat

Aquest resultat vol dir que totes les fórmules que veuràs donen el mateix polinomi: Lagrange, Newton i la baricèntrica són formes diferents d'escriure el mateix objecte, triades segons el que vulguis fer amb ell.

Lagrange: la forma conceptual

La base cardinal es construeix perquè cada element valgui $1$ al seu node i $0$ a tots els altres:

$$\ell_i(x) = \prod_{j\neq i}\frac{x-x_j}{x_i-x_j}, \qquad p(x) = \sum_{i=0}^{n} y_i\,\ell_i(x).$$

Amb aquesta propietat, que l'interpolació es compleixi és immediat: en avaluar al node $i$, només sobreviu el terme $i$. Els denominadors expliquen per què els nodes han de ser diferents.

És perfecta per demostrar coses i incòmoda per calcular: afegir un node obliga a refer-ho tot, i avaluar-la de manera ingènua és car. Per això existeix la forma baricèntrica, que precalcula uns pesos i converteix l'avaluació en un quocient de dues sumes. Multiplicar tots els pesos per una constant no canvia res, cosa que permet reescalar-los per evitar desbordaments.

Newton: la forma que es pot actualitzar

Les diferències dividides es defineixen recursivament: la d'ordre zero és el valor, i cada ordre superior és la diferència de dues de l'ordre anterior dividida per la separació dels nodes extrems. Amb elles,

$$p_n(x) = f[x_0] + \sum_{k=1}^{n} f[x_0,\ldots,x_k]\prod_{j=0}^{k-1}(x-x_j).$$

L'avantatge pràctic és decisiu: afegir un node nou només afegeix un terme, sense tocar els anteriors. L'ordre en què poses els nodes canvia les diferències intermèdies però no el polinomi final, perquè aquest és únic.

L'error d'interpolació

Si la funció és prou derivable en un interval que conté els nodes i el punt, existeix un punt intermedi tal que

$$f(x) - p_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^{n}(x-x_i).$$

La demostració consisteix a triar una constant perquè una funció auxiliar s'anul·li als nodes i al punt, i aplicar Rolle repetidament.

La fórmula té dos factors i tots dos importen. El producte nodal és petit a prop del centre dels nodes i gran als extrems, i creix molt de pressa fora de l'interval. I la derivada d'ordre alt pot créixer enormement amb $n$ per a algunes funcions.

Condicionament i nodes de Txebixev

Si les dades tenen soroll, la pertorbació de l'interpolant s'acota per la constant de Lebesgue, que és el màxim de la suma dels mòduls de la base cardinal. Mesura la sensibilitat del problema, no de l'algorisme: una constant de Lebesgue gran vol dir que cap mètode no pot ser robust amb aquells nodes.

La solució és triar millor els nodes. Les arrels dels polinomis de Txebixev,

$$x_k = \cos\frac{(2k+1)\pi}{2n+2},$$

minimitzen el màxim del producte nodal entre tots els polinomis mònics del mateix grau, i fan que la constant de Lebesgue creixi només logarítmicament en comptes d'exponencialment. Es concentren a prop dels extrems, que és justament on el problema era pitjor. Això millora molt el control de l'error, però no substitueix les hipòtesis de regularitat de la funció.

Splines cúbics

L'altra sortida és renunciar a un sol polinomi de grau alt i fer servir polinomis de grau baix a cada tros. Un spline cúbic interpolador és cúbic a cada interval, passa pels valors, i té continuïtat de les dues primeres derivades als nodes interiors. Aquestes condicions no basten: calen dues condicions addicionals, per exemple imposar segona derivada nul·la als extrems (spline natural) o fixar les derivades primeres.

Amb els separacions entre nodes i les segones derivades als nodes com a incògnites, les condicions de continuïtat donen un sistema tridiagonal, que es resol en temps lineal. Un cop tens les segones derivades, la fórmula del tros corresponent és explícita.

Exercici resolt: interpolació lineal i cota d'error

Interpola l'exponencial als nodes $0$ i $1$ i acota l'error a l'interval.

L'interpolant és la recta que passa per $(0,1)$ i $(1,e)$:

$$p(x) = 1 + (e-1)x.$$

La resta, amb $n = 1$, és

$$f(x)-p(x) = \frac{e^{\xi}}{2}\,x(x-1)$$

per a algun punt intermedi.

Acotem els dos factors. L'exponencial en l'interval no passa d'$e$. I el producte $|x(x-1)|$ té el màxim al punt mig, on val $1/4$. Per tant

$$|f(x)-p(x)| \leq \frac{e}{2}\cdot\frac14 = \frac{e}{8}\approx 0{,}34.$$

Precisió de la resposta: és una cota suficient, no l'error màxim exacte. L'error real màxim és menor, perquè els dos factors no assoleixen el seu màxim al mateix punt. Una cota vàlida i honesta és preferible a una estimació precisa i no justificada.

Exercici resolt: nodes repetits

Què falla si dos nodes coincideixen però tenen valors diferents?

No existeix cap funció que prengui dos valors diferents al mateix punt, i per tant el problema d'interpolació no té solució. A la fórmula de Lagrange es veu directament: un denominador s'anul·la.

I si els valors també coincideixen? Aleshores la dada és redundant: no aporta cap condició nova, i el sistema queda indeterminat. Amb $n+1$ nodes dels quals dos són iguals, només tens $n$ condicions independents i el polinomi de grau $n$ no queda determinat.

La sortida útil. La interpolació d'Hermite interpreta un node repetit com una condició sobre la derivada en aquell punt. Amb això, un node doble aporta dues condicions (valor i pendent) i el problema torna a estar ben plantejat. És el que hi ha darrere de les corbes de Bézier i dels splines amb derivades prescrites.