Approssimazione minimax

\|f - p_n^*\|_\infty = \min_{p \in \mathcal{P}_n} \|f - p\|_\infty

f(x_i) - p(x_i) = (-1)^i d_i, \quad i = 0, \dots, n+1

\min_{i = 0, \dots, n+1} |d_i| \le \delta_n^*

Dimostrazione.

Supponiamo senza perdita di generalità che tutti i d_i > 0.

Per assurdo, supponiamo che \min_i |d_i| > \delta_n^*. Ricordiamo che \delta_n^* = \inf_{q \in \mathcal{P}_n} \|f - q\|_\infty. Poiché l’immagine della funzione q \mapsto \|f - q\|_\infty è [\delta_n^*, +\infty), possiamo considerare un polinomio q \in \mathcal{P}_n tale che:

\delta_n^* \le \|f - q\|_\infty < \min_i d_i

Sia s(x) := p(x) - q(x) un polinomio di grado al più n. Valutiamolo nei punti x_i:

\begin{aligned}
s(x_i) &= p(x_i) - q(x_i) \\
&= (f(x_i) - q(x_i)) - (f(x_i) - p(x_i)) \\
&= (f(x_i) - q(x_i)) - (-1)^i d_i
\end{aligned}

Analizziamo il segno di s(x_i) ricordando che \|f - q\|_\infty < d_i per cui valutando in x_i abbiamo che |f(x_i) - q(x_i)| < d_i per ogni i:

• Se i è pari: s(x_i) = (f(x_i) - q(x_i)) - d_i < 0

• Se i è dispari: s(x_i) = (f(x_i) - q(x_i)) + d_i > 0

Quindi s(x) è un polinomio di grado \le n che assume n+2 segni alternati, il che implica che abbia almeno n+1 cambi di segno e quindi almeno n+1 zeri.

L’unico polinomio di grado \le n con n+1 zeri è il polinomio nullo, quindi s \equiv 0. Ma questo è assurdo poiché s(x_i) \neq 0. \square

r(x_i) = (-1)^i d, \quad \text{con } |d| = \|r\|_\infty

Dimostrazione.

Poiché r(x) = f(x) - p(x) è continua su un compatto [a, b], è uniformemente continua. Per cui per d = \|f - p\|_\infty > 0, esiste \eta > 0 tale che \forall x, y \in [a, b] con |x - y| \le \eta si ha |r(x) - r(y)| \le d.

Siano ora x_i e x_{i+1} sono due punti consecutivi in \mathcal A, allora per la proprietà di equioscillazione |r(x_i) - r(x_{i+1})| = 2d e 2d > d quindi usando la contronominale ottenuta dall’uniforme continuità, abbiamo che |x_i - x_{i+1}| > \eta.

Quindi in \mathcal A non possono esserci più di (b-a)/\eta punti, ovvero il numero di punti di equioscillazione è finito. \square

Dimostrazione.

1. Consideriamo due casi:

   • Se f \in \mathcal{P}_n, allora f = p e \|f - p\|_\infty = 0. Il resto è r \equiv 0, che ha infiniti (e quindi \ge n+2) punti di equioscillazione. Viceversa, se r ha \ge n+2 punti di equioscillazione ed è un polinomio di grado \le n, allora r cambia segno n+1 volte, il che implica r \equiv 0.

   • Se f \notin \mathcal{P}_n, allora \delta^* = \|f - p\|_\infty > 0.

     • \boxed{\Leftarrow} Segue direttamente dal Teorema di de la Vallée-Poussin: se esistono n+2 punti x_i tali che r(x_i) = (-1)^i d con |d| = \|r\|_\infty, allora \|f - p\|_\infty = |d| \le \delta^*, quindi \|f - p\|_\infty = \delta^*.

     • \boxed{\Rightarrow} Vedremo questo più avanti.

