Queste note sono basate sugli appunti fatti con Gianmarco Manzini negli anni 1995-2005

Esempio di Runge

Appunti di calcolo numerico

Autore/Autrice
Affiliazione

Enrico Bertolazzi

University of Trento, Department of Industrial Engineering

Approssimazione di funzioni continue

Diamo di seguito gli enunciati di alcuni teoremi classici sulla approssimazione di funzioni continue tramite polinomi. Il primo teorema ci assicura che i polinomi sono densi nelle funzioni continue. Ovvero che si può approssimare arbitrariamente bene una funzione continua con un (solo) polinomio in un intervallo [a,b].

Teorema di approssimazione di Weierstrass (Weierstraß, 1885)

Sia f:[a,b]\to\Bbb{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.

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

Sia f:[0,1]\to\Bbb{R} una funzione continua e per n\in\Bbb{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\Bbb{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 di polinomi interpolanti le cose non vanno cosi bene come si deduce dal seguente teorema:

Teorema 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\Bbb{R} che genera una sequenza di polinomi \{p_n(x)\}_{n\in\Bbb{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 far fallire l’interpolazione nel teorema di Faber bisogna costruire delle funzioni molto particolari. Gia se la funzione è è abbastanza regolare ad esempio C^1[a,b] (cioè è derivabile) allora le cose vanno meglio. Vediamo che per funzioni molto regolari si può dare una stima molto precisa dell’errore di interpolazione:

Errore 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 polihomio 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 disctribuzioni 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.

Successioni 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 Chebyshev 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.

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

Secondo 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).

Controesempio di Runge

Carl David Tolmé Runge

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

  • Carl Runge, Ü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 Chebichev si vede che le cose 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 fino ad un certo punto. Se aumentiamo troppo il grado del polinomio subentrano gli errori floating poing che si accumulano al punto da rendere totalmente errata 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)

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 teoricamente per funzioni regolari si ha una covergenza 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)