9  Esempio di Runge

Autore/Autrice
Affiliazione

Enrico Bertolazzi

University of Trento, Department of Industrial Engineering

9.1 Approssimazione di funzioni continue

Presentiamo di seguito alcuni teoremi classici sull’approssimazione delle funzioni continue mediante polinomi. Il primo afferma che i polinomi sono densi nello spazio delle funzioni continue: ogni funzione continua su un intervallo [a,b] può essere approssimata con precisione arbitraria da un polinomio.

ImportanteTeorema di approssimazione di Weierstrass (Weierstraß, 1885)

Sia f:[a,b]\to\mathbb{C} una funzione continua.

Allora per ogni \varepsilon>0 esiste un polinomio p(x) tale che |f(x)-p(x)| \leq \varepsilon,\qquad \forall x\in[a,b]

Nel caso di funzioni a valori reali Bernstein da una dimostrazione costruttiva, ovvero da un algoritmo per la costruzione del polinomio approssimante.

ImportanteTeorema di approssimazione di Bernstein (Sergej Natanovič Bernštejn, 1911)

Sia f:[0,1]\to\mathbb{R} una funzione continua e per n\in\mathbb{N} l’n-esimo polinomio di Bernstein sia definito come

B_n(x,f) = \sum_{k=0}^n{n\choose k}x^k(1-x)^{n-k}f\left(\dfrac{k}{n}\right)

allora la successione di polinomi B_n(x,f) converge uniformemente a f(x) ovvero per ogni \varepsilon>0 esiste un m\in\mathbb{N} tale che per ogni n\geq m vale

|f(x)-B_n(x,f)| \leq \varepsilon,\qquad \forall x\in[0,1]

Nel teorema di Bernstein il polinomio ha una costruzione ad hoc; nel caso dei polinomi interpolanti, le cose non vanno così bene, come mostra il teorema seguente:

ImportanteTeorema di interpolazione di Faber (Georg Faber, 1914)

Data una qualunque successione di nodi in un intervallo chiuso [a,b] esiste sempre una funzione continua f:[a,b]\to\mathbb{R} che genera una sequenza di polinomi \{p_n(x)\}_{n\in\mathbb{N}} di interpolazione che non convergono uniformemente a f(x) in [a,b]. Ovvero

\lim_{n\to\infty} \left(\max_{x\in[a,b]}|f(x)-p_n(x)|\right) \neq 0

G.Faber, Über die interpolatorische Darstellung stetiger Funktionen, Jahresber. Deut. Math. Verein. 23 (1914), 192-210.

Per ottenere il fenomeno descritto dal teorema di Faber occorre costruire funzioni particolari. Se invece la funzione è sufficientemente regolare, per esempio se appartiene a C^1[a,b] (cioè è derivabile), il comportamento è migliore. Per funzioni molto regolari si può ottenere una stima precisa dell’errore di interpolazione:

ImportanteErrore di interpolazione (Augustin-Louis Cauchy, 1840)

Sia f\in C^{n+1}[a,b] e siano \{x_0,x_1,\ldots,x_n\}\subset[a,b] punti distinti. Allora il polinomio interpolante p_n(x) (ovvero p_n(x_k)=f(x_k)) soddisfa

f(x)-p_n(x) = f^{(n+1)}(\zeta) \dfrac{(x-x_0)(x-x_1)\cdots(x-x_n)}{(n+1)!},

dove \zeta\in I(x,x_0,x_1,\ldots,x_n) ed I(x,x_0,x_1,\ldots,x_n) è il più piccolo intervallo aperto contenente i punti x, x_0, x_1,\ldots,x_n.

Per migliorare l’interpolazione non abbiamo il controllo di f^{(n+1)}(\zeta) ma possiamo cercare di controllare il termine (x-x_0)(x-x_1)\cdots(x-x_n) scegliendo opportunamente i nodi di interpolazione. Ci sono distribuzioni di nodi che minimizzano \max_{x\in I(x_0,x_1,\ldots,x_n)}|(x-x_0)(x-x_1)\cdots(x-x_n)| e sono i nodi di Chebyshev.

