From d9379b84f047d490aaaac4340000d2682a822a8b Mon Sep 17 00:00:00 2001 From: Leonardo Robol Date: Mon, 28 Dec 2009 16:30:23 +0100 Subject: [PATCH] Prime note sul problema generalizzato agli autovalori. --- CalcoloScientifico.tex | 3 ++ capitolo2.tex | 4 +- capitolo5.tex | 139 ++++++++++++++++++++++++++++++++++++++++++++++++- capitolo6.tex | 32 ++++++++++++ 4 files changed, 174 insertions(+), 4 deletions(-) create mode 100644 capitolo6.tex diff --git a/CalcoloScientifico.tex b/CalcoloScientifico.tex index 7a19397..c677f07 100644 --- a/CalcoloScientifico.tex +++ b/CalcoloScientifico.tex @@ -275,6 +275,9 @@ %% Matrici strutturate \include{capitolo5} +%% Problema generalizzato agli autovalori, qualche nota +\include{capitolo6} + %% Comincia l'appendice, ovvero dove %% esponiamo gli algoritmi visti con Bini \part{Esercitazioni} diff --git a/capitolo2.tex b/capitolo2.tex index dd628a1..7e88f99 100644 --- a/capitolo2.tex +++ b/capitolo2.tex @@ -107,7 +107,7 @@ la successione definita nel seguente modo A_{k+1} & = R_k Q_k \quad \text{dove} \ Q_k R_k \ \text{è la fattorizzazione QR di} \ A_k \end{array} \right. \] -\begin{os} +\begin{os} \label{os:qr_simili_ak} Osserviamo che per ogni $k$ $A_{k+1}$ è simile ad $A_k$. Infatti $A_{k+1} = \herm{Q_k}Q_k R_k Q_k$. Per ogni $k$ la matrice $A_k$ è simile a $A_{k+1}$ tramite trasformazione unitaria, che preserva il condizionamento del problema di calcolo degli autovalori. Questa quindi è una ``buona'' successione @@ -199,7 +199,7 @@ sono gli autovalori di $A$ e quindi abbiamo provato che il metodo converge. moltiplicati per un numero complesso e per il suo coniugato, lasciandoli invariati. \end{os} -\subsection{Il costo computazionale} +\subsection{Il costo computazionale} \label{subsec:qr_costo} Vorremmo ora valutare il costo computazionale di questo metodo. Consideriamo dapprima il caso di una matrice generale. Sappiamo che il costo di una fattorizzazione $QR$ è $O(n^3)$ e sperimentalmente si ottiene che il numero di passi per avere convergenza cresce linearmente con la dimensione. Questo ci permette di concludere diff --git a/capitolo5.tex b/capitolo5.tex index d5c1945..2f3a9ec 100644 --- a/capitolo5.tex +++ b/capitolo5.tex @@ -29,7 +29,8 @@ di sistemi lineari. $u\trasp u$; \end{description} -\subsection{Il metodo di Lanczos} +\section{Il metodo di Lanczos} +\subsection{Un'alternativa al metodo di Householder} 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}$ @@ -129,4 +130,138 @@ matrice dei vettori che generano: \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 +che essendo $R$ triangolare superiore e $n \times j$ con $j < n$ deve avere le ultime $n - j$ righe nulle. \\ +Calcolando ora $\trasp Q A Q = (b_{ij})$ si ottiene un matrice $k\times k$ simmetrica. Osserviamo in particolare +che se $i < j+1$ allora $b_{ij} = \trasp q_i A q_j$ e $Aq_j \in \Span{v, Av, \ldots , A^{j-1}v}$ per costruzione. +In particolare $Aq_j$ è ortogonale a $q_i$ e quindi $b_{ij} = 0$. La simmetria della matrice ci permette +di concludere che $B$ è tridiagonale, e si può verificare che è la matrice $k\times k$ generata dal metodo +di Lanczos dopo $k-1$ iterazioni. \\ +A questo punto si può supporre di avere una buona approssimazione dell'autovalore di modulo massimo (anche se +non c'è nessuna garanzia di averla davvero). Questa è di fatto l'unica applicazione del metodo di Lanczos, +data la sua instabilità numerica. + +\section{Matrici con struttura di rango}\label{sec:struttura_di_rango} +\subsection{Qualche esperimento con il metodo \qr} +Abbiamo spesso incontrato durante il corso matrici diagonali con correzioni di rango 1, +ovvero della forma $D + u\trasp u$. Queste +sono molto interessanti perché si ritrovano in molti problemi computazionali e perché sono inverse +di matrici tridiagonali. \\ +Ci domandiamo ora se esiste un metodo efficiente per applicare il Metodo~\qr\ a queste matrici. +Sappiamo di poterle tridiagonalizzare con matrici di Householder con un costo computazionale $O(n^2)$, ma +vogliamo provare ad applicare il \qr\ alla matrice piena senza dover necessariamente passare +per il procedimento di tridiagonalizzazione\footnote{Abbiamo fatto notare nella Sezione~\ref{subsec:qr_costo} che +in generale non è conveniente applicare il metodo ad una matrice piena; cercheremo però di trovare +qualche via più breve per questa particolare classe di matrici.}. \\ +Possiamo osservare sperimentalmente che facendo qualche passo del metodo \qr\ (anche utilizzando lo shift) +la struttura non viene completamente persa. + +Indichiamo con $\alpha_k$ il rango massimo delle sottomatrici quadrate strettamente contenute nella parte +inferiore della matrice della $k$-esima iterazione del \qr, e con $\beta_k$, analogamente, il rango massimo +di quelle superiori. + +\textbf{Esperimento 1}: Supponiamo di scegliere una matrice qualsiasi (complessa) e di applicare +il metodo. Osserveremo che $\alpha_0 = \alpha_1 = \ldots = \alpha_k = 1$ +mentre $\beta_k$ cresce. + +\textbf{Esperimento 2}: Supponiamo ora di restringere la scelta ad una matrice con $D$ reale, ovvero +$A = D + u\trasp u$ dove $D = \diag{\gamma_1, \ldots, \gamma_n}$ e i $\gamma_i$ sono tutti reali. Allora +otterremo sperimentalmente $\alpha_i = 1$ e $\beta_i = 3$ per ogni $i \geq 2$. + +\textbf{Esperimento 3}: Analogamente a prima scegliamo $D$ complessa ma con elementi di modulo $1$\footnote{ovvero +quella che abbiamo chiamato \emph{matrice di fase}.}. Otterremo ancora una volta $\alpha_i = 1$ e $\beta_i = 3 \: +\forall i \geq 2$. + +Come mai i $\beta_k$ in questi ultimi due casi non crescono più di $3$? Cerchiamo di rispondere analizzando separatamente +i vari casi. + +\subsection{Conservazione del rango nella parte triangolare inferiore} +Ricordiamo dall'Osservazione~\ref{os:qr_simili_ak} che le matrici $A_k$ generate dal metodo \qr\ sono +simili per trasformazione ortogonale. Se assumiamo che $R_k$ sia invertibile possiamo anche mostrare +qualcosa di più +\[ + A_{k+1} = R_k Q_k + \alpha_k I = R_k Q_k R_k R_k^{-1} + \alpha_k R_k R_k^{-1} = R_k A_k R_k^{-1} +\] +e quindi $A_{k+1}$ è simile ad $A_k$ tramite una trasformazione con una matrice triangolare superiore +$R_k$. Questo ci assicura che nella parte inferiore della matrice $A_{k+1}$ il rango venga conservato +(nel senso degli $\alpha_k = 1$). + +%% TODO: Spiegare perché il rango si conserva, da fare quando anche io lo avrò capito. + +\subsection{Limitazione del rango nella parte triangolare superiore} +Ci occuperemo ora di spiegare perché il rango di tutte le sottomatrici strettamente contenute nella +parte triangolare superiore è limitato superiormente da $3$, sia nel caso in cui $D$ sia una matrice +reale, sia in quello in cui sia una matrice di fase. Consideriamo il primo e osserviamo cosa succede +al primo passo del metodo. Poniamo $A_0 = D + u\trasp v$; si ha che: +\[ + A_1 = \herm{Q_1} A_0 Q_1 = \herm{Q_1}(D+ u\trasp v)Q_1 = \herm{Q_1} DQ_1 + u_1\trasp{v_1} +\] +Ricordando che $D$ è reale si può concludere che $\herm{Q_1}DQ_1$ è hermitiana e diagonale; +possiamo quindi scrivere il $k$-esimo passo del metodo in questo modo +\[ + A_{k+1} = H_{k+1} + u_{k+1}\trasp v_{k+1} +\] +dove $H_{k+1}$ è una matrice hermitiana. In particolare si ha $H_{k+1} = A_{k+1} - u_{k+1}\trasp v_{k+1}$. +Da quanto visto prima sappiamo che il rango nella parte inferiore di $H_{k}$ non può superare $2$. +Ricordando che $H_k$ è hermitiana si può concludere che il rango è al massimo $2$ nella parte superiore. +Osservando nuovamente che $A_k = H_k + u_k\trasp v_k$ si ottiene che il rango di $A_k$ nella parte superiore +non può superare $3$ e si ha quindi la tesi. + +La stessa cosa si può mostrare che quando la matrice diagonale $D$ è una matrice di fase. Ci sono due +procedure possibile per effettuare la dimostrazione; una è scrivere $D = QR$ ed osservare che data +l'hermitianità di $D$ si ottiene che $R$ deve forzatamente essere una matrice di fase. Questa via +richiede però tediosi passaggi molto contosi che quindi non svolgeremo. Un'alternativa più elegante +è utilizzare il \emph{Nullity theorem}, dimostrato attorno al 1960. Questo però non fa parte del +programma del corso e quindi non seguiremo neanche questa via. + +\subsection{Metodo \qr\ per il calcolo delle radici dei polinomi} +Il motivo principale (e storicamente il primo) per cui ci si è interessati a queste matrici +è stato la ricerca delle radici dei polinomi tramite l'uso delle matrici Companion. \\ +Le matrici Companion hanno una struttura come la seguente: +\[ +F = \left[ \begin{array}{cccc} + 0 & \cdots & \cdots & \times \\ + 1 & \ddots & & \vdots \\ + &\ddots & 0 & \times \\ + & & 1 & \times + \end{array} \right] +\] +La matrice $F$ si può scrivere come una matrice unitaria più una correzione di rango $1$ nel seguente modo +\[ +F = Q + u\trasp e_n = \left[ \begin{array}{cccc} + 0 & & & 1 \\ + 1 & \ddots & & \\ + & \ddots & \ddots & \\ + & & 1 & 0 \\ + \end{array} \right] ++ \left[ \begin{array}{cccc} + \: &\: &\: & v_1 \\ + & & & \vdots \\ + & & & \vdots \\ + & & & v_n \\ + \end{array} \right] +\] +e quindi sarebbe conveniente poter applicare delle ottimizzazioni al \qr\ sfruttando le osservazioni fatte +sul rango delle matrici contenute nella parte inferiore e superiore della matrice che viene iterata. + +Supponendo di voler determinare le radici del polinomio $p(x) = p_0 + p_1x + \ldots + p_nx^n$ si ottiene +la matrice +\[ +F = \left[ \begin{array}{cccc} + 0 & \cdots & \cdots & \frac{-p_0}{p_n}\\ + 1 & \ddots & & \vdots \\ + &\ddots & 0 & \vdots \\ + & & 1 & \frac{p_{n-1}}{p_n} + \end{array} \right] +\] +In generale, affrontando il problema della ricerca degli autovalori, usiamo il teorema di Bauer-Fike (Teorema~\ref{te:BauerFike}) +per assicurarci di ottenere il risultato con una buona approssimazione. Questo però non è sempre sufficiente +se $p_n$ è piccolo, perché la norma della matrice può crescere arbitrariamente. Come affrontare questo problema? + +Una soluzione può essere evitare di ricondursi ad un problema agli autovalori analizzando il seguente \emph{problema +generalizzato agli autovalori}\footnote{In generale si dice \emph{problema generalizzato agli autovalori} un problema +del tipo $\deter{A - \lambda B} = 0$. Se $B$ è invertibile questo può sempre essere ricondotto a trovare gli +autovalori di $B^{-1}A$, ma non sempre è conveniente. }: +\[ + \deter{F - \lambda I} = 0 \iff \deter{p_n F - \lambda( I + p_n e_n\trasp e_n)} = 0 +\] +Parleremo dei possibili metodi per analizzare questo problema nel Capitolo~\ref{cap:autovalori_generalizzato}. \ No newline at end of file diff --git a/capitolo6.tex b/capitolo6.tex new file mode 100644 index 0000000..fa796d7 --- /dev/null +++ b/capitolo6.tex @@ -0,0 +1,32 @@ +\chapter{Problema generalizzato agli autovalori} \label{cap:autovalori_generalizzato} +Vorremmo in questo capitolo analizzare\footnote{in realtà ci accontenteremo di dare uno sguardo +al problema, perché non avremo tempo per approfondirlo veramente.} il problema generalizzato +agli autovalori. In altre parole, date due matrici $A$ e $B$ vogliamo trovare i possibili +$\lambda$ tali che +\[ + \deter{ A - \lambda B} = 0 +\] + +\section{Il caso delle matrici Companion} +Ispirati dal problema visto alla fine della Sezione~\ref{sec:struttura_di_rango} analizziamo +il problema nel caso con $A$ in forma di Hessenberg e $B$ triangolare superiore. \\ +Per cercare di non peggiorare il condizionamento del problema sarebbe preferibile lavorare +unicamente con trasformazioni unitarie. Cerchiamo di generare una sequenza di matrici +$A_k$ e $B_k$ tali che +\[ + \deter{A - \lambda B} = 0 \iff \deter{A_k - \lambda B_k} = 0 \quad \forall k \in \N +\] +Nel nostro caso vogliamo anche mantenere le proprietà di struttura della matrice, ovvero +vorremmo che $A_k$ sia sempre in forma di Hessenberg e che $B_k$ sia sempre in forma +triangolare superiore. Cerchiamo delle matrici unitarie $U_k$ e $Q_k$ in modo da definire +la seguente successione +\[ + \left\{\begin{array}{lcl} + A_{k+1} &=& U_kA_kQ_k \\ + B_{k+1} &=& U_kB_kQ_k + \end{array} \right. +\] +e scegliendo opportunamente le matrici in modo che $A_k$ e $B_k$ siano rispettivamente +Hessenberg e triangolare superiore. \\ +Se queste condizioni sono soddisfatte allora $A_k - \lambda B_k$ è singolare solo se +$a_{jj}^{(k)} - \lambda b_{jj}^{(k)} = 0$ per qualche $j$, ovvero solo se $\lambda = \frac{a_{jj}^{(k)}}{b_{jj}^{(k)}}$ -- 2.1.4