

% Copyright (C) 2013 Alvise Sommariva. This is a free document; you can redistribute it and/or modify
% it under the terms of the GNU General Public License as published by
% the Free Software Foundation; either version 2 of the License, or
% at your option) any later version. This document is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
% GNU General Public License for more details. You should have received a copy of the GNU General Public License
% along with this program; if not, write to the Free Software
% Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA}

\documentclass[final]{siamltex}


%------------------------------------------------------------------------------------------------------------------------
% USEPACKAGE.
%------------------------------------------------------------------------------------------------------------------------

\usepackage[italian]{babel}
\usepackage[dvips]{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{times}
\usepackage{epsf}
\usepackage{graphicx,psfrag,color,pst-grad}
\usepackage{latexsym}
\usepackage{psboxit,pstricks}
\usepackage{fancyhdr}
\usepackage{fancyvrb}
\usepackage[colorlinks=true,linkcolor=purple,urlcolor=purple]{hyperref}

\usepackage{float}
\floatstyle{ruled}
\newfloat{program}{thp}{lop}
\floatname{program}{Codice}
\pdfpagewidth 8.5in
\pdfpageheight 11in

% \usepackage{palatino}
% \usepackage[latin1]{inputenc}
\usepackage{calc}
\usepackage{multicol}



%------------------------------------------------------------------------------------------------------------------------
% NEW COMMAND.
%------------------------------------------------------------------------------------------------------------------------

\newcommand{\ptenm}[2]{#1\mbox{-E#2}}
\newcommand{\ptenp}[2]{#1\mbox{+E#2}}
\newcommand{\mye}{\`e }
\newcommand{\myer}{\'e }
\newcommand{\myu}{\`u }
\newcommand{\myur}{\'u }
\newcommand{\mya}{\`a }
\newcommand{\myo}{\`o }
\newcommand{\myod}{\'o }
\newcommand{\myi}{\`i }
\newcommand{\myid}{\'i }

\newcommand{\myesh}{\`e}
\newcommand{\myersh}{\'e}
\newcommand{\myush}{\`u}
\newcommand{\myursh}{\'u}
\newcommand{\myash}{\`a}
\newcommand{\myosh}{\`o}
\newcommand{\myodsh}{\'o}
\newcommand{\myish}{\`i }
\newcommand{\myidsh}{\'i}

\newcommand{\myfl}{\mbox{fl}}
\newcommand{\smsp}{\vspace{0.2cm}}
\newcommand{\Rset}{\mathbb{R}}
\newcommand{\bs}{\boldsymbol}
\newcommand{\mylbar}{|}
\newcommand{\myrbar}{|}

%\pagestyle{fancy}
%\headheight 35pt
%\rhead{}
%\chead{}
%\lhead{}
%\rfoot{}
%\cfoot{\thepage}
%\lfoot{}



%------------------------------------------------------------------------------------------------------------------------
% NEW THEOREM.
%------------------------------------------------------------------------------------------------------------------------

%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{corollary}[theorem]{Corollary}
% \newtheorem{remark}[theorem]{Nota}
%\newenvironment{proof}[1][Proof]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
%\newenvironment{definition}[1][Definition:]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
%\newenvironment{example}[1][Esempio]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
%\newenvironment{remark}[1][Nota]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}


%------------------------------------------------------------------------------------------------------------------------
% NEW COMMAND.
%------------------------------------------------------------------------------------------------------------------------

\renewcommand{\figurename}{Figura}

%\newcommand{\qed}{\nobreak \ifvmode \relax \else
%     \ifdim\lastskip<1.5em \hskip-\lastskip
%    \hskip1.5em plus0em minus0.5em \fi \nobreak
% \vrule height0.75em width0.5em depth0.25em\fi}



%------------------------------------------------------------------------------------------------------------------------
% DEF.
%------------------------------------------------------------------------------------------------------------------------

\def\P{{\mathbb P}}
\def\n{{\mathcal N}}
\def\R{\mathbb{R}}
\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\F{{\mathcal F}}
\newcommand{\LL}{\mathcal L}
\def\C{\mathbb{C}}
\def\K{\mathbb{K}}
\def\T{\mathbb{T}}
\def\qed{\vbox{\hrule height0.6pt\hbox{%
   \vrule height1.3ex width0.6pt\hskip0.8ex
   \vrule width0.6pt}\hrule height0.6pt
  }}

\begin{document}

\title{\bf Approssimazione e interpolazione con polinomi algebrici \thanks{Ultima revisione: \today}}

\author{{A. Sommariva
{\thanks{Dipartimento di Matematica, Universit\`a degli Studi di  Padova, via Trieste 63, 35121 Padova, Italia ({\tt alvise@math.unipd.it})}}} }

\maketitle

Indichiamo con $${\mathbb{P}}_n=<1,x,x^2,\ldots,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\equiv {\mathbb{P}}_n$ si ha $$S_0 \subset S_1 \subset \ldots \subset S_n \subset \ldots$$

Inoltre se $(C([a,b]),\|\cdot\|_{\infty})$ \mye lo spazio normato delle continue $C([a,b])$ in un intervallo chiuso e limitato $[a,b]$, dotato della norma infinito
$$\|f\|_{\infty}=\max_{x \in [a,b]}{|f(x)|}$$
si ha che $\cup_{n \in {\mathbb{N}}} {\mathbb{P}}_n \subseteq (C([a,b]),\|\cdot\|_{\infty})$. 

\vspace{0.25cm}

\begin{theorem}\label{teorema1}
Sia $(X, \|\cdot\|)$ uno spazio funzionale normato e $$S_0\subset S_1 \subset \ldots \subset S_n \subset \ldots$$ una successione crescente
di sottospazi di dimensione finita $N_n = dim(S_n)$.
Allora $$E_n(f) \equiv \inf_{p_n\in S_n} \|p_n-f\| \stackrel{n} \rightarrow 0 $$ se e solo se
$\cup_{n \in {\mathbb{N}}} S_n$  \mye denso in $X$.
\end{theorem}
\vspace{0.25cm}

\begin{proof}

\vspace{0.25cm}

Supponiamo sia $E_n(f) \equiv \inf_{p_n\in S_n} \|p_n-f\| \stackrel{n} \rightarrow 0 $ per ogni $f \in X$. Sia $f \in X$ e sia fissato un arbitrario  $\epsilon >0$. Allora per un qualche $n$ si ha $E_n(f) < \epsilon/2$ e dalle propriet\mya dell'estremo inferiore si ha pure che esiste $p \in S_n$ tale che $\|p-f\| < \epsilon$. Di conseguenza per ogni $\epsilon > 0$ esiste un certo $p \in \cup_{n \in {\mathbb{N}}} S_n$ tale che $\|p-f\| < \epsilon$, cio\mye $\cup_{n \in {\mathbb{N}}} S_n$  \mye denso in $X$. 

\vspace{0.25cm}

Viceversa supponiamo che $\cup_{n \in {\mathbb{N}}} S_n$  sia denso in $X$ e che sia $f \in X$. Essendo $$S_0\subset S_1 \subset \ldots \subset S_n \subset \ldots$$ la successione $E_n(f)$ \mye decrescente e quindi ammette limite. Essendo $\cup_{n \in {\mathbb{N}}} S_n$  denso in $X$, per ogni $\epsilon > 0$ esiste un elemento $p \in \cup_{n \in {\mathbb{N}}} S_n$ tale che $\|f-p\| \leq \epsilon$ e quindi $E_n(f) \equiv \inf_{p_n\in S_n} \|p_n-f\| \stackrel{n} \rightarrow 0 $.
\end{proof}

\vspace{0.25cm}

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

\vspace{0.25cm}

Sussiste il seguente teorema di dovuto a Weierstrass (cf. {\cite[p.127]{DAVIS}}).

\vspace{0.25cm}

\begin{theorem}\label{weierstrass}
Ogni funzione continua in [a, b] \mye limite uniforme di una successione di polinomi.  
\end{theorem}
\vspace{0.25cm}

Il Teorema {\ref{weierstrass}} \mye equivalente a dire che $\cup_{n \in {\mathbb{N}}} {\mathbb{P}}_n$  \mye denso in $(C([a,b]),\|\cdot\|_{\infty})$ e quindi dal Teorema \ref{teorema1} deduciamo che se $f \in C([a,b])$ allora $E_n(f) \equiv \inf_{p_n\in {\mathbb{P}}_n} \|p_n-f\| \stackrel{n} \rightarrow 0 $ (cf. {\cite[p.146]{DAVIS}}).

\vspace{0.25cm}

\begin{theorem}
Sia $S_k$ un sottospazio vettoriale di uno spazio normato $X$. Si supponga che $S_k$ sia di dimensione finita e $f$ sia un certo elemento di $X$. Allora esiste esiste $s^{\ast}_k \in S_k$, detto di {\sl{miglior approssimazione di}} $f$ {\sl{in}} $S_k$, tale che
$$\|f-s^{\ast}_k\|=\min_{s \in S_k}{\|f-s\|}.$$

\end{theorem}

\vspace{0.25cm}

\begin{proof}
L'elemento $0$ dello spazio normato $X$ appartiene certamente a ogni sottospazio $S_k$. Quindi sicuramente $E_n(f) \equiv \inf_{p_n\in S_n} \|p_n-f\| \leq \|f-0\|=\|f\|$. La funzione $d(f,\cdot)=\|f-\cdot\|$ \mye continua. Inoltre essendo lo spazio $S_n$ di dimensione finita, la palla $B(0,\|f\|) =\{p \in S_n: \|p\| \leq \|f\|\}$ centrata in $0$ e avente raggio $\|f\|$ essendo chiusa e limitata \mye pure compatta e quindi per il teorema di Weierstrass la funzione  $d(f,\cdot)$ ha minimo in $B(0,\|f\|)$ e di conseguenza in $S_n$.
\end{proof}

\vspace{0.25cm}
Di conseguenza per ogni grado $k$, fissata $f \in (C([a,b]), \|\cdot\|_{\infty})$ esiste un polinomio $p^{\ast}_k \in {\mathbb{P}}_k$ di miglior approssimazione. 

Per quanto concerne l'unicit\mya del polinomio di miglior approssimazione, vale il seguente teorema dovuto a Chebyshev e noto come di {\sl{equi-oscillazione}} (cf.{\cite{ATKHAN}}, p. 112 oppure \cite{COM}).
\vspace{0.25cm}

\begin{theorem}\label{eqosc}
Sia $f \in C([a,b])$ con $[a,b]$ limitato e $n \in {\mathbb{N}}$. Allora esiste un unico elemento $p^{\ast}_n \in {\mathbb{P}}_n$ di miglior approssimazione. Si caratterizza come segue.
Esistono $n+2$ elementi $a\leq x_0<\ldots<x_{n+1}\leq b$ non necessariamente unici tali che 
$$f(x_j)-p^{\ast}_n(x_j)=\sigma(-1)^j {\min{p \in {\mathbb{P}}_n} \|f-p\|_{\infty}}, \hspace{0.2cm} j=0,1,\ldots,n+1$$
con $\sigma=1$ oppure $\sigma=-1$.
\end{theorem}


\vspace{0.25cm}
Il calcolo del polinomio $p^{\ast} \in {\mathbb{P}}_n$ di miglior approssimazione di una funzione $f \in C([a,b])$ non \mye semplice. L'algoritmo di Remez ne permette una sua determinazione ma la descrizione dello stesso non \mye semplice. Una sua buona implementazione la si ha in ambiente Matlab cui siano state aggiunte le routines di Chebfun (cf. {\cite{CHEBFUN}}). Il relativo comando si chiama {\tt{remez}}.

Digitando sulla shell di Matlab

\begin{verbatim}

>>deg=10;
>> x=chebfun('x',[-5 5]);
>> f=1./(1+x.^2);
>>[p,err]=remez(f,deg);

\end{verbatim}

\noindent
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). 


\begin{table}[h]
{\vspace{0.5cm}}
\begin{center}
{\renewcommand{\arraystretch}{1.1}
\begin{tabular}{| c | c | c | c |}
%\hline
\hline
{\mbox{Grado}} & {\mbox{Errore }} $1/(1+x^2)$ &  {\mbox{Errore }} $|x-4|$ &  {\mbox{Errore }} $\sin{(x)}$ \\ 
%\hline
\hline

$         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 $  & $ - $\\
\hline
\end {tabular}  
}
\caption{Algoritmo di Remez. Errore assoluto di miglior interpolazione relativamente alla funzione di Runge $1/(1+x^2)$, $|x-4|$ e $\sin{(x)}$ in $[-5,5]$.}
\label{T1a}
\end{center}
\end{table}

Dalla Tabella {\ref{T1a}}, risulta chiaro che la miglior approssimante polinomiale a parit\'a 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 {\cite[p.142]{COM}}, {\cite[p.224]{ATK}}

\vspace{0.25cm}

\begin{theorem}\label{JB}
Per ogni $n \geq 1$ e per ogni $f \in C([a,b])$ esiste una costante $M$ indipendente da $n$, $a$, $b$ tale che
$$\inf_{p \in {\mathbb{P}}_n} \|f-p\|_{\infty} \leq M \omega \left(f,\frac{b-a}{n} \right)$$
dove $\omega (f,\cdot)$ \mye il modulo di continuit\mya della funzione $f$ su [a,b], cio\mye 
$$\omega (f,\delta):=\sup_{x,y \in [a,b], \, |x-y| \leq \delta} |f(x)-f(y)|.$$
\end{theorem}

\begin{theorem}
Se $f \in C^p([a,b])$, $p \geq 0$ si ha per ogni $n > p$
$$\inf_{p \in {\mathbb{P}}_n} \|f-p\|_{\infty} \leq M^{p+1}  \frac{(b-a)^p}{n \cdot (n-1) \ldots (n-p+1)}  \omega \left(f^{(p)},\frac{b-a}{n-p} \right).$$
\end{theorem}

\begin{theorem}
Se $f \in C^k([a,b])$, ed $f^{(k)}$ \mye $\alpha$ holderiana, cio\mye $$\sup_{x,y \in [a,b]} |f^{(k)}(x)-f^{(k)}(y)| \leq M|x-y|^{\alpha} $$
per qualche $M>0$, $0 < \alpha \leq 1$. Allora esiste una costante $d_k$ indipendente da $f$ e $n$ per cui
$$\inf_{p \in {\mathbb{P}}_n} \|f-p\|_{\infty} \leq \frac{M \, d_k}{n^{k+\alpha}}, \, n \geq 1.$$
\end{theorem}


\begin{theorem}
Se $f$ \mye analitica (olomorfa) in un aperto $\Omega$
del piano complesso contenente $[a, b]$, allora esiste $\theta \in (0, 1)$ tale che $E_n(f) =\|p^{\ast}_n-f\| =O(\theta^n)$. Inoltre se $f$ \mye intera (cio\mye si pu\myo scegliere $\Omega =\mathbb{C}$) allora la la convergenza \mye superlineare, cio\mye
$$\lim \sup_{n \rightarrow \infty}{(E_n(f))^{1/n}} = 0.$$
\end{theorem}

La funzione di Runge $f(x)=1/(1+x^2)$, con $x \in [-5,5]$ \mye olomorfa in un  aperto $\Omega$ 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 $\theta \approx 0.814$.

La convergenza del polinomio di migliore approssimazione nel caso di $f(x)=\sin{(x)}$, con $x \in [-5,5]$ \mye molto rapida. In effetti tale funzione \mye intera e quindi la convergenza superlineare.

Nel caso di $f(x)=|x-4|$ da $||x-4|-|y-4||\leq |x-y|$ e dal fatto che per $x\leq 4$ si ha $f(x)=4-x$ mentre per $x> 4$ si ha $f(x)=x-4$ si vede facilmente che  
$$\omega (f,\delta):=\sup_{x,y \in [a,b], \, |x-y| \leq \delta} |f(x)-f(y)|=\delta$$
e quindi dal Teorema \ref{JB} che per qualche $M$
$$\inf_{p \in {\mathbb{P}}_n} \|f-p\|_{\infty} \leq M \frac{b-a}{n}.$$
In effetti, un confronto coi dati stabilisce che posti $a=-5$ e $b=5$ (estremi dell'intervallo)
$$\inf_{p \in {\mathbb{P}}_n} \|f-p\|_{\infty} \approx 0.085 \cdot  \frac{b-a}{n}=\frac{0.85}{n}$$
e quindi una convergenza lenta di $E_n(f)$ a $0$, se paragonata alla quantit\mya $E_n(f) \approx 0.814^n$ trovata nell'esempio di Runge.


\section{Alcune note sui polinomi di Chebyshev}
Consideriamo la funzione $$T_n(x)=\cos (n \arccos(x))$$ con $x \in [-1,1]$ (cf. \cite[p.211]{ATK}). A priori, in virt\myu della presenza del coseno, $T_n$ non sembra essere un polinomio. In realt\mya si vede subito che $T_0(x)=\cos (0 \arccos(x))=1$, $T_1(x)=\cos (1 \arccos(x))=x$. Dal teorema di prostaferesi
$$\cos ((n \pm 1) \, \theta)= \left( \cos (n \,\theta) \right) \cdot \cos (\theta) \mp \left( \sin (n \,\theta) \right) \cdot \sin (\theta)$$
si vede inoltre che per $\theta=\arccos(x)$ si ha
$$T_{n+1}(x)+T_{n-1}(x)=2 \left( \cos (n \,\theta) \right) \cdot \cos (\theta) =2 T_n(x) x$$
da cui
$$T_{n+1}(x)=2x \, T_{n}-T_{n-1}$$
Di conseguenza, per ricorrenza, si deduce che $T_n$ \mye un polinomio di grado $n$ e che inoltre per $n > 0$ \mye del tipo $T_{n}(x)=2^{n-1} \, x^{n} + \cdots$. 

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{\pi}{2}+k \pi=\frac{(2k+1) \pi}{2}$$ $$\arccos(x_k)= \frac{(2k+1) \pi}{2n}$$ $$x_k=\cos (\arccos(x_k))=\cos \left( \frac{(2k+1) \pi}{2n} \right), \, k=0,\ldots, n-1.$$

\noindent
Notiamo che gli zeri del polinomio di Chebyshev $T_n$ sono esattamente $n$, distinti e nell'intervallo [$-1,1$].


\section{Costanti di Lebesgue}

Sia $f \in C([a,b])$, con [$a,b$] intervallo chiuso e limitato e si consideri il polinomio $p_n \in {\mathbb{P}}_n$ che interpola le coppie ($x_k,f(x_k)$) (per $k=0,\ldots,n$, $x_k$ a due a due distinti). Si ponga per semplicit\mya di notazione $f_k:=f(x_k)$. Come \mye noto, indicato con $L_k$ il k-simo polinomio di Lagrange, si ha
$$p_n(x)=\sum_{k=0}^{n} f_k L_k(x).$$
Supponiamo che i valori di $f_k$ siano perturbati (per esempio per via dell'arrotondamento del numero) e sostituiti con ${\tilde f}_k$. Otteniamo quindi quale polinomio interpolatore
$${\tilde p_n}(x)=\sum_{k=0}^{n} {\tilde f}_k L_k(x).$$
Si ha cos\myi che
$$p_n(x)-{\tilde p}_n(x)=\sum_{k=0}^{n} (f_k-{\tilde f}_k) L_k(x)$$
$$|p_n(x)-{\tilde p}_n(x)|\leq \sum_{k=0}^{n} |f_k-{\tilde f}_k| |L_k(x)| \leq \left( \max_k |f_k-{\tilde f}_k| \right) \sum_{k=0}^{n} |L_k(x)|$$

\noindent
e quindi posto $$\Lambda_n=\max_{x \in [a,b]} \sum_{k=0}^{n} |L_k(x)|$$ si ha 

$$\|p_n-{\tilde p}_n\|_{\infty} \leq \left( \max_k |f_k-{\tilde f}_k| \right) \cdot \Lambda_n.$$

\noindent
Il valore $\Lambda_n$ \mye nota come {\sl{costante di Lebesgue}} dell'insieme di punti $x_0,\ldots,x_n$ (cf. \cite{WIKILCI}). Si vede immediatamente che \mye un indice di stabilit\mya dell'interpolazione di Lagrange: pi\myu \mye piccola e pi\myu l'approssimazione \mye stabile (cf. {\cite[p.139-140]{COM}}). 

\noindent
Ricordiamo che se ($X$, $\|\cdot\|_X$), ($Y$, $\|\cdot\|_Y$) sono due spazi normati, $A: X \rightarrow Y$ \mye un operatore lineare limitato se e solo sa il numero $$\|A\|=\sup_{\|x\| \leq 1} \|Ax\|_Y=\sup_{x \in X, x \neq 0}  \frac{\|Ax\|_Y}{\|x\|_X}   $$ \mye finito. Il numero reale $\|A\|$ si chiama {\sl{norma dell'operatore lineare}} $A$ (cf. \cite[p.224]{KOL}).  

\noindent
Si pu\myo mostrare che se ${\cal L}_n$ \mye l'operatore (lineare e limitato) che associa a $f \in C([a,b])$ il suo polinomio di interpolazione nei nodi $x_0,\ldots,x_n$ allora
$$\Lambda_n=\max_{g \in C([a,b]), \, g \neq 0} \frac{\|L_n(g)\|_{\infty}}{\|g\|_{\infty}}$$
cio\mye la costante di Lebesgue \mye la norma dell'operatore di interpolazione ${\cal L}_n$ rispetto alla norma $\| \cdot \|_{\infty}$.


\begin{theorem}
Se $f\in C([a,b])$ e $p_n$ \mye il suo polinomio di interpolazione relativo ai punti $x_0,\ldots,x_n$ si ha
\begin{equation}\label{ivsa}
\|f-p_n\|_{\infty} \leq (1+\Lambda_n) E_n(f)
\end{equation}
dove
$$E_n(f)=\inf_{q_n \in {\cal P}_n} \|f-p_n\|_{\infty}$$
\mye l'errore compiuto dal polinomio di migliore approssimazione uniforme.
\end{theorem}

\vspace{0.25cm}

\begin{proof}

Se $f \in {\cal P}_n$, allora $f \equiv p_n \equiv q_n$ e quindi l'asserto \mye ovvio. Supponiamo quindi che $f$ non appartenga a ${\cal P}_n$, cio\mye $f-q_n$ non sia la funzione nulla, qualsiasi sia $q_n \in {\cal P}_n$.

Per ogni polinomio $q_n \in {\cal P}_n$, \mye ${\cal L}_n(q_n)=q_n$, in quanto l'unico polinomio che interpola in $n+1$ punti distinti un polinomio di grado $n$ \mye il polinomio stesso. Inoltre $${\cal L}_n(f-q_n)={\cal L}_n(f)-{\cal L}_n(q_n)=p_n-q_n.$$

Poich\mye $f-q$ non \mye la funzione nulla, abbiamo
\begin{equation}\label{lebeq}
\Lambda_n=\max_{g \in C([a,b]), \, g \neq 0} \frac{\|{\cal L}_n(g)\|_{\infty}}{\|g\|_{\infty}} \geq \frac{\|{\cal L}_n(f-q_n)\|_{\infty}}{\|f-q_n\|_{\infty}}\frac{\|p_n-q_n\|_{\infty}}{\|f-q_n\|_{\infty}}
\end{equation}
e di conseguenza
\begin{equation}\label{lebeq1}
\|(p_n-q_n)\|_{\infty} \leq \Lambda_n \cdot \|f-q_n\|_{\infty}.
\end{equation}

Per concludere, osserviamo che per la disuguaglianza triangolare da $f-p=(f-q)+(q-p)$ e (\ref{lebeq1})
\begin{eqnarray}
\|f-p_n\|_{\infty} &=& \| (f-q_n)+(q-p_n) \|_{\infty} \nonumber \\
                 & \leq & \| f-q_n\|_{\infty} + \| q_n-p_n \|_{\infty} \nonumber \\
                 & \leq & \| f-q_n\|_{\infty} +  \Lambda_n \, \|f-q_n\|_{\infty} \nonumber \\
                 & = & (1+\Lambda_n) \, \| f-q_n\|_{\infty}
\end{eqnarray}

\end{proof}

\vspace{0.25cm}

Questo teorema \mye utile, perch\mye fa capire che se la costante di Lebesgue \mye piccola allora l'errore compiuto dall'interpolante polinomiale \mye 
{\sl{poco}} pi\myu grande dell'errore di miglior approssimazione uniforme.

  \begin{figure}[ht!]\label{fig1a}
 \centering
   {\includegraphics[scale=0.50,clip]{Lebesgue.eps}}
 \caption{Henri Lebesgue (1875-1941).}
 \end{figure}
 
Vediamo ora quali sono le stime delle costanti di Lebesgue per alcuni set di $n+1$ punti $x_0,\ldots,x_n$ particolarmente interessanti, nell'intervallo $[-1,1]$ (cf. \cite{SMITH}):

\begin{enumerate}
\item punti equispaziati: si dimostra che la costante di Lebesgue relativa a questi punti vale asintoticamente $\Lambda_n \approx  \frac{2^{n+1}}{e n \log(n)}$ (cf. {\cite[p.142]{COM}});
\item punti di Chebyshev: corrispondono a $ \frac{\cos(2k - 1)}{2(n+1)}$ dove $k = 1, \ldots, n+1$; si dimostra che la costante di Lebesgue relativa a questi punti vale asintoticamente
$$\frac{2}{\pi} \left( \log(n+1) + \gamma +\frac{8}{\pi}  \right)+ O\left( \frac{1}{(n+1)^2} \right)$$
\noindent dove $\gamma \approx 0.577$ \mye la {\sl{costante di Eulero-Mascheroni}} (cf. \cite{WIKICEM});
\item punti di Chebyshev estesi: sono definiti da $ \frac{\cos(2k - 1)}{2(n+1) \cdot \cos(\frac{\pi}{2n+1})}$ dove $k = 1, \ldots, n+1$; si dimostra che la costante di Lebesgue relativa a questi punti vale asintoticamente
$$\frac{2}{\pi} \left( \log(n+1) + \gamma +\log\left( \frac{8}{\pi} \right)-\frac{2}{3}  \right)+ O\left(\frac{1}{\log(n+1)} \right);$$
\item configurazione ottimale: si dimostra che la minima costante di Lebesgue (non \mye nota esplicitamente!) vale
$$\frac{2}{\pi} \left( \log(n+1) + \gamma +\log \left(\frac{4}{\pi} \right)  \right)+ O \left( \frac{ \log(\log(n+1)) }{\log(n+1)}\right)$$
\end{enumerate}

Vediamo usando Matlab quanto siano differenti tali costanti per gradi $n$ quali $5,10,\ldots,50$.

\begin{Verbatim}[fontsize=\small, formatcom=\color{blue}]

>> n=(5:5:50)'; % VETTORE COLONNA DI GRADI.
>> % NODI EQUISPAZIATI.
>> s=(2.^(n+1))./(exp(1)*n.*log(n));
>> % NODI CHEBYSHEV.
>> % \frac{2}{\pi} \left( \log(n+1) + \gamma 
      %+\frac{8}{\pi}  \right)+ O\left( \frac{1}{(n+1)^2} \right)
>> t=(2/pi)*( log(n+1) + 0.577 + (8/pi) );
>> [s t]

ans =

  2.9258e+000  3.1291e+000
  3.2720e+001  3.5150e+000
  5.9352e+002  3.7536e+000
  1.2877e+004  3.9267e+000
  3.0679e+005  4.0626e+000
  7.7425e+006  4.1746e+000
  2.0316e+008  4.2698e+000
  5.4825e+009  4.3526e+000
  1.5112e+011  4.4259e+000
  4.2351e+012  4.4915e+000

>> 

\end{Verbatim}

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

\section{Esercizi}
\begin{enumerate}
\item (Non facile, e richiede qualche conto su carta). Si implementi un codice Matlab che approssimi la costante di Lebesgue di un set di punti $x_0,\ldots,x_n$ in un intervallo prefissato $[a,b]$, valutando la {\sl{funzione di Lebesgue}} $\sum_{k=0}^{n} |L_k(x)|$ (dove al solito $L_k$ \mye il $k$-simo polinomio di Lagrange) in $M=1000$ punti test equispaziati in $[a,b]$. In seguito si valuti con tale codice la costante di Lebesgue di un set di 10 punti equispaziati in $[-1,1]$ e in 10 punti di Chebyshev.
\item (Facile, ma un po' lungo). Sfruttando i valori citati (a meno di $O$ grandi), si confrontino i valori delle costanti di Lebesgue per i nodi equispaziati, di Chebyshev e di Chebyshev estesi.
\end{enumerate}


\begin{thebibliography}{99} 
\bibitem{ATK} K. Atkinson, {\sl{Introduction to Numerical Analysis}}, Wiley, 1989.
\bibitem{ATKHAN} K. Atkinson e W. Han, {\sl{Theoretical Numerical Analysis, A Functional Analysis Framework}}, Springer, 2001.
\bibitem{COM} V. Comincioli, {\sl{Analisi Numerica, metodi modelli applicazioni}}, Mc Graw-Hill, 1990.
\bibitem{CHEBFUN} Chebfun, {\href{http://www.mathworks.com/matlabcentral/fileexchange/23972-chebfun}{http://www.mathworks.com/matlabcentral/fileexchange/23972-chebfun}}
\bibitem{DAVIS} P.J. Davis, {\sl{Interpolation & Approximation}}, Dover, 1975.
\bibitem{KOL} A.N. Kolmogorov e S.V. Fomin, {\sl{Introductory real analysis}}, Dover, 1970.
\bibitem{SMITH} S.J. Smith, {\sl{Lebesgue constants in polynomial interpolation}}, Annales Mathematicae et Informaticae, p. 109-123, 33 (2006) {\href{http://www.ektf.hu/tanszek/matematika/ami}{http://www.ektf.hu/tanszek/matematika/ami}}.
\bibitem{WIKICEM} Wikipedia, (Costante di Eulero Mascheroni),  
{\href{http://it.wikipedia.org/wiki/Costante\_di\_Eulero-Mascheroni}{http://it.wikipedia.org/wiki/Costante\_di\_Eulero-Mascheroni}}.
\bibitem{WIKILCI} Wikipedia, (Lebesgue constant interpolation), {\href{http://en.wikipedia.org/wiki/Lebesgue\_constant\_(interpolation)}{http://en.wikipedia.org/wiki/Lebesgue\_constant\_(interpolation)}}.
\end{thebibliography}

\end{document}



,  con 
$${\mathbb{T}}^{\mathbb{R}}_n=<1,\cos{(x)},\sin{(x)},\ldots,\cos{(nx)},\sin{(nx)}>$$
lo spazio vettoriale dei polinomi trigonometrici reali di grado $n$ definiti in $[-\pi,\pi]$, la cui dimensione \mye $N_n=2n+1$.
e con 
$${\mathbb{T}}^{\mathbb{C}}_n=<1,\exp{(ix)},\exp{(-ix)},\ldots,\exp{(inx)},\exp{(-inx)}>$$
lo spazio vettoriale dei polinomi trigonometrici complessi di grado $n$ definiti in $[-\pi,\pi]$, la cui dimensione \mye $N_n=2n+1$.

Si osserva subito dalla identit�\mya di Eulero
$$\exp{(it)}=\cos{(t)}+i \cdot \cos{(t)}$$
che 
$$
\cos{(kt)}=
{\frac
{ \exp{(ikt)}+\exp{(-ikt)} }
{2}
}
\,\,
\sin{(kt)}=
{\frac
{ \exp{(ikt)}-\exp{(-ikt)} }
{2i}
}
$$
e quindi facilmente che per $n >0$ si ha ${\mathbb{T}}^{\mathbb{R}}_n \subset {\mathbb{T}}^{\mathbb{C}}_n$, in quanto $\exp{(it)}$ non appartiene a $ {\mathbb{T}}^{\mathbb{R}}_n$.


Uno spazio normato di particolare interesse \mye quello delle funzioni continue e $2\pi$ periodiche denotato con $(C^{\mathbb{R}}_p(2\pi),\|\cdot\|_{\infty})$, cio\'e l'insieme delle funzioni reali continue sull'asse reale tali che $$f(x+2\pi)=f(x), \, x \in {\mathbb{R}}$$ dotato della norma $$\|f\|_{\infty}=\max_{x \in [a,b]}{|f(x)|}.$$
Evidentemente $\cup_{n \in {\mathbb{N}}}{\mathbb{T}}^{\mathbb{R}}_n \subseteq (C^{\mathbb{R}}_p(2\pi),\|\cdot\|_{\infty})$. 


Similmente se 
$ (L^2_{\mathbb{R}} (-\pi,\pi),\|\cdot\|_2)$ e  $(L^2_{\mathbb{C}}(-\pi,\pi),\|\cdot\|_2)$ 
sono gli spazi normati delle funzioni misurabili rispettivamente a valori reali e complesse in $(-\pi,\pi)$ tali che $$\|f\|_2^2 \equiv \int_a^b |f|^2 < \infty$$
si ha che $\cup_{n \in {\mathbb{N}}}{\mathbb{T}}^{\mathbb{R}}_n \subseteq (L^2_{\mathbb{R}}(-\pi,\pi),\|\cdot\|_2)$ e $\cup_{n \in {\mathbb{N}}}{\mathbb{T}}^{\mathbb{C}}_n \subseteq (L^2_{\mathbb{C}}(-\pi,\pi),\|\cdot\|_2)$. 


\bibitem{ATK} K. Atkinson, {\sl{Introduction to Numerical Analysis}}, Wiley, 1989.
\bibitem{BEL} Bellen, homepage personale, \\   {\href{http://www.dsm.units.it/\%7Ebellen/calcolo\_numerico/CAPIT-4.PDF}{http://www.dsm.units.it/\%7Ebellen/calcolo\_numerico/CAPIT-4.PDF}}.

\bibitem{CON} S.D. Conte e C. de Boor, {\sl{Elementary Numerical Analysis, 3rd Edition}}, Mc Graw-Hill, 1980.
\bibitem{MATW} The MathWorks Inc., \\   {\href{http://www.mathworks.com/moler/leastsquares.pdf}{http://www.mathworks.com/moler/leastsquares.pdf}}.
\bibitem{MOL} The MathWorks Inc., {\sl{Numerical Computing with Matlab}}, \\
{\href{http://www.mathworks.com/moler}{http://www.mathworks.com/moler}}.
\bibitem{QUA} A. Quarteroni e F. Saleri, {\sl{Introduzione al calcolo scientifico}}, Springer Verlag, 2006.
\bibitem{SULI} A. Suli e D. Mayers, {\sl{An Introduction to Numerical Analysis}}, Cambridge University Press, 2003.
\bibitem{WIKLS} Wikipedia, Least Squares, \\   {\href{http://en.wikipedia.org/wiki/Least\_squares}{http://en.wikipedia.org/wiki/Least\_squares}}.
\bibitem{WIKMQ} Wikipedia, Minimi quadrati, \\   {\href{http://it.wikipedia.org/wiki/Minimi\_quadrati}{http://it.wikipedia.org/wiki/Minimi\_quadrati}}.
\bibitem{WIKMQQ} Wikipedia, Minimi Quadrati, \\   {\href{http://it.wikipedia.org/wiki/Minimi\_Quadrati}{http://it.wikipedia.org/wiki/Minimi\_Quadrati}}.



\begin{verbatim}

>> x=0:0.01:2*pi;
>> y=sin(2*x)+(10^(-1))*rand(size(x));
>> plot(x,y,'r-'); 

\end{verbatim} \begin{figure}\label{fig1c}
 \centering
   {\includegraphics[scale=0.35,clip]{esempio2errore.eps}}
 \caption{Grafico che illustra l'errore assoluto compiuto tra il polinomio approssimante l'esponenziale arrotondato a due cifre decimali (in rosso) nei punti test $x_{\mbox{test}}=-1:(1/100):+1$.}
 \end{figure}