\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 $a0$ per $an$. \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 $j0 \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 j0$ 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$, $m0$ 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\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 \[ =\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 \[ =\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=\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 $a2$ 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