Approssimazione e interpolazione con polinomi algebrici

Alvise Sommariva

Università degli Studi di Padova Dipartimento di Matematica

Migliore approssimazione con polinomi algebrici in (C([a, b]), ∥ · ∥_{∞})

7 marzo 2017 Indichiamo con

ℙ_{n} =< 1, x, x^{2}, …, x^{n} >

lo spazio vettoriale dei polinomi algebrici univariati di grado n, aventi come noto dimensione N_{n} = n + 1. Risulta evidente che se S_{n} ≡ ℙ_{n} si ha

S_{0} ⊂ S_{1} ⊂ … ⊂ S_{n} ⊂ …

Inoltre se (C([a, b]), ∥ · ∥_{∞}) è lo spazio normato delle continue C([a, b]) in un intervallo chiuso e limitato [a, b], dotato della norma infinito

∥f ∥_{∞} = max_{x∈[a,b]}|f (x)|

si ha che ∪_{n∈ℕ}ℙ_{n} ⊆ (C([a, b]), ∥ · ∥_{∞}).

Definizione (Densità (in spazi normati))

Un insieme S si dice denso in uno spazio normato X se per ogni x ∈ X , fissato ϵ > 0, esiste s ∈ S tale che ∥x − s∥ < ϵ.

Più in generale, in spazi topologici,

Definizione (Densità (in spazi topologici))

Un insieme S si dice denso in uno spazio topologico X , se per ogni x ∈ X esiste una successione {s_{n}} di elementi di S tale che s_{n} → x. .

Definizione (Densità (in spazi topologici))

Sia X uno spazio topologico. Un insieme S ⊆ X si dice denso in X , se la chiusura di S è X (per la topologia di X ) .

Alvise Sommariva  Appross. e interpolazione con polinomi algebrici  3/ 50

Teorema

Sia (X , ∥ · ∥) uno spazio funzionale normato e

∅ ≠ S_{0} ⊂ S_{1} ⊂ … ⊂ S_{n} ⊂ …

una successione crescente di sottoinsiemi di X . Allora

E_{n}(f ) ≡ inf_{p_{n}∈S_{n}} ∥p_{n} − f ∥ →^{n} 0

se e solo se ∪_{n∈ℕ}S_{n} è denso in X .

Dimostrazione.

⇒ Supponiamo sia E_{n}(f ) = inf_{p_{n}∈S_{n}} ∥p_{n} − f ∥ →^{n} 0 per ogni f ∈ X . Sia f ∈ X e sia fissato un arbitrario ϵ > 0.

Allora per un qualche n si ha E_{n}(f )<ϵ, e quindi dalle proprietà dell’estremo inferiore esiste p_{n} ∈ S_{n} tale che ∥p_{n} − f ∥≤ϵ.

Di conseguenza per ogni ϵ > 0 esiste un certo p ∈ ∪_{n∈ℕ}S_{n} tale che ∥p − f ∥ ≤ ϵ, cioè ∪_{n∈ℕ}S_{n} è denso in X .

⇐ Viceversa sia ∪_{n∈ℕ}S_{n} denso in X ed f ∈ X . Essendo

S_{0} ⊂ S_{1} ⊂ … ⊂ S_{n} ⊂ …

la successione {E_{n}(f )}_{n} è decrescente e quindi ammette limite. Essendo ∪_{n∈ℕ}S_{n} denso in X , per ogni ϵ > 0 esiste p ∈ ∪_{n∈ℕ}S_{n} tale che ∥f − p∥ ≤ ϵ. Se in particolare p ∈ S_{n^{∗}} allora per n ≥ n^{∗} si ha E_{n}(f ) ≤ ϵ. Quindi per ϵ > 0 arbitrario, essendo la successione {E_{n}(f )} decrescente, si ha lim_{n} E_{n}(f ) ≤ ϵ per ogni ϵ > 0 cioè

E_{n}(f ) ≡ inf_{p_{n}∈S_{n}} ∥p_{n} − f ∥ →^{n} 0.
△
Alvise Sommariva  Appross. e interpolazione con polinomi algebrici  6/ 50

Nota.

Osserviamo che essendo S_{n} ≠ ∅, necessariamente esiste p_{n}^{∗} ∈ S_{n} e quindi se M = ∥p_{n}^{∗} − f ∥ abbiamo che 0 ≤ ∥p_{n} − f ∥ ≤ M per ogni p_{n} ∈ S_{n}. Sia A = {∥p_{n} − f ∥ : p_{n} ∈ S_{n}}.

Il teor. dell’estremo inferiore asserisce che un insieme A ⊂ ℝ non vuoto e limitato inferiormente ha estremo inferiore.

Di conseguenza A è inferiormente limitato e quindi esiste

E_{n}(f ) ≡ inf_{p_{n}∈S_{n}} ∥p_{n} − f ∥.

Teorema dell’approssimazione di Weierstrass

Ci interessa vedere come questo esempio sia applicabile al caso dei polinomi algebrici e quindi necessita disporre di un risultato di densità.

Sussiste il seguente teorema di Approssimazione di Weierstrass [6, p.107].

Teorema (Weierstrass, 1885, (ma anche Runge 1885))

Ogni funzione continua in [a, b] compatto è limite uniforme di una successione di polinomi.

Tale Teorema è equivalente a dire che ∪_{n∈ℕ}ℙ_{n} è denso in (C([a, b]), ∥ · ∥_{∞}) e quindi dal Teorema 0.1 deduciamo che se f ∈ C([a, b]) allora E_{n}(f ) ≡ inf_{p_{n}∈ℙ_{n}} ∥p_{n} − f ∥ →^{n} 0.

Miriamo a mostrare l’esistenza di un elemento di miglior appross., sotto particolari condizioni. Osserviamo che (cf. [7, p.151])

Teorema (Weierstrass (1860) (ma anche Bolzano (1830)))

Una funzione continua f : S → ℝ, con S sottinsieme compatto di uno spazio normato, ha massimo e minimo, cioè esistono xmin ed xmax tali che

f (xmin) ≤ f (x) ≤ f (xmax)

per ogni x ∈ S.

Nota.

Il teorema fu scoperto da Bolzano e in seguito riscoperto da Weierstrass.

Non lo si confonda con il teorema di Bolzano-Weierstrass.

Teorema (Bolzano-Weierstrass)

In uno spazio euclideo finito dimensionale, ogni successione reale limitata ammette almeno una sottosuccessione convergente.

Inoltre (cf. [7, p.150])

Lemma

In uno spazio normato X di dimensione finita, un suo sottinsieme S è compatto se e solo se chiuso e limitato.

Ricordiamo che

Definizione

Un sottoinsieme S di uno spazio metrico X si dice compatto se e solo se ogni successione di punti possiede una sottosuccessione che converge ad un punto di S.

Lemma

Sia X uno spazio normato e sia f ∈ X . Sia S ⊂ X aperto e d(f , ·) = ∥f − ·∥. La funzione d(f , ·) è continua in ogni punto di S.

Dimostrazione.

Osserviamo che se x, y ∈ X allora

|∥x∥ − ∥y∥| ≤ ∥x − y∥.

Infatti, siano x, y ∈ X , e vista la loro arbitrarietà non è restrittivo supporre ∥x∥ ≥ ∥y∥. Dalla disuguaglianza triangolare,

∥x∥ = ∥(x − y) + y∥ ≤ ∥x − y∥ + ∥y∥
⇔ 0 ≤ ∥x∥ − ∥y∥ ≤ ∥x − y∥ ⇔ |∥x∥ − ∥y∥| ≤ ∥x − y∥.
△

Alvise Sommariva  Appross. e interpolazione con polinomi algebrici  12/ 50

Intendiamo mostrare che la funzione d(f , ·) = ∥f − ·∥ è continua nell’aperto S cioè

▶ per ogni ϵ > 0, esiste δ(ϵ) > 0, tale che se |x − y| ≤ δ(ϵ), x, y ∈ S, allora ∥d(f , x) − d(f , y)∥ ≤ ϵ.

Fissato ϵ > 0, x ∈ S, sia δ(ϵ) = ϵ. Allora se y ∈ S, ∥x − y∥ ≤ ϵ, visto che |∥x_{1}∥ − ∥x_{2}∥| ≤ ∥x_{1} − x_{2}∥ pure per x_{1} = f − x, x_{2} = f − y,

|d(f , x) − d(f , y)| = |∥f − x∥ − ∥f − y∥|
≤ ∥(f − x) − (f − y)∥ = ∥x − y∥
≤ ϵ

e quindi la funzione d(f , ·) è continua in x ∈ S. △

Alvise Sommariva  Appross. e interpolazione con polinomi algebrici  13/ 50

Il lemma precedente serve a mostrare la seguente proposizione.

Teorema

Sia S un sottospazio vettoriale di uno spazio normato X . Si supponga che

▶ S sia di dimensione finita, ▶ f sia un certo elemento di X .

Allora esiste s^{∗} ∈ S, detto di miglior approssimazione di f in S, tale che

∥f − s^{∗}∥ = min_{s∈S}∥f − s∥.

Dimostrazione.

▶ L’elemento 0 dello spazio normato X appartiene certamente in ogni suo sottospazio, e quindi pure in S. Così sicuramente

E(f ) ≡ inf_{p∈S} ∥p − f ∥ ≤ ∥f − 0∥ = ∥f ∥.

▶ La funzione d(f , ·) = ∥f − ·∥ è continua in S. ▶ Essendo lo spazio S di dimensione finita, la palla

B_{S}(f , ∥f ∥) = {p ∈ S : ∥p − f ∥ ≤ ∥f ∥} centrata in f e avente raggio ∥f ∥ essendo chiusa (per la topologia indotta!) e limitata è pure compatta.

Quindi per il teorema di Weierstrass la funzione d(f , ·) ha minimo p^{∗} in B_{S}(f , ∥f ∥) e di conseguenza in E(f ) = ∥f − p^{∗}∥. △

Teorema di equioscillazione

Corollario

Per ogni k ≥ 0, fissata f ∈ (C([a, b]), ∥ · ∥_{∞}) esiste un polinomio p_{k}^{∗} ∈ ℙ_{k} di miglior approssimazione.

Riguardo l’unicità di tale p_{k}^{∗} (cf.[2], p.112, [4], [6, p.149], [3, p.3]).

Teorema (di equioscillazione (Chebyshev, ≈ 1850))

Sia f ∈ C([a, b]) con [a, b] limitato e n ∈ ℕ. Allora esiste un unico elemento p_{n}^{∗} ∈ ℙ_{n} di miglior approssimazione. Si caratterizza come segue. Esistono n + 2 elementi a ≤ x_{0} < … < x_{n+1} ≤ b tali che

f (x_{j}) − p_{n}^{∗}(x_{j}) = σ(−1)^{j}∥f − p_{n}∥_{∞}, j = 0, 1, …, n + 1

con σ = 1 oppure σ = −1.

Teorema di equioscillazione

Figura : Equioscillazione: in nero sin(x) in [0, 10], in rosso il polinomio di miglior approssimazione p_{5}^{∗} di grado 5, in verde le funzioni f ± E_{n}(f ). Si notino le 7 intersezioni dell’approssimante p_{5}^{∗} con il grafico di f ± E_{n}(f ).

Algoritmo di Remez

Il calcolo del polinomio p^{∗} ∈ ℙ_{n} di miglior approssimazione di una funzione f ∈ C([a, b]) non è semplice.

▶ L’algoritmo di Remez, scoperto nel 1934, ne permette una sua determinazione ma la descrizione dello stesso non è semplice (cf. [3, p.12]) .

▶ Una sua buona implementazione la si ha in ambiente Matlab cui siano state aggiunte le routines di Chebfun (cf. [5]). Il relativo comando si chiama remez.

Alcuni esempi

Digitando sulla shell di Matlab

>>deg =10;
>> x=chebfun ( ’ x ’ ,[−5 5 ] ) ;
>> f=1./(1+x . ˆ 2 ) ;

>>[p , err]= remez ( f , deg ) ;

otteniamo in p il polinomio di miglior approssimazione di grado 10 della funzione di Runge 1/(1 + x^{2}) nell’intervallo [−5, 5] (come stabilito dalla seconda riga).

Grado Errore 1/(1 + x^{2}) Errore |x − 4| Errore sin (x)
5  2.17e − 01  1.61e − 01  1.08e − 01
10  6.59e − 02  8.40e − 02  7.03e − 04
15  2.98e − 02  5.68e − 02  2.31e − 08
20  9.04e − 03  4.28e − 02  6.69e − 12
25  4.08e − 03  3.43e − 02  2.33e − 15
30  1.24e − 03  2.86e − 02  −
35  5.60e − 04  2.46e − 02  −
40  1.70e − 04  2.15e − 02  −
45  7.68e − 05  1.91e − 02  −
50  2.33e − 05  1.72e − 02  −
55  1.05e − 05  1.56e − 02  −
60  3.20e − 06  1.43e − 02  −
65  1.44e − 06  1.32e − 02  −
70  4.38e − 07  1.23e − 02  −
75  1.98e − 07  1.14e − 02  −
80  6.01e − 08  1.07e − 02  −
85  2.71e − 08  1.01e − 02  −
90  8.24e − 09  9.51e − 03  −
95  3.72e − 09  9.00e − 03  −
100  1.13e − 09  8.55e − 03  −

Tabella : Algoritmo di Remez. Errore assoluto di miglior approssimazione relativamente a 1/(1 + x^{2}), |x − 4| e sin (x) in [−5, 5].

Dalla Tabella, risulta chiaro che la miglior approssimante polinomiale a paritá di grado approssima meglio la funzione di Runge rispetto al |x − 4| e viene da chiedersi se esistano delle stime sull’errore compiuto dalla migliore approssimante.

Queste vengono fornite dai seguenti teoremi di Jackson [4, p.142], [1, p.224].

Modulo di continuità

Definizione (Modulo di continuità)

Sia f : [a, b] → ℝ. La quantità

ω(f , δ) := sup_{x,y∈[a,b], |x−y|≤δ}|f (x) − f (y)|

si chiama modulo di continuità di f .

Figura : Fissato un certo x si calcola il massimo di |f (x_{1}) − f (x_{2})| con x_{1}, x_{2} ∈ [x − d, x + d]. Quindi si calcola l’estremo superiore di questa quantità al variare di x ∈ [a, b], ottenendo ω(f , d).

Nota.

Se la funzione f : [a, b] → ℝ è L-lipschitziana, cioè

|f (x) − f (y)| ≤ L|x − y|, x, y ∈ [a, b]

allora

ω(f , δ) := sup_{x,y∈[a,b], |x−y|≤δ}|f (x) − f (y)|
≤ sup_{x,y∈[a,b], |x−y|≤δ}L|x − y| = Lδ.

Non è difficile mostrare che se f è L-lipschitziana in [a, b] allora è pure continua in [a, b].

Nota.

Sia [a, b] chiuso e limitato. Se la funzione f : [a, b] → ℝ è tale che f ∈ C^{(1)}([a, b]) allora è L-lipschitziana con L = max_{x∈[a,b]} |f^{(1)}(x)|.

Modulo di continuità

Nota.

Se la funzione f : (a, b) → ℝ è α-holderiana (α ∈ (0, 1)), cioè

|f (x) − f (y)| ≤ L|x − y|^{α}, x, y ∈ [a, b]

allora

ω(f , δ) := sup_{x,y∈[a,b], |x−y|≤δ}|f (x) − f (y)|
≤ sup_{x,y∈[a,b], |x−y|≤δ}L|x − y|^{α} = Lδ^{α}.
Alvise Sommariva  Appross. e interpolazione con polinomi algebrici  24/ 50

Teorema (Jackson, 1912)

Per ogni n ≥ 1 e per ogni f ∈ C([a, b]) esiste una costante M indipendente da n, a, b tale che

E_{n}(f ) = inf_{p∈ℙ_{n}} ∥f − p∥_{∞} ≤ M ω (f , \frac{b − a}{n})

dove ω(f , ·) è il modulo di continuità della funzione f su [a,b]

Corollario

Se f : [a, b] → ℝ è L-lipschitziana, allora esiste una costante M^{∗} indipendente da n, a, b tale che

E_{n}(f ) = inf_{p∈ℙ_{n}} ∥f − p∥_{∞} ≤ M^{∗} \frac{b − a}{n}.

Teorema (Jackson)

Se f ∈ C^{p}([a, b]), p ≥ 0 si ha per ogni n > p

inf_{p∈ℙ_{n}} ∥f − p∥_{∞} ≤ M^{p+1} \frac{(b − a)^{p}}{n · (n − 1) … (n − p + 1)}ω (f^{(p)}, \frac{b − a}{n − p}).

Corollario

Se f^{(p)} : [a, b] → ℝ, p > 0 è α-holderiana (di costante L), allora esiste una costante M indipendente da n, a, b tale che

E_{n}(f ) ≤ M^{p+1} \frac{(b − a)^{p}}{n · (n − 1) … (n − p + 1)} · L · (\frac{b − a}{n − p})^{α} .

Alvise Sommariva  Appross. e interpolazione con polinomi algebrici  26/ 50

Teorema (Jackson)

Se f ∈ C^{k}([a, b]), ed f^{(k)} è α holderiana, cioè

|f^{(k)}(x) − f^{(k)}(y)| ≤ M|x − y|^{α}, x, y ∈ [a, b]

per qualche M > 0, 0 < α ≤ 1. Allora esiste una costante d_{k} indipendente da f e n per cui

inf_{p∈ℙ_{n}} ∥f − p∥_{∞} ≤ \frac{M d_{k}}{n^{k+α}}, n ≥ 1.

Ricordiamo che (cf. [6, p.12]).

Definizione

Sia Ω ⊆ ℂ una regione del piano complesso e sia f : Ω → ℂ. Se z_{0} ∈ Ω, f si dice analitica in z_{0} se ha una rappresentazione della forma

f (z) = ∑_{n=0}^{∞}a_{n}(z − z_{0})^{n}

valida in qualche intorno di z_{0}.

Definizione

Una funzione si dice analitica in Ω ⊆ ℂ se e solo se è analitica in ogni punto di Ω.

Alcuni esempi di funzioni analitiche nel piano complesso sono i polinomi di grado arbitrario, le funzioni sin (z), cos (z), exp (z). La funzione di Runge 1/(1 + z^{2}) è analitica in ogni regione non contenente −i e +i.

Teorema

Se f : [a, b] → ℝ è analitica in un aperto Ω del piano complesso contenente [a, b], allora esiste θ ∈ (0, 1) tale che

E_{n}(f ) = ∥p_{n}^{∗} − f ∥ = O(θ^{n}).

Teorema (Bernstein)

Sia f : [a, b] → ℝ. Allora

lim_{n→∞}(E_{n}(f ))^{1/n} = 0

se e solo se f è intera (cioè si può scegliere Ω = ℂ).

Nota.

Si osservi che nel precedente teorema si dice che se la funzione f è intera allora la miglior approssimante ha asintoticamente un errore inferiore rispetto al caso in cui f sia analitica in un aperto strettamente contenuto nel piano complesso.

Nota. (Convergenza della funzione di Runge)

Per quanto visto, la funzione di Runge f (x) = 1/(1 + x^{2}), con x ∈ [−5, 5] è analitica in un aperto Ω del piano complesso contenente [−5, 5] (si noti che possiede i soli poli in −i e i) e una verifica empirica con i dati della tabella stabilisce che E_{n}(f ) = O(θ^{n}) con θ ≈ 0.814.

Nota. (Convergenza della funzione sin)

La convergenza del polinomio di migliore approssimazione nel caso di f (x) = sin (x), con x ∈ [−5, 5] è molto rapida. In effetti sin(z) è intera.

Nota. (Convergenza della funzione f (x) = |x − 4|)

Da ||x − 4| − |y − 4|| ≤ |x − y| e dal fatto che per x ≤ 4 si ha f (x) = 4 − x mentre per x > 4 si ha f (x) = x − 4 si vede facilmente che per δ ≤ 5

ω(f , δ) := sup_{x,y∈[−5,5], |x−y|≤δ}|f (x) − f (y)| = δ

Così, dal Teorema di Jackson, per qualche M,

E_{n}(f ) = ω (f , \frac{b − a}{n}) = M \frac{b − a}{n} = \frac{10M}{n} .

In effetti, un confronto coi dati stabilisce che posti a = −5, b = 5

inf_{p∈ℙ_{n}} ∥f − p∥_{∞} ≈ 0.085 · \frac{10}{n} = \frac{0.85}{n}

e quindi una convergenza lenta di E_{n}(f ) a 0, rispetto E_{n}(f ) ≈ 0.814^{n} dell’esempio di Runge.

Alvise Sommariva  Appross. e interpolazione con polinomi algebrici  32/ 50

Alcune note sui polinomi di Chebyshev (∼ 1850)

Consideriamo la funzione

T_{n}(x) = cos(n arccos(x))

con x ∈ [−1, 1] (cf. [1, p.211]). A priori, in virtù della presenza del coseno, T_{n} non sembra essere un polinomio. In realtà si vede subito che T_{0}(x) = cos(0 arccos(x)) = 1, T_{1}(x) = cos(1 arccos(x)) = x. Dalle formule trigonometriche di addizione e sottrazione

cos((n + 1) θ) = (cos(n θ)) · cos(θ) − (sin(n θ)) · sin(θ)
cos((n − 1) θ) = (cos(n θ)) · cos(θ) + (sin(n θ)) · sin(θ)

sommando membro a membro le due uguaglianze abbiamo

cos((n + 1) θ) + cos((n − 1) θ) = 2 (cos(n θ)) · cos(θ)

Alcune note sui polinomi di Chebyshev

Posto θ = arccos(x) si ha

T_{n+1}(x) = 2x T_{n}(x) − T_{n−1}(x)

poiché

T_{n+1}(x) + T_{n−1}(x) = 2 (cos(n θ)) · cos(θ) = 2T_{n}(x)x

Di conseguenza, per ricorrenza, essendo ▶ T_{0}(x) = 1, ▶ T_{1}(x) = x,

si deduce che T_{n} è un polinomio, detto di Chebyshev, di grado n e che inoltre per n > 0 è del tipo T_{n}(x) = 2^{n−1} x^{n} + · · ·.

Alcune note sui polinomi di Chebyshev

Gli zeri x_{k} del polinomio di Chebyshev sono i punti per cui cos(n arccos(x_{k})) = 0, per cui

n arccos(x_{k}) = \frac{π}{2} + kπ = \frac{(2k + 1)π}{2}
arccos(x_{k}) = \frac{(2k + 1)π}{2n}

x_{k} = cos(arccos(x_{k})) = cos (\frac{(2k + 1)π}{2n}), k = 0, …, n − 1.

Notiamo che gli zeri del polinomio di Chebyshev sono ▶ esattamente n, ▶ distinti, ▶ nell’intervallo (−1, 1).

Costanti di Lebesgue

Sia f ∈ C([a, b]), con [a, b] intervallo chiuso e limitato e si consideri il polinomio p_{n} ∈ ℙ_{n} che interpola le coppie (x_{k}, f (x_{k})) (per k = 0, …, n, x_{k} a due a due distinti). Si ponga per semplicità di notazione f_{k} := f (x_{k}). Come è noto, indicato con L_{k} il k-simo polinomio di Lagrange, si ha

p_{n}(x) = ∑_{k=0}^{n}f_{k}L_{k}(x)

con

L_{k}(x) = ∏_{j≠k}(x − x_{j})/ ∏_{j≠k}(x_{k} − x_{j}).

Supponiamo che i valori di f_{k} siano perturbati (per esempio per via dell’arrotondamento del numero) e sostituiti con f̃_{k}.

Costanti di Lebesgue

Quindi il polinomio interpolatore è p̃_{n}(x) = ∑_{k=0}^{n} f̃_{k}L_{k}(x). Essendo p_{n}(x) = ∑_{k=0}^{n} f_{k}L_{k}(x) abbiamo che

p_{n}(x) − p̃_{n}(x) = ∑_{k=0}^{n}(f_{k} − f̃_{k})L_{k}(x)

da cui |p_{n}(x) − p̃_{n}(x)| ≤ ∑_{k=0}^{n}|f_{k} − f̃_{k}||L_{k}(x)| ≤ (max_{k}|f_{k} − f̃_{k}|) ∑_{k=0}^{n}|L_{k}(x)| e

max_{x∈[a,b]}|p_{n}(x) − p̃_{n}(x)| ≤ (max_{k}|f_{k} − f̃_{k}|) max_{x∈[a,b]} ∑_{k=0}^{n}|L_{k}(x)|

Costanti di Lebesgue

Quindi posto

Λ_{n} = max_{x∈[a,b]} ∑_{k=0}^{n}|L_{k}(x)|

da ∥p_{n}−p̃_{n}∥_{∞} := max_{x∈[a,b]}|p_{n}(x)−p̃_{n}(x)| ≤ (max_{k}|f_{k} − f̃_{k}|) max_{x∈[a,b]} ∑_{k=0}^{n}|L_{k}(x)| ricaviamo

∥p_{n} − p̃_{n}∥_{∞} ≤ (max_{k}|f_{k} − f̃_{k}|) · Λ_{n}.

Osserviamo che il numero Λ_{n} dipende esclusivamente dai polinomi di Lagrange e quindi esclusivamente dai punti di interpolazione.

Alvise Sommariva  Appross. e interpolazione con polinomi algebrici  38/ 50

Il valore Λ_{n} è nota come costante di Lebesgue (1910) dell’insieme di punti x_{0}, …, x_{n} (cf. [11]). Si vede immediatamente che è un indice di stabilità dell’interpolazione di Lagrange: più è piccola e più l’approssimazione è stabile (cf. [4, p.139-140]).

Ricordiamo che se (X , ∥ · ∥_{X}), (Y , ∥ · ∥_{Y}) sono due spazi normati, A : X → Y è un operatore lineare limitato se e solo se il numero

∥A∥ = sup_{∥x∥≤1}∥Ax∥_{Y} = sup_{x∈X ,x≠0} \frac{∥Ax∥_{Y}}{∥x∥_{X}}

è finito.

Il numero reale ∥A∥ si chiama norma dell’operatore lineare A (cf. [8, p.224]).

Nota.

Essendo, per ogni x̃ ∈ X , x̃ ≠ 0.

∥A∥ = sup_{∥x∥≤1}∥Ax∥_{Y} = sup_{x∈X ,x≠0} \frac{∥Ax∥_{Y}}{∥x∥_{X}}
≥ \frac{∥Ax̃∥_{Y}}{∥x̃∥_{X}}

deduciamo facilmente che ∥A∥ è la più piccola costante C per cui

∥Ax∥_{Y} ≤ C∥x∥_{X}.

per ogni x ∈ X . Si osservi che qualsiasi sia C, l’asserto è banalmente vero per x̃ = 0.

Si può mostrare che se

L_{n} : (C([a, b]), ∞) → (C([a, b]), ∞)

è l’operatore (lineare e limitato) che associa a f ∈ C([a, b]) il suo polinomio di interpolazione p_{n} nei nodi x_{0}, …, x_{n} allora

Λ_{n} = max_{g∈C([a,b]), g≠0} \frac{∥L_{n}(g)∥_{∞}}{∥g∥_{∞}}

cioè la costante di Lebesgue è la norma dell’operatore di interpolazione L_{n} rispetto alla norma ∥ · ∥_{∞}.

Nota.

Si osservi che mentre nella norma di un operatore lineare e limitato è presente un sup, nella definizione precedente si dimostra che effettivamente è un max.

Teorema

Se f ∈ C([a, b]) e p_{n} è il suo polinomio di interpolazione relativo ai punti x_{0}, …, x_{n} si ha

∥f − p_{n}∥_{∞} ≤ (1 + Λ_{n})E_{n}(f )  (1)

dove

E_{n}(f ) = inf_{q_{n}∈P_{n}} ∥f − q_{n}∥_{∞}

è l’errore compiuto dal polinomio di migliore approssimazione uniforme.

Dimostrazione.

Se f ∈ P_{n}, allora f ≡ p_{n} ≡ p_{n}^{∗}, con p_{n}^{∗} elemento di miglior approssimazione e quindi l’asserto è ovvio. Supponiamo quindi che f ∉ P_{n}, cioè f − q_{n} ≠ 0, per ogni q_{n} ∈ P_{n}. Per ogni q_{n} ∈ P_{n}, è L_{n}(q_{n}) = q_{n}, in quanto l’unico polinomio che interpola in n + 1 punti distinti un polinomio di grado n è il polinomio stesso. Inoltre

L_{n}(f − q_{n}) = L_{n}(f ) − L_{n}(q_{n}) = p_{n} − q_{n}.

Poichè f − q_{n} non è la funzione nulla, abbiamo

Λ_{n} = max_{g∈C([a,b]), g≠0} \frac{∥L_{n}(g)∥_{∞}}{∥g∥_{∞}} ≥ \frac{∥L_{n}(f − q_{n})∥_{∞}}{∥f − q_{n}∥_{∞}} = \frac{∥p_{n} − q_{n}∥_{∞}}{∥f − q_{n}∥_{∞}}  (2)

e di conseguenza

∥(p_{n} − q_{n})∥_{∞} ≤ Λ_{n} · ∥f − q_{n}∥_{∞}.  (3)

Alvise Sommariva  Appross. e interpolazione con polinomi algebrici  43/ 50

Costanti di Lebesgue

Dimostrazione.

e di conseguenza

∥(p_{n} − q_{n})∥_{∞} ≤ Λ_{n} · ∥f − q_{n}∥_{∞}.  (4)

Per concludere, osserviamo che per la disuguaglianza triangolare da f − p = (f − q) + (q − p) e (4)

∥f − p_{n}∥_{∞} = ∥(f − q_{n}) + (q_{n} − p_{n})∥_{∞}
≤ ∥f − q_{n}∥_{∞} + ∥q_{n} − p_{n}∥_{∞}
≤ ∥f − q_{n}∥_{∞} + Λ_{n} ∥f − q_{n}∥_{∞}
= (1 + Λ_{n}) ∥f − q_{n}∥_{∞}  (5)
△
Alvise Sommariva  Appross. e interpolazione con polinomi algebrici  44/ 50

Questo teorema è utile, perchè fa capire che se la costante di Lebesgue è piccola allora l’errore compiuto dall’interpolante polinomiale è poco più grande dell’errore di miglior approssimazione uniforme.

Figura : Henri Lebesgue (1875-1941).

Vediamo ora quali sono le stime delle costanti di Lebesgue per alcuni set di n + 1 punti nell’intervallo [−1, 1] (cf. [9]):

▶ punti equispaziati: si dimostra che asintoticamente (Turetskii, 1940)

Λ_{n} ≈ \frac{2^{n+1}}{en log(n)};

▶ punti di Chebyshev: corrispondono a cos (\frac{(2k−1)π}{2(n+1)}) dove k = 1, …, n + 1; si dimostra che asintoticamente

Λ_{n} = \frac{2}{π} (log(n + 1) + γ + log (\frac{8}{π} )) + O (\frac{1}{(n + 1)^{2}})

dove γ ≈ 0.577 è la costante di Eulero-Mascheroni (cf. [10]);

Costanti di Lebesgue

▶ punti di Chebyshev estesi: sono definiti da cos( \frac{(2k−1)π}{2(n+1)}) ; cos( \frac{π}{2(n+1)}) dove k = 1, …, n + 1; si dimostra che asintoticamente Λ_{n} = \frac{2}{π} (log(n + 1) + γ + log (\frac{8}{π} ) − \frac{2}{3})+O (\frac{1}{log(n + 1)});

▶ configurazione ottimale: si dimostra che la minima costante di Lebesgue (non è nota esplicitamente!) vale Λ_{n} = \frac{2}{π} (log(n + 1) + γ + log (\frac{4}{π} )) + O (\frac{log(log(n + 1))}{log(n + 1)})

Alvise Sommariva  Appross. e interpolazione con polinomi algebrici  47/ 50

Costanti di Lebesgue

Usando Matlab, notiamo quanto siano differenti Λ_{n} per n = 5, 10, …, 50.

>> n = ( 5 : 5 : 5 0 ) ’ ; % GRADI .
>> s =(2.ˆ ( n+1) ) . / ( exp ( 1 ) ∗n . ∗ l o g ( n ) ) ; % EQSP .
>> t=(2/ p i ) ∗( l o g ( n+1) + 0.577 + (8/ p i ) ) ; % CHEB.
>> [ s t ]
ans =
2.9258 e+000 3.1291 e+000
3.2720 e+001 3.5150 e+000
5.9352 e+002 3.7536 e+000
1.2877 e+004 3.9267 e+000
3.0679 e+005 4.0626 e+000
7.7425 e+006 4.1746 e+000
2.0316 e+008 4.2698 e+000
5.4825 e+009 4.3526 e+000
1.5112 e+011 4.4259 e+000
4.2351 e+012 4.4915 e+000

>>

Dalla stima precedente tra errore compiuto dall’interpolante rispetto a quello della miglior approssimazione uniforme, si capisce bene, una volta ancora, perchè i nodi di Chebyshev siano da preferire a quelli equispaziati.

Bibliografia

K. Atkinson, Introduction to Numerical Analysis, Wiley, 1989. K. Atkinson e W. Han, Theoretical Numerical Analysis, A Functional Analysis Framework, Springer, 2001. D. Bini, Approssimazione minimax, http://www.dm.unipi.it/∼bini/Didattica/IAN/appunti/approx.pdf V. Comincioli, Analisi Numerica, metodi modelli applicazioni, Mc Graw-Hill, 1990. Chebfun, http://www.mathworks.com/matlabcentral/fileexchange/23972- chebfun P.J. Davis, Interpolation and Approximation, Dover, 1975. D.H. Grieffel, Applied Functional Analysis, Dover, 2002. A.N. Kolmogorov e S.V. Fomin, Introductory real analysis, Dover, 1970. S.J. Smith, Lebesgue constants in polynomial interpolation, Annales Mathematicae et Informaticae, p. 109-123, 33 (2006) http://www.ektf.hu/tanszek/matematika/ami. Wikipedia, (Costante di Eulero Mascheroni), http://it.wikipedia.org/wiki/Costante di Eulero-Mascheroni. Wikipedia, (Lebesgue constant interpolation), http://en.wikipedia.org/wiki/Lebesgue constant (interpolation).