ImportanteSuccessioni di nodi

Dato l’intervallo [a,b] è possibile definire le sequenti successioni di nodi

  • nodi equispaziati x_k=a+\dfrac{k}{n}(b-a),\qquad k=0,1,\ldots,n

  • nodi di Chebyshev1 x_k=\dfrac{a+b}{2}+\dfrac{b-a}{2}\cos\left(\pi\dfrac{2k+1}{2n+2}\right)\qquad k=0,1,\ldots,n

  • nodi di Chebyshev-Lobatto x_k=\dfrac{a+b}{2}+\dfrac{b-a}{2}\cos\left(\dfrac{k\,\pi}{n}\right)\qquad k=0,1,\ldots,n

i nodi di Chebyshev (e Chebyshev-Lobatto) si possono interpretare come la proiezioni di nodi equispaziati sulla semi-circonferenza sull’asse delle x.

Per entrambe le distribuzioni si sa stimare la costante di Lebesgue2, che cresce solo logaritmicamente invece che esponenzialmente come nel caso equispaziato:

\begin{aligned} \Lambda_n &< \dfrac{2}{\pi}\left(\ln n + \gamma + \ln\dfrac{8}{\pi}\right) + \dfrac{\pi}{72n^2} && \text{[Chebyshev-Lobatto]}\\[4pt] \Lambda_n &< \dfrac{2}{\pi}\left(\ln(n+1) + \gamma + \ln\dfrac{8}{\pi}\right) + \dfrac{\pi}{72(n+1)^2} && \text{[Chebyshev]} \end{aligned} \tag{9.1}

dove \gamma è la costante di Eulero-Mascheroni. Confrontando con il limite inferiore di Natanson3 si vede che questi nodi sono ottimali a meno di una costante additiva, e per 7.2 l’errore di interpolazione resta entro un fattore O(\ln n) dalla miglior approssimazione.

Scegliendo i nodi di Chebyshev per una funzione C^1[a,b] abbiamo il seguente risultato

ImportanteSecondo teorema di Bernstein

Per ogni funzione f\in C^1[a,b] allora se p_n(x) è il polinomio interpolante per gli n+1 nodi di Chebyshev allora l’errore E_n = \max_{x\in[a,b]} |f(x)-p_n(x)| soddisfa

\lim_{n\to\infty} E_n = 0

ovvero la successione di polinomi converge uniformemente a f(x).

9.2 Controesempio di Runge

Anche se la funzione è molto regolare (ad esempio C^\infty[a,b]) sono necessari i nodi di Chebyshev per avere la convergenza. Il seguente controesempio lo trovate in

  • Carl Runge4, Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten, Zeitschrift für Mathematik und Physik, 1901, vol. 46, pages 224-243

Innanzitutto costruiamo la funzione da interpolare f(x) = 1/(1+x^2):

rfun = function ( x ) { 1 / ( 1 + x ^ 2 ) }

e salviamo un certo numero di punti per plottare la funzione

x = seq(from = -5, to = 5, by = 0.01)

plotta la funzione da interpolare

y = rfun( x );

# salva il plot in una funzione per riusarla piu avanti
plot_runge = function() {
  plot(
    x,y,type="l",lwd=2,col=4,
    main="Funzione di Runge",
    xlim=c(-5,5), ylim=c(-1,4),
    xlab="x", ylab="y", asp=1
  )
  # Turn on grid
  grid(
    lty = 2,           # Grid line type
    col = "lightgray", # Grid line color
    lwd = 1
  )
}
plot_runge()

costruiamo un primo polinomio interpolante

library(polynom)

# punti di interpolazione
x1 = seq(from = -5, to = 5, by = 2)
y1 = rfun( x1 )

# costruzione del polinomio interopolante
poly1 = poly.calc(x1, y1)

# polinomio interpolante come funzione
fun1 = as.function(poly1)

# valutazione del polinomio
yy1 = fun1(x)

