Interpolazione polinomiale

L'interpolazione polinomiale è l'interpolazione di una serie di valori (ad esempio dei dati sperimentali) con una funzione polinomiale che passa per i punti dati. In particolare, un qualsiasi insieme di ${\displaystyle n+1}$ punti distinti può essere sempre interpolato da un polinomio di grado ${\displaystyle n}$ che assume esattamente il valore dato in corrispondenza dei punti iniziali.

Interpolazione e approssimazione

L'interpolazione polinomiale è un caso particolare di approssimazione tramite polinomi, dove il vettore degli scarti ${\displaystyle r,}$ ossia il vettore dei quadrati della distanza tra il valore dato in un punto e il valore del polinomio approssimante in quel punto è nullo. Mentre per l'approssimazione polinomiale si vuole trovare un polinomio (generalmente di basso grado) che approssima i punti dati con un errore minimo, nell'interpolazione si vuole trovare il polinomio (potenzialmente di alto grado) che passa esattamente per quei punti.

Sebbene il polinomio di interpolazione assuma il valore esatto nei punti dati, dato il grado superiore esso tenderà ad oscillare maggiormente tra un punto e l'altro, dando quindi una previsione del valore in quelle aree che sarà peggiore di quella data da un polinomio di grado inferiore che non passa per tutti i punti dati. Questo fenomeno è noto come fenomeno di Runge.

Costruzione di un polinomio di interpolazione

Un polinomio di interpolazione può essere costruito con diversi metodi, ad esempio ricorrendo alla matrice di Vandermonde o alla formula di interpolazione di Lagrange.

Esistenza del polinomio interpolatore

Dati ${\displaystyle n+1}$ punti ${\displaystyle (x_{i},y_{i})}$ distinti, dove ${\displaystyle y=f(x)}$, dobbiamo determinare il polinomio (eventualmente unico) di grado minimo che passa per i punti assegnati.

${\displaystyle (x_{i},y_{i}),\qquad i=0,1,\ldots ,n,\qquad y_{i}=f(x_{i}).}$

Teorema di unicità del polinomio interpolatore

Esiste uno ed un sol polinomio di grado al più ${\displaystyle n}$ che assume valori ${\displaystyle y_{i}}$, ${\displaystyle i=0,1,\ldots ,n}$, in corrispondenza di ${\displaystyle n+1}$ punti distinti ${\displaystyle x_{i}}$, ${\displaystyle i=0,1,\ldots ,n}$.

Dimostrazione

Abbiamo preso ${\displaystyle n+1}$ punti così da poter usare un polinomio di grado ${\displaystyle n}$ che ha ${\displaystyle n+1}$ coefficienti

${\displaystyle P_{n}(x)=a_{0}+a_{1}x+\dots +a_{n}x^{n}}$

e imporre le condizioni

${\displaystyle {\begin{cases}a_{0}+a_{1}x_{0}+\dots +a_{n}x_{0}^{n}=y_{0}\\a_{0}+a_{1}x_{1}+\dots +a_{n}x_{1}^{n}=y_{1}\\\qquad \vdots \\a_{0}+a_{1}x_{n}+\dots +a_{n}x_{n}^{n}=y_{n}.\end{cases}}}$

I parametri incogniti ${\displaystyle a_{0},a_{1},\ldots ,a_{n}}$ sono soluzione del seguente sistema quadrato di ordine ${\displaystyle n+1}$. Dovremo quindi risolvere il sistema associato

${\displaystyle Ax=b}$

${\displaystyle \left({\begin{array}{ccccc}1&x_{0}&x_{0}^{2}&\dots &x_{0}^{n}\\1&x_{1}&x_{1}^{2}&\dots &x_{1}^{n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}&x_{n}^{2}&\dots &x_{n}^{n}\\\end{array}}\right)\left({\begin{array}{c}a_{0}\\a_{1}\\\vdots \\a_{n}\end{array}}\right)=\left({\begin{array}{c}y_{0}\\y_{1}\\\vdots \\y_{n}\end{array}}\right),}$

dove ${\displaystyle A}$ è la classica matrice di Vandermonde, che risulta non singolare se e solo se ${\displaystyle x_{i}\neq x_{j}}$ per ${\displaystyle i\neq j}$ (e quindi ${\displaystyle x_{i}-x_{j}\neq 0}$), dato che

