From 7df32a29bec121e05823f99a70fa4507eaf86408 Mon Sep 17 00:00:00 2001 From: Leonardo Robol Date: Fri, 6 Nov 2009 15:04:32 +0100 Subject: [PATCH] Aggiunta lezione di Gemignani del 6 novembre e qualche nuovo comando --- CalcoloScientifico.tex | 12 +++++- capitolo3.tex | 113 ++++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 121 insertions(+), 4 deletions(-) diff --git a/CalcoloScientifico.tex b/CalcoloScientifico.tex index 4cb3426..17615f1 100644 --- a/CalcoloScientifico.tex +++ b/CalcoloScientifico.tex @@ -43,8 +43,8 @@ %% %% Insieme Immagine e dominio %% -\newcommand{\imm}[1]{\mathfrak{Im}(#1)} -\newcommand{\dom}[1]{\mathfrak{Dom}(#1)} +\newcommand{\imm}[1]{\mathrm{Im}(#1)} +\newcommand{\dom}[1]{\mathrm{Dom}(#1)} %% %% \leq e \geq più matematici @@ -118,6 +118,14 @@ \newcommand{\diag}[1]{\mathrm{diag}(#1)} %% +%% I nomi di algoritmi e fattorizzazioni +%% +\newcommand{\svd}{\texttt{SVD}} +\newcommand{\tsvd}{\texttt{TSVD}} +\newcommand{\Span}[1]{\mathrm{Span}(#1)} +\newcommand{\Ker}[1]{\mathrm{Ker}(#1)} + +%% %% Il comando per avere l'insieme delle parti %% \newcommand{\parts}[1]{% diff --git a/capitolo3.tex b/capitolo3.tex index 8df5df8..c97f62c 100644 --- a/capitolo3.tex +++ b/capitolo3.tex @@ -66,7 +66,7 @@ e quindi si ha l'unicità della soluzione e la risolubilità del sistema lineare di $\trasp AA$ potrebbe esserer oneroso e, soprattutto, nessuno ci garantisce in una situazione generale che il rango di $A$ sia massimo. -\subsection{La decomposizione in valori singolari} +\subsection{Teorema di decomposizione in valori singolari} Possiamo pensare di voler migliorare l'idea delle equazioni normali. In altre parole, vogliamo trovare il modo di evitare il calcolo di $\trasp AA$. Consideriamo dunque il seguente \begin{te}[Decomposizione in valori singolari] @@ -158,6 +158,115 @@ trovare un polinomio di grado al più $n$ tale che $p(x_i) = y_i$ per tutti gli Nelle applicazioni concrete si ha però a che fare con grandi moli di dati sperimentali e raramente il grado del polinomio che si vorrebbe usare per creare un modello matematico ha lo stesso ordine -di grandezza. Ci chiediamo: ``\`E allora possibile trovare il polinomio di grado $m$ << $n$ che meglio +di grandezza. Ci chiediamo: ``\`E allora possibile trovare il polinomio di grado $m \ll n$ che meglio approssimi la distribuzione dei nostri dati sperimentali?''; la risposta è sì e si tratta di risolvere un problema lineare ai minimi quadrati con una matrice $m \times n$. +Indagheremo in seguito questa tecnica per il calcolo del miglior polinomio approssimanete un insieme di dati +sperimentali, perché dovremo superare anche il problema del condizionamente della matrice di Van der Monde +che individua il problema\footnote{Questo era un problema anche nel caso standard con matrice quadrata, e rimarrà +complesso anche nel caso della matrice rettangolare}. + +\subsection{Principali proprietà della SVD} \label{subsec:svdprop} +Abbiamo introdotto la SVD parlando di sistemi lineari perché questo è il contesto in cui è stata originariamente +concepita. Possiamo però osservare che essa ha anche delle interessanti proprietà in molti altri ambiti. + +Consideriamo la matrice $A \in \matr{\R}{m}{n}$ che individua univocamente un'applicazione lineare +\[ +T_A : \R^n \longto \R^m +\] +La \svd\ ci permette di conoscere meglio questa applicazione. Sappiamo che se $A$ è di rango $k$ allora +$A = U\Sigma\trasp V$ e i $\sigma_i$ della matrice $\Sigma$ sono nulli a partire dal ($k+1$)-esimo. +\`E chiaro dunque che la scomposizione di permette di determinare il rango di $A$ e quindi di capire +che l'immagine di $T_A$ avrà dimensione $k$ e il kernel dell'applicazione $n-k$. Ricordando però che +\[ + Ax = U\Sigma\trasp Vx = \sum_{i=1}^{k} \sigma_i U_i\trasp V_i x +\] +possiamo estrarre altre informazioni. Dato che per ogni $x$ $V_i x$ è uno scalare l'immagine di $T_A$ +deve essere contenuta nello $\Span{U_1 \ldots U_k}$. Dato che quest'ultimo ha dimensione $k$, che è la +stessa di $\imm{T_A}$, devono coincidere e quindi le prime $k$ colonne di $U$ sono una base per l'immagine. +Analogamente dall'ortogonalità delle colonne di $V$ si ha che se $x = V_j$ con $j > k$ allora $Ax = 0$ +e quindi lo $\Span{V_{k+1} \ldots V_{n}}$ è contenuto nel kernel di $T_A$. Ancora una volta per motivi +dimensionali devono coincidere. + +In sintesi si ha che se $A = U\Sigma\trasp V$ è una matrice di rango $k$ allora +\begin{itemize} + \item $\Ker{A} = \Span{V_{k+1} \ldots V_n}$; + \item $\imm{A} = \Span{U_1 \ldots U_k}$; +\end{itemize} + +Introduciamo ora un'estensione del concetto di norma indotta visto nel corso di Analisi Numerica +\begin{de} + Sia $A$ una matrice $m \times n$. Si dice \emph{norma di $A$ indotta dalla norma vettoriale $||\cdot||$} + la seguente funzione + \[ + \begin{array}{rcl} +||\cdot|| : \matr{\R}{m}{n} &\longto& \R \\ + A & \longmapsto & \displaystyle \max_{||x|| = 1} ||Ax|| + \end{array} + \] +\end{de} +Questa è effettivamente una norma, ma la verifica viene qui omessa. +%TODO: Magari si potrebbe anche fare, suvvia! + +\begin{os} + Osserviamo la seguente catena di uguaglianze + \[ + ||Ax||_2 = ||U\Sigma \trasp V x||_2 = ||\Sigma \trasp V x||_2 = ||\Sigma z||_2 +\] +Queste ci dicono che, data l'invertibilità e l'ortogonalità di $V$, $||A||_2 = ||\Sigma||_2 = \sigma_1$. +\end{os} +Date queste considerazioni possiamo introdurre anche una generalizzazione del condizionamento +ridefinendole con la nuova norma e con la pseudo inversa. Nel caso della norma due si ottiene che +\[ + \cond{A} = ||A^+|| \cdot ||A||_2 = \frac{\sigma_1}{\sigma_k} +\] +dove $\sigma_k$ è il più piccolo $\sigma_i$ non nullo, ovvero, come al solito, $k$ è il rango di $A$. +Un'analisi dell'errore effettuata sul problema lineare ai minimi quadrati mostrerebbe come effettivamente +l'errore generato dal procedimento dipende proprio da questo coefficiente. + +\subsection{\tsvd, pulizia del rumore e compressione di immagini} +Le considerazioni fatte nella Sezione~\ref{subsec:svdprop} ci permettono di introdurre delle tecniche +per ridurre il condizionamento di alcuni problemi. + +Supponiamo di avere ad esempio un sistema lineare $Ax = b$ con $A$ una matrice con un condizionamento +molto alto. Siamo consci di non avere speranza di risolvere in maniera esatta il sistema senza aumentare +la precisione dei tipi che utilizziamo negli algoritmi. +Se ad esempio il condizionamento è nell'ordine di $10^{12}$ e la precisione di macchina di $10^{16}$ sappiamo +che probabilmente avremo circa $4$ cifre decimali corrette (nella migliore delle ipotesi). La soluzione di aumentare +la precisione di macchina (ad esempio portarla a $10^{-32}$) potrebbe essere una soluzione ma appesantirebbe +molto l'esecuzione dell'algoritmo. + +Consideriamo dunque la \svd di $A = U\Sigma\trasp V$. +Possiamo supporre che $\sigma_n$ sia molto piccolo e che +questo causi il cattivo condizionamento (ricordiamo che $\cond{A} = \frac{\sigma_1}{\sigma_n}$). Possiamo +pensare di troncare la matrice $\Sigma$ sostituendola con una matrice $\hat \Sigma$ identica ad eslusione del posto +$(n,n)$ dove rimpiazziamo $\sigma_n$ con $0$, e risolvere il problema $\hat Ax = U\hat \Sigma\trasp Vx = b$. +Questo \textbf{è un altro problema}, ma potrebbe essere molto meglio condizionato del precedente (ad esempio +se $\sigma_{n-1} \gg \sigma_n$) e talvolta è la scelta migliore. + +Questa pratica di ``troncamento'' viene chiamata \tsvd, ovvero \svd\ con troncamento. \`E tipicamente +utile nella ricostruzione di immagini (che vedremo più avanti) perché non ci interessa la soluzione esatta +del problema, ma la soluzione esatta di un problema ``semplice'' che si avvicini ai nostri dati. +Questo procedimento viene anche detto di soglia, o di filtro, perché è possbile decidere una soglia minima +sotto la quale i $\sigma_i$ non possono scendere, pena essere messi a $0$. In questo modo, fissata la +soglia $s$, avremo che il condizionamento sarà maggiorato da $\sigma_1s^{-1}$. + +In generale non è un problema banale scegliere il livello di soglia $s$. Nei casi più semplici si ha +un salto dei valori singolari, che passano da un ordine di grandezza ad uno (o a più) inferiori, dividendo +in due zone ben distinte quelli prossimi a $0$ e quelli $\gg 0$. + +Osservaiamo che in generale non abbiamo alcuna garanzia che i risultati ottenuti tramite +questa tecnica abbiano un riscontro con il problema che aveva generato i dati di partenza, e va quindi +usata con molta attenzione. + +Un altro esempio pratico di utilizzo della \tsvd\ è quello della compressione delle immagini. Supponiamo di avere +un'immagine rappresentata come una matrice di pixel $A$\footnote{non esiste un motivo per cui la matrice dovrebbe +essere quadrata, è solo per rendere più chiaro l'esempio} di dimensione $n \times n$. Possiamo scrivere +$A = U\Sigma\trasp V$ e pensare di limitarci ad una matrice di rango $k$ e quindi tronvare tutti i $\sigma_i$ +con $i > k$. In questo modo potremo rappresentare l'immagine considerando solo le prime $k$ colonne di $U$, le +prime $k$ righe di $V$ e i $\sigma_1 \ldots \sigma_k$. +Per fare un esempio pratico supponiamo $n = 1024$, ovvero un'immagine da 1 Megapixel. Questa occuperebbe in memoria +(suppoendo che sia in bianco e nero a 256 colori) $1 MB$. Decidendo di comprimerla con una matrice di rango $15$ +avremmo invece una dimensione di $15 KB$! Ovviamente l'immagine risultante darebbe solamente un'idea di quella originale, +ma si potrebbe pensare di trovare un punto d'incontro fra dimensione e qualità\footnote{e magari di raffinare anche +il metodo di compressione, ma questo lo vedremo in seguito}. \ No newline at end of file -- 2.1.4