# plotta funzione di Runge
plot_runge()

# punti di interpolazione
points(x1, y1)
lines(x, yy1, type = "l", lty = 1, col=6)

ne aggiungiamo un secondo

library(polynom)

# punti di interpolazione
x2 = seq(from = -5, to = 5, by = 1)
y2 = rfun( x2 )

# costruzione del polinomio interopolante
poly2 = poly.calc(x2, y2)

# polinomio interpolante come funzione
fun2 = as.function(poly2)

# valutazione del polinomio
yy2 = fun2(x)

# plotta funzione di Runge
plot_runge()

# punti di interpolazione
points(x2, y2)
lines(x, yy1, type = "l", lty = 1, col=6)
lines(x, yy2, type = "l", lty = 1, col=7)

aggiunge una serie di polinomi di grado crescente

library(polynom)

# plotta funzione di Runge
plot_runge()

kk = 1;
for ( delta in c(2,1,0.7,0.5) ) {
  xk    = seq(from = -5, to = 5, by = delta)
  yk    = rfun( xk )
  polyk = poly.calc(xk, yk)
  funk  = as.function(polyk)
  yyk   = funk(x)
  lines(x, yyk, type = "l", lty = 1, col=6+kk)
  kk = kk+1
}

si vede chiaramente che man mano che aumentano i punti di interpolazione i polinomi approssimano sempre peggio la funzione f(x) = 1/(1+x^2). Ma usando i nodi di Chebyshev si vede che le cose vanno meglio:

library(polynom)

# plotta funzione di Runge
plot_runge()

kk = 1;
for ( n in c(4,6,8,10,12) ) {
  tk    = seq(from = 1, to = n+1, by = 1)/(n+2)
  xk    = 5*cos(pi*tk)
  yk    = rfun( xk )
  polyk = poly.calc(xk, yk)
  funk  = as.function(polyk)
  yyk   = funk(x)
  lines(x, yyk, type = "l", lty = 1, col=6+kk)
  kk = kk+1
}

ma solo fino a un certo punto. Se il grado del polinomio diventa troppo elevato, gli errori in virgola mobile si accumulano e possono rendere del tutto inattendibile la valutazione:

library(polynom)

# plotta funzione di Runge
plot_runge()

kk = 1;
for ( n in c(12,15,17,20) ) {
  tk    = seq(from = 1, to = n+1, by = 1)/(n+2)
  xk    = 5*cos(pi*tk)
  yk    = rfun( xk )
  polyk = poly.calc(xk, yk)
  funk  = as.function(polyk)
  yyk   = funk(x)
  lines(x, yyk, type = "l", lwd=2, lty = 1, col=6+kk)
  kk = kk+1
}
# Add a legend
legend(4, 3, legend=c("n=12", "n=15", "n=17", "n=20"),
       col=c(7,8,9,10), lty=1, cex=0.8)

9.3 Conclusioni

  • I polinomi sono densi nelle funzioni continue ma approssimare una funzione continua con polinomi interpolanti non è facile.

  • Anche se la funzione è regolare i nodi di interpolazione vanno scelti con cura per ridurre l’errore (vedi teorema di Cauchy)

  • Usando i nodi di Chebyshev, per le funzioni regolari si ottiene teoricamente la convergenza uniforme del polinomio interpolante alla funzione da approssimare.

  • In ogni caso la valutazione di un polinomio è instabile e sopra gradi moderatamente alti (grado 10) non si dovrebbe usare un polinomio per approssimare una funzione.

    • Si possono usare polinomi a tratti (spline) di grado basso per approssiamare funzioni continue

    • Per migliorare la valutazione di un polinomio di grado si possono usare polinomi speciali (polinomi ortogonali con le loro ricorrenze)

  1. Pafnutij L’vovič Čebyšëv (1821-1894)↩︎

  2. Henri Léon Lebesgue (1875-1941)↩︎

  3. Isidor Pavlovič Natanson (1906-1964)↩︎

  4. Carl David Tolmé Runge (1856-1927)↩︎