${\displaystyle \det(V)=\prod _{n\geq i>j\geq 1}(x_{i}-x_{j})=\prod _{j=0}^{n-1}\left[\prod _{i=j+1}^{n}\underbrace {(x_{i}-x_{j})} _{\neq 0}\right].}$

Essendo la matrice non singolare, si ha che il polinomio di grado ${\displaystyle n}$ esiste ed è unico.

Il sistema ci è servito per stabilire l'esistenza di ${\displaystyle P_{n}(x)}$ ma non è consigliato risolvere il sistema per due motivi:

• i sistemi con matrici di Vandermonde sono mal condizionati;
• il numero di operazioni aritmetiche necessarie è elevato.

Esempio di interpolazione

Di una funzione ${\displaystyle f}$ che in altra sede è nota si supponga di conoscere alcuni valori; in particolare si considerino i seguenti valori tabulati

Diagramma dei punti dati.

x	f(x)
0	0
1	0,8415
2	0,9093
3	0,1411
4	−0,7568
5	−0,9589
6	−0,2794

Ci si chiede, per esempio: quanto vale la funzione in ${\displaystyle x=2,5}$? L'interpolazione risolve problemi come questo.

Il seguente polinomio di sesto grado passa attraverso tutti i sette punti dati:

${\displaystyle f(x)=-0,0001521x^{6}-0,003130x^{5}+0,07321x^{4}-0,3577x^{3}+0,2255x^{2}+0,9038x.}$

Sostituendo ${\displaystyle x=2,5,}$ si ha che ${\displaystyle f(2,5)=0,5965.}$

L'errore di interpolazione è proporzionale alla distanza fra i punti dati alla potenza ${\displaystyle n.}$ Inoltre questo interpolante, essendo un polinomio, è illimitatamente differenziabile. Quindi l'interpolazione polinomiale, in linea di principio, risolve tutti i problemi di interpolazione lineare.

Tuttavia questo metodo presenta alcuni svantaggi. Il calcolo che porta ai coefficienti del polinomio d'interpolazione è molto "costoso" (in termini di tempo di esecuzione richiesto al calcolatore e in termini di complessità delle elaborazioni). Inoltre, l'interpolazione polinomiale per il complesso dei valori dalla variabile indipendente non si rivela molto esatta; questo accade in particolare nei punti estremi. Questi svantaggi possono essere evitati usando i metodi dell'interpolazione spline o razionale col metodo Floater Hormann.

Interpolazione di funzioni su calcolatore

Su calcolatore l'interpolazione polinomiale è soggetta a diversi problemi. Il peggiore è sicuramente il mal condizionamento della matrice dei coefficienti (che assume la forma di matrice di Vandermonde). Ciò si traduce nella impossibilità di poter risolvere il sistema di equazioni con metodi standard come decomposizione LU o sostituzione all'indietro, infatti al crescere del numero dei nodi cresce il sistema e l'indice di condizionamento si fa sempre più grande.

Per calcolare i coefficienti del polinomio interpolante, senza dover risolvere il sistema di equazioni mal condizionato, viene utilizzata l'interpolazione di Lagrange oppure l'interpolazione spline.

I software per il calcolo numerico sono, il più delle volte, provvisti di funzioni built-in per risolvere questi problemi.

Su MATLAB vengono utilizzati due comandi per interpolare una funzione tramite polinomi:

• polyfit per calcolare il polinomio interpolante su un insieme di nodi noti;
• polyval per valutare il polinomio su punti in cui non si conosce la ${\displaystyle f(x).}$

La scelta dei nodi da utilizzare per l'interpolazione viene fatta in modo da soddisfare la proprietà di convergenza uniforme tra funzione interpolante e funzione da interpolare, scegliendo i nodi in modo che non siano equidistanti.

Sulla scelta influiscono diverse cause:

• Teorema di Faber: data una qualunque successione di nodi in un intervallo chiuso ${\displaystyle [a,b]}$ esiste sempre una funzione ${\displaystyle f(x)}$ che genera una sequenza di polinomi di interpolazione che non convergono uniformemente a ${\displaystyle f}$ in ${\displaystyle [a,b]}$.
• Fenomeno di Runge: nell'intervallo ${\displaystyle [-5,5]}$ la funzione ${\displaystyle f(x)=1/(1+x^{2})}$ se interpolata con una funzione ${\displaystyle p(x)}$ mostra che all'aumentare del numero di nodi (equidistanti) ${\displaystyle p(x)}$ non converge a ${\displaystyle f(x)}$ ma l'errore aumenta.

