From 0a8e6903f21de31ca8c355a4b4feb5ac96ab9931 Mon Sep 17 00:00:00 2001 From: Leonardo Robol Date: Fri, 4 Dec 2009 17:45:56 +0100 Subject: [PATCH] Aggiunto capitolo 5 e Metodo di Lanczos per l'approssimazione di autovalori minimi e masssimi. --- Bibliografia.tex | 1 + CalcoloScientifico.tex | 11 ++++- capitolo4.tex | 6 ++- capitolo5.tex | 132 +++++++++++++++++++++++++++++++++++++++++++++++++ title.tex | 2 +- 5 files changed, 148 insertions(+), 4 deletions(-) create mode 100644 capitolo5.tex diff --git a/Bibliografia.tex b/Bibliografia.tex index 5000a66..eca1a00 100644 --- a/Bibliografia.tex +++ b/Bibliografia.tex @@ -29,3 +29,4 @@ October 26, 2006, \verb-http://sourceforge.net/projects/pgf- } \end{thebibliography} + diff --git a/CalcoloScientifico.tex b/CalcoloScientifico.tex index 4a64577..7a19397 100644 --- a/CalcoloScientifico.tex +++ b/CalcoloScientifico.tex @@ -74,6 +74,8 @@ \newcommand{\cond}[1]{\mathcal{K}(#1)} \newcommand{\spe}[1]{\mathrm{Sp}(#1)} \newcommand{\rs}[1]{\rho(#1)} +\newcommand{\ray}[2]{\mathtt{R}(#1,#2)} +\newcommand{\kryl}[3]{\mathtt{K}_{#3}(#1,#2)} %% @@ -126,9 +128,11 @@ \newcommand{\tsvd}{\texttt{TSVD}} \newcommand{\qr}{\texttt{QR}} \newcommand{\fft}{\texttt{FFT}} +\newcommand{\dft}{\texttt{DFT}} +\newcommand{\idft}{\texttt{IDFT}} \newcommand{\matlab}{\texttt{Matlab}} \newcommand{\lapack}{\texttt{Lapack}} -\newcommand{\Span}[1]{<(#1)>} +\newcommand{\Span}[1]{<#1>} \newcommand{\Ker}[1]{\mathrm{Ker}(#1)} \newcommand{\Exp}[1]{\mathrm{exp}{#1}} @@ -155,7 +159,7 @@ \lstset{frameround=trbl} \lstset{% general command to set parameter(s) basicstyle=\footnotesize, % print whole listing small - keywordstyle=\color{keycolor}\bfseries\ttfamily\underbar, + keywordstyle=\color{keycolor}\bfseries\ttfamily, % underlined bold black keywords identifierstyle=, % nothing happens commentstyle=\color{red!80}\ttfamily, % white comments @@ -268,6 +272,9 @@ %% Risoluzione dei sistemi lineari \include{capitolo4} +%% Matrici strutturate +\include{capitolo5} + %% Comincia l'appendice, ovvero dove %% esponiamo gli algoritmi visti con Bini \part{Esercitazioni} diff --git a/capitolo4.tex b/capitolo4.tex index 9d9299d..6a68e56 100644 --- a/capitolo4.tex +++ b/capitolo4.tex @@ -191,7 +191,11 @@ Sottolineamo solo alcune problematiche che potrebbero nascere usando questo appr fare accontentandosi di approssimazioni dell'inversa piuttosto vaghe, ma poco invasive (come ad esempio una matrice diagonale); \end{enumerate} -\subsection{Le matrici di Toeplitz} +\section{Matrici strutturate} +Uno dei punti cardine nell'applicazione dei metodi per la soluzione dei sistemi lineari sarà riuscire a +sfruttare la struttura delle matrici con cui dovremo operare. + +\subsection{Le matrici di Toeplitz} \label{subsec:toeplitz} Molte delle matrici con cui avremo a che fare risolvendo sistemi lineari in pratica sono matrici di Toeplitz. \begin{de} Sia $A$ una matrice $n \times n$; $A$ si dice di \emph{Toeplitz} se le sue diagonali sono costanti, ovvero se per diff --git a/capitolo5.tex b/capitolo5.tex new file mode 100644 index 0000000..d5c1945 --- /dev/null +++ b/capitolo5.tex @@ -0,0 +1,132 @@ +\chapter{Calcolo degli autovalori di matrici strutturate} + +Abbiamo visto nell'analisi dei sistemi lineari vari metodi per utilizzare la struttura +delle matrici per ottimizzare il procedimento e diminuire il costo computazionale. \\ +Questo in generale è più difficile nel calcolo degli autovalori. L'unica struttura che siamo finora +riusciti a sfruttare per abbassare il costo è stata la tridiagonalità. + +\section{Strutture note} +In generale si parla di matrice strutturata quando una matrice è individuata da un numero di +parametri dell'ordine minore di $n^2$. \\ +Ricapitoliamo le strutture principali viste fino ad ora e i relativi vantaggi nella risoluzione +di sistemi lineari. +\begin{description} + \item[Matrici sparse] Parliamo di matrici sparse quando ci sono pochi elementi non nulli, ovvero un numero + con un ordine di grandezza strettamente inferiore a $n^2$. In questo caso riusciamo spesso ad ottimizzare + i metodi di moltiplicazione matrice per vettore e quindi possiamo trarre vantaggio dall'applicazione + di metodi iterativi; + + \item[Van der Monde] Non abbiamo analizzato in dettaglio\footnote{ad eccezione delle matrici di Fourier per il calcolo + della \dft, dove si riesce a scendere ad un costo $O(n\log n)$.} queste matrici ma esiste un metodo (tramite un'opportuna + rappresentazione dell'inversa) per risolvere un sistema lineare con un costo $O(n^2)$. + + \item[Toeplitz o H\"ankel] Abbiamo visto queste matrici nella Sezione~\ref{subsec:toeplitz} e tramite la + trasformata discreta di Fourier abbiamo mostrato che il costo del prodotto matrice vettore è molto basso. + Possiamo quindi ipotizzare di applicare dei metodi iterativi per risolvere il sistema. + + \item[Diagonali con correzione di rango 1] Queste martici sono piuttosto interessanti e sono le prime di + cui ci occuperemo. Sono appunto composte dalla somma di una matrice diagonale $D$ con una matrice di rango $1$ + $u\trasp u$; +\end{description} + +\subsection{Il metodo di Lanczos} +Introduciamo ora un metodo alternativo a quello di Householder per la tridiagonalizzazione di una +matrice simmetrica. \\ +Osserviamo che se $A$ è una matrice simmetrica in $\mat{\R}{n}$, allora esiste una matrice $T \in \mat{\R}{n}$ +tridiagonale simmetrica e una matrice unitaria $Q$ tali che +\[ + A = QT\trasp Q +\] +e quindi anche +\[ + AQ = QT +\] +Osserviamo ora solo la prima colonna di quest'uguaglianza, ovvero $AQe_1 = Aq_1 = QTe_1$. Se scriviamo +\[ + T = \left[ \begin{array}{cccc} + \alpha_1 & \beta_1 & & \\ + \beta_1 & \ddots & \ddots & \\ + & \ddots & \ddots & \beta_{n-1} \\ + & & \beta_{n-1} & \alpha_n \\ + \end{array} \right] +\] +Possiamo riscrivere la relazione come $Aq_1 = \alpha_1 q_1 + \beta_1 q_2$ e, una volta scelto $q_1$ vettore +di norma $1$, +si ha che $\trasp q_1 A q_1 = \alpha_1 \trasp q_1 q_1 + \beta_1 \trasp q_1 q_2 = \alpha_1$; possiamo quindi +calcolare $\alpha_1$ da cui possiamo poi ricavare $\beta_1$ considerando che $\beta q_2 = Aq_1 - \alpha_1 q_1$ +e quindi +\[ +\beta_1 = ||Aq_1 - \alpha_1 q_1||_2 \qquad \text{e} \qquad q_2 = \frac{Aq_1 - \alpha_1 q_1}{\beta_1} +\] +Ripetendo il procedimento con la seconda colonna (ora che conosciamo $q_2$) e poi continuando ancora si ottiene +la regola generale +\[ + \alpha_i = \trasp q_i A q_i \qquad \beta_i = ||Aq_i - \alpha_i q_i||_2 \qquad q_{i+1} = \frac{Aq_i - \alpha_i q_i}{\beta_i} +\] +e si può quindi ricostruire tutta la matrice $Q$ e la matrice $T$. + +Il costo computazionale dominante nello svolgimento di queste operazioni è dato dai prodotti matrice vettore +che costano generalmente $O(n^2)$ e portano quindi ad un costo complessivo del metodo di $O(n^3)$ (lo stesso +costo del metodo di Householder). \\ +Questo metodo non viene però generalemente utilizzato per calcolare la tridiagonalizzazione. Il motivo è che +non è numericamente stabile, ed in generale la matrice $Q$ ottenuta non è ortogonale. + +\begin{os} + A questo punto è naturale chiedersi che rapporto esiste fra la matrice calcolata con il metodo di Householder + e quella calcolata con il metodo di Lanczos, al variare del primo vettore $q_1$ scelto all'inizio. La risposta + che è possibile verificare è che scegliendo $q_1 = e_1$ le matrici differiscono per una matrice di fase. +\end{os} + +Nonostante in generale il metodo non venga usato per la sua poca precisione esiste un particolare caso in cui +risulta essere utile, ed è precisamente il seguente + +\subsection{Il quoziente di Rayleigh} +Cominciamo con una definizione +\begin{de} + Si dice \emph{quoziente di Rayleigh di $A$ e $x$} e si indica con $\ray{A}{x}$ lo scalare + \[ + \ray{A}{x} = \frac{\trasp x A x}{\trasp xx} + \] +\end{de} +Si può osservare che il minimo del quoziente di Rayleigh su tutto $\R^n$ corrisponde al modulo dell'autovalore minimo +e il massimo al modulo dell'autovalore massimo. \\ +Osserviamo poi che preso un generico sottospazio $k$-dimensionale $S \subseteq \R^n$ abbiamo che se +\[ + \lambda = \min_{x \in S} \ray{A}{x} +\] +allora $\lambda$ è l'autovalore di modulo minimo su un sottospazio di $\R^n$. Se $S$ è sufficientemente grande +possiamo pensare di usare $\lambda$ come approssimazione di $\lambda_{min}$. \\ +Consideriamo $\{ q_1 , \ldots, q_k \}$ base del sottospazio $S$ e la matrice $Q$ con i vettori $q_i$ come colonne. +Se prendiamo $x \in S$ allora +\[ +x = \sum_{i=1}^{k} \alpha_i q_i +\] +e quindi se $\alpha = (\alpha_1, \ldots, \alpha_k)$ si ha $x = Q\alpha$. +\[ +\frac{\trasp x A x}{\trasp xx} = \frac{\trasp \alpha \trasp Q A Q \alpha}{\trasp \alpha \trasp Q Q \alpha} = + \frac{\trasp \alpha \trasp Q A Q \alpha}{\trasp \alpha \alpha} +\] +In conclusione è sufficiente minimizzare $\ray{\trasp Q A Q}{x}$ su $\R^k$, ed essendo $\trasp Q A Q$ una matrice +$k \times k$ questo procedimento può risultare sensibilmente più economico rispetto all'idea originale. \\ +\begin{de} + Data una matrice $A$ a coefficienti reali\footnote{definiamo il procedimento sui numeri reali solo per non appesantire + la notazione, ma non c'è nessuna restrizione ad usarlo sui complessi.} e $x$ un vettore di $\R^n$. + Si dice \emph{sottospazio di Krylov} di $A$ e $v$ di ordine $j$ e si indica con $\kryl{A}{v}{j}$ il sottospazio + \[ + S = \Span{v, Av, \ldots, A^{j-1}v} + \] +\end{de} +Osserviamo che in generale $\dim{S} \leq j$. \\ +Siamo ora interessati ad utilizzare un sottospazio di Krylov come sottospazio $S$ con cui approssimare il nostro autovalore. +Per farlo però dobbiamo trovare una base ortonormale di $S$; possiamo procedere calcolando la scomposizione \qr\ della +matrice dei vettori che generano: +\[ + \left[ \begin{array}{c|c|c|c} + \multirow{4}{*}{$v$} & \multirow{4}{*}{$Av$} & \multirow{4}{*}{$\ldots$} & \multirow{4}{*}{$A^{j-1}v$} \\ + & & & \\ + & & & \\ + & & & \\ + \end{array} \right] = QR +\] +Si può mostrare che le prime $j$ colonne di $Q$ sono una base dello spazio $S$. Per farlo è sufficiente osservare +che essendo $R$ triangolare superiore e $n \times j$ con $j < n$ deve avere le ultime $n - j$ righe nulle. \ No newline at end of file diff --git a/title.tex b/title.tex index ec54d64..2770825 100644 --- a/title.tex +++ b/title.tex @@ -36,7 +36,7 @@ \includegraphics[scale=0.2]{camosci/camoscio_8.png} \caption{Una successione di camosci di 300 pixel di lato e di rango rispettivamente $100$, $50$, $25$, $15$ e $8$; le immagini sono state ridimensionate per stare nella pagina, e sono state realizzate con un programma - identico a quello realizzato in laboratorio durante il corso.} \label{fig:camosci} + identico a quello realizzato in laboratorio durante il corso.} \end{center} \end{figure} -- 2.1.4