\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.