Ciò che viene fatto generalmente è scegliere i nodi utilizzando la definizione di nodi di Čebyšëv che assicurano la convergenza uniforme all'aumentare del numero di nodi.

Su MATLAB i nodi di Čebyšëv su un intervallo ${\displaystyle [a,b]}$ vengono calcolati eseguendo la funzione:

  %i = vettore degli indici dei nodi (da 0 a n-1 nodi)
  %n = numero di nodi 
  nchev=(a+b)/2 + (a-b)/2 * cos((2*i+1)/(2*(n+1))*pi)

nchev conterrà alla fine un vettore riga che rappresenta i nodi (x) da utilizzare per interpolare la funzione.

Stima dell'errore

Siano dati ${\displaystyle n+1}$ punti distinti, ${\displaystyle x_{0},x_{1},\ldots ,x_{n}}$ dell'intervallo chiuso e limitato ${\displaystyle [a,b]\subset \mathbb {R} }$. Sia ${\displaystyle f(x)}$ una funzione assegnata nello spazio ${\displaystyle C^{n+1}[a,b]}$ e ${\displaystyle p(x)}$ il polinomio di grado ${\displaystyle n}$ tale che:

${\displaystyle p(x_{i})=f(x_{i}),\qquad i=0,1,\ldots ,n.}$

Allora per ogni ${\displaystyle x\in [a,b]}$ esiste un valore

${\displaystyle \zeta _{x}}$, con ${\displaystyle E(x)=f(x)-p(x)={\frac {1}{(n+1)!}}(x-x_{0})(x-x_{1})\ldots (x-x_{n})f^{(n+1)}(\zeta _{x})}$

con ${\displaystyle E(x)}$ definito errore di interpolazione, ossia l'errore che si commette approssimando il valore della funzione col valore del polinomio.

Posto ${\displaystyle M_{n+1}=\max _{x\in [a,b]}|f^{(n+1)}(x)|}$, un limite superiore del valore assoluto dell'errore di interpolazione ${\displaystyle E(x)=f(x)-p(x)}$ risulta essere

${\displaystyle |E(x)|\leq {\frac {M_{n+1}}{(n+1)!}}|(x-x_{0})(x-x_{1})\ldots (x-x_{n})|.}$

Questa formula è molto utile per stimare, ad esempio, il numero di nodi necessari ad ottenere un errore di interpolazione minore di una data tolleranza massima.

Nodi di Čebyšëv

I nodi di Čebyšëv sono una distribuzione specifica di punti sull'intervallo di interpolazione che permette di minimizzare l'errore massimo del polinomio interpolante, risolvendo i problemi di instabilità numerica che emergono con nodi equidistanti.

Il problema dei nodi equidistanti

La scelta intuitiva di utilizzare nodi equidistanti nell'interpolazione polinomiale porta a gravi problemi numerici. Come dimostrato dal fenomeno di Runge, l'uso di nodi equidistanti causa oscillazioni incontrollate del polinomio interpolante agli estremi dell'intervallo, oscillazioni che peggiorano all'aumentare del grado del polinomio.

Questo accade perché l'errore di interpolazione è proporzionale al prodotto:

${\displaystyle |(x-x_{0})(x-x_{1})\ldots (x-x_{n})|.}$

Con nodi equidistanti, questo prodotto raggiunge valori molto elevati vicino agli estremi dell'intervallo, rendendo l'interpolazione inaffidabile proprio dove spesso si ha maggiore interesse pratico.

Definizione e proprietà

I nodi di Čebyšëv dell'intervallo ${\displaystyle [-1,1]}$ sono definiti come:

${\displaystyle x_{k}=\cos \left({\frac {(2k+1)\pi }{2(n+1)}}\right),\qquad k=0,1,\ldots ,n.}$

Per un intervallo generico ${\displaystyle [a,b]}$, i nodi si ottengono tramite trasformazione lineare:

${\displaystyle x_{k}={\frac {a+b}{2}}+{\frac {b-a}{2}}\cos \left({\frac {(2k+1)\pi }{2(n+1)}}\right).}$

Questa distribuzione presenta le seguenti caratteristiche fondamentali:

• Addensamento agli estremi: i nodi sono più fitti vicino ai bordi dell'intervallo e più radi al centro.
• Origine geometrica: corrispondono alle proiezioni sull'asse delle ascisse di punti equidistanti sulla circonferenza unitaria.
• Ottimalità: minimizzano il valore massimo di ${\displaystyle |(x-x_{0})(x-x_{1})\ldots (x-x_{n})|}$ sull'intervallo.

Vantaggi teorici e pratici

L'utilizzo dei nodi di Čebyšëv garantisce:

• Convergenza uniforme: per funzioni sufficientemente regolari, l'errore di interpolazione tende a zero uniformemente su tutto l'intervallo all'aumentare del numero di nodi.
• Controllo dell'errore: il fattore ${\displaystyle |(x-x_{0})(x-x_{1})\ldots (x-x_{n})|}$ è limitato superiormente da ${\displaystyle 2^{-n}}$.
• Stabilità numerica: evita le oscillazioni spurie tipiche dei nodi equidistanti.
• Quasi-ottimalità: l'errore si avvicina al minimo teoricamente possibile (approssimazione uniforme ottima).

Implementazione numerica

In ambiente MATLAB, i nodi di Čebyšëv su un intervallo ${\displaystyle [a,b]}$ si calcolano con:

  %i = vettore degli indici dei nodi (da 0 a n-1)
  %n = numero di nodi 
  nchev = (a+b)/2 + (b-a)/2 * cos((2*i+1)/(2*n)*pi)

Confronto con altri metodi

Mentre i nodi equidistanti portano al fenomeno di Runge e i nodi casuali offrono prestazioni imprevedibili, i nodi di Čebyšëv rappresentano la scelta standard per l'interpolazione polinomiale quando si richiede:

• affidabilità numerica su tutto l'intervallo;
• controllo teorico dell'errore;
• convergenza garantita per funzioni analitiche.

Tuttavia, per funzioni con comportamenti molto localizzati o discontinuità, approcci adattivi o metodi spline possono risultare più appropriati.

Nodi di Leja

I nodi di Leja sono una sequenza di punti di interpolazione definiti ricorsivamente su un insieme compatto, introdotti dal matematico polacco Franciszek Leja nel 1957. Questi nodi rappresentano un'alternativa ai nodi di Čebyšëv nell'interpolazione polinomiale, offrendo vantaggi computazionali significativi in applicazioni che richiedono l'aggiunta iterativa di punti di interpolazione.

Definizione

Dato un insieme compatto ${\displaystyle K\subset \mathbb {C} }$, la sequenza dei nodi di Leja ${\displaystyle \{z_{n}\}_{n=0}^{\infty }}$ viene costruita nel modo seguente:

• Il primo punto ${\displaystyle z_{0}}$ è scelto arbitrariamente in ${\displaystyle K}$.
• Per ${\displaystyle n\geq 1}$, il punto ${\displaystyle z_{n}}$ è determinato dalla condizione:

${\displaystyle z_{n}=\arg \max _{z\in K}\prod _{j=0}^{n-1}|z-z_{j}|.}$

In altre parole, ogni nuovo punto viene scelto in modo da massimizzare il prodotto delle distanze da tutti i punti precedentemente selezionati.

Per l'intervallo reale ${\displaystyle [-1,1]}$, questa costruzione produce una distribuzione di punti che si addensa verso gli estremi dell'intervallo, simile a quella dei nodi di Čebyšëv, ma con una struttura ricorsiva che consente l'aggiunta incrementale di nuovi nodi.

Proprietà teoriche

La teoria dei punti di Leja è strettamente legata alla teoria del potenziale e presenta diverse proprietà notevoli:

• Crescita subesponenziale della costante di Lebesgue: per molti insiemi compatti, la costante di Lebesgue associata ai primi ${\displaystyle n}$ nodi di Leja cresce subexponenzialmente in ${\displaystyle n}$, garantendo la stabilità numerica dell'interpolazione.

• Convergenza dell'interpolazione: per funzioni analitiche su ${\displaystyle K}$, l'interpolazione polinomiale sui nodi di Leja converge uniformemente alla funzione originale.

• Distribuzione asintotica: la distribuzione asintotica dei nodi di Leja coincide con la misura di equilibrio dell'insieme ${\displaystyle K}$, proprietà condivisa con i nodi di Čebyšëv.

Vantaggi computazionali

I nodi di Leja presentano diversi vantaggi rispetto ai nodi di Čebyšëv in contesti computazionali:

