\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage{hyperref}
\usepackage{microtype}
\usepackage[usenames,dvipsnames]{color}
\usepackage{listings}
\definecolor{MyLightGrey}{rgb}{0.95,0.95,0.95}
\definecolor{MyMediumGrey}{rgb}{0.5,0.5,0.5}
\definecolor{MyDarkGrey}{rgb}{0.3,0.3,0.3}
\lstset{language=Matlab,showstringspaces=false,morecomment=[l]\%,
backgroundcolor=\color{MyLightGrey},breaklines,
extendedchars=true,columns=fullflexible,basicstyle=\tt\small,
commentstyle=\color{MyMediumGrey},keywordstyle=\color{MyDarkGrey},
morekeywords={ordschur,ordeig,fminbnd,ordqz,error}}
\usepackage{verbatim,comment}


\usepackage{amsfonts,amssymb,amsmath}
\usepackage{graphicx}
\usepackage{epsfig}
\usepackage[italian]{babel}
\newcommand{\bm}[1]{\mbox{\boldmath $#1$}}
\newcommand{\K}{\mathbb K}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\N}{\mathbb N}
\newcommand{\cu}{\bm i}
\newcommand{\V}{\mathcal V}
\newcommand{\HH}{\mathcal H}
\newcommand{\A}{\mathcal A}
\newcommand{\B}{\mathcal B}
\newcommand{\PP}{\mathcal P}
\newcommand{\overcirc}{\mathring}
\newcommand{\vvec}{\hbox{\rm vec}}
\newcommand{\qed}{\hfill $\Box$\\}
\newcommand{\ones}{\bm e}
\newcommand{\err}{\bm \epsilon}
\newcommand{\diag}{\hbox{\rm diag}}

\newtheorem{teo}{Teorema}
\newtheorem{defi}[teo]{Definizione}
\newtheorem{lem}[teo]{Lemma}
\newtheorem{cor}[teo]{Corollario}
\newtheorem{oss}[teo]{Osservazione}
\newtheorem{ese}{Esercizio}
\newcommand{\scal}[2]{\left\langle #1, #2 \right\rangle}
\newcommand{\norm}[1]{\left\Vert #1 \right\Vert}
\newcommand{\abs}[1]{\left\vert #1 \right\vert}





\begin{document}
\title{Traccia della prima parte del corso di IAN, a.a. 2014-2015}
\author{Dario A. Bini}
\maketitle

\section{Introduzione} Questo documento
contiene una traccia pi\`u o meno dettagliata di parte degli argomenti trattati 
nel corso di Istituzioni di Analisi Numerica (IAN). La traccia degli altri argomenti trattati si trova in un secondo
documento sulla risoluzione numerica di equazioni differenziali alle derivate parziali e
dagli appunti forniti dall prof.ssa Ornella Menchi durante lo svolgimento del
corso di IAN.\\[1ex]


Scopo dell'Analisi Numerica \`e il progetto e l'analisi di metodi di
risoluzione di vari problemi matematici mediante l'uso di sole operazioni
aritmetiche fra numeri {\em floating point}. Nel corso dell'insegnamento di
Analisi Numerica ci siamo occupati principalmente di problemi dell'algebra
lineare e del discreto quali sistemi lineari, trasformate discrete,
interpolazione. Nel corso di Calcolo Scientifico l'interesse si \`e rivolto
verso problemi spettrali (autovalori, SVD) e metodi per sistemi lineari
di grandi dimensioni provenenti dalle applicazioni. Nel corso di IAN ci occupiamo principalmente di
problemi del ``continuo''. problemi cio\`e in cui l'oggetto da ``calcolare''
\`e una funzione da $\R^n$ in $\R$ e non un vettore. La motivazione e lo scopo
saranno comunque gli stessi: progettare e analizzare metodi di risoluzione che
impieghino un numero finito di operazioni aritmetiche. Naturalmente la
finitezza del numero di operazioni comporter\`a l'impossibilit\`a di calcolare
esattamente la soluzione per cui sar\`a necessario approssimarla.

I problemi che andiamo a trattare sono:


\begin{itemize}
\item approssimazione di funzioni: data $f(x):[a,b]\subset\R\to\R$ 
determinare una $g(x)$ in una
  classe di funzioni facilmente calcolabili che meglio approssimi $g(x)$;
\item integrazione approssimata: data $f(x):[a,b]\subset\R\to\R$ approssimare
$\int_a^bf(x)dx$;
\item approssimare la soluzione di certe equazioni differenziali alle derivate
  parziali che si incontrano nelle applicazioni
\end{itemize}

I metodi numerici diventano necessit\`a in tutte le situazioni in cui la
soluzione (funzione) di cui cerchiamo informazioni non si lascia esprimere in
modo esplicito in termini di funzioni elementari. Questa situazione si
presenta nella quasi totalit\`a dei casi di interesse.

Il corso \`e suddiviso in 
\begin{itemize}
\item parte sui polinomi ortogonali: contiene la definizione e l'analisi delle
  propriet\`a di questa classe di polinomi con la tassonomia delle principali
  tipologie di polinomi; saranno evidenziate analogie tra polinomi ortogonali
  e matrici tridiagonali con propriet\`a dell'algebra lineare numerica;

\item parte sull'applicazione dei polinomi ortogonali alla costruzione di
  efficienti formule di integrazione approssimata;

\item parte che riguarda i metodi per l'approssimazione di funzioni in
  generale; particolare attenzione \`e rivolta alla migliore approssimazione
  in norma 2 e in norma infinito; saranno utilizzate le propriet\`a dei
  polinomi ortogonali; saranno sottolineate le relazioni tra approssimazione e
  interpolazione con particolare attenzione ai problemi del condizionamento;
  verr\`a considerato un risultato generale noto come teorema di Korovkin;
  verranno introdotte e analizzate le funzioni curvilinee

\item parte sulla risoluzione numerica di equazioni differenziali alle
  derivate parziali: sar\`a fatta la classificazione in equazioni ellittiche,
  paraboliche e iperboliche con esempi dalle applicazioni; verr\`a sviluppata la
  parte relativa al metodo delle differenze finite dove viene data una
  impostazione il pi\`u possibile ``matriciale''; \`e fatto un cenno ai metodi
  di Rayleigh-Ritz-Galerkin e di collocazione.

\end{itemize}

\section{Polinomi ortogonali}
Nel seguito si denota con $\mathcal P_n$ lo spazio vettoriale di
dimensione $n+1$ costituito dai polinomi a coefficienti reali di grado
al pi\`u $n$ e con $\mathcal P$ lo spazio vettoriale di tutti i
polinomi a coefficienti reali. Inoltre $a,b$ denotano due costanti
della retta reale estesa $\R\cup\{+\infty,-\infty\}$ con $a<b$. In
questo modo l'intervallo $[a,b]$ pu\`o essere anche del tipo
$[-\infty,\beta]$, $[\alpha,+\infty]$, con $\alpha,\beta\in\R$, e
$[-\infty,+\infty]$.

Sia $\omega(x):[a,b]\to\R$ una funzione a valori nella retta 
reale estesa tale che $\omega(x)>0$ per $a<x<b$ ed  esista finito
$\int_a^bf(x)\omega(x)dx$ per ogni polinomio $f(x)\in\mathcal P(x)$. 
%% FEDE: $\omega$ a quadrato integrabile ??? problema su intervalli infiniti
%% Guardare in letteratura 
Si osserva che l'applicazione che a una
coppia di polinomi $(f(x),g(x))$, $f(x),g(x)\in\mathcal P$ associa il
numero reale
\begin{equation}\label{prodscal}
\left\langle f,g \right\rangle :=\int_a^bf(x)g(x)\omega(x)dx
\end{equation}
\`e un prodotto scalare sul $\mathcal P$.
L'applicazione che a $f(x)\in\mathcal P$ associa 
$(\int_a^bf(x)\omega(x)dx)^{1/2}$
\`e una norma su $\mathcal P$ che viene denotata con $\|f(x)\|$.

\begin{oss}\rm
Il prodotto scalare appena introdotto verifica la propriet\`a $\langle
xf(x),g(x)\rangle=\langle f(x),x g(x)\rangle$. Non tutti i prodotti
scalari su $\mathcal P$ verificano questa propriet\`a. Ad esempio, se
consideriamo $\mathcal P_n$, e associamo a $p(x)\in\mathcal P_n$ la
$(n+1)$-upla dei suoi coefficienti, possiamo rappresentare lo spazio
lineare $\mathcal P_n$ con $\mathbb R^{n+1}$. Per cui ogni prodotto
scalare su $\mathbb R^{n+1}$ induce un prodotto scalare su $\mathcal
P_n$. In particolare il prodotto scalare euclideo su $\mathbb R^{n+1}$
induce il prodotto scalare tra polinomi $\langle
p(x),q(x)\rangle=\sum_{i=0}^np_iq_i$ dove $p(x)=\sum_{i=0}^n p_ix^i$,
$q(x)=\sum_{i=0}^n q_ix^i$, che non soddisfa la propriet\`a $\langle
xf(x),g(x)\rangle=\langle f(x),x g(x)\rangle$.
\qed\end{oss}


\begin{defi} Dato un prodotto scalare $\langle \cdot,\cdot\rangle$, 
su $\mathcal P$,
un insieme di polinomi $\{p_i(x)\in\mathcal P_i,~i=0,1\ldots\}$ tale
che ${\rm deg}(p_i)=i$ e $\left\langle p_i,p_j \right\rangle =0$ se
$i\ne j$ \`e detto {\em insieme di polinomi ortogonali} relativamente
al prodotto scalare $\left\langle \cdot,\cdot \right\rangle $.\qed
\end{defi}

I polinomi $p_i(x)/h_i^{1/2}$, $h_i=\left\langle p_i,p_i \right\rangle
$ sono detti polinomi ortonormali.  Ad esempio, i polinomi $x^i$,
$i=0,1,\ldots$, sono ortonormali rispetto al prodotto scalare indotto
dal prodotto euclideo.



Esempi classici di funzioni peso che definiscono il prodotto scalare di tipo integrale sono $\omega(x)=1$ su $[-1,1]$, $\omega(x)=\sqrt{1-x^2}$ su $[-1,1]$, $\omega(x)=1/\sqrt{1-x^2}$ su $[-1,1]$, $\omega(x)=e^{-x}$ su $[0,+\infty]$, $e^{-x^2}$ su $[-\infty,+\infty]$.
 
\begin{oss}\label{oss1}\rm
Per un generico prodotto scalare su $\mathcal P$,  esistono sempre polinomi ortogonali che possono essere costruiti mediante il procedimento di
ortogonalizzazione di Gram-Schmidt a partire dai monomi $1,x,x^2,x^3,\ldots$,
nel seguente modo:
\begin{equation}\label{tilde}
\begin{array}{ll}
p_0(x)=1,~~p_{k}(x)=x^{k}+\sum_{i=0}^{k-1} \alpha_{k,i}
  p_i(x),\\
&k=1,2,\ldots\\
\alpha_{k,i}=-\left\langle x^{k},p_i(x) \right\rangle /\left\langle p_i(x),p_i(x) \right\rangle,~~i=0,\ldots,k-1 
\end{array}
\end{equation}
Col prodotto scalare integrale \eqref{prodscal} per calcolare i
coefficienti $\alpha_{k,i}$ per $i=0,\ldots,k-1$ e $k=1,\ldots,n$, occorre
calcolare, o approssimare numericamente, $n(n+1)/2$ integrali.
Inoltre, per calcolare i coefficienti del generico polinomio $p_k$ di
grado $k$ occorre eseguire circa $k^2$ operazioni aritmetiche per cui
il costo totale per calcolare i coefficienti di tutti i polinomi
$p_k$, $k=0,\ldots,n$ \`e di $O(n^3)$ operazioni.  Questo per\`o non
\`e il modo migliore di procedere. Come vedremo tra poco ci sono
espressioni pi\`u semplici per esprimere i coefficienti di $p_k(x)$.

Inoltre per calcolare il valore che $p_k(x)$ assume in un punto $\xi$
usando la \eqref{tilde} occorrono circa $2k$ operazioni aritmetiche
avendo per\`o prima calcolato i valori di $p_i(\xi)$,
$i=0,1,\ldots,k-1$ e i coefficienti $a_{k,i}$.  Quindi occorrono
$O(k^2)$ operazioni. Anche questo calcolo pu\`o essere semplificato
mediante una diversa rappresentazione dei polinomi ortogonali.
\qed\end{oss}

La seguente banale osservazione ha una serie di conseguenze meno
immediate e di particolare rilevanza.

\begin{oss}\label{oss2}\rm
I polinomi ortogonali $p_0(x),p_1(x),\ldots, p_n(x)$ sono linearmente
indipendenti e quindi costituiscono una base dello spazio vettoriale $\mathcal
P_n$ dei polinomi di grado minore o uguale ad $n$.
\qed\end{oss}

Dalla precedente osservazione segue il

\begin{teo}\label{th:ort}
Se  $p_0,p_1,\ldots, $ sono polinomi ortogonali rispetto al prodotto scalare \eqref{prodscal} allora per ogni polinomio $q$
di grado $n$ vale $\left\langle p_i,q \right\rangle =0$ per ogni $i>n$.
\end{teo}
{\bf Dim.} Per l'osservazione \ref{oss2} si ha
$q(x)=\sum_{j=0}^n \gamma_j p_j(x)$, $\gamma_n\ne 0$. Se $i>n$ vale allora
$\left\langle p_i,q \right\rangle =
\sum_{j=0}^n\gamma_j\left\langle p_i,p_j \right\rangle =0$.
\qed

La propriet\`a espressa nel teorema precedente ci permette di
dimostrare il seguente risultato interessante.

\begin{teo}
Gli zeri dei polinomi ortogonali rispetto al prodotto sclare \eqref{prodscal}
 sono reali e semplici e stanno in $(a,b)$.
\end{teo}
{\bf Dim.} Siano $x_1,\ldots,x_j$ gli zeri reali e distinti di $p_n(x)$ in
$(a,b)$. Per assurdo supponiamo $j<n$. Supponiamo inoltre che $k$ di questi
zeri abbiano molteplicit\`a dispari e $j-k$ pari. Numeriamo gli $x_i$ in modo
che i primi $k$ abbiano molteplicit\`a dispari. Definiamo
\[
q(x)=\left\{\begin{array}{ll}1&\hbox{se }k=0\\[1ex]
\prod_{s=1}^k(x-x_s)&\hbox{se }k>0
\end{array}\right.
\]
Allora gli zeri in $(a,b)$ di $p_n(x)q(x)$ hanno molteplicit\`a pari e quindi
questo prodotto non cambia segno in $(a,b)$. Conseguentemente
\[
\left\langle p_n,q \right\rangle =\int_a^bp_n(x)q(x)\omega(x)dx\ne 0
\]
che \`e assurdo per il teorema \ref{th:ort} poich\'e il grado di $q(x)$ \`e
$k\le j<n$\qed


%\begin{oss}\rm
%In effetti per dimostrare la propriet\`a data nel precedente teorema
%basta supporre che il prodotto scalare verifichi la condizione
%$\langle xf(x),g(x)\rangle=\langle f(x),x g(x)\rangle$.
%\qed\end{oss}

%\begin{teo}
%Siano $p_i(x)$, per $i=0,1,\ldots$, un insieme di polinomi ortogonali.
%L'unione degli zeri di tutti i $p_i(x)$ \`e denso in $(a,b)$.
%\end{teo}
%{\bf Dim.} Dimostriamo la propriet\`a nel caso in cui $[a,b]$ sia un
%intervallo finito. Supponiamo per assurdo che esista un intervallo
%$[c,d]\subset [a,b]$ che non contiene zeri di alcun polinomio $p_i(x)$. Sia
%$f(x)$ una funzione continua su $[a,b]$ positiva su $[c,d]$ e nulla
%altrove. Per il teorema di Weierstrass (vedi pi\`u avanti) poich\'e $f(x)$ \`e
%continua su un compatto, per ogni $\epsilon>0$ esiste un polinomio
%$q_\epsilon(x)$ tale che $\max_{a\le x\le
%  b}|f(x)-q_\epsilon(x)|\le\epsilon$. Per cui, per ogni $k>0$ vale
%\[
%\int_a^b p_k(x)q_\epsilon(x)\omega(x)dx=\int_a^b 
%p_k(x)f(x)\omega(x)dx+\gamma_\epsilon,
%\]
%dove $\gamma_\epsilon=\int_a^b p_k(x)(q_\epsilon(x)-f(x))\omega(x)dx$. Quindi
%$|\gamma_\epsilon|\le\epsilon\int_a^b|p_k(x)|\omega(x)dx$.

Vale il seguente risultato di minima norma

\begin{teo}
Tra tutti i polinomi $p(x)$ di grado $n$ che hanno coefficiente del termine di grado massimo uguale a quello di $p_n(x)$, il polinomio $p_n(x)$ \`e quello di minima norma.
\end{teo}
 {\bf Dim.} Ogni polinomio $q$ di grado $n$ che ha lo stesso coefficiente di grado massimo di $p_n(x)$ si lascia scrivere come $q=p_n(x)+q_{n-1}(x)$, dove $q_{n-1}(x)$ \`e un polinomio di grado al pi\`u $n-1$. Vale quindi 
\[
\|q\|^2=\langle q,q\rangle=\langle p_n,p_n\rangle+\langle q_{n-1},q_{n-1}\rangle
\]
essendo $\langle q_{n-1},p_n\rangle=0$ per l'ortogonalit\`a. Risulta allora
$\|q\|^2\ge\|p_n\|^2$ dove l'uguaglianza \`e raggiunta se e solo se $q_{n-1}=0$ cio\`e $q=p$.\qed

Un'altra conseguenza del teorema \ref{th:ort} \`e data dal seguente risultato che ha rilevanza sia teorica che computazionale.

\begin{teo}[Ricorrenza a tre termini]\label{theo:tret}
Siano $p_i(x)$, $i=0,1,\ldots$, un insieme di polinomi ortogonali su $[a,b]$
rispetto a un prodotto scalare \eqref{prodscal}. Si denoti $p_0(x)=a_0$,
$p_1(x)=a_1 x+b_1$.
Esistono $A_i,B_i,C_i\in\R$ tali che
\[
p_{i+1}(x)=(xA_{i+1}+B_{i+1})p_i(x)-C_ip_{i-1}(x),~~i\ge 1,~~~A_{i+1},C_i\ne 0.
\]
Inoltre 
\[\begin{split}
A_{i+1}&=\frac{\left\langle p_{i+1},p_{i+1} \right\rangle }{\left\langle xp_i,p_{i+1} \right\rangle },~~B_{i+1}=-A_{i+1}\frac{\left\langle xp_i,p_i \right\rangle }{
  \left\langle p_i,p_i \right\rangle },\\
&C_i=A_{i+1}\frac{\left\langle xp_i,p_{i-1} \right\rangle }{\left\langle p_{i-1},p_{i-1} \right\rangle }=\frac{A_{i+1}}{A_i}\frac {\left\langle p_i,p_i \right\rangle }{\left\langle p_{i-1},p_{i-1} \right\rangle }.
\end{split}
\]
Denotando con $a_i$ e $b_i$ rispettivamente
i coefficienti di $x^i$ e $x^{i-1}$ in $p_i(x)$, vale
$A_{i+1}=\frac{a_{i+1}}{a_i}$, $B_{i+1}=\frac{a_{i+1}}{a_i}
(\frac{b_{i+1}}{a_{i+1}}-\frac{b_i}{a_i})$,
  $C_i=\frac{a_{i+1}a_{i-1}}{a_i^2}\frac{h_i}{h_{i-1}}$, dove
$h_i=\left\langle p_i,p_i \right\rangle$. 
\end{teo}
{\bf Dim.} Il polinomio $xp_i(x)$ ha grado $i+1$ per cui $xp_i,p_i,\ldots,p_0$
sono linearmente indipendenti. Esistono allora $\alpha_0,\alpha_1,\ldots,\alpha_{i+1}\in\R$ tali che
\[
p_{i+1}=\alpha_0p_0+\cdots+\alpha_ip_i+\alpha_{i+1}xp_i.
\]
Per $j\ne i+1$ vale
\[
0=\left\langle p_j,p_{i+1} \right\rangle =\alpha_j\left\langle p_j,p_j \right\rangle +\alpha_{i+1}\left\langle p_j,xp_i \right\rangle =
\alpha_j\left\langle p_j,p_j \right\rangle +\alpha_{i+1}\left\langle xp_j,p_i \right\rangle .
\]
Poich\'e se $j\le i-2$ il polinomio $xp_j$ ha grado minore di $i$, per il
teorema \ref{th:ort} \`e $\left\langle xp_j,p_i \right\rangle =0$. Quindi $\alpha_j=0$ per
$j=0,\ldots,i-2$ per cui
\begin{equation}\label{tmp1}
p_{i+1}=\alpha_{i+1}xp_i+\alpha_ip_i+\alpha_{i-1}p_{i-1}.
\end{equation}
Vale quindi il risultato del teorema con $A_{i+1}=\alpha_{i+1}$, $B_{i+1}=\alpha_i$
$C_i=-\alpha_{i-1}$.
Le costanti $A_i,B_i,C_i$  possono essere facilmente espresse in termini di prodotti scalari. Infatti  moltiplicando scalarmente per $p_{i+1}, p_i$ e $p_{i-1}$ entrambi i membri della
\eqref{tmp1} si ottiene 
\[
\begin{split}
&\langle 
p_{i+1},p_{i+1}\rangle=A_{i+1}\langle xp_i,p_{i+1}\rangle,\\
&A_{i+1}\langle xp_i,p_i\rangle +B_{i+1}\langle p_i,p_i\rangle=0\\
&A_{i+1}\langle p_{i-1},xp_i\rangle-C_i\langle p_{i-1},p_{i-1}\rangle=0
\end{split}
\]
da cui $\langle xp_i(x),p_{i+1}(x)\rangle\ne 0$ e si ricavano le
espressioni per $A_{i+1},B_{i+1},C_i$. Le altre relazioni seguono da
un confronto diretto dei polinomi. Inoltre, poich\'e $\langle p_{i+1},p_{i+1}\rangle\ne 0$ ne segue che $A_{i+1}\ne 0$, inoltre dall'espressione $C_i=\frac{A_{i+1}}{A_i}\frac{\langle p_i,p_i\rangle}{\langle p_{i-1,},p_{i-1}\rangle}$ segue $C_i\ne 0$. \qed


\begin{oss}\rm
Poich\'e i polinomi del teorema \ref{theo:tret} sono definiti a meno di una
costante moltiplicativa, possiamo scegliere i polinomi monici in modo che
$a_i=1$ per ogni $i\ge 1$ per cui $A_i=1$ per $i\ge 1$.
In questo modo risulta
\[
A_{i+1}=1,~~B_{i+1}=-\frac{\left\langle xp_i,p_i \right\rangle }{\left\langle p_i,p_i \right\rangle },~~C_i=\frac{\left\langle p_i,p_i \right\rangle }{\left\langle p_{i-1},p_{i-1} \right\rangle }>0.
\] 
\qed\end{oss}

\begin{oss}\rm
Si noti che la relazione a tre termini data nel teorema
\ref{theo:tret} ci dice che $p_{i-1}(x)$ \`e il resto della divisione
di $p_{i+1}(x)$ per $p_i(x)$.  Per cui i polinomi ortogonali
$p_{n+1}(x),p_n(x),\ldots,p_0(x)$ possono essere visti come i polinomi
generati dall'algoritmo Euclideo applicato a $p_{n+1}(x)$ e $p_n(x)$.
\qed\end{oss}

\begin{oss}\rm
Fissato $i$, i coefficienti $A_{i+1}=1$, $B_{i+1}$, $C_i$ richiedono
il calcolo dei prodotti scalari $\langle p_i,p_i\rangle$, $\langle
p_{i-1},p_{i-1}\rangle$, $\langle xp_i,p_i\rangle$. Per cui il loro
calcolo per $i=1,\ldots, k$ comporta solamente $2k$ prodotti scalari.

Per calcolare il valore di $p_k(\xi)$ usando la relazione a tre
termini, supponendo di avere a disposizione i coefficienti
$A_{i+1}=1$, $B_{i+1}$ e $C_i$ e di aver caclolato i valori $p_i(\xi)$
per $i=0,\ldots,k-1$, bastano $4$ operazioni aritmetiche. Quindi per
calcolare tutti i valori $p_i(\xi)$ per $i=1,\ldots, k$ bastano $4k$
operazioni aritmetiche.

In modo analogo si vede che i coefficienti di tutti i polinomi
ortogonali di grado al pi\`u $k$ sono calcolabili in $O(k^2)$
operazioni.

Un confronto col metodo di ortogonalizzazione di Gram-Schmidt mostra
che l'uso della relazione ricorrente a tre termini abbassa
sostanzialmente i costi computazionali delle operazioni con polinomi
ortogonali.
\qed\end{oss}

\begin{teo}[Formula di Christoffel-Darboux]
Vale
\begin{equation}\label{eq:chd}
(x-y)\sum_{i=0}^n\frac 1{h_i}p_i(x)p_i(y)=\gamma_n
\left[
p_{n+1}(x)p_n(y)-p_{n+1}(y)p_n(x)\right]
\end{equation}
dove $\gamma_n=\frac{a_n}{a_{n+1}h_n}=\frac 1{h_n A_{n+1}}$, 
$h_i=\left\langle p_i,p_i \right\rangle $.
\end{teo}
{\bf Dim.} Procediamo per induzione. 
Se $n=0$ allora devo dimostrare che 
$(x-y)\frac 1{h_0}p_0(x)p_0(y)=
\frac{a_0}{a_1h_0}\left[p_1(x)p_0(y)-p_1(y)p_0(x)\right]$.
Poich\'e $p_0(x)=a_0$, e $p_1(x)=a_1x+b_1$, allora il secondo membro della relazione precedente diventa 
\[
\frac{a_0}{a_1h_0}\left[(a_1x+b_1)a_0-(a_1y+b_1)a_0\right]\\
=\frac{a_0}{a_1h_0}a_1(x-y)a_0,
\]
che coincide con $\frac{a_0^2}{h_0}(x-y)$.

Per l'implicazione $n-1\to n$, consideriamo il secondo membro di
\eqref{eq:chd} dove sostituiamo al posto di $p_{n+1}(x)$ e di
$p_{n+1}(y)$ l'espressione ottenuta con la relazione a tre termini. Si
ottiene quindi
\[\begin{split}
\gamma_n  \left[((xA_{n+1}+B_{n+1})\right. & p_{n}(x)-C_np_{n-1}(x))p_n(y)\\
 & -\left.((yA_{n+1}+B_{n+1})p_{n}(y)-C_np_{n-1}(y))p_n(x)\right].
\end{split}
\]
Semplificando si arriva a
\[
(x-y)\gamma_nA_{n+1}p_{n}(x)p_n(y) +\gamma_nC_n(p_n(x)p_{n-1}(y)-p_n(y)p_{n-1}(x))
\]
Per l'ipotesi induttiva il secondo addendo coincide con
\[
\frac{C_n\gamma_n}{\gamma_{n-1}}(x-y)\sum_{i=0}^{n-1}\frac
1{h_i}p_i(x)p_i(y).
\]
 La tesi segue dal fatto che $\frac
{\gamma_nC_n}{\gamma_{n-1}}=1$ e $\gamma_nA_{n+1}=1/h_{n}$, per la
definizione di $\gamma_n$ e per le relazioni date nel teorema
\ref{theo:tret}.
\qed

\begin{oss}\rm
Una dimostrazione alternativa della formula di Christoffel-Darboux \`e la seguente.
Vale
{\small
\[\begin{array}{ll}
p_{i+1}(x)=(A_{i+1}x+B_{i+1})p_i(x)-C_ip_{i-1}(x) & \hbox{moltiplico per
}p_i(y)
\\[1ex]
p_{i+1}(x)p_{i}(y)=(A_{i+1}x+B_{i+1})p_i(x)p_i(y)-C_ip_{i-1}(x)p_i(y) &
\hbox{scambio variabili}
\\[1ex]
p_{i+1}(y)p_{i}(x)=(A_{i+1}y+B_{i+1})p_i(y)p_i(x)-C_ip_{i-1}(y)p_i(x) &
\hbox{sottraggo}
\\[1ex]
p_{i+1}(x)p_{i}(y)-p_{i+1}(y)p_{i}(x)\\
\phantom{p_{i+1}(y)p_{i}(x)}=p_i(x)p_i(y)[x-y]A_{i+1}-C_i[p_{i-1}(x)p_i(y)-p_{i-1}(y)p_i(x)]
\end{array}
\]
}
Quindi
\[
\begin{split}
[x-y]p_i(x)p_i(y)A_{i+1}&=p_{i+1}(x)p_i(y)-p_{i+1}(y)p_i(x)\\
                           &~~+C_i[p_{i-1}(x)p_i(y)-p_{i-1}(y)p_i(x)]\\
\frac1{h_i}[x-y]p_i(x)p_i(y)&=\frac
1{h_iA_{i+1}}[p_{i+1}(x)p_i(y)-p_{i+1}(y)p_i(x)]\\
&~~+\frac{C_i}{h_{i}A_{i+1}}[p_{i-1}(x)p_i(y)-p_{i-1}(y)p_i(x)]
\end{split}
\]
dove $C_i=(h_i/h_{i-1})(A_{i+1}/A_i)$. Si ottiene allora
\[\begin{split}
\frac 1{h_i}[x-y]p_i(x)p_i(y)&=\frac
1{h_iA_{i+1}}[p_{i+1}(x)p_i(y)-p_{i+1}(y)p_i(x)]\\
&+\frac{1}{h_{i-1}A_i}[p_{i-1}(x)p_i(y)-p_{i-1}(y)p_i(x)]
\end{split}\]
Sommando, i termini si elidono a due a due e si ottiene la tesi.
\qed\end{oss}

\begin{oss}\rm
Applicando la formula di Christoffel Darboux per $x=x_i$ e $y=x_j$, dove
$x_1,\ldots,x_{n+1}$ sono gli zeri di $p_{n+1}(x)$, si ottiene
\[
\sum_{k=0}^n \frac 1{h_k}p_k(x_i)p_k(x_j)=0,~~i\ne j.
\]
Inoltre $\sum_{k=0}^{n+1}p_k(x_i)^2/h_k\ne 0$ essendo $p_0(x_i)^2/h_0=a_0^2/h_0>0$.
La matrice $V=(v_{i,j})_{i,j=1,n+1}$, $v_{i,j}=p_{i-1}(x_j)/\sqrt{h_{i-1}}$ 
\`e tale che $V^TV$ \`e una matrice diagonale. Cio\`e $V$ ha le colonne $v_{.j}$ ortogonali. Possiamo scalare le colonne in modo da farle diventare ortonormali, basta per questo dividerle per la loro norma euclidea. Posto
\[
\sigma_j=1/\|v_{.j}\|^2,\quad  \|v_{.j}\|^2=\sum_{i=0}^n\frac{p_i(x_j)^2}{h_i},
\]
 la matrice $W=V\hbox{diag}(\sigma_1,\ldots,\sigma_{n+1})$ ha colonne
 ortonormali e verifica la propriet\`a $W^TW=I$ per cui \`e ortogonale
 e quindi $WW^T=I$. Quest'ultima relazione si scrive come
 $\sum_{k=1}^{n+1} w_{i,k}w_{j,k}=\delta_{i,j}$, da cui
\begin{equation}\label{eq:ortogdisc}
\sum_{k=1}^{n+1}\frac{p_i(x_k)}{\sqrt{h_i}}\frac{p_j(x_k)}{\sqrt{h_j}}\sigma_k=\delta_{i,j},
\quad \sigma_k=1/\sum_{s=0}^n\frac {p_s(x_k)^2}{h_s}.
\end{equation}


Questa espressione fornisce una sorta di {\em ortogonalit\`a
  ``discreta''} dei polinomi $p_i(x)$ relativa ai punti $x_k$ e ai
pesi $\sigma_k$.  In particolare, se associamo ai polinomi $p_j(x)$ i
vettori $\bm u^{(j)}=(u^{(j)}_i)$ per $j=0,\ldots,n$, ottenuti campionando
i polinomi ortonormali negli zeri di $p_{n+1}(x)$, cio\`e tali che
$u^{(j)}_i=p_j(x_i)/\sqrt{h_j}$, abbiamo che $\bm u^{(0)},\ldots,\bm u^{(n)}$ sono
ortonormali rispetto al prodotto scalare (discreto pesato)
\[
\langle \bm y,\bm z\rangle=\sum_{i=1}^{n+1} y_iz_i\sigma_i.
\]
\qed\end{oss}

\begin{oss}[Formule di integrazione Gaussiana]\rm
Se su uno spazio vettoriale $\mathcal V_{n+1}$ di dimensione $n+1$ sono
assegnati due prodotti scalari $\langle\cdot,\cdot\rangle'$ e
$\langle\cdot,\cdot\rangle''$ che coincidono su una base
$v_1,\ldots,v_{n+1}$ di $\mathcal V_{n+1}$, cio\`e $\langle
v_i,v_j\rangle'=\langle v_i,v_j\rangle''$, allora tali prodotti
scalari coincidono dappertutto, cio\`e $\langle u, v\rangle' =\langle
u, v\rangle''$ per ogni $u,v\in\mathcal V_{n+1}$. Questo pu\`o essere
facilmente dimostrato rappresentando $u$ e $v$ nella base
$v_1,\ldots,v_{n+1}$ e applicando la bilinearit\`a del prodotto scalare.

Se consideriamo allora come $\mathcal V_{n+1}$ lo spazio dei polinomi di
grado al pi\`u $n$ abbiamo che i due prodotti scalari $\langle
u,v\rangle'=\int_a^b u(x)v(x)\omega(x)dx$ e
$\langle u(x),v(x)\rangle''=\sum_{k=1}^{n+1}u(x_k)v(x_k)\sigma_k$, dove
$x_k$ per $k=1,\ldots,n+1$ denotano gli zeri del polinomio ortogonale $p_{n+1}$
di grado $n+1$, coincidono sulla base dei polinomi ortogonali.  Quindi
coincidono dappertutto. In particolare, se $u(x)$ e $v(x)$ sono
polinomi di grado al pi\`u $n$ si ha
\begin{equation}\label{eq:ortdisc}
\int_a^b u(x)v(x)\omega(x)dx=\sum_{k=1}^{n+1} u(x_k)v(x_k)\sigma_k.
\end{equation}
Questa propriet\`a permette di dimostrare che per ogni polinomio
$g(x)$ di grado al pi\`u $2n+1$ vale
\[
\int_a^b g(x)\omega(x)dx=\sum_{k=1}^{n+1}g(x_k)\sigma_k.
\]
Cio\`e la formula di integrazione discreta 
\[
\int_a^bf(x)\omega(x)dx\approx \sum_{k=1}^{n+1}f(x_k)\sigma_k
\]
per approssimare l'integrale di una funzione $f(x)$, detta formula di
integrazione Gaussiana, \`e esatta per ogni polinomio di grado al
pi\`u $2n+1$, o come si suole dire, ha grado di precisione $2n+1$.
Per dimostrare questo basta scrivere $g(x)$ come
\[
g(x)=p_{n+1}(x)q(x)+r(x)
\]
dove $q(x)$ \`e il quoziente e $r(x)$ il resto della divisione di
$g(x)$ per $p_{n+1}(x)$. In questo modo il grado di $q(x)$ e il grado
di $r(x)$ sono al pi\`u $n$ e inoltre vale $g(x_j)=r(x_j)$,
$j=1,\ldots,n+1$ essendo $p_{n+1}(x_j)=0$, per $j=1,\ldots,n+1$.  Si
osserva allora che moltiplicando entrambi i membri della relazione
precedente per $\omega(x)$ e integrando su $[a,b]$ si ha
\[
\int_a^b g(x)\omega(x)dx=\langle p_{n+1}(x)q(x)\rangle+\langle 1,r(x)\rangle.
\]
Il primo addendo del membro destro \`e nullo essendo $p_{n+1}$
ortogonale a $q(x)$. Applicando la \eqref{eq:ortdisc} con $u(x)=1$ e
$v(x)=r(x)$, e ricordando che il grado di $r(x)$ \`e al pi\`u $n$, si
ottiene che il secondo addendo coincide con
$\sum_{k=1}^{n+1}r(x_k)\sigma_k= \sum_{k=1}^{n+1}g(x_k)\sigma_k$.
\qed\end{oss}

\begin{oss}\label{oss:bezout}\rm
Dati due polinomi $u(x)$ e $v(y)$  il {\em bezoutiano} $B(x,y)$ di
$u(x)$ e $v(x)$ \`e il polinomio in due variabili
$(u(x)v(y)-u(y)v(x))/(x-y)$. Il bezoutiano ha diverse particolarit\`a
interessanti che sono utili in computer algebra.  La formula di
Cristoffel-Darboux aggiunge una ulteriore propriet\`a: se $u$ e $v$
sono polinomi ortogonali di grado $n+1$ e $n$ il loro bezoutiano \`e
somma di prodotti di polinomi ortogonali.  Si associa al bezoutiano
$B(x,y)$ la matrice $B=(b_{i,j})$ tale che
$B(x,y)=\sum_{i=1}^{n+1}\sum_{j=1}^{n+1}b_{i,j}x^{i-1}y^{j-1}$ chiamata {\em matrice
  bezoutiana}. \`E immediato verificare che $B$ \`e simmetrica e che
$B(x,y)=\bm x^T B\bm y$ dove $\bm x=(x^i)_{i=0,n-1}$, $\bm
y=(y^i)_{i=0,n-1}$. Poich\'e $p_k(x)p_k(y)=\bm x^T\bm p^{(k)}\bm
p^{(k)T}\bm y$, dove $\bm p^{(k)}$ \`e il vettore dei coefficienti del
polinomio $p_k(x)$, la formula di Christoffel Darboux permette di
scrivere la matrice bezoutiana di $p_n(x)$ e $p_{n+1}(x)$ come somma
delle $n$ diadi simmetriche $\frac 1{\gamma_nh_k}\bm p^{(k)}\bm p^{(k)T}$. La
stessa somma di diadi simmetriche permette di scrivere la matrice
bezoutiana come $\gamma_n B=L^TL$, dove $L$ \`e una matrice triangolare
inferiore che sulla riga $i$-esima ha i coefficienti del polinomio
$p_i(x)/\sqrt{h_i}$.

Una propriet\`a interessante della matrice bezoutiana di due polinomi
qualsiasi $u(x)$ e $v(x)$\`e che la sua fattorizzazione UL a blocchi
fornisce quozienti e resti generati dall'algoritmo euclideo applicato
a $u(x)$ e $v(x)$. Inoltre la matrice bezoutiana \`e non singolare se
e solo se i polinomi $u(x)$ e $v(x)$ sono primi tra loro.

Maggiori informazioni sul bezoutiano, per chi volesse approfondire, si trovano sui lavori:\\
H.K. Wimmer, ``On the History of the Bezoutian and the Resultant Matrix'',
{\em Linear Algebra Appl.} 128:27-34(1990),\\
U. Helmke, P.A. Fuhrmann, ``Bezoutians'', {\em Linear Algebra Appl.} 122--124:1039-1097(1989),\\
G. Heinig, K. Rost, Bezoutians, \url{https://www.tu-chemnitz.de/mathematik/preprint/.../PREPRINT_09.pdf}\\
Onorato Nicoletti, ``Sulla caratteristica delle matrici di Sylvester e di Bezout'', Da una lettera al Prof. Alfredo Capelli, 27 Dicembre 1908 
\url{http://link.springer.com/article/10.1007%2FBF03018209#page-1}
\qed\end{oss}


\subsection{Polinomi ortogonali e matrici tridiagonali}
Sia $T_n(x)$ la matrice definita da
\[
T_n(x)=\left[\begin{array}{ccccc}
a_1x+b_1&-a_0\\
-C_1&A_2x+B_2&-1\\
   &\ddots&\ddots&\ddots\\
   &      &\ddots&\ddots&-1\\
   &      &      &-C_{n-1}&A_nx+B_n
\end{array}
\right]
\]
Applicando la regola di Laplace per calcolare $\det T_n(x)$ lungo l'ultima riga
si scopre che
\[
\det T_n(x)=(A_nx+B_n)\det T_{n-1}(x)-C_{n-1}\det T_{n-2}(x)
\]
inoltre $\det T_1(x)=a_1x+b_1=p_1(x)$ e $\det T_2(x)=(A_2x+B_2)p_1(x)-C_1
p_0(x)$. 
Per cui vale $\det T_n(x)=p_n(x)$.

\`E interessante osservare che
\[
T_n(x)\left[\begin{array}{c}p_0(x)\\p_1(x)\\\vdots\\p_{n-1}(x)\end{array}\right]=
\left[\begin{array}{c}0\\\vdots\\0\\p_{n}(x)\end{array}\right]
\]
per cui il vettore di componenti $(p_i(x))_{i=0:n-1}$ sta nel nucleo di $T_n(x)$
se $x$ \`e uno zero di $p_n(x)$.

\begin{oss}\label{osstrid}\rm
Se i polinomi ortogonali vengono normalizzati in modo che $A_i=1$ allora gli
zeri di $p_n(x)$ possono essere visti come gli autovalori della matrice
$T_n:=-\hbox{trid}_n(-C_i,B_i,-1)$, dove per semplicit\`a di notazione si \`e posto
$B_1=b_1$,  e gli autovettori corrispondenti hanno per
componenti i valori dei polinomi ortogonali calcolati negli zeri di $p_n(x)$.
Vale infatti $T_n(x)=xI-T_n$. Si osservi ancora che la matrice ottenuta cambiando segno agli elementi sopra
e sotto diagonali ha gli stessi autovalori della matrice originale e
autovettori con componenti a segno alterno.
\qed\end{oss}

\begin{oss}\label{osssim}\rm Assumendo di aver normalizzato i polinomi in modo
  che $a_0=A_i=1$, $i=1,\ldots,n+1$,
 poich\'e i $C_i$ sono tutti positivi, \`e possibile determinare
  una matrice diagonale $D=\hbox{diag}_n(d_1,\ldots,d_n)$ tale che
  $D^{-1}T_nD$
\`e simmetrica. Tale matrice \`e data da $d_i=\sqrt{h_{i-1}}=\langle p_{i-1},p_{i-1}\rangle^{1/2}$, $i=1,\ldots,n-1$ e
vale
\[
D^{-1}T_{n}(x)D=\left[\begin{array}{ccccc}
b_1+x&-\sqrt{C_1}\\
-\sqrt{C_1}&B_2+x&-\sqrt{C_2}\\
           &\ddots&\ddots&\ddots\\
           &      &\ddots&\ddots&-\sqrt{C_{n-1}}\\
           &      &      &-\sqrt{C_{n-1}}&B_n + x
\end{array}
\right]
\]
Gli autovettori $\bm v^{(j)}$ tali che $D^{-1}T_{n+1}(x_j)D\bm v^{(j)}=0$ sono
$\bm v^{(j)}=D^{-1}\bm u^{(j)}$ con $\bm u^{(j)}=(p_0(x_j),\ldots,p_{n-1}(x_j))^T$, dove i polinomi ortogonali $p_i(x)$ sono monici. 
Dall'ortogonalit\`a dei vettori
$\bm v^{(j)}$ segue che  
\[
\sum_{k=0}^n\frac 1{h_k}p_k(x_i)p_k(x_j)=0,~~ i\ne j.
\]
Si osservi che $p_k(x)/\sqrt{h_k}$ \`e il polinomio ortogonale normalizzato
rispetto alla sua norma indotta dal prodotto scalare.
Questa propriet\`a era stata ottenuta anche dalla formula di Christoffel
Darboux.  
\qed\end{oss}

Le propriet\`a degli zeri dei polinomi ortogonali sono quindi strettamente
legate alle propriet\`a degli autovalori delle matrici tridiagonali
simmetriche.
Nel prossimo paragrafo riportiamo un teorema molto utile, di interesse
generale, che ci permette di scoprire propriet\`a interessanti degli zeri dei
polinomi ortogonali

\subsection{Il teorema del minimax di Courant-Fischer}
Data $A\in\R^{n\times n}$ simmetrica e $\bm x\in\R^n$, $\bm x\ne 0$ si definisce il
quoziente di Rayleigh di $A$ in $\bm x$ l'espressione
\[
\frac{\bm x^TA\bm x}{\bm x^T\bm x}
\]

\begin{oss}\rm Il gradiente del quoziente di Rayleigh \`e
\[
\frac{2}{\bm x^T\bm x}(A-\lambda I)\bm x,~~~~\lambda=\frac{\bm x^TA\bm x}{\bm
  x^T\bm x}.
\]
\qed\end{oss}

Quindi i punti stazionari del quoziente di Rayleigh sono gli autovettori di
$A$ e i valori presi dal quoziente in corrispondenza dei punti stazionari sono
i corrispondenti autovalori. Questo porta al seguente primo risultato

\begin{teo}
Siano $\lambda_1\ge\cdots\ge\lambda_n$ gli autovalori della matrice
simmetrica $A\in\R^{n\times n}$. Vale
\[
\max_{\bm x\ne 0}\frac{\bm x^TA\bm x}{\bm x^T\bm x}=\lambda_1,~~
\min_{\bm x\ne 0}\frac{\bm x^TA\bm x}{\bm x^T\bm x}=\lambda_n.~~
\]
\end{teo}

Si pu\`o dimostrare molto di pi\`u:

\begin{teo}[Teorema di Courant-Fischer del minimax]
Vale
\[
\min_{\small \begin{array}{c} U\subset\R^n\\ \hbox{\rm dim}\,U=k\end{array}} \max_{\small
\begin{array}{c}\bm x\in U\\\bm x\ne 0\end{array}} 
\frac{\bm x^TA\bm x}{\bm x^T\bm x}=\lambda_{n-k+1},~~k=1,2,\ldots,n
\]
\[
\max_{\small\begin{array}{c} U\subset\R^n\\ \hbox{\rm dim}\,U=k\end{array}} \min_{
\small\begin{array}{c}\bm x\in U\\\bm x\ne 0\end{array}} 
\frac{\bm x^TA\bm x}{\bm x^T\bm x}=\lambda_{k},~~k=1,2,\ldots,n
\]
\end{teo}
{\bf Dim.} Si dimostra la versione maxmin. Siano $\bm x_i$ gli autovettori di
$A$ ortonormali e $S$=span$(\bm x_k,\ldots,\bm x_n)$. Allora per ogni
sottospazio $V_k$ di dimensione $k$ vale $S\cap V_k\ne\{0\}$ poich\'e
dim(S)=$n-k+1$ e dim$(V_k)=k$. Allora esiste $\bm x\in S\cap V_k$, $\bm
x=\sum_{i=k}^n \alpha_i\bm x_i\ne 0$. Vale
\[
\frac{\bm x^TA\bm x}{\bm x^T\bm
  x}=\frac{\sum_{i=k}^n|\alpha_i|^2\lambda_i}{\sum_{i=k}^n|\alpha_i|^2}\le
\lambda_k\frac{ \sum_{i=k}^n|\alpha_i|^2}{\sum_{i=k}^n|\alpha_i|^2}=\lambda_k.
\]
Quindi il minimo su ogni $V_k$ del quoziente di Rayleigh \`e minore o uguale a
$\lambda_k$ e quindi anche il massimo al variare di $V_k$ dei minimi \`e
minore o uguale a $\lambda_k$. Basta quindi fare vedere che esiste un
$\widehat V_k$
speciale in cui il minimo del quoziente di Rayleigh vale $\lambda_k$. Per
questo basta scegliere $\widehat V_k=$span$(\bm x_1,\ldots,\bm x_k)$.
Infatti per $\bm x\in \widehat V_k$ risulta $\bm x=\sum_{i=1}^k \alpha_i \bm x_i$ per cui
\[
\bm x^TA\bm x/\bm x^T\bm x=\sum_{i=1}^k \lambda_i\alpha_i^2\bm x_i^T\bm x_i/\sum_{i=1}^k\alpha_i^2 
\bm x_i^T\bm x_i\ge \lambda_k.
\]
 La versione MinMax del teorema si ottiene applicando
la versione MaxMin alla matrice $-A$.\qed

Alcuni corollari interessanti del teorema del minimax.

\begin{cor}
$A$ matrice reale simmetrica $n\times n$ di autovalori
  $\alpha_1\ge\cdots\ge\alpha_n$. $U\in\R^{n\times(n-1)}$ tale che
  $U^TU=I_{n-1}$.
Allora gli autovalori $\beta_1\ge\cdots\ge \beta_{n-1} $ di $B=U^TAU$ sono
tali che
\[
\alpha_1\ge\beta_1\ge\alpha_2\ge\beta_2\ge\cdots\ge\beta_{n-1}\ge\alpha_n.
\]
e si dice che gli autovalori di $B$ separano gli autovalori di $A$.
\end{cor}
{\bf Dim.} Vale
\[
\beta_k=\max_{W_k}\min_{\bm y\in W_k\backslash 0}\frac{\bm y^TB\bm y}{\bm
  y^T\bm y}=\min_{\bm y\in\widehat W_k\backslash 0}\frac{\bm y^TB\bm y}{\bm
  y^T\bm y}=\min_{\bm y\in\widehat W_k\backslash 0}\frac{\bm y^TU^TAU\bm y}{\bm
  y^T\bm y}
\]
dove $\widehat W_k$ \`e il sottospazio dove viene preso il massimo. Sia
\[
\widehat V_k=\{\bm x\in\R^n:\quad \bm x=U\bm y, \bm y\in\widehat W_k\}.
\] 
Vale dim$(\widehat V_k)=k$ e 
\[
\frac{\bm y^TU^TAU\bm y}{\bm
  y^T\bm y}=\frac{\bm x^TA\bm x}{\bm x^T\bm x}
\]
per cui
\[
\beta_k=\min_{\bm y\in\widehat W_k\backslash 0}\frac{\bm y^TU^TAU\bm y}{\bm
  y^T\bm y}=\min_{\bm x\in\widehat V_k\backslash 0}\frac{\bm x^TA\bm x}{\bm
  x^T\bm x}\le\max_{V_k}\min_{\bm x\in V_k\backslash 0}\frac{\bm x^TA\bm x}{\bm
  x^T\bm x}=\alpha_k.
\]
La diseguaglianza $\beta_{k-1}\ge \alpha_k$ si ottiene applicando il risultato
a $-A$ e $-B$. \qed




\begin{cor}\label{corsep}
Se $A_n$ \`e matrice tridiagonale simmetrica, gli autovalori di una qualsiasi
 sottomatrice
principale di $A_n$ di dimensione $(n-1)\times(n-1)$ separano gli autovalori di
$A$. 
%Se poi $A_n$ \`e anche irriducibile, gli autovalori della sottomatrice
%principale $A_{n-1}$
%ottenuta da $A_n$ togliendo ultima (o prima) riga e colonna separano gli
% autovalori di $A_n$ con diseguaglianze strette.
\end{cor}

Come conseguenza del teorema del minimax segue l'importante propriet\`a degli
zeri dei polinomi ortogonali

\begin{teo} 
Gli  zeri del polinomio
ortogonale $p_n(x)$ separano strettamente gli zeri del polinomio ortogonale $p_{n+1}(x)$.
\end{teo}
{\bf Dim.}
La separazione con diseguaglianza debole segue dal corollario \ref{corsep}
applicato alla matrice tridiagonale simmetrica ottenuta simmetrizzando la
matrice trid$_n(-C_i,B_i,-1)$ alla luce delle osservazioni \ref{osstrid},
\ref{osssim}. Per dimostrare la diseguaglianza stretta si supponga per assurdo
che $\lambda$ sia zero di $p_n$ e di $p_{n-1}$. Dalla relazione a tre termini
segue che $\lambda$ \`e zero di $p_{n-1}$. Procedendo per induzione si
conclude che $\lambda$ \`e zero di $p_0$ che \`e assurdo.\qed

Si riportano a titolo di curiosit\`a due altri corollari di cui non si d\`a
dimostrazione.

\begin{cor}
Se $A,B,C$ sono matrici reali simmetriche tali che $A=B+C$ allora per gli
autovalori $\alpha_i,\beta_i,\gamma_i$ ordinati in modo non crescente vale
\[
\beta_i+\gamma_n\le\alpha_i\le\beta_i+\gamma_1.
\]
\end{cor}


\begin{cor}
Se $A,B,C$ sono matrici reali simmetriche tali che $A=B+C$ 
e $C=\bm u\bm u^T$ per un vettore nonnullo $\bm u$,
allora per gli
autovalori $\alpha_i,\beta_i$ di $A$ e $B$ ordinati in modo non crescente vale
\[
\beta_i\le\alpha_i\le\beta_{i+1}
\]
\end{cor}

\section{Rappresentazione di polinomi ortogonali}
Oltre alla rappresentazione data mediante la relazione ricorrente a tre termini esistono altri modi per rappresentare i polinomi ortogonali. In questo paragrafo esaminiamo due rappresentazioni diverse, quella basata sulla matrice dei momenti e quella data dalla formula di Rodrigues.
\subsection{Matrice dei momenti}
Le quantit\`a $\mu_k=\int_a^bx^k\omega(x)dx$, $k=0,1,\ldots,n$, vengono dette
{\em momenti}. Vale il seguente risultato
\begin{teo}
I seguenti polinomi sono ortogonali rispetto al prodotto scalare $\langle
f,g\rangle=\int_a^bf(x)g(x)\omega(x)dx$
\begin{equation}\label{hankel}
p_n(x)=\det\left[\begin{array}{ccccc}
\mu_0&\mu_1&\mu_2&\ldots&\mu_n\\
\mu_1&\mu_2&\mu_3&\ldots&\mu_{n+1}\\
\mu_2&\mu_3&\mu_4&\ldots&\mu_{n+2}\\
\vdots&\vdots&\vdots&\ldots&\vdots\\
\mu_{n-1}&\mu_{n}&\mu_{n+1}&\ldots&\mu_{2n-1}\\
1&x&x^2&\ldots&x^n
\end{array}\right]
\end{equation}
\end{teo}
{\bf Dim.} Basta verificare che $\langle x^k,p_n(x)\rangle=0$ per
$k=0,1,\ldots,n-1$. Per la linearit\`a dell'integrale e la multilinearit\`a
del determinante si ha che $\langle x^k,p_n(x)\rangle$ \`e uguale al
determinante della matrice che si ottiene sostituendo l'ultima riga della
matrice in \eqref{hankel} con $(\int_a^b x^k, \int_a^b
x^{k+1},\ldots,\int_a^b x^{k+n})$, cio\`e
$(\mu_k,\mu_{k+1},\ldots,\mu_{k+n})$. Questo determinante \`e nullo poich\'e la
matrice ha due righe uguali.\qed 

\begin{oss}\rm Col prodotto scalare su $[0,1]$ definito da $\langle f,g\rangle=\int_0^1f(x)g(x)dx$, la sottomatrice principale di testa $n\times n$
della matrice dei momenti \`e la matrice di Hilbert di elementi
$(1/(i+j-1))$ per $i,j=1,\ldots,n$. Le sottomatrice principali di testa
di dimensione minore o uguale a $n$ di una matrice dei momenti sono
{\em matrici di Hankel}. Cio\`e i loro elementi dipendono dalla somma
degli indici e quindi sono costanti lungo le anti-diagonali. Si pu\`o
dimostrare che l'inversa di una matrice di Hankel non singolare \`e
una matrice di Bezout.
\qed\end{oss}

\begin{oss}\rm
Si ricorda che se $A$ \`e una matrice reale simmetrica definita positiva allora l'applicazione $(u,v)\to u^TAv$ da $\R^n\times\R^n$ in $\R$ \`e un prodotto scalare. Se denotiamo $H_n$ la matrice di elementi $\mu_{i+j-2}$, $i,j=1,\ldots,n$,
si ha $\mu_{i+j-2}=\langle x^{i-1},x^{j-1}\rangle$ per $i,j=1,\ldots,n$.
Per cui
$u^TH_nv=\sum_{i}\sum_{j}u_i\mu_{i+j-1}v_j=\langle\sum_i u_ix^{i-1},\sum_j v_jx^{j-1}\rangle$ non \`e altro he il prodotto scalare tra il polinomio di coefficienti $u_1,\ldots,u_{n}$ e il polinomio di coefficienti $v_1,\ldots,v_n$. Cio\`e $H_n$ descrive il prodotto scalare di tipo integrale 
tra polinomi in termini dei loro coefficienti.

Si osserva ancora che se $H_n=LL^T$ \`e la fattorizzazione di Cholesky
di $H_n$, dove $L$ \`e triangolare inferiore $n\times n$, allora dalla
condizione $(L^{-1})^TH_nL^{-1}=I$ segue che le righe di $(L^{-1})^T)$
sono i coefficienti dei polinomi ortogonali normalizzati in modo da
avere norma 1. Avevamo inoltre puntualizzato nell'Osservazione
\ref{oss:bezout}, come conseguenza della formula di Christoffel
Darboux, che la matrice di Bezout $B_n$ di $p_n(x)$ e $p_{n-1}(x)$ si
fattorizza nel prodotto $B=\widehat L^T\widehat L$ dove $\widehat L$
\`e triangolare inferiore e le colonne di $L$ hanno per elementi i
coefficienti del generico polinomio ortogonale normalizzato per cui
vale $\widehat L=L^{-1}$. Allora, confrontando la relazione $=\widehat
L^T\widehat L$ e $H^{-1}=(L^{-1})^TL^{-1}$ si deduce che
$H_n=B_n^{-1}$.
\qed\end{oss}

\subsection{Formula di Rodrigues}
\begin{teo}
Sia $s(x)\in C^n[a,b]$, $s^{(k)}(a)=s^{(k)}(b)=0$, $k=0,1,\ldots,n-1$. Allora
la funzione $t(x)= s^{(n)}(x)/\omega(x)$ \`e ortogonale a ogni polinomio di grado al pi\`u
$n-1$ col prodotto scalare $\left\langle f,g \right\rangle =\int_a^bf(x)g(x)\omega(x)dx$.
\end{teo}
{\bf Dim.} Sia $q(x)$ polinomio di grado $k\le n-1$. Allora
$\left\langle q,s^{(n)}/\omega(n) \right\rangle =\int_a^b
\omega(x)q(x)\frac{s^{(n)}}{\omega(x)}dx=\int_a^b
q(x)s^{(n)}(x)dx$. Integrando per parti si ha
\[
\begin{split}
\left\langle q,\frac{s^{(n)}(x)}{\omega(x)} \right\rangle &=[q(x)s^{(n-1)}(x)]_a^b-\int_a^b
  q'(x)s^{(n-1)}(x)dx\\&=-\int_a^bq'(x)s^{(n-1)}(x)dx=\cdots=(-1)^n\int_a^b
  q^{(n)}(x)s(x)dx=0
\end{split}
\]
poich\'e $q^{(n)}=0$ essendo il grado di $q$ minore di $n$.\qed



\begin{oss}\rm Nelle ipotesi del teorema, se $s^{(n)}(x)/\omega(x)$ \`e un
      polinomio di grado $n$ allora esso coincide con $p_n(x)$.
\qed\end{oss}

Ci\`o permette di esprimere i polinomi ortogonali mediante la {\em Formula di
  Rodrigues}
\begin{equation}\label{rodrigues}
\begin{split}
&p_n(x)=\frac{\beta_n}{\omega(x)}\frac{d^n}{dx^n}s_n(x),~~n=0,1,\ldots,\\
&\beta_n\in\R,~~s_n(x)\in C^n[a,b],:~s_n^{(k)}(a)=s_n^{(k)}(b)=0,
  ~k=0,1,\ldots,n-1,\\
&\frac 1{\omega(x)}\frac{d^n}{dx^n} s_n(x),~~\hbox{polinomio di grado }n.
\end{split}
\end{equation}

I valori dei $\beta_n$ sono scelti in modo da normalizzare i polinomi in modo
pi\`u conveniente a seconda dei casi.

%Esercizio: verificare che $h_i=\left\langle p_i,p_i \right\rangle =(-1)^ia_i\beta_i i!\int_a^b s_i(x)dx$


%\subsection{Polinomi ortogonali e equazioni differenziali}
%Si consideri il seguente problema differenziale agli autovalori
%\[
%q(x)f''+\ell(x)f'+\lambda f=0
%\]
%dove $q(x)$ \`e un polinomio di grado al pi\`u 2
% e $\ell(x)$ \`e un polinomio di grado 1.


\section{Polinomi ortogonali specifici}
Nella tabella \ref{tab1} si riportano le definizioni dei polinomi ortogonali
classici
di Legendre, Chebyshev di prima e di seconda specie, Laguerre ed Hermite.

\begin{table}\begin{center}
\begin{tabular}{cccc}
\hline
$[a,b]$&$\omega(x)$&$s_n(x)$&Nome\\
\hline
$[-1,1]$&1&$(1-x^2)^n$&Legendre\\
$[-1,1]$&$(1-x^2)^{-1/2}$&$(1-x^2)^{n-1/2}$&Chebyshev di prima
specie\\
$[-1,1]$&$(1-x^2)^{1/2}$&$(1-x^2)^{n+1/2}$&Chebyshev di seconda
specie\\
$[0,+\infty]$&$e^{-x}$&$e^{-x}x^n$& Laguerre\\
$[-\infty,+\infty]$&$e^{-x^2}$&$e^{-x^2}$&Hermite\\
\hline
\end{tabular}
\caption{Tassonomia dei principali polinomi ortogonali}\label{tab1}
\end{center}
\end{table}

I polinomi di Legendre e di Chebyshev sono casi particolari dei 
{\em polinomi ultrasferici}, noti anche come polinomi di {\em Gegenbauer}
 cio\`e i polinomi ortogonali su $[-1,1]$ rispetto al peso
$\omega=(1-x^2)^\alpha$, $\alpha>-1$.
Per questi polinomi \`e possibile dare una espressione dei coefficienti in
termini della funzione $\Gamma$ di Eulero
\url{http://en.wikipedia.org/wiki/Gamma_function}
\[
\Gamma(x)=\int_0^{+\infty} t^{x-1}e^{-t}dt,~~x>0.
%~~x\in\R,~x\ne 0,-1,-2,\ldots.
\]
Tale funzione \`e estendibile a $x\in\C$, $x\ne 0,-1,-2,\ldots$, mediante
l'espressione 
\[
\Gamma(x)=\frac 1z\prod_{n=1}^\infty\frac{(1+\frac 1n)^x}{1+\frac xn}.
\]
Non solo, ma \`e possibile dare una forma esplicita alla funzione $s(x)$ nella
formula di Rodrigues, infatti vale $s(x)=(x^2-1)^{n+\alpha}$.

\begin{oss}\rm La Funzione Gamma di Eulero gode di molte propriet\`a
  interessanti tra cui
\[\begin{split}
&\Gamma(x+1)=x\Gamma(x),~~x\in\R,~x\ne 0,-1,-2,\ldots\\
&\Gamma(1)=1\\
&\Gamma(n+1)=n!,~~\hbox{ se $n$ \`e intero}
\end{split}
\]
Vale inoltre
\[
\frac{d^n x^\alpha}{dx^n}=\alpha(\alpha-1)\cdots(\alpha-n+1)x^{\alpha-n}
=\frac{\Gamma(\alpha+1)}{\Gamma(\alpha-m+1)}x^{\alpha-n}
\]
Per ulteriori propriet\`a si veda \cite{bbcm}.
\qed\end{oss}

\begin{teo}\label{thm:ultrasf}
Se $\omega(x)=(1-x^2)^\alpha$, $\alpha>-1$, $s_n(x)=(1-x^2)^{\alpha+n}$,
allora $\frac{s_n^{(n)}(x)}{\omega(x)}$ \`e polinomio di grado $n$ e vale
$s_n^{(k)}(1)=s_n^{(k)}(-1)=0$, $k=0,1,\ldots,n-1$. Vale inoltre
\[
\frac{s_n^{(n)}(x)}{\omega(x)}=\sum_{j=0}^n(-1)^j{n\choose j}\frac
{\Gamma(\alpha+n+1)^2}{\Gamma(\alpha+j+1)\Gamma(\alpha+n-j+1)}(1-x)^{n-j}(1+x)^j.
\]
\end{teo}
{\bf Dim.} Se $n=0$ \`e
$\frac{s_0^{(0)}}{\omega(x)}=\frac{(1-x^2)^\alpha}{(1-x^2)^\alpha}=1$. Se
$n>0$ pongo $z=\alpha+n$ e ho
\[
\begin{split}
\frac{d^k}{dx^k}(1-x^2)^z=&\frac{d^k}{dx^k}[(1-x)^z(1+x)^z]\\
=&\sum_{j=0}^k{k\choose j}\frac{d^j}{dx^j}(1-x)^z\frac{d^{k-j}}{dx^{k-j}}(1+x)^z
\end{split}
\] 
D'altro canto vale
\[
\frac{d^m}{dx^m}x^\theta=\frac{\Gamma(\theta+1)}{\Gamma(\theta-m+1)}x^{\theta-m}
\]
da cui
\[
\begin{split}
\frac{d^k}{dx^k}(1-x^2)^z&=\sum_{j=0}^k{k\choose j}(-1)^j\frac{\Gamma(z+1)}{\Gamma(z-j+1)}(1-x)^{z-j}
\frac{\Gamma(z+1)}{\Gamma(z-k+j+1)}(1+x)^{z-k+j}\\
&=(1-x^2)^{z-k} \sum_{j=0}^k{k\choose j}(-1)^j\frac{\Gamma(z+1)^2(1-x)^{k-j}(1+x)^j}{\Gamma(z-j+1)\Gamma(z-k+j+1)}
\end{split}
\]
che diviso per $\omega(x)=(1-x^2)^\alpha$ 
\`e un polinomio in $x$. Inoltre, per $k=0,1,\ldots,n-1$ \`e
$z-k\ge\alpha+1>0$ per cui $s_n^{(k)}(-1)=s_n^{(k)}(1)=0$. Infine per $k=n$
vale $s_n^{(n)}(x)=(1-x^2)^{z-n}\phi(x)$, dove $\phi(x)$ \`e un polinomio, per
cui $\frac{s_n^{(n)}(x)}{(1-x^2)^\alpha}$ \`e un polinomio
\qed



Per i polinomi ultrasferici $p_{n,\alpha}(x)$ vale allora la formula
\[
p_{n,\alpha}(x)=\beta_{n,\alpha}\frac 1{(1-x^2)^{\alpha}}\frac{d^n}{dx^n}(1-x^2)^{\alpha+n}
\]
Dal teorema precedente si possono ricavare le espressioni di $a_n$, $h_n$ in
funzione di $\Gamma$.

Si osservi che vale ancora $p_{n,\alpha}(-x)=(-1)^n p_{n,\alpha}(x)$ per cui
$p_{n,\alpha}$ ha coefficienti nulli per le potenze che hanno esponente con la stessa
parit\`a di $n+1$. Conseguentemente il coefficienti $B_n$ nella relazione
ricorrente a tre termini sono nulli.
\subsection{Polinomi di Legendre}
I polinomi di Legendre sono polinomi ultrasferici con $\alpha=0$, e la
relazione ricorrente a tre termini \`e data da
\[
\begin{split}
&p_{n+1}(x)=\frac{2n+1}{n+1}xp_n(x)-\frac n{n+1}p_{n-1}(x)\\
&p_0=1,~~p_1=x
\end{split}
\]
In particolare

\[
p_0(x)=1,~p_1(x)=x,~p_2(x)=\frac 12(3x^2-1),~p_3(x)=\frac 12(5x^3-3x)
\]
La matrice tridiagonale associata \`e
\[
\left[\begin{array}{cccccccc}
x&-1\\
-\frac 12&\frac 32 x&-1\\
&-\frac 23&\frac 53 x &-1\\
&&-\frac 34&\frac 74 x& -1\\
&&&\ddots&\ddots&\ddots\\
&&&&-\frac i{i+1}&\frac{2i+1}{i+1}x&-1\\
&&&&&\ddots&\ddots&\ddots
\end{array}\right]
\]
che normalizzando i polinomi a essere monici diventa
\[
\left[\begin{array}{cccccccc}
x&-1\\
-\frac 13&x&-\frac 23\\
&-\frac 25&x &-\frac 35\\
&&-\frac 37&x& -\frac 47\\
&&&\ddots&\ddots&\ddots\\
&&&&-\frac i{2i+1}&x&-\frac{i+1}{2i+1}\\
&&&&&\ddots&\ddots&\ddots
\end{array}\right]
\]
La sua simmetrizzazione \`e data da
\[
\left[\begin{array}{cccccccc}
x&-\frac1{\sqrt 3}\\
-\frac 1{\sqrt 3}&x&-\frac 2{\sqrt{15}}\\
&-\frac 2{\sqrt{15}}&x &-\frac 3{\sqrt{35}}\\
&&-\frac 3{\sqrt{35}}&x& -\frac 4{\sqrt{63}}\\
&&&\ddots&\ddots&\ddots\\
&&&&\ddots&x&-\frac{i}{\sqrt{(2i+1)(2i-1)}}\\
&&&&&-\frac{i}{\sqrt{(2i+1)(2i-1)}} &\ddots&\ddots
\end{array}\right]
\]

Gli zeri del polinomio di Legendre di grado $n$ sono gli autovalori
della matrice  trid$_n((i-1)/(2i-1),0,i/(2i+1))$ 
tridiagonale $n\times n$ dove l'indice $i$ scorre da 1 a $n$ e sulla prima ed ultima riga compaiono due soli elementi dei tre indicati.

Il seguente codice Octave calcola tali zeri come autovalori della matrice tridiagonale con $n=6$:
\begin{verbatim}
n = 6;
T = zeros(n);
for i=1:n-1;
   T(i,i+1) = i/sqrt((2*i-1)*(2i+1));
end;
T=T+T';
zeri=eig(T);
\end{verbatim}
Infatti, scrivendo {\tt sort(zeri)'} 
(l'apice serve per fare scrivere gli autovalori come vettore riga)
Octave fornisce i valori 
\begin{verbatim}
ans =
-0.93247  -0.66121  -0.23862   0.23862   0.66121   0.93247
\end{verbatim}

\subsection{Polinomi di Chebyshev di prima specie}
I polinomi di Chebyshev di prima specie, che rientrano nella classe
dei polinomi ultrasferici con $\alpha=-1/2$, soddisfano la relazione
ricorrente a tre termini
\[
\begin{split}
&T_{n+1}(x)=2x T_n(x)-T_{n-1}(x)\\
&T_0(x)=1,~T_1(x)=x
\end{split}
\]

Ponendo $x=\cos\theta$, $0\le\theta\le\pi$, dalla relazione a tre termini 
segue che $T_n(\cos\theta)=\cos
n\theta$. La dimostrazione pu\`o essere fatta per induzione. Infatti per $n=0,1$ la propriet\`a \`e banalmente verificata. In generale, per l'ipotesi induttiva vale
\[
T_{n+1}(\cos\theta)=2\cos\theta \cos n\theta-\cos (n-1)\theta.
\]
Da cui
\[\begin{split}
T_{n+1}(\cos\theta)=&2\cos\theta\cos n\theta-\cos n\theta\cos\theta-\sin n\theta\sin\theta\\
=& \cos\theta\cos n\theta-\sin n\theta\sin\theta=\cos(n+1)\theta.
\end{split}
\]

Questo fatto permette di dare una espressione esplicita agli zeri 
$x_k^{(n)}$ di
$T_n(x)$. Infatti vale $x_k^{(n)}=\cos\frac{(2k-1)\pi}{2n}$, $k=1,\ldots,n$.
Inoltre su $[-1,1]$ il polinomio $T_n(x)$ \`e sempre compreso tra $-1$ e $1$.

Si osservi anche che $T_n(\cos \theta)=\pm 1$ se e solo se $\cos (n\theta)=\pm
1$, se e solo se $n\theta=k\pi$, se e solo se $\theta=k\pi/n$, $k=0,1,\ldots
n$.
Cio\`e nell'intervallo $[-1,1]$ il polinomio $T_n(x)$ assume $n+1$ volte i
valori massimi e minimi.

\begin{teo}
Tra tutti i polinomi monici di grado $n\ge 1$ il polinomio monico $\frac
1{2^{n-1}}T_n(x)$ \`e quello che ha minima norma infinito su $[-1,1]$
\end{teo}
{\bf Dim.} Si \`e gi\`a osservato che  $T_n(x)$ assume il valore massimo 1 e
il valore  minimo $-1$ per $n+1$ volte. Quindi $\|T_n(x)\|_\infty=1$ e
$\|T_n(x)/2^n\|_\infty=1/2^{n-1}$. Supponiamo per assurdo che esista un polinomio
$p_n$ monico di grado $n$ tale che $\|p_n(x)\|_\infty<1/2^{n-1}$. Il polinomio
$p_n(x)$ ha massimo minore di $1/2^{n-1}$ e minimo maggiore di
$-1/2^{n-1}$. Quindi il polinomio differenza $ q(x)=p_n(x)-T_n(x)/2^{n-1}$ di
grado al pi\`u $n-1$ \`e negativo dove $T_n$ ha massimo e positivo dove $T_n$
ha minimo. Ci\`o accade in $n+1$ punti di $[-1,1]$. Quindi $q(x)$ ha $n$
zeri. Il che \`e assurdo.\qed

La matrice tridiagonale associata ai polinomi di Chebyshev di prima specie 
 \`e
\[
\left[\begin{array}{cccccc}
x&-1\\
-1&2x&-1\\
&-1&2x&-1\\
&&-1&2x&-1\\
&&&\ddots&\ddots&\ddots
\end{array}\right]
\]
Un polinomio $q(x)$ di grado $n$ pu\`o essere rappresentato nella base di
Chebyshev come $q(x)=\sum_{k=0}^n a_k T_k(x)$. Data l'ortogonalit\`a dei
polinomi $T_k(x)$, i valori di $a_k$ possono essere calcolati come
\[
a_k=\langle q(x),T_k(x)\rangle/\langle T_k(x),T_k(x)\rangle.
\]

Poich\'e vale la propriet\`a di ortogonalit\`a discreta \eqref{eq:ortogdisc}
si ha
\[
\sum_{k=0}^{n-1}T_i(x_k)T_j(x_k)\sigma_k=\delta_{i,j}\sqrt{h_i}\sqrt{h_j},
\quad 
\sigma_k=1/\sum_{s=0}^{n-1}\frac{T_s(x_k)^2}{h_s}
\]
dove $x_s$ sono gli zeri di $T_n(x)$, i coefficienti $a_k$ possono essere
calcolati come
\[
a_k=\sum_{s=0}^{n-1}q(x_s)T_k(x_s)\sigma_s/\sum_{s=0}^{n-1}T_k(x_s)T_k(x_s)\sigma_s.
\]
La somma infinita
\[
f(x)=\sum_{k=0}^\infty a_k T_k(x)
\]
se convergente, definisce una funzione $f(x)$ ed \`e chiamata {\em serie di
  Chebyshev} di $f(x)$. Data una funzione $f(x)$ le condizioni a cui deve
soddisfare $f(x)$ affinch\'e esista convergente la serie di Chebyshev sono analoghe a
quelle valide per la convergenza della serie di Fourier.

\begin{oss}\rm
Per i polinomi di Chebyshev di prima specie i valori di $h_k$ sono dati da
\[
\langle T_k(x),T_k(x)\rangle = \int_{-1}^1T_k(x)^2\frac1{\sqrt{1-x^2}}dx.
\]
Con la sostituzione di variabile $x=\cos \theta$ si ottiene quindi
\[
h_k=\int_{0}^\pi\cos^2 k\theta d\theta=\left\{\begin{array}{ll}
\frac{\pi}2&\hbox{ se }k\ne 0\\
\pi&\hbox{ se } k=0.
\end{array}\right.
\]
Inoltre, poich\'e gli zeri di $T_n(x)$ sono
$x_k=\cos\frac{(2k-1)\pi}{2n}$ e vale $T_s(x)=\cos(s\theta)$ con
$x=\cos\theta$, si ha $T_s(x_k)=\cos(s\frac{(2k-1)\pi}{2n} )$ per cui,
$1/\sigma_k=\sum_{s=0}^{n-1} T_s(x_k)^2/h_s=\frac{2}{\pi}(1/2+\sum_{s=1}^{n-1}
T_s(x_k)^2)= \frac{n}\pi$.

Quindi la popriet\`a di ortogonalit\`a discreta dei polinomi di
Chebyshev diventa
\[
\sum_{k=1}^n T_i(x_k)T_j(x_k) =\left\{\begin{array}{ll} \frac{n}2\delta_{i,j}\hbox{ se }i\ne 0\\[1ex]
n\delta_{i,j}\hbox{ se }i=0.
\end{array}\right.
\]
La matrice $C=(c_{i,j})$ di elementi $c_{i,j}=T_{j}(x_{i-1})$ definisce
la trasformata discreta dei coseni di secondo tipo
\url{http://en.wikipedia.org/wiki/Discrete_cosine_transform} e gode
della propriet\`a che $C^TC=n\hbox{diag}(1,1/2,\ldots,1/2)$.
\qed\end{oss}

La function Octave riportata nel listing \ref{cheby1} crea una matrice
{\tt t} di dimensioni $m\times n$ che ha nella colonna $j$-esima i
valori di $T_{j-1}(x)$ calcolati in $m$ punti equispaziati tra $-1$ e
1. Mentre la function riportata nel listing \ref{chebyshev1}
crea una matrice {\tt t} di dimensioni $n\times n$ che ha nella
colonna $j$-esima i valori di $T_{j-1}(x)$ calcolati negli $n$ zeri
del polinomio di Chebyshev $T_n(x)$ di prima specie di grado $n$.

In questo modo, con i seguenti comandi
\begin{verbatim}
t = cheby1(100,6);
x = t(:,2);
plot(x,t(:,2),x,t(:,3),x,t(:,4),x,t(:,5),x,t(:,6));
\end{verbatim}
si tracciano i grafici dei primi 6 polinomi di Chebyshev di prima specie
riportati nella figura \ref{fig:cheb1}.
Mentre scrivendo
\begin{verbatim}
t=chebyshev1(6);
t'*t
\end{verbatim}
si ottiene la matrice numericamente diagonale
\begin{verbatim}
ans =

   6.00000   0.00000   0.00000   0.00000  -0.00000   0.00000
   0.00000   3.00000   0.00000  -0.00000   0.00000  -0.00000
   0.00000   0.00000   3.00000   0.00000  -0.00000   0.00000
   0.00000  -0.00000   0.00000   3.00000   0.00000  -0.00000
  -0.00000   0.00000  -0.00000   0.00000   3.00000   0.00000
   0.00000  -0.00000   0.00000  -0.00000   0.00000   3.00000
\end{verbatim}
che conferma l'ortogonalit\`a delle colonne di {\tt t} per $n=6$. 

\begin{lstlisting}[float,frame=single,
  caption={Function cheby1},
   label=cheby1]
function t=cheby1(m,n)
% function t=cheby1(m,n)
% output: t e' la matrice mxn la cui colonna j-esima contiene i valori
%   del polinomio di Chebyshev di prima specie grado j-1 campionato nei
%   punti x_i=(-1+ i*2/(m-1)) per i=0,1,...,m-1
  t = ones(m,n);
  x = [-1:2/(m-1):1]';
  t(:,2) = x;
  for j=3:n
     t(:,j) = 2*x.*t(:,j-1) - t(:,j-2);
  end
\end{lstlisting}



\begin{figure}\centering
\includegraphics[width=10cm,angle= 270]{cheby1}
\caption{Polynomi di Chebyshev di prima specie}
\label{fig:cheb1}
 \end{figure}

\begin{lstlisting}[float,frame=single,
  caption={Function chebyshev1},
   label=chebyshev1]
function t=chebyshev1(n)
% function t=chebyshev1(n)
% output: t e' la matrice nxn la cui colonna j-esima contiene i valori
%   del polinomio di Chebyshev di prima specie grado j-1 campionato negli
%   zeri del polinomio di Chebyshev di grado n: x_k=cos((2k-1)pi/(2n))
%   per k=1,...,n
  t = ones(n);
  x = cos([pi/(2*n): pi/n : (2*n-1)*pi/(2*n)]');
  t(:,2) = x;
  for j=3:n
     t(:,j) = 2*x.*t(:,j-1) - t(:,j-2);
  end
\end{lstlisting}



\subsection{Polinomi di Chebyshev di seconda specie}
Anche i polinomi di Chebyshev di seconda specie rientrano nella classe
dei polinomi ultrasferici. Sono definiti da $\alpha=1/2$ e soddisfano
la relazione ricorrente
\[\begin{split}
&U_{n+1}(x)=2x U_n(x)-U_{n-1}\\
&U_0(x)=1,~~U_1(x)=2x
\end{split}
\]

Dalla relazione a tre termini segue che ponendo $x=\cos\theta$ risulta
\[
U_n(\cos \theta)=\frac{\sin((n+1)\theta)}{\sin\theta}
\]
Quindi gli zeri di $U_n(x)$ sono $x_k^{(n)}=\cos\frac{k\pi}{n+1}$,
$k=1,\ldots,n$. 

Si osserva che 
\[
\frac{d T_n}{dx}=\frac{dT_n(\cos\theta)}{d\theta}\cdot\frac{d\theta}{dx}=
\frac{d\cos(n\theta)}{d\theta}/\frac{d\cos\theta}{d\theta}=n\frac{\sin(n\theta)}{\sin\theta}
\]
che implica 
\[
T'_n(x)=nU_{n-1}(x).
\]

La matrice tridiagonale associata ai polinomi di Chebyshev di seconda specie 
 \`e
\[
\left[\begin{array}{cccccc}
2x&-1\\
-1&2x&-1\\
&-1&2x&-1\\
&&-1&2x&-1\\
&&&\ddots&\ddots&\ddots
\end{array}\right]
\]


La function Octave riportata nel listing \ref{cheby2} crea una matrice
{\tt u} di dimensioni $m\times n$ che ha nella colonna $j$-esima i
valori di $U_{j-1}(x)$ calcolati in $m$ punti equispaziati tra $-1$ e
1. Mentre la function riportata nel listing \ref{chebyshev2}
crea una matrice {\tt u} di dimensioni $n\times n$ che ha nella
colonna $j$-esima i valori di $U_{j-1}(x)$ calcolati negli $n$ zeri
del polinomio di Chebyshev $U_n(x)$ di seconda specie di grado $n$.


In questo modo, con i seguenti comandi
\begin{verbatim}
u = cheby1(100,6);
x = [-1:2/99:1];
plot(x,u(:,2),x,u(:,3),x,u(:,4),x,u(:,5),x,u(:,6));
\end{verbatim}
si tracciano i grafici dei primi 6 polinomi di Chebyshev di seconda specie
riportati nella figura \ref{fig:cheb2}.
Mentre scrivendo
\begin{verbatim}
u = chebyshev2(6);
u*u'
\end{verbatim}
si ottiene la matrice numericamente diagonale
\begin{verbatim}
   1.8592e+01  -1.7048e-15   1.3849e-15  -6.6331e-16   5.0209e-16  -4.0007e-16
  -1.7048e-15   5.7259e+00  -4.9922e-16   9.9204e-17  -1.6046e-16  -5.1337e-16
   1.3849e-15  -4.9922e-16   3.6823e+00   2.9891e-16  -1.9125e-16   8.2611e-16
  -6.6331e-16   9.9204e-17   2.9891e-16   3.6823e+00  -3.9411e-17  -5.7718e-16
   5.0209e-16  -1.6046e-16  -1.9125e-16  -3.9411e-17   5.7259e+00   2.0095e-15
  -4.0007e-16  -5.1337e-16   8.2611e-16  -5.7718e-16   2.0095e-15   1.8592e+01
\end{verbatim}



\begin{lstlisting}[float,frame=single,
  caption={Function cheby2},
   label=cheby2]
function t=cheby2(m,n)
% function t=cheby1(m,n)
% output: t e' la matrice mxn la cui colonna j-esima contiene i valori
%   del polinomio di Chebyshev di seconda specie grado j-1 campionato nei
%   punti x_i=(-1+ i*2/(m-1)) per i=0,1,...,m-1
  t = ones(m,n);
  x = [-1:2/(m-1):1]';
  t(:,2) = 2*x;
  for j=3:n
     t(:,j) = 2*x.*t(:,j-1) - t(:,j-2);
  end
\end{lstlisting}



\begin{figure}\centering
\includegraphics[width=10cm, angle=270]{cheby2}
\caption{Polynomi di Chebyshev di seconda specie}
\label{fig:cheb2}
 \end{figure}

\begin{lstlisting}[float,frame=single,
  caption={Function chebyshev2},
   label=chebyshev2]
function t=chebyshev2(n)
% function t=chebyshev2(n)
% output: t e' la matrice nxn la cui colonna j-esima contiene i valori
%   del polinomio di Chebyshev di seconda specie grado j-1 campionato negli
%   zeri del polinomio di Chebyshev di grado n: x_k=cos(k*pi/(n+1))
%   per k=1,...,n
  t = ones(n);
  x = cos([pi/(n+1): pi/(n+1) : n*pi/(n+1)]');
  t(:,2) = 2*x;
  for j=3:n
     t(:,j) = 2*x.*t(:,j-1) - t(:,j-2);
  end
\end{lstlisting}

\subsection{Polinomi di Laguerre}
Peso $\omega(x)=e^{-x}$, intervallo $[0,+\infty]$.
Coefficienti della ricorrenza a tre termini: $A_{n+1}=-\frac 1{n+1}$,
$B_{n+1}=\frac{2n+1}{n+1}$, $C_n=\frac n{n+1}$.
\[
\begin{split}
&L_{n+1}(x)=\frac 1{n+1}\left(({2n+1}-x)L_n(x)-nL_{n-1}(x)\right)\\
&L_0(x)=1,~~L_1(x)=1-x
\end{split}
\]
Matrice tridiagonale associata
\[
\hbox{diag}(1,\frac 12,\frac 13, \frac 14,\ldots)
\left[\begin{array}{cccccc}
1-x&-1\\
-1&3-x&-1\\
&-2&5-x&-1\\
&&-3&7-x&-1\\
&&&\ddots&\ddots&\ddots
\end{array}\right]
\]


\subsection{Polinomi di Hermite}
Peso $\omega(x)=e^{-x^2}$, intervallo $[-\infty,+\infty]$.
Ricorrenza a tre termini: 
\[
\begin{split}
&H_{n+1}(x)=2xH_n(x)-2nH_{n-1}(x)\\
&H_0(x)=1,~~H_1(x)=2x
\end{split}
\]
Matrice tridiagonale associata
\[
\left[\begin{array}{cccccc}
2x&-1\\
-2&2x&-1\\
&-4&2x&-1\\
&&-6&2x&-1\\
&&&\ddots&\ddots&\ddots
\end{array}\right]
\]




\section{Il problema dell'approssimazione di funzioni}
Lo scopo \`e quello di approssimare funzioni continue $f:K\subset
\R^n\to\R$, dove $K$ \`e un compatto, con polinomi o con funzioni
facilmente calcolabili, ad esempio, polinomi o funzioni razionali. 
La funzione $f(x)$ pu\`o essere assegnata
esplicitamente in termini di funzioni elementari oppure essere
assegnata formalmente come soluzione di una equazione
differenziale. 

Per semplicit\`a lavoriamo su $\R$ e scegliamo $K=[a,b]$.  
%La
%motivazione \`e quella di poter meglio calcolare in modo approssimato
%delle funzioni continue assegnate formalmente in termini di funzioni
%elementari o assegnate implicitamente come soluzioni di particolari
%equazioni differenziali.

La scelta di usare polinomi \`e saggia dal punto di vista computazionale, ma
lo \`e anche dal punto di vista dell'approssimazione. Vale infatti

\begin{teo}[Weierstrass] Per ogni $f(x): K\to \R$ continua e per ogni
  $\epsilon>0$ esiste un polinomio $p_\epsilon(x)$ tale che $\max_{x\in
    K}|f(x)-p_\epsilon(x)|\le\epsilon$. 
\end{teo}

Denotiamo $\mathcal P_n$ l'insieme dei polinomi di grado al pi\`u $n$.
Denotiamo $d(f,\mathcal P_n)=\inf_{p\in\mathcal P_n}\max_{x\in K}|f(x)-p(x)|$.

%\begin{oss}\rm L'approssimazione di funzioni continue mediante polinomi non
%  \`e sempre ``buona''. Si pu\`o dimostrare che
%\[
%\forall \{\epsilon_n\},~\epsilon_n>0,~\epsilon_n\downarrow 0,~\exists f(x)\in
%C[a,b]:~ d(f,\mathcal P_n)\ge\epsilon_n,~\forall n.
%\]
%\qed\end{oss}


\subsection{Il problema dell'approssimazione lineare}
Viene fissato un ``modello'' di approssimazione scegliendo un insieme di
funzioni continue $\{\varphi_0,\varphi_1,\ldots\}$ e si cerca di approssimare
nel modo migliore possibile una funzione assegnata $f(x)\in C[a,b]$ mediante
$g(x)=\sum_{i=0}^n \alpha_i\varphi_i(x)$.

Le funzioni $\varphi_i(x)$ devono essere computazionalmente facili e in grado
di approssimare bene la $f(x)$. Ad esempio, i polinomi non sono adatti ad
approsimare funzioni che hanno asintoti verticali (in questo caso l'insieme in cui sono definite le funzioni non \`e un compatto). In questo caso le funzioni
razionali si prestano meglio. Similmente per funzioni periodiche sono pi\`u
adatte le funzioni trigonometriche.

Sia $\mathcal V$ spazio vettoriale sul corpo $\K$ ($\K=\C$, $\K=\R$).

\begin{defi}
$\|\cdot\|:\mathcal V\to\R$  \`e una norma se per ogni $x,y\in\mathcal V$,
$\alpha\in\R$ \`e 
\[
\begin{split}
&\|x\|\ge 0\\&\|x\|=0\Leftrightarrow x=0\\
&\|\alpha x\|=|\alpha|\cdot\|x\|\\
&\|x+y\|\le \|x\|+\|y\|~~\hbox{diseguaglianza triangolare}
\end{split}
\]
\end{defi}


\begin{teo}
Ogni norma su $\mathcal V$ \`e funzione uniformemente 
continua nella topologia indotta dalla
norma.
\end{teo}
{\bf Dim.} Dalla diseguaglianza triangolare segue che
$|\|x\|-\|y\||\le\|x-y\|$. Quindi $\forall \epsilon>0$ $\exists\delta>0
~(\delta=\epsilon)$: $\|x-y\|\le\delta\Rightarrow
|\|x\|-\|y\| |\le\epsilon$. \qed


Esempi di norme su $C[a,b]$:
\[
\begin{split}
&
\|f(x)\|_2=\left(\int_a^b f(x)^2dx\right)^{1/2}\\
&\|f(x)\|_\infty=\max_{x\in[a,b]}|f(x)|
\end{split}
\]
Dato un prodotto scalare $\left\langle \cdot,\cdot \right\rangle $ su $C[a,b]$, ad esempio
$\left\langle f,g \right\rangle =\int_a^bf(x)g(x)\omega(x)dx$, si definisce norma indotta dal prodotto
scalare
\[
\|f(x)\|=\left\langle f,f \right\rangle ^{1/2}.
\]

{\bf Poblema dell'approssimazione lineare}
Data $f(x)\in C[a,b]$ e l'insieme di funzioni linearmente indipendenti
$\{\varphi_0,\varphi_1,\ldots\}$, data una norma $\|\cdot\|$ e un intero $n$,
calcolare $\alpha_i^*$, $i=0,1,\ldots,n$ tali che la funzione
$g_n(x)=\sum_{i=0}^n\alpha_i^*\varphi_i(x)$ \`e tale che
\[
\|f(x)-g_n(x)\|=\min_{\alpha_0,\ldots,\alpha_n}\|f(x)-\sum_{i=0}^{n}\alpha_i\varphi_i(x)\|.
\]
La funzione $g_n(x)$ \`e detta {\em funzione di migliore approssimazione}\\
$r_n(x)=f(x)-g_n(x)$ \`e detto {\em resto dell'approssimazione}\\
$\delta_n=\|r_n(x)\|$ \`e detto {\em errore assoluto in norma}\\[2ex]

\begin{oss}\rm
Se $\|\cdot\|=\|\cdot\|_\infty$ allora la funzione di migliore approssimazione
$g_n(x)$ di $f(x)$ \`e tale che $|r_n(x)|=|f(x)-g_n(x)|\le \delta_n$ $\forall x\in[a,b]$. In questo caso si parla di {\em 
approssimazione uniforme}. Se
$\|\cdot\|=\|\cdot\|_2$ non \`e vero che $|r_n(x)|\le\delta_n$ per ogni
$x\in[a,b]$. Si consideri ad esempio $r_n(x)=x^n:[0,1]\to \R$. Vale
$\|r_n(x)\|_\infty=1$ mentre $\|r_n(x)\|_2=1/\sqrt{2n+1}$ che pu\`o essere
arbitrariamente piccola.
\qed\end{oss}

\begin{teo}
Sia $ \mathcal F=\{f(x):[a,b]\to\R\}$ uno spazio di funzioni dotoato di norma $\|\cdot\|$, e sia $\mathcal G_n\subset \mathcal F$ un sottospazio di
$\mathcal F$ generato da un insieme di funzioni linearmente indipendenti
$\{\varphi_0,\varphi_1,\ldots,\varphi_n\}$. Allora 
\begin{itemize}
\item il
  problema dell'approssimazione lineare su $\mathcal G_n$ ha soluzione;
\item
  l'insieme delle soluzioni \`e convesso;
\item la successione $\{\delta_n\}$ \`e non crescente;
\item esiste $\lim_n\delta_n\ge 0$.
\end{itemize}
\end{teo}
{\bf Dim.}  Dimostriamo che il problema ha soluzione. L'idea della
dimostrazione consiste nel verificare che l'inf del resto si pu\`o
restringere all'insieme $\{\alpha=(\alpha_i)\in\R^{n+1}:\quad
\|\alpha\|_\infty\le\gamma\}$ per una opportuna costante $\gamma$. Poich\`e
questo insieme \`e un compatto di $\R^{n+1}$ e la norma \`e continua esiste il
minimo e quindi il problema dell'approssimazione lineare ha soluzione.
Tecnicamente si introducono le funzioni
$c(\alpha)=\|\sum_{i=0}^n\alpha_i\varphi_i\|$ e
$d(\alpha)=\|f-\sum_{i=0}^n\alpha_i\varphi_i\|$ che sono continue. Per
cui $c(\alpha)$ ha minimo su $S=\{\alpha\in\R^{n+1}:\quad
\|\alpha\|_\infty=1\}$. Sia $\gamma$ il minimo. Vale $\gamma\ne 0$
poich\'e $\varphi_i$ sono linearmente indipendenti. Vale
\[
c(\alpha)=\|\sum\frac{\alpha_i}{\|\alpha\|_\infty}\varphi_i\|\cdot\|\alpha\|_\infty\ge
\gamma\|\alpha\|_\infty
\]
inoltre
\[
d(\alpha)=\|f-\sum\alpha_i\varphi_i\|\ge
\|\sum\alpha_i\varphi_i\|-\|f\|\ge\gamma\|\alpha\|_\infty-\|f\|.
\]
Posto $t=\inf d(\alpha)$ si scelga $\mu$ tale che $\mu\ge \frac{t+\|f\|}\gamma$. Risulta
che se $\|\alpha\|_\infty>\mu$ allora
$d(\alpha)\ge\gamma\|\alpha\|_\infty-\|f\|>\gamma \mu -\|f\|\ge t$, per cui
\[
t=\inf_\alpha d(\alpha)=\inf_{\|\alpha\|_\infty\le \mu}d(\alpha).
\]
Ma poich\'e $\{\alpha\in\R^{n+1}:\ \|\alpha\|_\infty\le \mu\}$ \`e compatto,
l'inf \`e un minimo. Esiste quindi $g_n(x)\in\mathcal G_n$ tale che 
$\|f(x)-g_n(x)\|=t$ \`e minimo.

Per dimostrare la convessit\`a: siano $g_n$ e $\hat g_n$ due funzioni di $\mathcal G_n$ tali che
$\|f-g_n\|=\|f-\hat g_n\|$ \`e il minimo. Per $\lambda\in[0,1]$ vale
\[\begin{split}
\|f-(\lambda g_n+(1-\lambda) \hat g_n)\|=&\|\lambda f-(1-\lambda)f-(\lambda
g_n+(1-\lambda)\hat g_n\|\\
=&\|\lambda(f-g_n)+(1-\lambda)(f-\hat g_n)\|\\
\le&
\lambda\|f-g_n\|+(1-\lambda)\|f-\hat g_n\|=\|f-g_n\|
\end{split}
\]
Quindi anche $\lambda g_n+(1-\lambda)\hat g_n$ \`e funzione di migliore
approssimazione. Per la non crescenza dei $\delta_n$ basta osservare che
$\delta_{n+1}$ \`e il minimo ottenuto su un insieme pi\`u ampio. \qed

\begin{oss}\rm Il problema lineare di approssimazione ha una oppure infinite
  soluzioni.
\qed\end{oss}

\begin{oss}\rm Il teorema precedente non garantisce che $\delta_n\to 0$ e che
  quindi $g_n$ \`e una ``buona approssimazione''.
\qed\end{oss}

\begin{defi}
$\mathcal F$ \`e {\em strettamente convesso} rispetto alla
  norma $\|\cdot\|$ se
per ogni
$f,g\in\mathcal F,~f\ne g$, vale
\[
\|f\|\le m,~\|g\|\le m\Rightarrow \|f+g\|<2m.
\] 
\end{defi}

\begin{oss}\rm
$\R^2$ con la norma infinito non \`e strettamente convesso infatti $(1,0)+(0,1)=(1,1)$ e i tre vettori hanno tutti norma infinito 1. Mentre $\R^2$ con la norma 2 \`e strettamente convesso.
\qed\end{oss}

\begin{teo}\label{thsc}
Se $\mathcal F$ \`e strettamente convesso allora il problema
dell'approssimazione lineare ha una sola soluzione
\end{teo}
{\bf Dim.}
Se esistono $g_n\ne \hat g_n$ funzioni di migliore approssimazione allora
\[
\|f-g_n\|=\|f-\hat g_n\|=\delta_n
\]
quindi per la stretta convessit\`a vale $\|f-g_n+f-\hat g_n\|<2\delta_n$ e
quindi la funzione $h(x)=\frac 12(g_n(x)+\hat g_n(x))$ \`e tale che
$\|f-h\|<\delta_n$ che \`e assurdo.
\qed

Il teorema precedente non garantisce ancora che $\lim \delta_n=0$.

\subsection{Richiami sugli spazi di Banach e di Hilbert.}


\begin{defi}
Sia $\mathcal V$ spazio vettoriale normato. Una successione $f_n\in\mathcal V$
\`e di Cauchy se $\forall\epsilon>0~\exists n_0$: $\forall m,n\ge n_0$ $\|f_m-f_n\|\le\epsilon$. 
\end{defi} 

Esempi: \begin{itemize}
\item
$\mathcal V=C[0,1]$, $\|f\|=\|f\|_\infty=\max_{x\in[0,1]}|f(x)|$:
$f_n(x)=x^n$ non \`e di Cauchy. Infatti $x^{n}-x^{2n}$ per $x=(1/2)^{1/n}$
vale $1/4$ qualsiasi sia $n$.
\item $\mathcal V=C[0,1]$ con la norma $\|f\|_2=(\int_0^1f(x)^2dx)^{1/2}$: $f_n(x)=x^n$
  \`e di Cauchy. Infatti $\int_0^1 (x^{m}-x^n)^2dx=...$
\end{itemize}

\begin{defi}
Uno spazio vettoriale normato $\mathcal B$ \`e di Banach se ogni successione
di Cauchy $\{f_n\}$ converge in norma ad un elemento $f\in\mathcal B$. Cio\`e
se esiste $f\in\mathcal B$ tale che $\lim_n \|f_n-f\|=0$.
\end{defi}

Esempi di spazi di Banach
\begin{itemize}
\item $\R^n$, $\C^n$;
\item $C[a,b]$ con $\|\cdot\|_\infty$;
\item funzioni continue da un compatto $K\subset\R$ in $\R$ con $\|\cdot\|_\infty$;
\item funzioni analitiche da un aperto $\Omega\subset\C$ in $\C$ con
  $\|\cdot\|_\infty$;
\item $\ell^p=\{(x_i)_{i=1,2,\ldots}\in\R^\infty:\quad
  \sum_i|x_i|^p<+\infty\}$ con $\|x\|_p=(\sum_i|x_i|^p)^{1/p}$, $p\ge 1$;
\item $\ell^\infty=\{(x_i)_{i=1,2,\ldots}\in\R^\infty:\quad
  \sup_i|x_i|<+\infty$\} con $\|x\|_\infty=\sup_i|x_i|$.
\end{itemize}

\begin{oss}\rm Nello spazio vettoriale
$\{f:[a,b]\to\R:\quad \int_a^b|f|^pdx<+\infty~ (\hbox{int. di Lebesgue})\}$
  l'applicazione $f\to \|f\|_p=(\int_a^b|f|^pdx)^{1/p}$ non \`e norma poich\'e
 esistono
  $f(x)\ne 0$: $\|f\|_p=0$. Ma diventa una norma nello spazio quoziente con la
 relazione di equivalenza $f\equiv g$ se $\|f-g\|_p=0$. Questo spazio \`e
 denotato con $L^p$ ed \`e di Banach. 
\qed\end{oss}

%\begin{oss}\rm
%Aver usato l'integrale di Riemann al posto dell'integrale di Lebesgue non
%avrebbe dato uno spazio completo. Esisterebbero infatti successioni di Cauchy
%integrabili secondo Riemann il cui limite non \`e integrabile secondo Riemann.
%\qed\end{oss}


Un prodotto scalare $\left\langle \cdot,\cdot \right\rangle $ induce una norma $\|f\|=\left\langle f,f \right\rangle ^{1/2}$.

\begin{defi}
Uno spazio vettoriale $\mathcal H$ con prodotto scalare $\left\langle \cdot,\cdot \right\rangle $ \`e di
Hilbert se ogni successione di Cauchy converge ad un elemento di $\mathcal H$
nella norma $\|\cdot\|$ indotta dal prodotto scalare.
\end{defi}

\begin{oss}\rm
Non tutte le norme sono indotte da un prodotto scalare. Non tutti gli spazi di
Banach sono di Hilbert.
\qed\end{oss}

\begin{oss}\rm
Lo spazio $C[a,b]$ col prodotto scalare
$\left\langle f,g \right\rangle =(\int_a^bf(x)g(x)dx)^{1/2}$ non \`e di Hilbert. Infatti con $[a,b]=[0,2]$, la successione
\[
f_n(x)=\left\{\begin{array}{ll}
x^n&\hbox{se }x\in[0,1]\\
1&\hbox{se }x\in[1,2]
\end{array}\right.
\]
\`e di Cauchy, ma la successione non ha limite in $C[0,2]$.
\qed\end{oss}

\begin{teo}
Una norma sullo spazio $\mathcal V$ \`e indotta da un prodotto scalare se e
solo se vale la legge del parallelogramma
\[
\|u+v\|^2+\|u-v\|^2=2(\|u\|^2+\|v\|^2)
\]
e vale
\[\begin{split}
&\left\langle u,v \right\rangle =\frac 14(\|u+v\|^2-\|u-v\|^2)~~\hbox{su }\R\\
&\left\langle u,v \right\rangle =\frac 14(\|u+v\|^2-\|u-v\|^2+\cu (\|u+\cu v\|^2-\|u-\cu
v\|^2))~~\hbox{su }\C.
\end{split}
\]
dove $\cu$ \`e l'unit\`a immaginaria tale che $\cu^2=-1$.
\end{teo}

\begin{cor}\label{cor1}
Uno spazio vettoriale $\mathcal V$ con norma indotta da un prodotto scalare \`e strettamente convesso.
\end{cor}
{\bf Dim.} Dalla legge del parallelogramma si ha $\|u+v\|^2=2(\|u\|^2+\|v\|^2)-\|u-v\|^2$. Per cui, se $u-v\ne 0$ segue che $\|u+v\|^2<2(\|u\|^2+\|v\|^2)$.
Quindi, se $\|u\|\le m$ e $\|v\|\le m$ e $u\ne v$, allora $\|u+v\|^2<2(m^2+m^2)=4m^2$. Ne segue $\|u+v\|<2m$ e quindi la stretta convessit\`a di $\mathcal V$.
\qed

\begin{oss}\rm
Dalla legge del parallelogramma e dalla diseguaglianza triangolare segue
la diseguaglianza di Cauchy-Schwarz, $|\langle x,y\rangle|^2\le\langle
x,x\rangle\langle y,y\rangle$. Infatti, dalla diseguaglianza triangolare scritta nella forma
$(\|u\|-\|v\|)^2\le\|u-v\|^2$ segue
\[
\|u\|^2+\|v\|^2-2\|u\|\cdot\|v\|\le\|u-v\|^2
\]
da cui, per la legge del parallelogramma, si ha
\[
\frac 12(\|u+v\|^2+\|u-v\|^2)-\|u-v\|^2\le 2\|u\|\cdot\|v\|
\]
cio\`e 
\[
\frac 12(\|u+v\|^2-\|u-v\|^2)\le2\|u\|\cdot\|v\|,
\]
quindi
$\langle u,v\rangle\le\|u\|\cdot\|v\|$.
\qed\end{oss}

\`E utile la seguente definizione

\begin{defi} \rm Sia $\mathcal V$ spazio di Hilbert con prodotto scalare $\langle\cdot,\cdot\rangle$ e siano $\varphi_i(x)\in\mathcal V$, per $i=0,1,\ldots$, tali che $\langle\varphi_i,\varphi_j\rangle=0$ per $i\ne j$. L'insieme ortogonale $\{\varphi_i\in\mathcal
  V,\ i=0,1,2,\ldots\}$,  \`e
  completo se non esistono $y\in\V$ tali che $\left\langle \varphi_i,y
  \right\rangle =0$ per ogni $i$. Cio\`e non esiste un altro insieme
  ortogonale di cui l'insieme originale sia sottoinsieme proprio.
\end{defi}


Ricordiamo il 
seguente risultato riguardante insiemi ortogonali completi in uno
spazio di Hilbert.

\begin{lem}\label{lem3}
Sia $\{\varphi_i(x)\in\mathcal H,\ i=0,1,2,\ldots\}$ un insieme
ortogonale completo nello spazio di Hilbert $\mathcal H$. Allora
l'insieme $\mathcal S=\{f=\sum_{i=0}^n\alpha _i\varphi_i,~ n\in\N,~\alpha_i\in
K\}$ \`e denso in $\mathcal H$. Cio\`e per ogni $f\in\mathcal H$ e per ogni $\epsilon>0$ esiste
$g_n=\sum_{i=0}^n\alpha_i\varphi_i\in\mathcal S$ tale che $\|f-g_n\|\le\epsilon$.
\end{lem}



\subsection{Funzione di migliore approssimazione}
\begin{teo}\label{miglapp}
Sia $\mathcal V$ spazio vettoriale dotato di prodotto scalare e sia
$f\in\mathcal V$. Siano inoltre
$\varphi_0,\ldots,\varphi_n\in\mathcal V$ linearmente
indipendenti. Allora $\exists ! ~g=\sum_{i=0}^n\alpha_i\varphi_i$ tale
che $\|g-f\|$ \`e minima. Inoltre $\|g-f\|$ \`e minima se e solo se
$\left\langle g-f,v \right\rangle =0$ per ogni $v\in\mathcal
W:=\hbox{span}(\varphi_0,\ldots,\varphi_n)$.
\end{teo}

{\bf Dim.}  L'esistenza e unicit\`a di $g$ segue dal fatto che
$\mathcal V$ \`e strettamente convesso alla luce del teorema \ref{thsc}
  e del corollario \ref{cor1}.

 Sia $h=f-g$. Dimostriamo ora che $\|h\|$ \`e minima se e solo se il vettore $h$ \`e
ortogonale a $\mathcal W=\hbox{span}(\varphi_0,\ldots\varphi_{n})$, 
cio\`e $\left\langle h,v\right\rangle =0$ per ogni 
$v\in\mathcal W$. 
Se $\|h\|$ \`e minimo, allora
 $\|h\|^2\le \|h+\gamma v\|$ per ogni $\gamma$ e $v\in\mathcal W$, da cui
\[\|h\|^2\le
\|h+\gamma v\|^2=\left\langle  h+\gamma v,h+\gamma v
 \right\rangle =\|h\|^2+2\gamma\left\langle  h,v \right\rangle +\gamma^2 
\|v\|^2
\]
cio\`'e $2\gamma\langle h,h\rangle+\gamma^2\|v\|\ge 0$
per ogni $\gamma$. Scelgo $\gamma=-\left\langle  h,v \right\rangle /\left\langle  v,v \right\rangle $ ed ho
$-\langle  h,v \rangle ^2/\langle  v,v \rangle \ge 0$, cio\`e 
$\langle  h,v \rangle =0$. 

Viceversa, se $\langle h,v\rangle=0$ per ogni $v\in\mathcal W$ allora $\|h+\gamma v\|^2=\langle h+\gamma v,h+\gamma v\rangle=
\langle h,h\rangle+\gamma^2\langle v,v\rangle\ge \|h\|^2$.
\qed

Il seguente risultato d\`a una espressione esplicita della soluzione di
miglior approssimazione

\begin{teo}
Nell'ipotesi del teorema precedente la soluzione di miglior approssimazione
 $g$ \`e :
$g=\sum_{i=0}^n\alpha_i \varphi_i$ dove
\[
A\left[\begin{array}{c}\alpha_0\\\vdots\\\alpha_n\end{array}\right]=
\left[\begin{array}{c}b_0\\\vdots\\b_n\end{array}\right]
\]
con $A=(a_{i,j})$, $a_{i,j}=\left\langle  \varphi_i,\varphi_j \right\rangle $, $b_i=\left\langle  f,\varphi_i \right\rangle $.
\end{teo}
{\bf Dim.} $f-g$ \`e
ortogonale a $\mathcal W=\hbox{span}(\varphi_0,\ldots,\varphi_n)$, 
cio\`e $\left\langle  f-g,\varphi_j \right\rangle =0$ per $j=0,1,\ldots,n$
e questa \`e la $j$-esima equazione.\qed

\begin{cor}
Se $\varphi_0,\ldots,\varphi_n$ sono ortogonali allora
$\alpha_i=\left\langle  f,\varphi_i \right\rangle /\left\langle  \varphi_i,\varphi_i \right\rangle $. Quindi
\[
g_n=\sum_{i=0}^n \frac{\left\langle  f,\varphi_i \right\rangle }{\left\langle  \varphi_i,\varphi_i \right\rangle }\varphi_i
\]
\end{cor}

I coefficienti $\frac{\left\langle f,\varphi_i \right\rangle
}{\left\langle \varphi_i,\varphi_i \right\rangle }$ sono chiamati i
{\em coefficienti di Fourier} di $f(x)$.



\begin{teo}
Sia $\{\varphi_i\in\HH,~ i=0,1,2,\ldots\}$ un insieme ortogonale nello
spazio di Hilbert $\HH$. Sia \[
g_n=\sum_{i=0}^n\frac{\left\langle  f,\varphi_i \right\rangle }{\left\langle  \varphi_i,\varphi_i \right\rangle }\varphi_i
\]
la funzione di miglior approssimazione di $f$, $r_n=f-g_n$ il resto e 
$\delta_n=\|r_n\|$ l'errore di approssimazione. Allora vale
\begin{equation}\label{M1}
\delta_n^2=\|f\|^2-\sum_{i=0}^n\frac{\langle f,\varphi_i\rangle^2}{\langle\varphi_i,\varphi_i\rangle}
\end{equation}
per cui la successione $\delta_n$ \`e non crescente.
 inoltre la serie $\sum_{i=0}^{\infty}\frac{\langle f,\varphi_i\rangle^2}{\langle \varphi,\varphi\rangle}$ \`e convergente e
\begin{equation}\label{bessel}
\|f\|^2\ge \sum_{i=0}^\infty\frac{\left\langle  f,\varphi_i \right\rangle ^2}{\left\langle  \varphi_i,\varphi_i \right\rangle }\hfill\hbox{\rm
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~diseguaglianza di Bessel}
\end{equation}
quindi la serie in \eqref{bessel} \`e convergente. Se inoltre l'insieme 
$\{\varphi_i\in\HH,~ i=0,1,2,\ldots\}$ \`e anche completo vale
\begin{equation}\label{parseval}
\|f\|^2=\sum_{i=0}^n\frac{\left\langle  f,\varphi_i \right\rangle ^2}{\left\langle  \varphi_i,\varphi_i \right\rangle }+\delta_n^2=
\sum_{i=0}^{+\infty}\frac{\left\langle  f,\varphi_i \right\rangle ^2}{\left\langle  \varphi_i,\varphi_i \right\rangle }\hfill\hbox{\rm 
~~~~~~~~~uguaglianza di Parseval}
\end{equation}
per cui la successione $\delta_n$ converge a zero in modo monotono.
\end{teo}
{\bf Dim.}
Se $g_n$ \`e di migliore approssimazione per $f$ rispetto a
$\varphi_0,\varphi_1,\ldots,\varphi_n$, allora
$\delta_n^2=\|f-g_n\|^2=\left\langle  f-g_n,f-g_n \right\rangle =\left\langle  f-g_n,f \right\rangle $ essendo $g_n$ ortogonale a
$h=f-g_n$. Risulta allora che
\[\begin{split}
\delta_n^2=&\|f\|^2-\left\langle  f,g_n \right\rangle \\
=&
\|f\|^2-\left\langle  f,\sum_{i=0}^n \frac{\left\langle  f,\varphi_i \right\rangle }{\left\langle  \varphi,\varphi \right\rangle }\varphi_i \right\rangle \\
=&\|f\|^2-\sum_{i=0}^n\frac{\left\langle  f,\varphi_i \right\rangle ^2}{\left\langle  \varphi_i,\varphi_i \right\rangle }\ge 0
\end{split}
\]
cio\`e la \eqref{M1}. In particolare, per ogni $n$ vale
\[
\|f\|^2\ge \sum_{i=0}^n\frac{\left\langle  f,\varphi_i \right\rangle ^2}{\left\langle  \varphi_i,\varphi_i \right\rangle }.
\]
Quindi la serie
$\sum_{i=0}^{+\infty}\frac{\left\langle  f,\varphi_i \right\rangle ^2}{\left\langle  \varphi_i,\varphi_i \right\rangle }$ converge e
vale
\[
\|f\|^2\ge \sum_{i=0}^{+\infty}\frac{\left\langle  f,\varphi_i \right\rangle ^2}{\left\langle  \varphi_i,\varphi_i \right\rangle }.
\]
Dimostriamo ora che se $\{\varphi_0,\varphi_1,\ldots\}$ \`e completo allora $\|f\|^2\le
\sum_{i=0}^{+\infty}\frac{\left\langle  f,\varphi_i \right\rangle ^2}{\left\langle  \varphi_i,\varphi_i \right\rangle }$. Sia
$\mathcal S=\{\sum_{i=0}^n\alpha_i\varphi_i:~n\in\N,~\alpha_i\in\R\}$. 
Per il lemma
\ref{lem3} vale $\bar {\mathcal S}=\HH$. Quindi per ogni $\epsilon>0$ esiste $\psi\in \mathcal S$
tale che $\|f-\psi\|\le \epsilon$, $\psi=\sum_{i=0}^n\gamma_i\varphi_i$. Per il
teorema \ref{miglapp} esiste ed \`e unica la soluzione di migliore approssimazione
$g=\sum_{i=0}^n\alpha_i^*\varphi_i$ tale che $\|f-g\|\le\|f-\psi\|\le
\epsilon$. Quindi
\[
\epsilon\ge \|f-g\|\ge |\, \|f\|-\|g\|\, |\ge \|f\|-\|g\|
\] 
da cui
\[
(\|f\|-\epsilon)^2\le\|g\|^2=\left\langle  g,g \right\rangle =\sum_{i=0}^n\frac{\left\langle  f,\varphi_i \right\rangle ^2}{\left\langle  \varphi_i,\varphi_i \right\rangle }\le \sum_{i=0}^{+\infty}\frac{\left\langle  f,\varphi_i \right\rangle ^2}{\left\langle  \varphi_i,\varphi_i \right\rangle }
\]
per ogni $\epsilon>0$. Passando al limite per $\epsilon\to 0$ si ha
\[
\|f\|^2\le\sum_{i=0}^{+\infty}
\frac{\left\langle  f,\varphi_i \right\rangle ^2}{\left\langle\varphi_i,\varphi_i \right\rangle }
\]
che completa la dimostrazione.
\qed
\\

Esempio: il prodotto scalare $\left\langle  f,g \right\rangle =\int_a^bf(x)g(x)\omega(x)dx$ definisce lo
spazio di Hilbert delle funzioni da $[a,b]$ in $R$ per cui \`e finito
l'integrale di Lebesgue $\int_a^bf(x)^2\omega(x)dx$, dove
$\omega(x):(a,b)\to\R$ \`e una funzione a valori positivi.
\\

Esempio: $\varphi_i(x)=x^i$, $i=0,1,2,\ldots$, non \`e un sistema
ortonormale in $L^2[0,1]$. Vale
$\left\langle  \varphi_i,\varphi_j \right\rangle =\int_0^1x^{i+j}dx=1/(i+j+1)$. La matrice
$A=(a_{i,j})_{i,j=0:n}$, $a_{i,j}=1/(i+j+1)$ \`e detta matrice di Hilbert. Il
suo numero di condizionamento cresce esponenzialmente con $n$.\\

\begin{oss}\rm
La scelta $\varphi_i(x)=x^i$ oltre a non fornire un sistema ortonormale di
funzioni, \`e particolarmente infelice poich\'e  la matrice del sistema che
fornisce la funzione di migliore approssimazione \`e fortemente mal
condizionata per cui dal punto di vista numerico il problema della sua
risoluzione diventa intrattabile gi\`a per valori moderati  di $n$.
Un'altro inconveniente \`e che nel passare da $n$ a $n+1$ i calcoli svolti per
risolvere il sistema $n\times n$ non possono essere utilizzati per facilitare
la risoluzione del sistema $(n+1)\times(n+1)$.
\qed\end{oss}

\begin{oss}\rm
Si osservi che se $\{\varphi_i\}$ \`e sistema ortogonale completo, 
dall'espressione 
\[
\delta_n^2=\|f\|_2^2-\sum_{i=0}^n\frac{\left\langle  \varphi_i,f \right\rangle
  ^2}{\left\langle \varphi_i,\varphi_i \right\rangle }
\]
segue che il valore di $\delta_n$ \`e calcolabile esplicitamente. Per cui,
data una tolleranza $\epsilon$, il calcolo dei coefficienti di Fourier pu\`o
essere condotto per $n=1,2,3,\ldots$, fintanto che $\delta_n<\epsilon$. Inoltre il passare da $n$ a
$n+1$ non comporta il dover risolvere un nuovo sistema lineare come nel caso
di un sistema non ortogonale.
\qed\end{oss}

\begin{oss}\rm
Purtroppo, con un sistema ortogonale completo dato da un prodotto scalare, la
relazione $\|\delta_n\|\le\epsilon$ non implica che $|f(x)-g_n(x)|\le\epsilon$
per ogni $x$. Per avere verificata quest'ultima condizione bisogna adottare la
norma infinito la quale non \`e indotta da nessun prodotto scalare.

In particolare $\|h\|_2\le\epsilon$ non implica $\|h\|_\infty\le\epsilon$. Per
questo basta scegliere $L^2([0,1])$ con 
$h(x)=x^n$ per cui $\|h\|_2^2=1/(2n+1)$, $\|h\|_\infty=1$.
\qed\end{oss}

In generale la convergenza in $L^2$ non implica la convergenza in $L^\infty$.
Per\`o sotto particolari condizioni s\`\i. Vale infatti il seguente

\begin{teo}
Per $n\ge 1$ sia $g_n(x)$ la funzione di migliore approssimazione di $f(x)\in
C[-1,1]$ ottenuta scegliendo come $\varphi_i$ i polinomi di Chebyshev di prima specie e col prodotto
scalare ad essi associato. Se $f(x)$ \`e
Lipschitziana allora $g_n(x)$ converge uniformemente a $f(x)$, i.e.,
$\lim_n\|f(x)-g_n(x)\|_\infty=0$.
Se $f\in C^k[-1,1]$, $k\ge 1$, allora $\exists$ $\gamma\in\R$, $\gamma>0$:
$\|f-g_n\|_\infty\le \gamma\frac{\log n}{n^k}$ e vale
\[
f(x)=\frac{\alpha_0}2+\sum_{i=1}^{+\infty}\alpha_i T_i(x).
\]
\end{teo}
La serie del teorema precedente \`e detta Serie di Chebyshev.

\begin{oss}\rm
Dal punto di vista computazionale talvolta \`e conveniente scegliere delle
funzioni $\varphi_i(x)$ che pur non essendo ortogonali verifichino la seguente
propriet\`a: siano a supporto compatto e siano tali che
supp$(\varphi_i)\cap$supp$(\varphi_j)=\emptyset$ se $|i-j|\ge k$ per un intero
$k>0$ ragionevolmente piccolo. In questo modo si verifica facilmente che la
matrice $A$ del sistema lineare che fornisce i coefficienti della migliore
approssimazione \`e una matrice a banda con $2k+1$ diagonali. 
Sistemi lineari con matrici a banda si risolvono in modo poco costoso con le
metodologie dell'algebra lineare numerica. 

Una possibile scelta a questo riguardo \`e quella di suddividere
l'intervallo $[a,b]$ in intervalli equispaziati $x_i=a+ih$,
$h=1/(b-a)$, $i=0,1,\ldots,n$, fissare una funzione $\varphi(x)$ che
abbia supporto $[-h,h]$ e sia nulla al di fuori di esso e porre
$\varphi_i(x)=\varphi(x-x_i)$, $i=0,\ldots,n$. Funzioni usualmente
utilizzate nel contesto delle equazioni differenziali sono le {\em hat
  functions} \\ \includegraphics[width=5cm]{hatfunction} \\
ottenute con
$\varphi(x)=\max(0,h-|x|)$.  Per l'insieme delle funzioni hat col
prodotto scalare $\langle f,g\rangle=\int_a^bf(x)g(x)dx$ la matrice
$A$ \`e tale che $A=(h^3/6)$trid$(1,4,1)$, cio\`e \`e tridiagonale con
elementi diagonali uguali a $4(h^3/6)$ e elementi sopra e
sottodiagonali uguali a $h^3/6$. La matrice \`e fortemente dominante
diagonale e ha numero di condizionamento indipendente dalla
dimensione. Questo d\`a alla matrice propriet\`a computazionali
rilevanti.
\qed\end{oss}


\section{Alcune considerazioni sull'interpolazione}
Finora abbiamo studiato metodi e propriet\`a di approssimazione di funzioni
mediante polinomi. Su spazi di Hilbert con norme derivanti da un prodotto
scalare abbiamo caratterizzato la migliore soluzione con resto di
 minima norma e descritto come calcolarla.

Abbiamo introdotto polinomi ortogonali che ben si prestano all'uopo. Per spazi
di Banach, ad esempio $C[a,b]$ con la norma infinito la situazione \`e un po'
pi\`u complicata. Ci sono comunque metodi per calcolare il polinomio di
migliore approssimazione in norma infinito.

Abbiamo poi visto come usando polinomi di Chebyshev, e quindi il prodotto
scalare associato, la serie di Fourier, ribattezzata serie di Chebyshev,
converge uniformemente a $f(x)$ se $f$ \`e lipschitziana o di classe
$C^k[a,b]$. Per cui la serie di Chebyshev d\`a un buon approssimante in norma
infinito anche se non ottimo.

Ci chiediamo ora cosa si pu\`o dire delle approssimazioni ottenute con
polinomi di interpolazione.

\begin{defi}
Dato un intervallo $[a,b]$ definiamo {\em tavola dei nodi} su $[a,b]$ l'insieme
$\{x^{(n)}_i\in[a,b]:\quad i=0,\ldots,n,~~n\in\N,~~x^{(n)}_i\ne x^{(n)}_j,~~
\hbox {se}~i\ne j\}$.
\end{defi}

Dati un intervallo $[a,b]$ e una tavola di nodi $x^{(n)}_i\in[a,b]$, 
$i=0,\ldots,n$,  e una $f\in C[a,b]$, definiamo
$p_n(x)=\sum_{i=0}^nf(x_i^{(n)})L_{i,n}(x)$, dove $L_{i,n}(x)$ sono i polinomi
di Lagrange definiti da
\[
L_{i,n}(x)=\prod_{j=0,n,~j\ne i}\frac{x-x_j^{(n)}} {x_i^{(n)}-x_j^{(n)}}. 
\]
Poich\'e $L_{i,n}(x_j^{(n)})=\delta_{i,j}$, ne segue che
$p_n(x_i^{(n)})=f(x_i^{(n)})$, cio\`e il polinomio $p_n(x)$ \`e il polinomio di
interpolazione di $f(x)$ relativo ai nodi $x_i^{(n)}$, $i=0,1,\ldots,n$.

Definisco l'operatore $\mathcal A_n:C[a,b]\to \mathcal P_n$ tale che
$\mathcal A_n(f)=p_n$. Voglio studiare il condizionamento di $\mathcal A_n$

\subsection{Costanti di Lebesgue e condizionamento dell'interpolazione}
Denotiamo $f_i=f(x_i^{(n)})$ (tralasciando per semplicit\`a la dipendenza da
$n$). In questo modo il polinomio di interpolazione si scrive come
$p_n(x)=\sum_{i=0}^n f_iL_{i,n}(x)$. Se perturbo i valori $f_i$ in $\tilde
f_i$ ho il polinomio $\tilde p_n(x)=\sum_{i=0}^n \tilde f_iL_{i,n}(x)$.
Per cui
\[
|p_n(x)-\tilde p_n(x)|\le \sum_{i=0}^n|f_i-\tilde f_i|\cdot |L_{i,n}(x)|\le
\max_i|f_i-\tilde f_i|\, \sum_{i=0}^n |L_{i,n}(x)|.
\]
Pongo $\Lambda_n=\max_{x\in[a,b]}\sum_{i=0}^n |L_{i,n}(x)|$ ed ho
\[
|p_n(x)-\tilde p_n(x)|\le\Lambda_n\max_i|f_i-\tilde f_i|, ~~\forall~ x\in[a,b],
\]
da cui 
\begin{equation}\label{starred}
\|p_n-\tilde p_n\|_\infty\le\Lambda_n\|f-\tilde f\|_\infty.
\end{equation}
Cio\`e la quantit\`a $\Lambda_n$ esprime la massima amplificazione che  pu\`o
avere $\|p_n-\tilde p_n\|_\infty$ sotto perturbazioni dei valori di
$f$. Quindi esprime una maggiorazione del condizionamento numerico
dell'operatore $\mathcal A_n$ che a $f(x)$ associa il polinomio di
 interpolazione in relazione alla tavola di nodi scelta.

La costante $\Lambda_n$ \`e chiamata {\em costante di Lebesgue} e dipende
unicamente dalla tavola di nodi di interpolazione. Ogni tavola di nodi di
interpolazione ha quindi la sua corrispondente costante di Lebesgue.

Da \eqref{starred} applicata con $g=f-\widetilde f$, segue
$\Lambda_n\ge\frac{\max_x|\mathcal A_n(g(x))}{\max_x |g(x)|}$.
Vale la seguente propriet\`a:

\[
\Lambda_n=\max_{g\in C[a,b],\, \|g\|_\infty=1}\|\mathcal
A_n(g)\|_\infty=:\|\mathcal A_n\|_\infty
\]
per dimostrarlo basta osservare che
\[\begin{split}
\sup_{g\in C[a,b]}\frac{\|\A_n(g)\|_\infty}{\|g\|_\infty}&=\sup_{g\in C[a,b]}\frac{\|\sum g(x_i^{(n)})L_{i,n}(x)\|_\infty}{\|g\|_\infty}\\
&\le\frac{\max_i|g(x^{(n)}_i)|\max_{x\in[a,b]}\sum_i|L_{i,n}(x)|}{\|g\|_\infty}\\
&\le\max_{x\in[a,b]}
\sum_i|L_{i,n}(x)|.
\end{split}
\]
Inoltre, se si sceglie $g$ in modo che $\|g\|_\infty=1$ e $g(x_i^{(n)})=\pm 1$ a seconda del segno di $L_{i,n}(\xi)$,  dove $\xi$ \`e il punto in cui 
$\sum_i|L_{i,n}(x)|$ prende il valore massimo, si ottiene l'uguaglianza.


\begin{teo}\label{thcheb}
Sia $f\in C[a,b]$ e $p_n(x)$ il polinomio di interpolazione relativo alla
tavola di nodi $x_i^{(n)}$. Sia inoltre $q_n(x)$ il polinomio di migliore approssimazione uniforme. Allora vale
\[
\|f-p_n\|_\infty\le (1+\Lambda_n)\|f-q_n\|_\infty.
\]
\end{teo}
{\bf Dim.}
Siano $p_n$ il polinomio di interpolazione e $q_n$ il polinomio di miglior
approssimazione uniforme. 
%Se $f\in\PP_n$ allora $p_n=q_n=f$. Supponiamo allora
%$f\not\in\PP_n$, cio\`e $f-q\not\equiv 0$ $\forall q\in\PP_n$. Per ogni
%$q\in\PP_n$ vale $\A_n(q)=q$ inoltre
%\[
%\A_n(f-q_n)=\A_n(f)-\A_n(q_n)=p_n-q_n.
%\] 
%Poich\'e $f-q_n\not\equiv 0$ ho
%\[
%\Lambda_n=\sup_{g\in C[a,b]\backslash 0}
%\frac{\|\A_n(g)\|_\infty}{\|g\|_\infty}\ge \frac{\|\A_n(f-q_n)\|_\infty}{\|f-q_n\|_\infty}=\frac{\|p_n-q_n\|_\infty}{\|f-q_n\|_\infty}
%\]
%che implica $\|p_n-q_n\|_\infty\le\Lambda_n\|f-q_n\|_\infty$. Quindi, 
Poich\'e
$f-p_n=f-q_n+q_n-p_n$ si ha
\[
\|f-p_n\|_\infty\le \|f-q_n\|_\infty+\|q_n-p_n\|_\infty=\|f-q_n\|_\infty+\|\mathcal A_n(q_n-f)\|_\infty\le (1+\Lambda_n)\|q_n-f\|_\infty
\]
che completa la dimostrazione.
\qed

\begin{oss}\rm Se $\Lambda_n$ \`e ``piccola'' allora l'errore
  dell'interpolazione \`e poco pi\`u grande di quello della migliore
  approssimazione uniforme. \`E quindi importante usare delle tavole di nodi
  che comportino costanti di Lebesgue $\Lambda_n$ il pi\`u piccole possibile.
\qed\end{oss}


Si riportano i valori di $\Lambda_n$ per alcune tavole di nodi su $[-1,1]$
\begin{itemize}
\item Punti equispaziati: $\Lambda_n\approx 2^{n+1}/(e n\log n)$
\item Punti di Chebyshev $x_{i}^{(n)}=\cos(\frac{(2i+1)\pi}{2(n+1)})$,
  $i=0,\ldots,n$:
\[
\frac 2\pi \log(n+1)+0.96\le\Lambda_n\le \frac 2\pi \log(n+1)+1.
\]
I nodi$x_i^{(n)}$  sono gli zeri dei polinomi di Chebyshev di prima specie.
\end{itemize}


Si osservi la enorme differenza nei due casi che sottolinea
l'importanza dei nodi di Chebyshev. Per il teorema \ref{thcheb}
l'interpolazione sui nodi di Cebyshev, anche se non fornisce la
funzione di migliore approssimazione uniforme, d\`a un'approssimazione
che pu\`o essere ragionevole data la crescita logaritmica della
costante di Lebesgue associata $\Lambda_n$.

\`E noto che $\Lambda_n\ge \frac 2\pi\log(n+1)+0.818$ per ogni scelta dei nodi
ma non \`e nota la
tavola dei nodi che d\`a il valore minimo di $\Lambda_n$. Maggiori
informazioni sulle costanti di Lebesgue si trovano in \cite{smith}.

Un risultato negativo relativo all'interpolazione \`e il seguente teorema di Faber:

\begin{teo}[Faber]
Non esiste nessuna tavola di nodi su $[a,b]$ tale che  per ogni $f\in C[a,b]$
il polinomio di interpolazione relativo a questa tavola di nodi converga
uniformemente a $f$.
\end{teo}

Per dimostrare questo risultato bisogna richiamare il teorema di
Banach-Steinhaus

\begin{teo}[Banach-Steinhaus]
$X$ spazio di Banach, $Y$ spazio normato, $\mathcal F=\{\A:X\to
  Y,~~\A~\hbox{lineare e continuo}\}$, $\|\A\|=\sup\frac{\|\A(x)\|}{\|x\|}$.
Se per ogni $x\in X$ \`e $\sup_{\A\in\mathcal F}\|\A(x)\|<+\infty$ allora
$\sup_{\A\in\mathcal F}\|\A\|<+\infty$.
\end{teo}

La dimostrazione del teorema di Faber procede allora nel seguente
modo: se per assurdo esiste una tavola dei nodi tale che $\A_n(f)$
converge uniformemente a $f$ per ogni $f\in C[a,b]$, allora $\forall
f\in C[a,b]$ \`e $\lim_n \|\A_n(f)-f\|_\infty=0$, cio\`e
$\|\A_n(f)-f\|_\infty$ \`e limitata per ogni $n$. Si applica allora il
teorema di Banach-Steinhaus a $\{\mathcal A_n-1\}$ e si ha che 
$\|\mathcal A-1\|$ \`e limitata per ogni $n$ ma 
$\|\mathcal A_n-1\|\ge\|\mathcal A_n\|-1\ge\Lambda_n-1\ge \frac 2\pi\log n-1$, che \`e assurdo.
\qed

\section{Osservazioni su ``continuo e discreto''}
\begin{oss}
\rm
Nel caso discreto il problema di approssimare un vettore 
$\bm f\in\R^n$ con un vettore $\bm g\in\mathcal S\subset \R^n$ dove $\mathcal
S$ \`e il sottospazio generato dalle colonne della matrice
$A$ di dimensioni  $n\times m$, $m<n$ \`e
\[
\min_{\bm x\in\mathcal S} \|A\bm x-\bm f\|
\]
dove $\|\bm x\|=\left\langle  \bm x,\bm x \right\rangle ^{1/2}$. Se $A$ ha rango massimo, cio\`e le sue
colonne formano una base di $\mathcal S$ un approccio risolutivo \`e quello di
usare le {\em equazioni normali}
\[
\left\langle  A\bm e_i,A\bm c-\bm f \right\rangle =0
\]
che nel prodotto euclideo diventano
\[
A^T(A\bm x-\bm f)=0.
\]
Esse impongono l'ortogonalit\`a del residuo rispetto alle colonne di $A$,
cio\`e l'ortogonalit\`a del residuo rispetto allo spazio $\mathcal S$
esattamente come accadeva nel caso continuo.

Un altro approccio numericamente pi\`u stabile nel discreto consiste nel
calcolare la fattorizzazione $QR$ della matrice $A$: $A=QR$, dove $Q$ ha
colonne ortogonali e $R$ \`e triangolare superiore, e poi risolvere
\[
\min\|A\bm x-\bm f\|=\min\|QR\bm x-\bm f\|=\min\|Q(R\bm x-Q^T\bm f)\|=\min\|R\bm x-Q^T\bm f\|
\]
che fornisce $y_i=(Q^T\bm f)_i$, $R\bm x=\bm y$.

Nel continuo, questo corrisponde a costruirsi prima una base ortogonale di
$\mathcal S$ e a calcolarsi i coefficienti di Fourier.
\qed\end{oss}

\begin{oss}\rm
In Octave il grafico della funzione $f(x)$ su $[a,b]$
pu\`o essere tracciato
calcolando i vettori $\bm f=(f_i)$, $f_i=f(x_i)$ per $x_i=a+hi$, $i=0,\ldots,n$ con $h=(b-a)/n$ e tracciando la spezzata che
unisce i punti $(x_i,f_i)$ con $(x_{i+1},f_{i+1})$. 

Il prodotto scalare tra $f(x)$ e $g(x)$ pu\`o essere stimato approssimando
l'integrale $\int_0^1f(x)g(x)dx$ con $h\sum_{i}f_ig_i$, cio\`e $h\left\langle  \bm f,\bm g \right\rangle =h \bm f^T\bm g$.

La norma di $f(x)$ viene quindi approssimata da $(\frac {b-a}n\sum_i f_i^2)^{1/2}$.
Quindi la discretizzazione del problema continuo conduce ad un  problema
discreto come descritto nell'osservazione precedente
\qed\end{oss}

\begin{oss}\rm
Scegliendo la base dei monomi $\varphi_i(x)=x^i$ e campionando ciascun
polinomio $\varphi_i(x)$ nei nodi $x_i$ scelti si ottiene la matrice di
Vandermonde. Nel discreto la matrice di Hilbert $\left\langle  x^i,x^j \right\rangle $ \`e approssimata
dal prodotto tra la matrice di Vandermonde e la sua trasposta. 
\qed\end{oss}

Come potrebbe essere definita nel continuo l'analogo di una matrice di
Householder?

\begin{oss}\rm
Se $Ax=b$ \`e sistema lineare con $A$ matrice definita positiva,
allora il funzionale $\varphi(x)=\frac 12 x^TAx-b^Tx$ ha gradiente
$\nabla \varphi(x)=Ax-b$ che si annulla se e solo se $x$ \`e soluzione
del sistema lineare $Ax=b$. Inoltre l'hessiano di $\varphi(x)$
coincide con la matrice $A$ che \`e definita positiva. Quindi il
funzionale $\varphi$ \`e convesso e il suo unico punto di minimo \`e
la soluzione del sistema lineare $Ax=b$.

Questo fatto permette di interpretare la soluzione di un sistema
lineare definito positivo come punto di minimo di un funzionale e
quindi permette di costruire dei metodi di risoluzione iterativi
cos\`\i\ detti del gradiente, quali i metodi della discesa pi\`u
ripida e del gradiente coniugato. Tali metodi generano una successione
di punti $x_k$ in cui il funzionale assume valori decrescenti e tale
che $\lim_k\varphi(x_k)=0$.  Propriet\`a analoghe valgono per
operatori differenziali lineari ``definiti positivi''. Vedremo ci\`o
nella seconda parte.

La minimizzazione del funzionale $\varphi(x)$ pu\`o essere vista come
un problema di minima norma. Infatti, introduciamo il prodotto scalare
$\langle x,y\rangle= x^TAy$ (\`e prodotto scalare data la definita
positivit\`a di $A$) e la norma conseguente $\| x\|_A:=\langle
x,x\rangle^{1/2}$. Questa norma \`e chiamata {\em norma in energia}.
Denotata con $u$ la soluzione del sistema $Ax=b$
risulta allora
\[\begin{split}
\|x-u\|_A^2=&\langle x-u,x-u\rangle=x^TAx-2x^TAu+u^TAu\\
=&x^TAx-2x^Tb +u^Tb=2\varphi(x)+u^Tb
\end{split}\]
Cio\`e minimizzare il funzionale $\varphi(x)$ su un sottospazio $\mathcal V$ di $\R^n$ equivale a trovare il vettore di $\mathcal V$ che \`e pi\`u vicino alla soluzione del sistema $Ax=b$ in norma in energia.
\qed\end{oss}

\section{Il teorema di Korovkin}
In questa sezione\footnote{scritta da Federico Poloni} si presenta il
Teorema di Korovkin la cui estrema potenza risiede nella semplicit\`a
delle ipotesi, nella loro facile verificabilit\`a e nella notevole
forza della tesi. In particolare, data una successione di operatori da
$C(K)$ in s\'e, $K$ compatto di $\R^n$, basta verificare che tali
operatori siano lineari e positivi e che siano convergenti per un
numero finito di semplici funzioni continue (alcuni polinomi di grado
al pi\`u due) per concludere che la data successione di operatori \`e
in grado di approssimare ogni funzione continua. Non ultimo pregio del
Teorema di Korovkin \`e la estrema essenzialit\`a della sua
dimostrazione che si basa su conoscenze elementari di analisi
matematica.

     Per meglio definire il quadro in cui ci muoviamo, si riporta la
     definizione di operatore lineare e positivo (LPO).


Un operatore $L$ \`e detto \emph{operatore lineare positivo} (LPO) se:
\begin{enumerate}
 \item \`E lineare, cio\`e $L[\lambda f]=\lambda L[f]$ per ogni $\lambda \in \mathbb R$ (o $\mathbb C$), e $L[f+g]=L[f]+L[g]$
 \item \`E \emph{positivo}, cio\`e $L[f](x) \geq 0$ per ogni funzione $f$ tale che $f(x)\geq 0$ per ogni $x$. Cio\`e $L$ manda funzioni non negative su tutto il dominio in funzioni non negative su tutto il dominio.
\end{enumerate}
Notate che le due ipotesi implicano che se $f(x) \leq g(x)$ per ogni $x$ nel dominio, allora
\begin{equation}\label{monotonia}
 L[f](x) \leq L[g](x) \quad\text{per ogni $x$ nel dominio}
\end{equation}
e che
\begin{equation}\label{valass}
 \abs{L[f]} \leq L[|f|].
\end{equation}

Sia $L_n$ una successione di operatori. Diciamo che $L_n$ \emph{approssima bene} una funzione $f$ (in una certa norma $\norm\cdot$) se $\norm{L_n[f]-f} \to 0$ per $n\to\infty$.

\begin{teo}[Teorema di Korovkin, versione 1-dimensionale]
 Sia $K \subseteq \mathbb R$ un compatto, e sia $C(K)$ lo spazio delle
 funzioni continue da $K$ a $\mathbb R$ con la norma del sup
 (convergenza uniforme). Sia $(L_n)_{n=1}^\infty$ una successione di
 LPO su $C(K)$. Se $L_n$ approssima bene le tre funzioni:
\begin{itemize}
 \item $x\mapsto 1$ (la funzione costante uguale a 1),
 \item $x\mapsto x$ (l'identit\`a),
 \item $x\mapsto x^2$ (la funzione ``elevare al quadrato''),
\end{itemize}
allora $L_n$ approssima bene tutte le funzioni di $C(K)$.
\end{teo}
{\bf Dim.}
Siano $f \in C(K)$, e $\varepsilon>0$ fissati; dobbiamo mostrare che esiste $\tilde n$ tale che per ogni $n\geq \tilde n$ valga
\[
 \abs{L_n[f](y)-f(y)} \leq \varepsilon \quad \forall y \in K.
\]
Notiamo anche che al posto di $\varepsilon$ al membro di destra
possiamo mettere anche un'espressione del tipo $\gamma\varepsilon$, a patto
che $\gamma>0$ non dipenda n\'e da $n$ n\'e da $a$.

Chiamiamo inoltre $M:=\norm{f}_\infty$,
$
 N:=\max_{x \in K} \abs{x},
$
e $\delta$ \`e tale che $|x-y|<\delta \Rightarrow
|f(x)-f(y)|<\varepsilon$ (che esiste perch\'e una funzione continua su
un compatto \`e uniformemente continua).

Innanzitutto sfruttiamo l'ipotesi: definiamo per ogni $n$, $y$
\[
\begin{aligned}
 \epsilon^{(n)}_0(y):=&L_n[x\mapsto 1](y)-1,\\
 \epsilon^{(n)}_1(y):=&L_n[x\mapsto x](y)-y,\\
 \epsilon^{(n)}_2(y):=&L_n[x\mapsto x^2](y)-y^2.\\
\end{aligned}
\]

Per l'ipotesi, possiamo prendere $\tilde n$ sufficientemente grande, in modo che per $n\geq \tilde n$ si abbia $\norm{\epsilon^{(n)}_i}_\infty<
\min(\varepsilon,\varepsilon\delta^2)$ per $i=0,1,2$. 

Ora, fissiamo $y \in K$ e per ogni $n\geq \tilde n$ scriviamo la stima
\[
\begin{aligned}
 \abs{L_n[f](y)-f(y)} \leq &\abs{L_n[f](y)-f(y)L_n[ 1](y)}+\abs{f(y)L_n[ 1](y)-f(y)}\\
 =& \abs{L_n[ f(x)-f(y)](y)}+\abs{\epsilon_0^{(n)}(y)f(y)}\\
 \leq& L_n[ \abs{f(x)-f(y)}](y)+M\varepsilon
\end{aligned}
\]
(abbiamo usato la \eqref{valass} nell'ultimo passaggio). Lavoriamo separatamente ora sul primo dei due addendi; si ha
\[
\begin{aligned}
 \abs{f(x)-f(y)} \leq &\begin{cases}
                                      \varepsilon & \text{per }|x-y|\le\delta\\
                                      2M & \text{per }|x-y|>\delta
                                     \end{cases}\\
\leq & \begin{cases}
                                      \varepsilon & \text{per }|x-y|\le\delta\\
                                      \frac {2M}{\delta^2} (x-y)^2 & \text{per }|x-a|>\delta
                                     \end{cases} \\ \leq& \varepsilon+\frac {2M}{\delta^2} (x-y)^2
\end{aligned}
\]
quindi per la \eqref{monotonia} e la \eqref{valass}, abbiamo
\[
\begin{aligned}
L_n[ \abs{f(x)-f(y)}](y) \leq& L_n[ \varepsilon+\frac {2M}{\delta^2} (x-y)^2]\\
=& \varepsilon L_n[ 1](y)+\frac{2M}{\delta^2}\left(y^2L_n[ 1](y)+
L_n[ x^2](y)-2yL_n[ x](y)\right)\\
=& \varepsilon(1+\epsilon_0^{(n)}(y))+\frac{2M}{\delta^2}
\left(y^2(1+\epsilon_0^{(n)}(y))+(y^2+\epsilon_1^{(n)}(y))-
2y(y+\epsilon_2^{(n)}(y)  \right)\\
=& \varepsilon(1+\epsilon_0^{(n)}(y))+\frac{2M}{\delta^2}
(y^2\epsilon_0^{(n)}(y)+\epsilon_1^{(n)}(y)-2y\epsilon_2^{(n)}(y))
%=& \left(\varepsilon + \frac{y^2 M}{\delta^2}\right) L_n[x\mapsto 1](y)+
%\frac M{\delta^2}L_n[x\mapsto x^2](y)-\frac {2yM}{\delta^2}L_n[x\mapsto x](y)
%\\ =& \left(\varepsilon + \frac{y^2 M}{\delta^2}\right) (1+\epsilon_0(y))+
%\frac M{\delta^2}(y^2+\epsilon_2(y))-\frac {2yM}{\delta^2}(y+\epsilon_1(y))\\
%=& \varepsilon+\frac{y^2M}{\delta^2}\epsilon_0^{(n)}(y)+
%\frac M{\delta^2}\epsilon_2^{(n)}(y)-\frac {2yM}{\delta^2}\epsilon_1^{(n)}(y)
\end{aligned}
\]
Ora, poich\'e abbiamo scelto $\tilde n$ in modo che per $n\ge\tilde n$
le quantit\`a $\epsilon_i^{(n)}(y)$ siano in modulo minori di $\delta^2\varepsilon$ si ha
\[
L_n[ \abs{f(x)-f(y)}](y) 
\leq \gamma\varepsilon %+{N^2M}\varepsilon+M\varepsilon+{2NM}\varepsilon
\]
con $\gamma>0$ 
% La quantit\`a a cui arriviamo, come richiesto, \`e della forma 
% $C\varepsilon$, con $C$ costante 
che dipende solo dalle scelte di $K$ e $f$. Quindi il teorema \`e dimostrato.
\qed

Notate che nelle stime compaiono quantit\`a che dipendono da $f$:
quindi la successione di LPO approssima bene tutte le funzioni, ma su
alcune funzioni l'approssimazione converge pi\`u lentamente che su
altre.

Cosa si pu\`o dire sulla velocit\`a di convergenza? Se
$\norm{\epsilon^{(n)}_i}_\infty=O(h(n))$ per $i=0,1,2$, allora
$\norm{f-L_n[f]}_\infty=O(h(n))$ per ogni $f$ (per\`o occhio che la
costante nascosta nella notazione $O(\cdot)$ dipende da $f$). Quindi
se per esempio una successione di LPO converge linearmente,
quadraticamente, \dots sulle tre funzioni di test, allora converge con
lo stesso ordine per tutte le funzioni. Osservate che nella
dimostrazione abbiamo richiesto che per $n>\tilde n$ valga
$|\epsilon_i^{(n)}|\le \varepsilon/\delta^2$ dove $\delta$ \`e tale
che $|x-y|\le\delta~\Rightarrow~|f(x)-f(y)|\le\varepsilon$. La
``piccolezza'' di $\delta$ rispetto a $\epsilon$ ha un ruolo negativo
sulla convergenza. Pi\`u piccolo \`e $\delta$ e maggiore \`e il valore
di $\tilde n$ oltre il quale vale la maggiorazione dell'errore $|L_n[
  f(x)](y)-f(y)|\le \gamma\varepsilon$.

Osserviamo ancora che avremmo potuto maggiorare $|f(x)-f(y)|$ con
$\varepsilon+\frac{2M}\delta |x-y|$, rimuovendo il $\delta^2$ al
denominatore. Per\`o in questo caso non avremmo potuto esprimere
$|x-y|$ come combinazione lineare dei polinomi $1,x,x^2$. Questo fatto
\`e essenziale per arrivare alla maggiorazione richiesta.



\subsection{Generalizzazioni}
\begin{teo}[Teorema di Korovkin, versione $m$-dimensionale]
 Sia $K \subseteq \mathbb R^m$ un compatto, e sia $C(K)$ lo spazio delle funzioni continue da $K$ a $\mathbb R$ con la norma del sup (convergenza uniforme). Sia $(L_n)_{n=1}^\infty$ una successione di LPO su $C(K)$. Se $L_n$ approssima bene le tre funzioni:
\begin{itemize}
 \item $x\mapsto 1$ (la funzione costante uguale a 1),
 \item $x\mapsto x_i$, $i=1,2,\dots,m$ (la proiezione sulla $i$-esima componente)
 \item $x\mapsto x_i^2$, $i=1,2,\dots,m$ (la funzione ``elevare al quadrato''),
\end{itemize}
allora $L_n$ approssima bene tutte le funzioni di $C(K)$.
\end{teo}

Vale una versione del teorema di Korovkin per funzioni di variabile
reale a valori complessi. In questo caso la monotonia dell'operatore
va intesa ristretta a funzioni che prendono valori reali, cio\`e se
$f$ \`e tale che $f(x)\in\mathbb R$ e $f(x)\ge 0$ allora $L[f]$ \`e
una funzione a valori reali tale che $L[f](y)\ge 0$. Per linearit\`a
la monotonia si applica anche alla parte reale e alla parte
immaginaria della funzione. Ad esempio, se $f(x)=f_1(x)+i f_2(x)$,
dove $i^2=-1$, con $f_1(x)$ e $f_2(x)$ funzioni reali non negative,
posto $g(y)=L[f(x)](y)=g_1(y)+ig_2(y)$, con $g_1(y),g_2(y)$ funzioni
reali, allora la monotonia di $L$ implica che anche $g_1(y)$ e
$g_2(y)$ sono non negative.

\begin{teo}[Teorema di Korovkin, versione complessa]
 Sia $\mathcal B=\{f:[0,2\pi]\to \mathbb C, f(0)=f(2\pi)\}$ (funzioni
 complesse continue e $2\pi$-periodiche), con la norma del sup
 (convergenza uniforme). Sia $(L_n)_{n=1}^\infty$ una successione di
 LPO su $\mathcal B$. Se $L_n$ approssima bene le tre funzioni:
\begin{itemize}
 \item $x\mapsto 1$,
 \item $x\mapsto e^{ix}$,
 \item $x\mapsto e^{-ix}$,
\end{itemize}
allora $L_n$ approssima bene tutte le funzioni di $\mathcal B$.
\end{teo}

Rispetto alla versione 1D, cambia solo l'insieme delle funzioni su cui
richiediamo la convergenza tra le ipotesi (il cosiddetto \emph{test di
  Korovkin}).

\subsection{Polinomi di Bernstein}
I \emph{polinomi di Bernstein} sono la successione di LPO su $K=[0,1]$ definita da
\[
 B_n[f](x):=\sum_{k=0}^n \binom{n}{k}x^k(1-x)^{n-k}f\left(\frac kn\right)
\]

Si verifichi per esercizio che 
 i polinomi di Bernstein sono LPO.


\subsection{Un'applicazione: dimostrazione del teorema di approssimazione di Weierstrass}
Ci servir\`a nel seguito questo lemmetto con i binomiali.
\begin{lem}[formule ``in-and-out'' per i binomiali]
Valgono le seguenti identit\`a.
 \begin{enumerate}
  \item $\binom{n}{k}=\frac nk \binom{n-1}{k-1}$
  \item $\binom{n}{k}=\frac {n(n-1)}{k(k-1)} \binom{n-2}{k-2}$
 \end{enumerate}
\end{lem}
{\bf Dim.} Applica le definizioni\dots \qed

\begin{teo}[di approssimazione di Weierstrass, caso 1D]
 Sia $K \subseteq \mathbb R$ un compatto, e $f \in C(K)$. Allora, per ogni $\varepsilon>0$ esiste un polinomio $p=p_{f,\varepsilon}$ tale che
\[
 \norm{f-p}_\infty \leq \varepsilon.
\]
\end{teo}
{\bf Dim.}
Ci basta provare il teorema per $K=[0,1]$, poi con qualche semplice trasformazione del dominio possiamo estenderlo a tutti gli altri compatti (come?).

Mostreremo che
\begin{equation} \label{Bnapprox}
\norm{f-B_n[f]}_\infty \to 0  \quad \text{quando $n\to \infty$.}
\end{equation}
Quindi basta prendere $p=B_n[f]$ per un $n$ sufficientemente grande. La \eqref{Bnapprox} \`e la tesi del teorema di Korovkin per i $B_n$, quindi ci basta dimostrare che sono soddisfatte le ipotesi, cio\`e che $\norm{f-B_n[f]}_\infty \to 0$ per le tre funzioni di test $x \mapsto 1$, $x \mapsto x$, $x \mapsto x^2$
\begin{itemize}
 \item Per $x \mapsto 1$:
\[ B_n[1](y)=\sum_{k=0}^n \binom{n}{k}y^k(1-y)^{n-k}=
(y+(1-y))^n=1,\]quindi l'errore \`e costantemente uguale a 0.
 \item Per $x \mapsto x$:
\[
 \begin{aligned}
  B_n[x](y)=&\sum_{k=0}^n \binom{n}{k}y^k(1-y)^{n-k}\frac kn\\
 =&\sum_{k=1}^n \binom{n}{k}y^k(1-y)^{n-k}\frac kn\\
 =&\sum_{k=1}^n \binom{n-1}{k-1}y^k(1-y)^{n-k}\\
 =&\sum_{h=0}^{n-1} \binom{n-1}{h}y^{h+1}(1-y)^{n-1-h}=y(1+(1-y))^{n-1}=y\\
 \end{aligned}
\]
(abbiamo usato la in-and-out formula e cambiato indice $h:=k-1$) quindi di nuovo l'errore \`e sempre nullo.

\item Per $x \mapsto x^2$: usiamo l'identit\`a 
\[
 \frac{k^2}n^2=\frac k{n^2}+\frac{k^2}{n^2}-\frac k{n^2}=  \frac 1n \frac kn + \frac{n-1}n \frac{k(k-1)}{n(n-1)},
\]
le in-and-out formulas, e il risultato del punto precedente:
\[
 \begin{aligned}
  B_n[x^2](y)=&\sum_{k=0}^n \binom{n}{k}y^k(1-y)^{n-k}\frac {k^2}{n^2}\\
 =& \frac1n \left(\sum_{k=0}^n \binom{n}{k}y^k(1-y)^{n-k}\frac kn \right)\\
 &+\frac{n-1}n \left(\sum_{k=0}^n \binom{n}{k}y^k(1-y)^{n-k}\frac {k(k-1)}{n(n-1)}\right)\\
 =& \frac 1n y + \frac{n-1}n \left(\sum_{h=0}^{n-2} \binom{n-2}{h}y^{h+2}(1-y)^{n-2-h}\right)\\
 =& \frac 1n y + \frac{n-1}{n}y^2=y^2-\frac 1n y^2+\frac 1 n y
 \end{aligned}
\]
(stavolta abbiamo fatto il cambio di variabile $h:=k-2$).  Quindi
$B_n[x\mapsto x^2]$ converge uniformemente a $x \mapsto x^2$ (come ci
serviva per provare che valgono le ipotesi del teorema di Korovkin),
anche se stavolta c'\`e un errore di $O(\frac 1n)$. Del resto non
potevamo aspettarci che l'errore fosse zero anche stavolta: difatti,
se nella dimostrazione del teorema di Korovkin si ha $\epsilon_i^n=0$
per ogni $n$\dots
\end{itemize}
Quindi i polinomi di Bernstein soddisfano il teorema di Korovkin, e in particolare ci forniscono l'approssimazione che cercavamo sopra.
\qed

\subsection{Caso multidimensionale}
Il teorema di Weierstrass funziona pari pari in dimensione maggiore:
\begin{teo}[di approssimazione di Weierstrass]
 Sia $K \subseteq \mathbb R^m$ un compatto, e $f \in C(K)$. Allora, per ogni $\varepsilon>0$ esiste un polinomio $p=p_{f,\varepsilon}$ tale che
\[
 \norm{f-p}_\infty \leq \varepsilon.
\]
\end{teo}
{\bf Dim.}
Se $K=[0,1]^m$, funziona lo stesso trucco di sopra. Definiamo i \emph{polinomi di Bernstein $m$-dimensionali} come
\begin{multline*}
 B^{(m)}_n[f](y_1,\dots,y_n):=\\ \sum_{\scriptsize{\begin{array}{c}k_1=1,\dots,n\\k_2=1,\dots,n\\\vdots\\ k_m=1,\dots n  \end{array}}} \binom{n}{k_1}y_1^{k_1}(1-y_1)^{n-k_1}\binom{n}{k_2}y_2^{k_2}(1-y_2)^{n-k_2}\dots \binom{n}{k_m} y_m^{k_m}(1-y_m)^{n-k_m}f\left(\frac{k_1}n,\frac{k_2}n,\dots,\frac{k_m}n\right)
\end{multline*}
Con un po' di lavoro si riesce a provare che sono un LPO (facile) e che soddisfano le ipotesi del teorema di Korovkin (non \`e difficile come sembra: si riutilizzano diverse volte i calcoli fatti per il caso 1D \dots), quindi concludiamo come sopra.

Stavolta per\`o non \`e banale estendere il risultato da $K=[0,1]^m$ a un qualunque altro compatto. \`E facile estenderlo con un cambio di variabile a qualunque ``cubo'' $[-t,t]^m$, ma per passare a un compatto qualsiasi ora serve usare anche questo risultato (con $H=[-t,t]^m$ un cubo ``sufficientemente grande''):
\begin{teo}[caso $\mathbb R^m$ del teorema di estensione di Tietze]
 Sia $H \subseteq \mathbb R^m$ compatto, $K \subseteq H$ compatto in $H$, $f:K \to \mathbb R$ continua. Allora esiste $\tilde f: H \to \mathbb R$ che estende $f$.
\end{teo}
Il risultato \`e un caso particolare di un teorema pi\`u generale di topologia; non conosco una dimostrazione rapida e indolore di questo teorema nel caso $\mathbb R^m$ che serve a noi\footnote{Quando l'ho chiesto a un paio di analisti mi hanno assicurato che ``ma s\`\i, si dovrebbe fare con un po' di lavoro, considerando il modulo di continuit\`a di $f$ su $K$, che \`e uniformemente continua, estendendola localmente e usando la compattezza\dots''}.
\qed

\newpage
\section*{Esercizi}
\begin{ese}\rm
Sia $N$ intero positivo e
$a_i<b_i\le a_{i+1}<b_{i+1}$, per $i=1,\ldots,N-1$ numeri reali,
$\omega(x)$ funzione definita su $\cup_{i=1}^N[a_i,b_i]$ a valori
positivi tale che $\int_{a_i}^{b_i}f(x)\omega(x)dx$ sia finito per
$i=1,\ldots, N$ e per ogni polinomio $f(x)$.  Si verificichi che
$\langle p(x),q(x)\rangle=\sum_{i=1}^N\int_{a_i}^{b_i}p(x)q(x)\omega(x)dx$ 
\`e un  prodotto scalare, e si definiscano
 $p_i(x)$, $i=0,1,\ldots$, i polinomi ortogonali (normalizzati secondo un
qualsiasi criterio) rispetto a questo prodotto scalare.  
Dimostrare che

\noindent
a) i polinomi soddisfano una relazione a tre termini;\\
b) gli zeri di $p_n(x)$ sono tutti reali e distinti, gli intervalli $(b_i,a_{i+1})$ contengono al pi\`u uno zero, i rimaneni zeri  appartengono all'insieme
$\cup_{i=1}^N(a_i,b_i)$;  \\
\phantom{xxx} b1)
esiste un $\hat N$ tale che se $n>\hat N$ ogni intervallo $(a_i,b_i)$ contiene almeno uno zero di $p_n(x)$;\\
c) vale la formula di Christoffel-Darboux e la propriet\`a di ortogonalit\`a discreta $\sum_{k=1}^{n+1}p_i(x_k)p_j(x_k)w_k=0$ per $i\ne j$ dove $x_k$ sono gli zeri di $p_{n+1}(x)$, e $w_k$  delle opportune costanti positive;\\
d) il grado di precisione della formula di integrazione approssimata di Gauss sull'insieme $\cup_{i=1}^N[a_i,b_i]$ \`e $2n+1$.
\\ 
e) dire se \`e vero che per $n\ge N$ ogni intervallo contiene almeno uno zero di $p_n$.\\
\end{ese}


\begin{ese}\rm
Sia $T_n=(t_{ij})$ la matrice tridiagonale $n\times n$ definita da
$t_{ii}=10$, per $i=1,\ldots,n$, e $t_{i,i+1}=t_{i+1,i}=-1$, per
$i=1,\ldots,n-1$.
\begin{description}
\item {(a)}\quad Posto $p_0=1$ e $p_k(x)=\det(x\,I_k-t_k)$, per
$k=1,\ldots,n$, dove $I_k$ \`e la matrice identica di ordine $k$,
dire se i polinomi $p_k(x)$ sono ortogonali rispetto a qualche
prodotto scalare su qualche intervallo $[a,b]$.
\item {(b)}\quad In caso di risposta
affermativa, determinare l'intervallo $[a,b]$ e il prodotto
scalare.
\end{description}
\end{ese}

\begin{ese}\rm
Siano $\varphi_i(x)$, $i=0, 1,\ldots,n$, polinomi ortogonali
sull'intervallo $[-1,1]$ rispetto al prodotto scalare
\[
  <f,g>=\int_{-1}^1 \omega(x)f(x)g(x)\; dx,\quad
  \hbox{dove}\quad \omega(x)=(x^2-1)^2,\]
e dove $\varphi_i(x)$ ha grado $i$.
\begin{description}
\item {(a)}\quad  Si esprimano i $\varphi_i(x)$ mediante la formula di
Rodrigues.
 \item {(b)}\quad  Si calcolino i primi $\varphi_i(x)$.
 \item {(c)}\quad Sia ${\cal V}$ lo spazio dei polinomi di grado minore o
uguale a $n+2$ che si annullano in 1 e in $-1$. Si descriva mediante
i $\varphi_i(x)$ una base di
 polinomi ortogonali su $[-1,1]$ rispetto al prodotto scalare
 \[
  <f,g>=\int_{-1}^1 f(x)g(x)\; dx\]
per lo spazio ${\cal V}$.\quad (6 Aprile 2010)
\end{description}
\end{ese}


\begin{ese}\rm
Sia $\varphi_i(x)$, $i=0, 1,\ldots,n$, un insieme di polinomi
ortogonali normalizzati in modo che $\varphi_i(x)$ sia monico e tale
che il grado di $\varphi_i(x)$ sia $i$. Per $i=1,2,\ldots,n$ si
consideri la funzione razionale
$f_i(x)=\varphi_i(x)/\varphi_{i-1}(x)$.
\begin{description}
\item {(a)}\quad
Si dimostri che $f_{i+1}(x)=x+B_i-C_i/f_i(x)$, $i=1,2,\ldots,n-1$
per opportune costanti $B_i$ e $C_i$.
\item {(b)}\quad Si usi questa propriet\`a per
dimostrare che gli zeri di $\varphi_i(x)$ separano quelli di
$\varphi_{i+1}(x)$.
 \end{description}
\end{ese}

\begin{ese}\rm
Vogliamo estendere la teoria dei polinomi ortogonali a polinomi che hanno
coefficienti matriciali e definiamo $ \mathcal
P_n=\{P(x)=\sum\limits_{i=0}^nx^i A_i,~~ A_i\in \mathbb{R}^{m\times m}\} $. In
questo modo, $P(x)$ \`e una combinazione lineare con coefficienti $A_i$ dei
polinomi elementari $x^i\,I_m$. $P(x)$ ha grado $n$ se $A_n\ne 0$, \`e monico
se $A_n=I_m$.

Per fare questo introduciamo inoltre un ``prodotto scalare'' a valori
matriciali mediante l'applicazione
 $\langle \cdot,\cdot\rangle:\mathcal P_n\to \mathbb{R}^{m\times m}$
definita da
\[
\langle P,Q\rangle=\int_a^bP(x)W(x)Q(x)^T\;dx,
\]
dove $W(x):[a,b]\to \mathbb{R}^{m\times m}$ \`e tale che $W(x)$ \`e continua,
simmetrica e definita positiva per ogni $x\in [a,b]$, dove l'integrale di una
matrice di elementi $a_{i,j}(x)$ \`e la matrice i cui elementi sono $\int_a^b
a_{i,j}(x)dx$.

Si dimostri preliminarmente che per ogni $P,Q,R\in\mathcal P_n$ e $A\in
\mathbb{R}^{m\times m}$ vale
\begin{description}

\item{(a)} ${\langle P,Q\rangle=\langle Q,P\rangle^T}$;

\item{(b)} $V=\langle P,P\rangle$ \`e matrice simmetrica semidefinita positiva,
inoltre $V$ \`e definita positiva  se $\det P(x)\not\equiv 0$, infine $V=0$ se
e solo se $P=0$;

\item{(c)} $\langle A P,Q\rangle=A\langle P,Q\rangle$, $\langle
P,AQ\rangle=\langle P,Q\rangle A^T$,
 $\langle xP,Q\rangle=\langle P,xQ\rangle$;

\item{(d)} $\langle P+R,Q\rangle=\langle P,Q\rangle+\langle R,Q\rangle$,~~~
$\langle P,Q+R\rangle=\langle P,Q\rangle+\langle P,R\rangle$.
\end{description}

\noindent Definiamo $P_0,P_1,\ldots,P_n\in\mathcal P_n$  una {\em sequenza di
polinomi ortogonali} se $P_i$ ha grado $i$, \`e monico, e vale $\langle
P_i,P_j\rangle=0$ per ogni $i\ne j$. Si dimostri che
\begin{description}
\item{(e)} Se esiste una sequenza di polinomi ortogonali $P_j$, $j=0,\ldots,n$
 allora $\langle P_j,P_j\rangle$ \`e definita positiva;

\item{(f)} in $\mathcal P_n$ esiste ed \`e unica una sequenza $P_i$,
  $i=0,\ldots,n$ di polinomi ortogonali e ogni altro polinomio
  $Q\in\mathcal P_n$ pu\`o essere scritto come $\sum\limits_{i=0}^n A_iP_i$
  per $A_i\in \mathbb{R}^{m\times m}$;

\item{(g)} $P_i$ \`e ortogonale ad ogni polinomio di grado minore di $i$;

\item{(h)} i polinomi $P_i(x)$ soddisfano una relazione a tre termini del tipo
\[
\begin{array}{l}
P_{j+1}(x)=(x\,I_m-B_j)P_{j}(x)-C_j P_{j-1}(x),~~j=0,1,\ldots,n-1\\[1ex]
P_0=I,~~P_1=x\,I_m-\int_a^b xW(x)\;dx\;\Big(\int_a^b W(x)\;dx\Big)^{-1}
\end{array}
\]
con $B_j,C_j\in \mathbb{R}^{m\times m}$.

 \item{(i)} \hskip 2cm
  $P_k(x)=x^k\,I_m- [\mu_k, \ldots \mu_{2k-1}] A_{k-1}^{-1}
  \left[\begin{array}{c}I_m\\
  x\,I_m\\ \vdots\\x^{k-1}\,I_m\end{array}\right],$ \\
dove i momenti $\mu_k \in\mathbb{R}^{m\times m}$ sono definiti da
$\mu_k=\int_a^b x^kW(x)dx$ ed $A_{k-1}$ \`e la matrice a blocchi in cui il
blocco di posto $(i,j)$ \`e $\mu_{i+j-2}$, $i,j=1,\ldots,k$.

\item{(j)} Vale un analogo della formula di Christoffel-Darboux? 
\end{description}
\end{ese}

\begin{ese}\rm
Si vuole estendere il concetto di famiglia di polinomi ortogonali a polinomi di
due variabili $p(x,y)=\sum_{i=0}^h\sum_{j=0}^ka_{i,j}x^iy^j$ con coefficienti
reali $a_{i,j}$. Per questo si definisce {\em grado} di $p(x,y)$ il valore
$\max\{i+j:\  a_{i,j}\ne 0\}$ e si indica con $\Pi_n$ l'insieme dei polinomi in
due variabili di grado al pi\`u $n$ e con $\Pi$ l'insieme di tutti i polinomi
in due variabili.

Dato un prodotto scalare $\langle\cdot,\cdot\rangle$, si definisce
$p(x,y)\in\Pi_n$ {\em polinomio orto\-gonale di grado $n$} se $p(x,y)$ ha grado
$n$ e $\langle p(x,y),q(x,y)\rangle=0$ per ogni polinomio $q(x,y)\in\Pi_{n-1}$.
Si definisce poi  $\mathcal V_n$ lo spazio dei polinomi ortogonali di grado
$n$.

Infine, fissati due reali $a,b$ tali che $a<b$, si introduce una funzione
$W(x,y)$ definita e continua su $(a,b)\times(a,b)$, a valori reali positivi,
tale che esiste finito $\int_a^b\int_a^b W(x,y)p(x,y)dx\,dy$ per ogni polinomio
$p(x,y)\in\Pi$.

\begin{description}
\item{(a)}\quad Si dimostri che l'applicazione $\langle\cdot,\cdot\rangle:
  \Pi\times\Pi\to \mathbb R$ definita da
  \[\langle
  p(x,y),q(x,y)\rangle=\int_a^b\int_a^bp(x,y)q(x,y)W(x,y)dx\,dy\]
   \`e  un prodotto scalare.

\item{(b)}\quad Si descriva un procedimento per generare  basi ortogonali di
$\mathcal V_0$, $\mathcal V_1,\ldots,\mathcal V_n$ e si dimostri che dim
$\mathcal V_k=k+1$.

\item{(c)}\quad Si verifichi che l'unione delle basi ortogonali di $\mathcal
V_k$,
  $k=0,\ldots,n$, costituisce una base di polinomi ortogonali di
  $\Pi_n$, e che, diversamente dal caso dei polinomi nella sola $x$,
  tale base non \`e unica (a meno di multipli scalari).
  Gli spazi $\mathcal V_k$, $k=0,\ldots, n$ sono univocamente determinati?

\item{(d)}\quad Si verifichi che se $v_i^{(n)}$ per $i=1,\ldots,n+1$ \`e una
base ortogonale di $\mathcal V_n$ tale che $\langle
  v_i^{(n)},v_i^{(n)}\rangle$ \`e indipendente da $i$, allora
$u^{(n)}=(u^{(n)}_i)_{i=1,\ldots,n+1}:=Qv^{(n)}$ \`e tale che $u^{(n)}_i$,
$i=1,\ldots,n+1$ \`e base ortogonale di $\mathcal V_n$ per ogni matrice
ortogonale $Q$ di dimensione $n+1$.

\item{(e)}\quad Si dimostri  che se $p(x,y)\in\mathcal V_n$ allora i polinomi
$xp(x,y)$ e $yp(x,y)$ sono ortogonali a tutti i polinomi di grado al pi\`u
$n-2$ e a tutti i polinomi ortogonali di grado almeno $n+2$.

\item{(f)}\quad Si deduca che vale un analogo della relazione ricorrente a tre
  termini nel senso che per ogni $p(x,y)\in \mathcal V_n$, sia
  $xp(x,y)$ che $yp(x,y)$ si scrivono come combinazioni lineare di tre
  polinomi in $\mathcal V_{n-1},\mathcal V_n$ e $\mathcal V_{n+1}$.

\item{(g)}\quad %(facoltativo) 
Denotando con $v^{(k)}$ un vettore di $k+1$
  componenti tale che $v^{(k)}_i$, $i=1,\ldots,k+1$ \`e una base di
  $\mathcal V_k$, si dimostri  che esistono e sono uniche matrici $A_n$,
  $(n+1)\times (n+2)$, $B_n$ $(n+1)\times(n+1)$ e $C_n$ $(n+1)\times
  n$ tali che
\[
xv^{(n)}=A_n v^{(n+1)}+B_n v^{(n)}+C_n v^{(n-1)}
\]
con $v^{(-1)}=0$, $C_{-1}=0$. Similmente vale una propriet\`a analoga per
$yv^{(n)}$.

\item{(h)}\quad Si dimostri che se $\varphi_n(x)$ sono polinomi ortogonali
rispetto al prodotto scalare
$<f(x),g(x)>=\int_a^bf(x)g(x)\omega(x)dx$ dato dal peso
$\omega(x):(a.b)\to\mathbb R^+$, allora
$q_{m,n}(x,y)=\varphi_m(x)\varphi_n(y)$ \`e un insieme di polinomi
in due variabili ortogonali rispetto al peso
$W(x,y)=\omega(x)\omega(y)$ e $q_{n,k-n}(x,y)$ per $k=0,\ldots,n$
costituisce una base ortogonale di $\mathcal V_n$.
\end{description}
\end{ese}


\begin{comment}
\begin{ese}\rm
Sia $\langle\cdot,\cdot\rangle$ un prodotto scalare sullo spazio di polinomi
nella variabile $x$. Sia $A=(a_{i,j})$ la matrice $n\times n$ dei momenti tale
che $a_{i,j}=\langle x^i, x^j\rangle$.
\begin{description}

\item{(a)} Si dimostri che $A$ \`e definita positiva.

\item{(b)} Si dimostri che esiste la fattorizzazione $A=LDL^T$ con $L$
triangolare inferiore ed elementi diagonali uguali ad 1, $D$ matrice diagonale
con elementi diagonali positivi.

\item{(c)} Si mettano in relazione gli elementi di $L^{-1}$ con i coefficienti
dei polinomi or\-to\-go\-na\-li  rispetto al prodotto scalare $\langle
\cdot,\cdot\rangle$.

\item{(d)} Si ricavi un metodo di calcolo dei coefficienti dei primi $n$
polinomi ortogonali e se ne valuti il costo computazionale.
\end{description}
\end{ese}
\end{comment}

\begin{ese}\rm
Siano $p_0(x),\ldots,p_{n+1}(x)$ polinomi ortogonali sull'intervallo $[a,b]$
rispetto al prodotto scalare $\langle p,q\rangle=\int_a^bp(x)q(x)w(x)dx$, con
$w(x)$ funzione peso positiva su $[a,b]$, e $p_j(x)=\sum_{i=0}^j p_{i,j}x^i$.
Siano $x_0,\ldots,x_n$ gli zeri di $p_{n+1}(x)$. Si definiscano le matrici
$(n+1)\times (n+1)$, dove gli indici scorrono da $0$ a $n$: $A=(a_{i,j})$,
$V=(v_{i,j})$, $S=(s_{i,j})$
tali che $a_{i,j}=p_j(x_i)$, $v_{i,j}=x_i^j$, $s_{i,j}=p_{i,j}$ per $i\le j$, $s_{i,j}=0$ altrove.
\begin{description}
 \item{(a)} Si verifichi che $A=VS$.
 \item{(b)} Si dimostri che esistono matrici diagonali $D_1$ e $D_2$
 con elementi diagonali positivi tali che $Q=D_1AD_2$ \`e ortogonale.
 \item{(c)} Si dimostri che $Q$ \`e il fattore ortogonale della
fattorizzazione QR  della matrice $D_1V$, cio\`e $D_1V=QR$ dove
$R=D_2^{-1}S^{-1}$. Si ricavi un algoritmo per il calcolo dei
coefficienti di $p_i(x)$, $i=0,\ldots,n$.
\end{description}
\end{ese}


\begin{ese}\rm
Sia $\mathcal P_n$ lo spazio dei polinomi $a(x)=\sum_{i=0}^{n} a_ix^i$ di grado
al pi\`u $n$ con un prodotto scalare $\langle \cdot,\cdot\rangle$. Sia
$p_i(x)$, $i=0,\ldots,n$ una successione di polinomi ortogonali tali che deg$
p_i(x)=i$.

\begin{description}
\item{(a)}\quad Si dimostri che la successione soddisfa una relazione a tre
termini del tipo $p_{i+1}(x)=(a_ix+b_i)p_i(x)-c_ip_{i-1}(x)$, $c_i>0$,  se e
solo se il prodotto scalare \`e tale che $\langle xp(x),q(x)\rangle=\langle
p(x),xq(x)\rangle$ per ogni coppia di polinomi in $\mathcal P_n$ di grado al
pi\`u $n-1$.

\item{(b)}\quad Si dimostri che per ogni prodotto scalare
$\langle\cdot,\cdot\rangle$ su $\mathcal P_n$ esiste una matrice simmetrica
definita positiva $H$ di dimensione $n+1$ tale che $\langle
p(x),q(x)\rangle={\bm p}^TH{\bm q}$ dove ${\bm p}$ e ${\bm q}$ sono i vettori
$(n+1)$-dimensionali dei coefficienti dei polinomi $p(x)$ e $q(x)$ nella base
dei monomi. Inoltre, data una matrice simmetrica definita positiva $H$ di
dimensione $n+1$ si dimostri che l'applicazione che associa alla coppia
$(p(x),q(x))$ il numero reale $p^THq$ \`e un prodotto scalare.

\item{(c)}\quad Si dica come \`e fatta la matrice nel caso in cui i polinomi
ortogonali relativi al prodotto scalare $\langle\cdot,\cdot\rangle$ soddisfano
una relazione ricorrente a tre termini.

\item{(d)}\quad Siano $\xi_i$, $i=0,\ldots,n$ numeri reali distinti. Si
verifichi che $\langle p(x),q(x)\rangle=\sum_{i=0}^n
p(\xi_i)q(\xi_i)$ \`e un prodotto scalare e che i polinomi
ortogonali relativi a tale prodotto verificano una relazione a tre
termini.
\end{description}
\end{ese}

\begin{ese}\rm
Si supponga che esista un prodotto scalare
$\langle\cdot,\cdot\rangle$ su $\mathcal P$ tale che 
\begin{equation}
\langle
x^2f(x),g(x)\rangle=\langle f(x),x^2 g(x)\rangle,\quad \forall f,g\in\mathcal P 
\end{equation}
e non necessariamente sia $\langle
xf(x),g(x)\rangle = \langle f(x),xg(x)\rangle$.

{\bf a)} Si dimostri che i polinomi ortogonali $p_i(x)$, $i=0,1,\ldots,$
tali che deg$(p_i(x))=i$, ottenuti con questo prodotto scalare
verificano una relazione di ricorrenza del tipo
$
p_{i+1}(x)=(a_ix^2+b_i)p_{i-1}(x)+c_ip_{i}(x)+d_ip_{i-2}(x)+e_ip_{i-3}(x)
$,
%$a_i,b_i,c_i,d_i\in\mathbb R$.
per opportune costanti $a_i,b_i,c_i,d_i$.  
%Si esprimano le costanti
%$a_i,b_i,c_i,d_i$ in funzione dei prodotti scalari $\langle
%p_j(x),p_j(x)\rangle$ e $\langle x^2p_{i-1}(x),p_j(x)\rangle$,
%$j=i-3,\ldots,i$.

{\bf b)} Si dica se la matrice dei momenti, intesa come $H_n=(h_{i,j})$,
$h_{i,j}=\langle x^i,x^j\rangle$, $i,j=0,1,\ldots,n$, 
mantiene ancora la struttura di
Hankel. 
Si verifichi che permutando righe e colonne di $H_n$ con la permutazione
$(1,3,5,7,\ldots,2,4,6,8,\ldots)$ si ottiene una matrice $2\times 2$ a
blocchi formata da 4 blocchi di Hankel e che ogni matrice di questo tipo, 
definita positiva, determina un prodotto scalare su $\mathcal P_n$ che gode della propriet\`a (1).
 Si dia un esempio di prodotto scalare su $\mathcal P_n$, definito tramite la matrice $H_n$, con la propriet\`a (1).


{\bf c)} Sia $H_n(x)$ la matrice ottenuta sostituendo l'ultima riga di $H_n$ con
$[1,x,x^2,$ $\ldots,x^n]$. Dire, motivando adeguatamente la risposta, se
$p_n(x)=\det H_n(x)$.  


{\bf d)} Si decomponga $p(x)=\sum_{i=0}^n p_ix^i$ come
$p(x)=p_+(x^2)+xp_-(x^2)$ dove $p_+(x^2)=(p(x)+p(-x))/2$ e
$p_-(x^2)=(p(x)-p(-x))/(2x)$ sono la parte pari e la parte dispari di $p(x)$. 
Si consideri il prodotto scalare su $[a,b]$ dato da 
$\langle p(x),q(x)\rangle=\int_a^b
w(x)p(x)q(x)dx$, associato al peso $w(x)$ e 
 si definisca 
\[
\langle
p(x),q(x)\rangle':=\langle p_+(x),q_+(x)\rangle+\langle
p_-(x),q_-(x)\rangle
%+ \langle p_-(x),q_+(x)\rangle
\]
Si verifichi che
$\langle\cdot,\cdot\rangle'$ \`e un prodotto scalare tale che $\langle
x^2 f(x),g(x)\rangle=\langle f(x),x^2 g(x)\rangle$ ed esistono
polinomi $p(x),q(x)$ tali che $\langle x p(x),q(x)\rangle\ne \langle
p(x),x q(x)\rangle$.


{\bf e)} %(Facoltativo) 
Si possono esprimere i polinomi ortogonali di cui al punto a) come determinanti di opportune matrici a banda? Come \`e fatta la matrice dei momenti del prodotto scalare del punto c)? Si analizzino le propriet\`a dei polinomi $p_n(x)$ ottenuti col prodotto scalare dato nel punto c).
\end{ese}

\begin{ese}\rm
Siano $ p_0 (x),\ldots, p_n(x) ,\ldots\in\mathcal P$ 
polinomi ortogonali rispetto al prodotto scalare 
$\langle p(x),q(x)\rangle=\int_a^b p(x)q(x)\omega(x)dx$, dove $a<b$ e $\omega(x)$ \`e una funzione peso. 
Dimostrare che le seguenti condizioni sono equivalenti
\begin{enumerate}
\item I sottospazi di polinomi $\mathcal P^+=\{q(x^2),~ q(x)\in\mathcal P\}$ e $\mathcal P^-\{xq(x^2),~ q(x)\in\mathcal P\}$ sono ortogonali. 
\item Vale $p_1(x)=A_1x$, $p_{i+1}(x)=xA_{i+1}p_i(x)-C_ip_{i-1}(x)$, per $i=1,2,\ldots$, dove $A_i,C_i\ne 0$.
\item Esistono polinomi $\varphi_i(x)$ e $\psi_i(x)$ di grado $i$ tali che
$p_{2i}(x)=\varphi_i(x^2)$, $p_{2i+1}(x)=x\psi_i(x^2)$.
%\item Vale $b=-a$ e $\omega(x)=\omega(-x)$ per ogni $x\in[a,b]$.
\end{enumerate}

Sotto le condizioni dei punti precedenti dimostrare che $ab<0$ e che i
polinomi $\varphi_i(x)$ sono ortogonali rispetto ad un opportuno
prodotto scalare sull'intervallo $[\hat a,\hat b]$ con peso
$\hat\omega$. Si determinino $\hat a,\hat b,\hat\omega$. Dimostrare
analoga propriet\`a per $\psi_i(x)$.

Mettere in relazione i coefficienti della relazione a tre termini dei
polinomi $\varphi_i(x)$, $\psi_i(x)$ con quelli dei polinomi $p_i(x)$.

Dire come \`e fatta la matrice dei momenti per il prodotto scalare per
cui valgono le propriet\`a 1,2,3.

\`E possibile che con il prodotto scalare che rende ortogonali i
polinomi $\varphi_i(x)$ i sottospazi $\mathcal P^+$ e $\mathcal P^-$
siano ortogonali?  \`E possibile che ci\`o valga per il prodotto
scalare che rende ortogonali i $\psi_i(x)$?

%Facoltativo. 
Dire se la condizione
\medskip

 4. $b=-a$ e $\omega(x)=\omega(-x)$ per ogni $x\in[a,b]$.
\medskip

\noindent \`e equivalente alle condizioni 1-3.
\end{ese}


\begin{ese}\rm
Sia $n>2$ un intero, $h=1/n$ e si definiscano i punti $x_i=ih$,
${i=-1,\ldots,n+1}$. Per $i=0,\ldots,n$ si definiscano le funzioni
``hat'' da $[0,1]$ in $\mathbb R$
\[
  \varphi_i(x)=\left\{\begin{array}{ll}1-\displaystyle\frac 1h |x-x_i|
  &\hbox{se } x\in[x_{i-1},x_{i+1}]\cap[0,1],\\
  0&\hbox{altrove}\end{array}\right.
\]
Si consideri l'operatore di interpolazione $L_n$ che a $f(x)\in
C[0,1]$ associa la funzione continua
$g_n(x)=\displaystyle\sum_{i=0}^na_i\varphi_i(x)$ tale che
$g_n(x_i)=f(x_i)$, $i=0,\ldots,n$.
\begin{description}

\item{(a)} Dimostrare che le funzioni $\varphi_i(x)$, $i=0,\ldots,n$ sono
linearmente indipendenti.

\item{(b)} Dimostrare che l'operatore $L_n$ \`e ben definito e dare una formula
per il calcolo degli $a_i$, confrontare il
  costo della formula ottenuta con quello del calcolo della funzione
  di migliore approssimazione in norma 2.

\item{(c)} Dimostrare che l'operatore $L_n$ \`e lineare e positivo.

\item{(d)} Dimostrare che per ogni $f(x)\in C([0,1])$ vale
$\lim_{n}\|g_n(x)-f(x)\|_{\infty}=0$.

\item{(e)} Valutare l'ordine con cui l'errore di approssimazione
$\|g_n(x)-f(x)\|_{\infty}$ converge a zero.
\end{description}
\end{ese}

\begin{ese}\rm
Sia $n>0$ un intero, $h=1/n$, $x_i=ih$, per $i=0,\ldots,n$. Si considerino le funzioni $\varphi_i(x):[0,1]\to\mathbb R$ definite da
\[
\varphi_i(x)=\left\{\begin{array}{ll}
0&\hbox{se } x\le x_{i-1}\\
\frac{x-x_{i-1}}h&\hbox{se } x\in[x_{i-1},x_{i}]\\
1&\hbox{se }x\ge x_{i}
\end{array}\right.
\]
per $i=0,1,\ldots,n$.
Sia $C[0,1]$ lo spazio delle funzioni continue da $[0,1]$ in $\mathbb R$ e si definisca l'operatore $\mathcal L_n$ che ad $f(x)\in C[0,1]$ associa la funzione $g_n(x)=\mathcal L_n(f)=\sum_{i=0}^n\alpha_i\varphi_i(x)$ tale che $g_n(x_i)=f(x_i)$.
\begin{enumerate}
\item Si esplicitino i coefficienti $\alpha_i$ di $\mathcal L_n$.
\item % (Riformulazione). 
Si dimostri che $g_n(x)$ approssima bene le funzioni $1$, $x$ con errore nullo e la funzione $x^2$ con errore $O(h^2)$ e quindi approssima bene ogni $f(x)\in
  C[0,1]$. Dire se per ogni $f\in C$ esiste una costante $\gamma$ tale
  che $\|g_n(x)-f(x)\|_\infty\le\gamma h^2$.
\item Se $f(x)\in C^2[0,1]$ si dimostri la diseguaglianza del punto 2 e si 
metta in relazione $\gamma$ con la derivata seconda di $f(x)$.
\item Si imposti il problema del calcolo della funzione di miglior approssimazione in norma 2 dove $\|f\|_2=\left(\int_0^1f(x)^2dx\right)^{\frac 12}$.
\item %(Facoltativo) 
Si valuti il costo computazionale del calcolo della funzione di migliore approssimazione
\end{enumerate}
\end{ese}

\begin{ese}\rm
Sia ${\cal H}$ spazio di Hilbert con prodotto scalare $\langle\cdot,\cdot\rangle$, sia $n>0$ intero e ${\cal V}_n$ spazio lineare generato
da $\varphi_1,\ldots,\varphi_n\in {\cal H}$.
\begin{description}
\item {(a)}\quad  Siano $A=(a_{i,j})$ la matrice $n\times n$ di elementi
$a_{i,j}=\langle\varphi_i,\varphi_j\rangle$, e $Q=(q_{i,j})$, tale che
$A=QDQ^T$, con $Q^TQ=I$ e $D$ matrice diagonale. Si dimostri che
$\psi_j=\sum_{i=1}^n q_{i,j}\,\varphi_i$,  $j=1,\ldots,n$, \`e una
base ortogonale di ${\cal V}_n$.
 \item {(b)}\quad Sia ${\cal H}$ lo spazio lineare delle funzioni da $[0,2\pi]$
 in $\mathbb{R}$ periodiche a quadrato integrabile col prodotto scalare
 $\langle f,g\rangle=\int_-^{2\pi} f(x)g(x)\,dx$. Dato un intero $n$, si definiscano
 $x_i=ih$, $i=0,\ldots,n+1$, con $h=2\pi/(n+1)$. Sia ${\cal V}_n$ lo spazio
 lineare generato dalle funzioni
 \begin{equation}\label{fu}
  \varphi_i(x)=\left\{
  \begin{array}{ll}
  \displaystyle\frac{1}{\sqrt h}&{\rm se}\ x\in [x_{i-1},x_{i+1}),\\[0.3cm]
    0&{\rm altrove},
  \end{array}\right.
  \qquad {\rm per}\ i=1,\ldots,n.
  \end{equation}
Si formuli il problema della migliore approssimazione di una
funzione $f\in{\cal H}$ con una funzione $g_n\in {\cal V}_n$. In
particolare si studi la complessit\`a di calcolo e il
condizionamento in norma 2 del sistema lineare associato.
 \item {(c)}\quad Si determini una base ortogonale dello spazio ${\cal
V}_n$ del punto (b).
 \item {(d)}\quad Supponendo che $f(x)$ sia la funzione identicamente uguale a 1,
si dia una valutazione di $\|f-g_n^*\|_2$ e $\|f-g_n^*\|_\infty$,
dove $g_n^*$ \`e la funzione di migliore approssimazione nello
spazio ${\cal V}_n$ del punto (b) e
\[\|f\|_2=(\int_0^{2\pi}f(x)^2dx)^{1/2},\quad\|f\|_\infty=\max_{x\in
[0,2\pi]}|f(x)|.\]
 \item {(e)} %\quad(facoltativo)  
Si tratti il punto (b) e il punto (d) per lo
 spazio ${\cal V}_{n+1}$ gene\-rato dalle funzioni $\varphi_i(x)$ in (\ref{fu}) e
 dalla funzione $\varphi_{n+1}(x)$ che vale $1/\sqrt h$ per $x\in
 [x_0,x_1)\,\cup\,[x_n,x_{n+1}]$ e 0 altrove.
\end{description}
\end{ese}



\begin{ese}\rm
Sia $\psi(x)=(x^k-1)^k$ per $k$ intero pari,
e si definisca
$\varphi(x)=\psi(x)$ per $-1\le x\le 1$, $\varphi(x)=0$ altrove. Si
verifichi che $\varphi$ \`e di classe $C^k-1$.  Dato un intero $n$ si
ponga $h=\frac 1{n+1}$, $x_i=ih$, per $i=-(n+1),\ldots,(n+1)$,
$\varphi_i(x)=\varphi((x-x_i)/h)$, per $i=-n,\ldots,n$.

Oppure $\varphi(x)=1-2x^2$ su $[-1/2,1/2]$, $x^2-3x+7/4$ su $[1/2,3/2]$,
$(x+1)^2-3(x+1)+7/4$ su $[-3/2,-1/2]$.

Oppure $(x^2-1)^k$ (come cambia la dominanza diag in funzione di k?)
Dare il migliore $k$ che d\`a la convergenza su $(1,x,x^2)$ migliore.



 Si consideri l'operatore $L_n:C[-1,1]\to C[-1,1]$ tale che
$L_n[f]=\sum_{i=-n}^nf(x_i)\varphi_i(x)$.
\\
a) Si dimostri che $L_n$ \`e lineare e positivo.
\\
b) Si dica se $\lim_n \|L_n[f]-f\|_\infty=0$ per ogni $f\in C[-1,1]$
\\
c) Si dica come si pu\`o calcolare la funzione $g_n$ che minimizza  $\delta_n=\int_{-1}^1 (f(x)-g_n(x))^2dx$ dove $g(x)$ varia nello spazio generato da $\varphi_i(x)$, $i=-n,\ldots,n$, valutando gli aspetti computazionali (costo, condizionamento stabilit\`a).
\\
d)
Dire se $\lim_n \delta_n=0$

\end{ese}

\begin{ese}\rm
Sia $\varphi(t)$ funzione continua e non negativa,
nulla al di fuori di $[-1,1]$, tale che $\varphi(1)=0$,
$\varphi(0)=1$, $\varphi(t)=\varphi(-t)$.  Sia $n$ intero positivo,
$h=1/(n+1)$, $x_i=ih$, $i=0,\ldots,n+1$. Si definisca
$L_n[f]:C[0,1]\to C[0,1]$ l'operatore che associa alla funzione $f\in
C[0,1]$ la funzione $g_n(x)=L_n[f]$ data da
$\sum_{i=0}^{n+1}f(x_i)\varphi_i(x)$, dove
$\varphi_i(x)=\varphi((x-x_i)/h)$.

a) Si dimostri che $L_n$ \`e un operatore lineare positivo.

b) Si dimostri che se $\varphi(t)+\varphi(1-t)=1$ per $t\in[0,1]$ allora
$\lim_{n\to\infty}\|L_n[f]-f\|_\infty=0$ per ogni funzione
 $f(x)\in C[0,1]$. La condizione 
$\varphi(t)+\varphi(1-t)=1$ \`e necessaria per la convergenza?

c)
Quale dei seguenti due casi fornisce la migliore convergenza? 
$
\varphi(t)=
1-t$ per $0\le t\le 1$,
%$\varphi(t)=
%1-t^2$,  per $0\le t\le 1$,
$
\varphi(t)=
1-3t^2+2t^3$ per $0\le t\le 1$.

\includegraphics[width=6cm]{fi1}~~
\includegraphics[width=6cm]{fi2}


d) Valutare il costo computazionale e il numero di condizionamento
nel calcolo della funzione $g_n(x)=\sum_{i=0}^{n+1}\alpha_i\varphi_i(x)$ 
di migliore approssimazione in norma $L^2$ nei casi del punto c). 

e) %(Facoltativo) 
Dire se \`e possibile migliorare la convergenza 
scegliendo come $\varphi(t)$ su $[0,1]$ un polinomio di grado pi\`u alto.
Dire se \`e possibile migliorare la convergenza scegliendo come $\varphi(t)$ una funzione con supporto pi\`u ampio.

\end{ese}

\newpage


%\begin{thebibliography}
%\bibitem{leb}
\begin{thebibliography}{99}
\bibitem{bcmbook} D. Bini, M. Capovani, O. Menchi, {\em Metodi Numerici per
  l'Algebra Lineare}. Zanichelli, Bologna, 1987.
\bibitem{bbcm} R. Bevilacqua, D. Bini, M. Capovani e O. Menchi, Metodi numerici,
    Zanichelli, Bologna 1992.
\bibitem{smith}
Simon J. Smith, Lebesgue constants in polynomial interpolation, Annales
Mathematicae et Informaticae, v. 33 (2006) pp. 109-123.\\
{\tt www.ektf.hu/tanszek/matematika/ami}
\bibitem{sb}
J. Stoer, R. Burlisch, Introduction to Numerical Analysis, Third Edition,
    Springer, 2002.
\bibitem{rudin} W. Rudin, Real and Complex Analysis, Second Edition, Tata McGraw-Hill,
    1974.
\end{thebibliography}

\newpage
\section*{Appendice A: soluzione di alcuni esercizi}


\end{document}


\begin{defi} Sia $S$ uno spazio vettoriale di funzioni da $K$ compatto di 
$\R^n$ in $\R$
 e si consideri un operatore $\Phi$  da $S$ in $S$. Si definisca la
seguente coppia di propriet\`a di $\Phi$:
\begin{enumerate}
\item     $\Phi$ \`e lineare, cio\`e per ogni scelta di $\alpha$ e $\beta$ in $\R$ e per ogni scelta di 
$f$ e $g$ in $S$, vale $\Phi(\alpha f+\beta g)=\alpha\Phi(f)+\beta\Phi(g)$;
\item $\Phi_n$ \`e positivo, cio\`e per ogni scelta di $f\in S$, $f\ge 0$ ,  vale $\Phi(f)\ge 0$.
\end{enumerate}
\end{defi}


Un operatore $\Phi$ che soddisfa entrambe le condizioni \`e detto lineare e
positivo e si scrive in breve che esso \`e LPO.

\begin{defi}
Sia $S$ uno spazio di Banach di funzioni da $K$ compatto di $\R^n$
in $\R$,
 e si consideri una successione $\{\Phi_n\}_n$ di operatori
da $S$ in $S$. La successione \`e detta {\em successione di operatori 
di approssimazione} o,
pi\`u brevemente, {\em processo di approssimazione}, se per 
ogni $f\in S$ vale
$\lim_n\|\Phi_n(f)-f\|=0$
 \end{defi}


\begin{teo}[Korovkin]
Sia $K$ un compatto di $\R^n$ e si consideri lo spazio
di Banach delle funzioni continue $C(K)$ con la norma del sup. Si consideri
l'insieme di funzioni $T = \{1, x_1,\ldots, x_n, \sum_{j=1}^n x_j^2\}$,
 detto insieme test di Korovkin, e si consideri
una successione $\{\Phi_n\}$ di operatori lineari e positivi su $C(K)$. 
Se per ogni $g\in T$ $\Phi_n(g)$
converge uniformemente a $g$
allora $\{\Phi_n\}$ \`e un processo di approssimazione ovvero
$\Phi_n(f)$ converge uniformemente a $f$ per ogni $f\in C(K)$.
\end{teo}





\begin{lem}\label{lem1}
Sia $\mathcal H$ spazio di Hilbert con prodotto scalare $\left\langle \cdot,\cdot \right\rangle $ e
$X\subset \mathcal H$ chiuso, convesso e non vuoto. Allora $\exists ! x^*\in
X$: $\|x^*\|=\min_{x\in X} \|x\|$.
\end{lem}


{\bf Dim.}
 Poich\'e $\|x\|\ge 0$, esiste $\delta=\inf_{x\in
  X}\|x\|$. Dimostriamo che $\delta$ \`e un minimo. Poich\'e $\mathcal H$ \`e
di Hilbert, vale l'identit\`a del parallelogramma
\begin{equation}\label{parallel}
\|x+y\|^2+\|x-y\|^2=2\|x\|^2+2\|y\|^2,~~~\forall x,y\in\mathcal H
\end{equation}
Se $f,g\in X$ per la convessit\`a \`e $\frac 12(f+g)\in X$. Applico
\eqref{parallel} con $x=f/2$, $y=g/2$ e ottengo
\[
\|\frac f2+\frac g2\|^2+\|\frac f2-\frac g2\|^2=\frac{\|f\|^2}2+\frac{\|g\|^2}2
\]
da cui
\begin{equation}\label{stella}
\|f-g\|^2=2\|f\|^2+2\|g\|^2-4\|\frac{f+g}2\|\le 2\|f\|^2+2\|g\|^2-4\delta^2.
\end{equation}
Inoltre $\forall n\exists y_n\in X:$ $\|y_n\|\le\delta+\frac 1n$. Vale allora
\[\begin{split}
\|y_n-y_m\|^2\le& 2\|y_n\|^2+2\|y_m\|^2-4\delta^2\\
             \le&  2(\delta^2+\frac
1{n^2}+\frac{2\delta}n)+2(\delta^2+\frac
1{m^2}+\frac{2\delta}m)-4\delta^2\\
=&\frac 2{n^2}+\frac 2{m^2}+\frac {4\delta}n+\frac{4\delta}m:=\epsilon
\end{split}
\]
Cio\`e $\{y_n\}$ \`e successione di Cauchy, quindi $\exists x\in\mathcal H:$
$\lim_n \|x-y_n\|=0$. Ma poich\'e $X$ \`e chiuso risulta $x\in X$. Poich\'e
$\|\cdot\|$ \`e continua vale $\|x\|=\lim_n\|y_n\|=\delta$.
Inoltre, se esistessero $f,g$ tali che $\|f\|=\|g\|=\delta$, allora
da \eqref{stella} sarebbe $\|f-g\|^2\le 0$ cio\`e $f=g$.
\qed

\begin{lem}\label{lem2}
Sia $\mathcal V\subset\mathcal H$ sottospazio di dimensione finita di uno
spazio di Hilbert $H$. Allora $\mathcal V$ \`e chiuso. 
\end{lem}
{\bf Dim.} Per induzione sulla dimensione $k$ di $\mathcal V$. Se $k=0$,
cio\`e $\mathcal V=\{0\}$ allora $\mathcal V$ \`e chiuso. Dimostriamo il passo
induttivo, cio\`e che se $\mathcal V$ \`e chiuso e $y\not\in\mathcal V$ allora
span$(\mathcal V,y)$ \`e chiuso. Sia $z_n\in\mathcal W=$span$(\mathcal V,y)$
tale che $\lim \|z_n-z\|=0$, per $z\in\mathcal H$. Vale $z_n=x_n+\lambda_ny$
con $x_n\in\mathcal V$ e $\|z_n\|<\eta$, $\eta$ costante, poich\'e $z_n$
converge a un valore $z$ di norma finita. Inoltre $|\lambda_n|$ \`e
limitata. Infatti se non lo fosse allora $\exists \lambda_{n_j}:$ $\lim
|\lambda_{n_j}|=+\infty$ e quindi $\lambda_{n_j}\ne 0$
definitivamente. Varrebbe allora
\[
\|\frac{x_{n_j}}{\lambda_{n_j}}+y\|<\frac\eta{\lambda_{n_j}}\to 0
\]
per cui $\frac{x_{n_j}}{\lambda_{n_j}}\to -y$ e quindi $y\in\mathcal V$,
assurdo.
Poich\'e $\lambda_n$ \`e limitata esiste $\lambda_{n_j}$ che converge a un
limite $\lambda^*$. Quindi la successione $x_{n_j}=z_{n_j}-\lambda_{n_j}y$
ha limite $x:=z-\lambda^*y$. Per cui vale $z=\lim z_n=\lim
z_{n_j}=\lim(x_{n_j}+\lambda_{n_j}y)=x+\lambda^*y\in\mathcal W$.
\qed





Sia $V=$span$(\varphi_0,\ldots,\varphi_n)$. Per il lemma \ref{lem2}
$V$ \`e chiuso. Anche il sottospazio affine $f+V$ \`e chiuso perch\'e immagine
inversa mediante applicazione continua $g\to g-f$ di $V$. Poich\'e $f+V$ \`e
chiuso, convesso e non vuoto, per il lemma \ref{lem1} esiste ed \`e unica
$h\in f+V$ di norma minima. Vale allora che $g=f-h\in V$ \`e il punto che
minimizza $\|f-g\|$. Infatti, poich\'e $h=f-g$ \`e di minima norma vale
$\|f-\hat g\|\ge \|f-g\|=\|h\|$ per ogni altro $\hat g\in V$. L'unicit\`a di
$g$ segue da quella di $h$.



-------------------

Premettiamo alcuni lemmi.

\begin{lem}\label{lemchius}
 Se $S$ \`e un sottospazio di uno spazio di Hilbert $\mathcal H$
allora anche la sua chiusura $\bar S$ \`e un sottospazio.
\end{lem}

{\bf Dim.}  Si dimostra
che se $x,y\in\bar S$ allora $\alpha x+\beta y\in\bar S$. Per definizione di
chiusura esistono successioni $x_n,y_n\in S$ tali che $\|x_n- x\|\to 0$, 
$\|y_n-y\|\to 0$.
Vale $w_n=\alpha x_n+\beta y_n\in S$ e $\| w_n\in\bar S$. Inoltre,
$\|w_n-(\alpha x+\beta y)\|\le |\alpha|\cdot\|x_n-x\|+|\beta|\cdot\|y_n-y\| \to 0$. Quindi $\alpha x+\beta y\in\bar S$.
\qed



\begin{lem}\label{lem1}
Sia $\mathcal H$ spazio di Hilbert con prodotto scalare $\left\langle \cdot,\cdot \right\rangle $ e
$X\subset \mathcal H$ chiuso, convesso e non vuoto. Allora $\exists ! x^*\in
X$: $\|x^*\|=\min_{x\in X} \|x\|$.
\end{lem}


{\bf Dim.}
 Poich\'e $\|x\|\ge 0$, esiste $\delta=\inf_{x\in
  X}\|x\|$. Dimostriamo che $\delta$ \`e un minimo. Poich\'e $\mathcal H$ \`e
di Hilbert, vale l'identit\`a del parallelogramma
\begin{equation}\label{parallel}
\|x+y\|^2+\|x-y\|^2=2\|x\|^2+2\|y\|^2,~~~\forall x,y\in\mathcal H
\end{equation}
Se $f,g\in X$ per la convessit\`a \`e $\frac 12(f+g)\in X$. Applico
\eqref{parallel} con $x=f/2$, $y=g/2$ e ottengo
\[
\|\frac f2+\frac g2\|^2+\|\frac f2-\frac g2\|^2=\frac{\|f\|^2}2+\frac{\|g\|^2}2
\]
da cui
\begin{equation}\label{stella}
\|f-g\|^2=2\|f\|^2+2\|g\|^2-4\|\frac{f+g}2\|\le 2\|f\|^2+2\|g\|^2-4\delta^2.
\end{equation}
Inoltre $\forall n\exists y_n\in X:$ $\|y_n\|\le\delta+\frac 1n$. Vale allora
\[\begin{split}
\|y_n-y_m\|^2\le& 2\|y_n\|^2+2\|y_m\|^2-4\delta^2\\
             \le&  2(\delta^2+\frac
1{n^2}+\frac{2\delta}n)+2(\delta^2+\frac
1{m^2}+\frac{2\delta}m)-4\delta^2\\
=&\frac 2{n^2}+\frac 2{m^2}+\frac {4\delta}n+\frac{4\delta}m:=\epsilon
\end{split}
\]
Cio\`e $\{y_n\}$ \`e successione di Cauchy, quindi $\exists x\in\mathcal H:$
$\lim_n \|x-y_n\|=0$. Ma poich\'e $X$ \`e chiuso risulta $x\in X$. Poich\'e
$\|\cdot\|$ \`e continua vale $\|x\|=\lim_n\|y_n\|=\delta$.
Inoltre, se esistessero $f,g$ tali che $\|f\|=\|g\|=\delta$, allora
da \eqref{stella} sarebbe $\|f-g\|^2\le 0$ cio\`e $f=g$.
\qed

\begin{cor} Sia $\mathcal H$ spazio di Hilbert e $\mathcal V\subset\mathcal H$ un suo sottospazio.
Sia inoltre $f\in\mathcal H$. Allora il sottospazio affine $f+\mathcal
V$ ha un elemento $h$ di minima norma. Inoltre vale $\langle
h,v\rangle=0$ per ogni $v\in\mathcal V$.
\end{cor}
{\bf Dim.} 
Per il lemma \ref{lem2}
$\mathcal V$ \`e chiuso. Anche il sottospazio affine $f+V$ \`e chiuso perch\'e immagine
inversa mediante applicazione continua $g\to g-f$ di $V$. Poich\'e $f+V$ \`e
chiuso, convesso e non vuoto, per il lemma \ref{lem1} esiste ed \`e unica
$h\in f+V$ di norma minima. Vale allora che $g=f-h\in V$ \`e il punto che
minimizza $\|f-g\|$. Infatti, poich\'e $h=f-g$ \`e di minima norma vale
$\|f-\hat g\|\ge \|f-g\|=\|h\|$ per ogni altro $\hat g\in V$. L'unicit\`a di
$g$ segue da quella di $h$.
\qed

\begin{lem}\label{lem3}
Sia $\{\varphi_i(x)\in\mathcal H,\ i=0,1,2,\ldots\}$ un insieme
ortogonale completo nello spazio di Hilbert $\mathcal H$. Allora
l'insieme $S=\{f=\sum_{i=0}^n\alpha _i\varphi_i,~ n\in\N,~\alpha_i\in
K\}$ \`e denso in $\mathcal H$.
\end{lem}
{\bf Dim.} $S$ \`e sottospazio di $\mathcal H$ e anche la sua chiusura $\bar
S$ lo \`e per il lemma \ref{lemchius}. Se $\bar S\ne\HH$ esisterebbe 
$y\in\HH-\bar S$. Il sottospazio affine
$y+\bar S$ ha un elemento di norma minima che \`e ortogonale a $\bar S$ e
quindi a $S$, e quindi a tutti i $\varphi_i$. Ma questo \`e assurdo poiche il
sistema \`e completo.\qed