2. Vediamo l’unicità. Siano p, \tilde{p} \in \mathcal{P}_n due polinomi di migliore approssimazione. Poiché l’insieme dei polinomi di migliore approssimazione è convesso, anche q = (p + \tilde{p}) / 2 è un polinomio di migliore approssimazione. Per quanto dimostrato sopra, q deve avere almeno n+2 punti di equioscillazione.

   Sia y uno di questi punti. Allora:

   \begin{aligned}
   \delta_n^* &= |f(y) - q(y)| \\
   &= \left| \frac{1}{2}(f(y) - p(y)) + \frac{1}{2}(f(y) - \tilde{p}(y)) \right| \\
   &\le \frac{1}{2}|f(y) - p(y)| + \frac{1}{2}|f(y) - \tilde{p}(y)| \\
   &\le \frac{1}{2}\delta_n^* + \frac{1}{2}\delta_n^* = \delta_n^*
   \end{aligned}

   Quindi devono valere tutte uguaglianze, il che implica f(y) - p(y) = f(y) - \tilde{p}(y), ovvero p(y) = \tilde{p}(y).

   Poiché questo vale per ogni punto di equioscillazione y di q, e tali punti sono almeno n+2, i polinomi p e \tilde{p} coincidono su almeno n+2 punti. Essendo di grado \le n, concludiamo che p = \tilde{p}. \square

Dimostrazione.

Sia k il numero di punti di equioscillazione nell’intervallo (a, b), avendo tolto gli estremi vorremmo vedere che k = n.

Supponiamo per assurdo k > n. In ogni punto di equioscillazione interno, la derivata r'(x) deve annullarsi (essendo punti di estremo). Quindi r'(x) ha almeno k > n zeri in (a, b).

Per il teorema di Rolle, la derivata seconda r''(x) avrà almeno k-1 > n-1 zeri in (a, b).

Procedendo per induzione, la derivata (n+1)-esima r^{(n+1)}(x) si annullerebbe in almeno k-n \ge 1 punti in (a, b). Tuttavia, r^{(n+1)}(x) = f^{(n+1)}(x) - p^{(n+1)}(x) = f^{(n+1)}(x), poiché p \in \mathcal{P}_n. Ma per ipotesi f^{(n+1)}(x) \neq 0, il che è un assurdo. \square

Dimostrazione. Vogliamo dimostrare che

\forall \varepsilon > 0, \exists \bar{n} \text{ t.c. } \forall n > \bar{n}, \delta_n^* \le \varepsilon

Dato \varepsilon > 0, per il teorema di Weierstrass esiste m \in \mathbb{N} e q_m \in \mathcal{P}_m tale che \|f - q_m\|_\infty \le \varepsilon.

Inoltre sappiamo che dato m esiste un unico p_m^* polinomio di migliore approssimazione di grado m (per unicità), tale che \delta_m^* = \|f - p_m^*\|_\infty, allora essendo p_m^* il polinomio di migliore approssimazione di grado m:

\delta_m^* = \|f - p_m^*\|_\infty \le \|f - q_m\|_\infty \le \varepsilon

Per la monotonia di (\delta_n^*)_n ne segue che \forall n \ge m, \delta_n^* \le \delta_m^* \le \varepsilon. \square

\delta_n^* \le \frac{\gamma \|f^{(k)}\|_\infty}{n^k}

Dimostrazione.

Basta scegliere \varepsilon = \min_{j=0, \dots, k} \varepsilon_j. Poiché l’insieme delle sezioni è finito, il minimo di valori strettamente positivi è ancora strettamente positivo. \square

\|f - (p + q)\|_\infty < \delta

Dimostrazione.

• Caso k \ge 1: Siano \xi_1, \dots, \xi_k i punti di separazione tra le sezioni I_0, \dots, I_k, ovvero

  I_0 = [a, \xi_1], I_1 = [\xi_1, \xi_2], \dots, I_k = [\xi_k, b]

  e definiamo il polinomio:

  s(x) := \prod_{i=1}^k (x - \xi_i) \in \mathcal{P}_k

  Osserviamo che s(x) ha segno costante all’interno di ogni sezione I_j. Senza perdita di generalità, assumiamo che s(x) > 0 sulle sezioni superiori e s(x) < 0 sulle sezioni inferiori.

  Dato \varepsilon > 0 dal lemma precedente, riscaliamo s(x) definendo q(x) := \gamma s(x) con \gamma > 0 sufficientemente piccolo tale che \|q\|_\infty < \varepsilon.

  Verifichiamo che \forall x \in [a, b] si ha |f(x) - (p(x) + q(x))| = |r(x) - q(x)| < \delta:

  • Sia x \in I_j una sezione inferiore. Allora -\delta \le r(x) \le \delta - \varepsilon e q(x) < 0 con |q(x)| < \varepsilon.

    Sommando -q(x) > 0 a r(x), abbiamo r(x) - q(x) > r(x) \ge -\delta (il limite inferiore non viene superato). Inoltre r(x) - q(x) < (\delta - \varepsilon) + \varepsilon = \delta.

    Quindi -\delta < r(x) - q(x) < \delta.

    In breve, abbiamo che 0 < -q(x) < \varepsilon e -\delta \le r(x) \le \delta - \varepsilon implica:

    -\delta < r(x) - q(x) < \delta

  • Il ragionamento è analogo per le sezioni superiori.

  • Se x = \xi_i (uno zero di q), x non può essere un punto di equioscillazione (che sono interni alle sezioni o agli estremi di [a, b] ma non punti di separazione tra sezioni di segno opposto per definizione di insieme sezionato), quindi |r(x)| < \delta e |r(x) - q(x)| = |r(x)| < \delta.

• Caso k = 0: C’è un solo punto di equioscillazione x_0, quindi un’unica sezione I_0 = [a, b]. Basta scegliere q(x) \equiv \gamma o q(x) \equiv -\gamma a seconda che x_0 sia un punto di massimo o di minimo.

In tutti i casi abbiamo trovato un polinomio p + q \in \mathcal{P}_n che approssima f meglio di p. \square

Dimostrazione.

\boxed{\Rightarrow} Sia p \in \mathcal{P}_n il polinomio di migliore approssimazione uniforme di f. Supponiamo per assurdo che il resto r(x) = f(x) - p(x) abbia un insieme alternante che possiamo estendere ad un insieme alternante sezionato \mathcal A = \{x_0, \dots, x_k\} con k+1 < n+2, ovvero k \le n. Per il Teorema di miglioramento dell’approssimazione, esiste un polinomio q \in \mathcal{P}_k \subseteq \mathcal{P}_n tale che:

\|f - (p + q)\|_\infty < \|f - p\|_\infty

Questo contraddice l’ipotesi che p sia il polinomio di migliore approssimazione in \mathcal{P}_n. Pertanto deve essere k \ge n+1, ovvero devono esserci almeno n+2 punti di equioscillazione. \square

\frac{m (b - a)^{n+1}}{2^{2n+1} (n+1)!} \le \delta_n^* \le \frac{M (b - a)^{n+1}}{2^{2n+1} (n+1)!}

Dimostrazione.

Senza perdita di generalità, assumiamo [a, b] = [-1, 1]. Per cui la tesi diventa:

\frac{m}{2^n (n+1)!} \le \delta_n^* \le \frac{M}{2^n (n+1)!}

Sia T_{n+1}(x) il polinomio di Chebyshev di prima specie e t_{n+1}(x) := T_{n+1}(x)/2^n il corrispondente polinomio monico di grado n+1. Ricordiamo che \|t_{n+1}\|_\infty = \min_{p \in \mathcal{P}_{n+1} \text{ monico}} \|p\|_\infty = 1/2^n.

Sia p_n il polinomio di migliore approssimazione minimax di f. Sappiamo che esso può essere visto come un polinomio che interpola f in n+1 punti \xi_0, \dots, \xi_n in cui il resto r_n(x) = f(x) - p_n(x) si annulla.

Usando la formula del resto per l’interpolazione polinomiale:

r_n(x) = f(x) - p_n(x) = \prod_{j=0}^{n} (x - \xi_j) \frac{f^{(n+1)}(\eta)}{(n+1)!} =: s(x) \frac{f^{(n+1)}(\eta)}{(n+1)!}

con \eta \in (-1, 1) e s(x) \in \mathcal{P}_{n+1} polinomio monico.

1. Limite inferiore: Poiché s(x) è un polinomio monico di grado n+1, si ha \|s\|_\infty \ge 1/2^n. Sia y un punto tale che |s(y)| = \|s\|_\infty. Allora:

   \delta_n^* = \|r_n\|_\infty \ge |r_n(y)| = |s(y)| \frac{|f^{(n+1)}(\eta)|}{(n+1)!} \ge \frac{1}{2^n} \frac{m}{(n+1)!}

2. Limite superiore: Possiamo scrivere s(x) = r_n(x) \frac{(n+1)!}{f^{(n+1)}(\eta)}. Poiché f^{(n+1)} è continua e mai nulla in [-1, 1], essa ha segno costante. Pertanto s(x) e r_n(x) hanno lo stesso segno (modulo il segno di f^{(n+1)}). Segue che:

   |s(x)| = |r_n(x)| \frac{(n+1)!}{|f^{(n+1)}(\eta)|} \ge \frac{|r_n(x)| (n+1)!}{M}

   Supponiamo per assurdo che \delta_n^* > \frac{M}{2^n (n+1)!}. Siano x_i gli n+2 punti di equioscillazione di r_n(x), allora |r_n(x_i)| = \delta_n^* e:

   |s(x_i)| \ge \frac{|r_n(x_i)| (n+1)!}{M} = \frac{\delta_n^* (n+1)!}{M} > \frac{M}{2^n (n+1)!} \frac{(n+1)!}{M} = \frac{1}{2^n}

   Quindi s(x) assume in gli x_i valori in modulo strettamente maggiori di 1/2^n con segni alterni. Consideriamo il polinomio h = s - t_{n+1}. Poiché sia s che t_{n+1} sono polinomi monici di grado n+1, il loro grado è al più n. Tuttavia, dato che |s(x_i)| > |t_{n+1}(x_i)| per ogni i e s(x_i) ha segni alterni, h(x_i) deve avere lo stesso segno di s(x_i). Quindi h cambia segno almeno n+1 volte in [a, b], il che implica che h abbia almeno n+1 zeri. Essendo \deg(h) \le n, deve essere h \equiv 0, ovvero s = t_{n+1}. Ma questo è assurdo poiché \|s\|_\infty > 1/2^n mentre \|t_{n+1}\|_\infty = 1/2^n. \square

a \le x_0^{(k)} < x_1^{(k)} < \dots < x_{n+1}^{(k)} \le b

x_i^{(0)} = \frac{b-a}{2} \cos \left( \frac{(n+1-i)\pi}{n+1} \right) + \frac{a+b}{2}

\begin{aligned}
r^{(k)}(x_i^{(k)}) &= f(x_i^{(k)}) - p^{(k)}(x_i^{(k)}) \\
&= f(x_i^{(k)}) - (q^{(k)}(x_i^{(k)}) - d^{(k)}s^{(k)}(x_i^{(k)})) \\
&= f(x_i^{(k)}) - f(x_i^{(k)}) + d^{(k)}(-1)^i \\
&= (-1)^i d^{(k)} \neq 0
\end{aligned}

f(x) \approx \sum_{i=0}^n c_i T_i(x) \in \mathcal{P}_n

c_n = \int_{-1}^{+1} \frac{f(s) T_n(s)}{\sqrt{1 - s^2}} \mathrm ds

\delta_n^* \le \|f - C_n\|_\infty \le 4 \left( 1 + \frac{1}{\pi^2} \log n \right) \delta_n^*

f(x) - C_n(x) \approx c_{n+1} T_{n+1}(x)

\xi_i = \cos \left( \frac{(2i + 1) \pi}{2(n + 1)} \right)

f(x) - I_n(x) = \prod_{i=0}^n (x - \xi_i) \frac{f^{(n+1)}(\zeta)}{(n+1)!}, \quad \zeta \in (-1, 1)

\|f - I_n\|_\infty \le \frac{\|f^{(n+1)}\|_\infty}{(n+1)!} \left\| \prod_{i=0}^n (x - \xi_i) \right\|_\infty

\mathcal{R}_{m,n} = \left\{ s(x) = \frac{p(x)}{q(x)} : p \in \mathcal{P}_m, q \in \mathcal{P}_n, q(x) \neq 0 \text{ in } [a, b] \right\}

\|f - s^*\|_\infty = \min_{s \in \mathcal{R}_{m,n}} \|f - s\|_\infty