La costruzione ricorsiva permette di estendere facilmente un'interpolazione esistente aggiungendo nuovi punti, senza dover ricalcolare l'intera griglia. Questo è particolarmente utile in algoritmi adattivi dove il numero di punti necessari non è noto a priori.

La compatibilità con la forma di Newton dell'interpolazione polinomiale consente di aggiornare il polinomio interpolante con costo computazionale ${\displaystyle O(n)}$ quando si aggiunge un nuovo punto, rendendo i nodi di Leja ideali per applicazioni che richiedono un controllo adattivo dell'errore.

La stabilità numerica è comparabile a quella dei nodi di Čebyšëv, evitando il fenomeno di Runge tipico dei nodi equidistanti.

Confronto con i nodi di Čebyšëv

Mentre i nodi di Čebyšëv minimizzano teoricamente la costante di Lebesgue, i nodi di Leja offrono prestazioni quasi ottimali con maggiore flessibilità computazionale. La principale differenza risiede nella struttura: i nodi di Čebyšëv di grado ${\displaystyle n}$ non contengono quelli di grado ${\displaystyle n-1}$, rendendo difficile l'estensione incrementale dell'interpolazione.

Per l'intervallo ${\displaystyle [-1,1]}$, entrambe le distribuzioni mostrano un addensamento verso gli estremi, ma i nodi di Leja permettono una migliore gestione della crescita adattiva del grado del polinomio interpolante.

Implementazione numerica

L'algoritmo per la costruzione dei nodi di Leja su un intervallo ${\displaystyle [a,b]}$ può essere implementato discretizzando l'intervallo e applicando la definizione ricorsiva:

  % Inizializzazione
  K = linspace(a, b, N);  % Discretizzazione dell'intervallo
  leja_points = [];
  
  % Primo punto (spesso al centro)
  leja_points(1) = (a + b) / 2;
  
  % Costruzione ricorsiva
  for n = 2:num_points
      distances = ones(size(K));
      for j = 1:length(leja_points)
          distances = distances .* abs(K - leja_points(j));
      end
      [~, idx] = max(distances);
      leja_points(n) = K(idx);
  end

Per insiemi compatti più generali nel piano complesso, esistono generalizzazioni dell'algoritmo che utilizzano tecniche di ottimizzazione numerica per la ricerca del massimo.

Applicazioni

I nodi di Leja trovano applicazione in diversi contesti dell'analisi numerica:

• Interpolazione adattiva: in algoritmi che richiedono un controllo dinamico dell'errore di approssimazione.
• Integrazione numerica: come punti di quadratura in formule composte adattive.
• Approssimazione di funzioni: in metodi spettrali per la risoluzione di equazioni differenziali.
• Calcolo di funzioni matriciali: nell'implementazione di integratori esponenziali basati su interpolazione polinomiale.

La natura ricorsiva della costruzione rende i nodi di Leja particolarmente adatti a problemi dove la precisione richiesta non è nota a priori e deve essere determinata durante il calcolo.

Bibliografia

• R.Bevilacqua, D. Bini, M.Capovani, O. Menchi (2003). Appunti di Calcolo Numerico. Capitolo 5. Servizio Editoriale Universitario Pisa - Azienda Regionale Diritto allo Studio Universitario.
• F. Leja (1957). Sur certaines suites liées aux ensembles plans et leur application à la représentation conforme. Ann. Polon. Math. 4, 8–13. DOI: 10.4064/ap-4-1-8-13
• L. Reichel (1990). Newton interpolation at Leja points. BIT Numerical Mathematics 30, 332–346. DOI: 10.1007/BF02017352
• R. Taylor, V. Totik (2010). Lebesgue constants for Leja points. IMA Journal of Numerical Analysis 30, 462–486. DOI: 10.1093/imanum/drn082
• J. Baglama, D. Calvetti, L. Reichel (1998). Fast Leja points. Electronic Transactions on Numerical Analysis 7, 124–140. PDF

Collegamenti esterni

• Applet interattivo per Fast Leja points - Electronic Transactions on Numerical Analysis
• Implementazione Julia dei nodi di Leja - MatrixPolynomials.jl
• Algoritmo greedy per punti di interpolazione - Chebfun

Voci correlate

• Polinomio osculatore

Collegamenti esterni

• (EN) polynomial interpolation, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica