\chapter{Il polinomio caratteristico}
In questo capitolo ci occuperemo di descrivere le forme normali tipicamente usate per
calcolare agevolmente gli autovalori di una matrice. Descriveremo dei metodi efficienti
per valutare in un punto il polinomio caratteristico, che potranno essere usati
nei capitolo seguenti per implementare gli algoritmi di calcolo effettivo. \\
Premetteremo a questo una breve esposizione degli utilizzi pratici più comuni dei
metodi che verranno in seguito esposti.
 
\section{Esempi pratici di utilizzo}
Prima di cominciare ad analizzare in dettaglio l'argomento presentiamo due applicazioni pratiche
(che poi verranno analizzate in maggior dettaglio) che richiederanno la determinazione mediante
metodi numerici degli autovalori di una matrice associata al problema.
 
\subsection{Risoluzione di equazioni algebriche}
\label{subsec:esempi:eqalgebriche}
Un problema comune è, data un'equazione algebrica della forma
\[
 p(z) = p_0 + p_{1}z + \ldots + p_{n}z^{n} = 0
\]
trovare la $n$ radici $z_1 , \ldots , z_n$ tali che $p(z_i) = 0 \ \forall i = 1\ldots n$.
 
Risolvere questo problema tramite algoritmi di iterazione funzionale, come vedremo, potrebbe non essere
conveniente, e quindi ci si riconduce spesso (quasi sempre) ad un problema di calcolo di autovalori tramite
il seguente procedimento. \\
Consideriamo la matrice
\[
 F = \begin{bmatrix}
      0 & 0    & \ldots & -\frac{p_0}{p_n} \\
      1 & 0     &        & -\frac{p_1}{p_n} \\
      0 & \ddots & \ddots & \vdots           \\
      0 &  \hdots & 1      & -\frac{p_{n-1}}{p_n} \\
     \end{bmatrix}
\]
detta matrice di \emph{Frobenius}\index{Frobenius, matrice di} o matrice \emph{Companion} \index{Companion, matrice}. Questa
ha come polinomio caratteristico esattamente $p(z)$ e quindi i suoi autovalori sono esattamente le radici dello stesso. \\
Osserveremo inoltre che sarà possibile mostrare la stabilità all'indietro del procedimento per calcolare
gli autovalori, ovvero potremo essere sicuri che gli autovalori calcolati mediante l'aritmetica approssimata
di macchina saranno le radici di un polinomio i cui coefficienti ``disteranno poco'' da quelli originali di $p(z)$.
Questo in generale non ci assicura di avere un risultato con una buona approssimazione; più precisamente questo sarà
garantito solo nel caso in cui il problema sia ben condizionato\footnote{Ricordiamo che un problema è ben condizionato
quando a piccole variazioni dei dati iniziali corrispondono piccole variazioni dei dati finali.}.
 
\subsection{Equazioni differenziali}
Un altro caso in cui il calcolo di autovalori ci permetterà di risolvere un problema comune sarà quello delle
equazioni differenziali. Non abbiamo ancora gli strumenti per approfondire questo argomento, ma possiamo anticipare
che i metodi per il calcolo di autovalori ci permetteranno sia di arrivare alla soluzione (in qualche caso) che
di stimare l'effetto di una perturbazione dei dati iniziali (in altri casi).
 
\section{Analisi del condizionamento} \label{sec:analisidelcondizionamento}
In questa sezione vorremmo analizzare il condizionamento del nostro problema. Il calcolo degli autovalori non
è sempre un problema ben condizionato, come possiamo mostrare con questo esempio: \\
Sia $F$ la matrice di Frobenius associata al polinomio $z^n$, ovvero la matrice con soli zeri ad eccezione della
sottodiagonale, composta da soli $1$. \\
I suoi autovalori sono tutti $0$ ed hanno moleplicità algebrica $n$ e molteplicità geometrica $1$\footnote{il che si
capisce facilmente notando che la matrice $F$ è in forma di Jordan}. \\
Se noi perturbiamo la matrice sottraendole la matrice $\eps e_1 \trasp{e_n}$ otteniamo la matrice di Frobenius
associata al polinoio $z^n + \eps$. Da quanto abbiamo osservato nella Sezione~\ref{subsec:esempi:eqalgebriche} sappiamo che
gli autovalori di quest'ultima sono le radici $n$-esime dell'unità moltiplicate per $||\eps||^{\frac{1}{n}}$;
possiamo osservare che al crescere di $n$ anche se $\eps$ è piccolo questo numero può diventare piuttosto grande, e
portare quindi ad errori non trascurabili.
\subsection{Il caso di una matrice diagonalizzabile}
Cominciamo ad analizzare un caso relativamente semplice, ovvero quello dove $A$ è una matrice diagonalizzabile,
per cui dimostreremo un risultato detto
\begin{te}[di Bauer - Fike] \label{te:BauerFike}
 Se $A \in \mat{\R}{n}$ è una matrice diagonalizzabile tramite il cambio di base $V^{-1}$ ed $\eta$ è
 un autovalore della matrice perturbata $A + \delta A$ allora esiste un autovalore $\lambda$ di $A$ tale che
 \[
  ||\lambda - \eta|| \leq ||\delta A || \cdot \cond{V}
 \]
\end{te}
\begin{proof}
Sappiamo che esiste $V$ base di autovettori tali che
\[
 A = VDV^{-1} \; \textrm{con} \ D \ \textrm{diagonale}
\]
Supponiamo ora di aver calcolato $\eta$ autovettore di una matrice $A + \delta A$ e verifichiamo
quanto dista $\eta$ dagli autovettori di $A$.\\
Osserviamo che questo equivale a
\[
 (A + \delta A) y = \eta y \ \iff \ (A - \eta y) = \delta A y
\]
Possiamo distinguere due casi:
\begin{description}
 \item[$(A-\eta I)$ è singolare] Questo è il caso migliore in cui possiamo sperare, in quanto questo significa
 che $\eta$ è un autovalore di $A$ e quindi la distanza è $0$.
  \item[$(A-\eta I)$ non è singolare] ed allora ammette un'inversa. Abbiamo quindi che
  \[
   y = -(A - \eta I)^{-1}( \delta A y )
  \]
  Consideriamo dunque una norma matriciale indotta tale che data una matrice $D$ diagonale si abbia
  $||D|| = \max_{i = 1 \ldots n}\{|d_{ii}|\}$\footnote{la norma $1$, $2$ e $\infty$ soddisfano questo
  requisito,  ad esempio; questo tipo di norma è detta \emph{assoluta}.} ed effettuiamo le seguenti maggiorazioni
  \[
   ||y|| \leq ||(A -\eta I)^{-1}|| \cdot || \delta A || \cdot ||y||
  \]
  che si verifica solo se (ricordando che essendo $y$ un autovettore
  $y \neq 0$ e quindi $||y|| \neq 0$)
  \[
   1 \leq ||V|| \cdot ||( D -\eta I)^{-1}|| \cdot ||V^{-1}|| \cdot || \delta A ||
   \leq \frac{\cond{V} \cdot ||\delta A ||}{\min_{i = 1 \ldots n}\{ \lambda_i - \eta\}}
  \]
  da cui si ottiene che esiste un $j \in 1 \ldots n$ tale che
  \[
   ||\lambda_j - \eta|| \leq ||\delta A || \cdot \cond{V}
  \]
\end{description}
 \`E evidente quindi che in entrambi i casi è valida la diseguaglianza della tesi (nel primo caso si ha addirittura
 che $||\lambda - \eta|| = 0$), e quindi il teorema è provato.
\end{proof}
 
\begin{os}
 Dobbiamo fare attenzione al fatto che questa maggiorazione ottenuta dal precedente teorema è in valore
 assoluto, e quindi non ci dice nulla sull'errore relativo. Saremo certi di ottenere un buon
 condizionamento solo nel caso in cui gli autovalori trovati non siano troppo ``piccoli''.
\end{os}
 
Data questa maggiorazione dell'errore ci possiamo chiedere come fare a minimizzare l'unico fattore
su cui possiamo avere un ``controllo'', ovvero $\cond{V}$. Dalle proprietà delle norme matriciali
indotte sappiamo che $\forall V \ \cond{V} \geq 1$. \\
Inoltre possiamo osservare che se $V$ è una matrice unitaria allora $\cond{V}$ vale esattamente $1$. \\
Sembra quindi opportuno, quando possibile, cercare di rendere diagonale la matrice $A$ tramite un cambio
di base unitario. Quando è possibile farlo? \\
Grazie alla forma normale di Schur possiamo dare una caratterizzazione completa delle matrici per cui questo
è possibile. Si può infatti provare che data $A \in \mat{\C}{n}$ questa è diagonalizzabile mediante
matrici unitarie se e solo se $A$ è normale, ovvero $A\herm{A} = \herm{A}A$.
 
\begin{os}
 Ci ricordiamo che per risolvere i sistemi lineari abbiamo individuato due classi di metodi:
 \begin{description}
  \item[I metodi diretti] i quali forniscono una soluzione ``esatta'' del problema in un numero
  finito di passi, a meno dell'errore di macchina e algoritmico.
  \item[I metodi iterativi] i quali invece forniscono una soluzione approssimata del sistema,
  iterando un numero finito di passi di una successione che converge solamente dopo un numero
  infinito.
 \end{description}
Nel caso della ricerca degli autovalori la prima classe di metodi non può essere applicata, in quanto
il problema è equivalente a trovare le radici del polinomio caratteristico, problema che \emph{non può
essere risolto tramite una formula}.
\end{os}
 
Siamo quindi consci che la nostra unica opportunità per arrivare alla soluzione sarà eseguire una
successione di cambi di base (che sono degli invarianti del problema) che porti la matrice in una forma
in cui gli autovalori siano facilmente determinabili. \\
Il condizionamento del problema sarà quindi maggiorabile con il prodotto dei condizionamenti di tutti i
cambi di base (si può infatti mostrare che prese due matrici $V$, $S$ si ha $\cond{VS}\leq\cond{V}\cdot\cond{S}$)
e quindi dovremo
cercare dei cambi di base con un piccolo condizionamento (come, ad esempio, quelli unitari).
 
Il teorema di Bauer--Fike ci permette di dare una maggiorazione globale sul condizionamento degli autovalori,
ma in alcuni casi è possibile dare anche una maggiorazione del condizionamento per un autovalore singolo. \\
Consideriamo ad esempio il caso di un autovalore con molteplicità algebrica e geometrica $1$.
 
\begin{pr}
 Data una matrice $A \in \mat{\C}{n}$, una matrice di perturbazione $\eps F$, un autovalore
 $\lambda \in \spe{A}$ ed $\eta$ un autovalore della matrice perturbata $A + \eps F$ si ha che,
 dati $y, w$ autovettori destro e sinistro di modulo $1$ relativi a $\lambda$
 \[
  ||\eta - \lambda|| \leq \frac{1}{\herm{w}y} \cdot ||\eps F||
 \]
\end{pr}
\begin{proof}
 Sappiamo che $\eta$ e il suo autovettore relativo\footnote{che evidentemente non è unico, ma possiamo supporre
 di sceglierlo in modo continuo} $y$ sono funzioni analitiche di $\eps$ e quindi
 possiamo scrivere
 \[ \left\{\begin{array}{l}
  \eta(\eps) = \lambda  + \eps \cdot \xi + O(\eps^2) \\
  y(\eps)   = y + \eps \cdot w + O(\eps^2) \\
  \end{array}\right.
 \]
Effettuando un'analisi al I ordine otteniamo
\begin{align*}
 (A + \eps F) ( y + \eps w) & = (\lambda + \eps \xi)(y + \eps w) \\
 Ay + \eps A w + \eps Fy & = \lambda y + \lambda \eps w + \eps \xi y   \\
\end{align*}
considerando che $Ay = \lambda y$ e dividendo tutto per $\eps$ si ottiene
\[
 Aw + Fy = \lambda w + \xi y
\]
Sappiamo inoltre che deve esistere $u$ autovettore sinistro unitario di $A$ relativo all'autovalore
$\lambda$ e quindi, moltiplicando tutto per $u$
\begin{align*}
 \herm{u}Aw + Fy & = \lambda \herm{u} w + \xi \herm{w} y \\
 Fy & = \xi \herm{u} y
\end{align*}
Ricordando infine che, a meno di termini di ordine maggiore di $1$, $||\eps \xi|| = ||\lambda - \eta||$ e
che $||u|| = ||y|| = 1$ si ottiene
\[
 ||\lambda - \eta|| = ||\eps \xi|| \leq || \eps F|| \cdot \frac{1}{\herm{u}y}
\]
che è la tesi.
\end{proof}
 
%% 1 ottobre 2009
\section{Operazioni preliminari}
In questa sezione vorremmo introdurre delle operazioni preliminari da compiere prima di applicare
un qualsiasi metodo per il calcolo effettivo degli autovalori. \\
\subsection{Matrici di Householder}
I metodi che solitamente vengono usati accettano infatti in input solo matrici particolari, più
precisamente
\begin{description}
 \item[Matrici hermitiane tridiagonali] Ovvero delle matrici hermitiane tali che $a_{ij} = 0$ se
  $| i -j | \geq 2$ e tale che $a_{ij} = \con{a_{ji}} \ \forall i,j \in 1 \ldots n$.
  \item[Matrici in forma di Hessenberg superiore] Ovvero le matrici tali che $a_{ij} = 0$ se $i > j +1$.
\end{description}
 
\begin{figure}[h]
\begin{center}
 \subfigure{
$ T =
   \begin{bmatrix}
    \alpha_1 & \con{\beta_1} & 0      & 0 \\
    \beta_1  & \ddots        & \ddots & 0  \\
    0        & \ddots        & \ddots & \con{\beta_{n-1}} \\
    0        & 0             & \beta_{n-1} & \alpha_n \\
   \end{bmatrix}$
}
\subfigure{
$ H =
\begin{bmatrix}
 \times & \hdots & \hdots & \times \\
 \times & \ddots &     & \vdots \\
 0  & \ddots & \ddots & \vdots \\
 0 & 0       & \times   & \times \\
\end{bmatrix}$
}
\end{center}
 \caption{Struttura delle matrici tridiagonali e di Hessenberg superiore}
\end{figure}
 
Abbiamo quindi la necessità di trovare un algoritmo efficiente e stabile per trasformare
una generica matrice $A$ in una matrice $T$ o $H$ rispettivamente tridiagonale o in forma
di Hessenberg superiore. \\
Per quanto osservato nella Sezione~\ref{sec:analisidelcondizionamento} cercheremo una $Q$ unitaria
tale che
\[
 QA\herm{Q} = T \qquad \textrm{oppure} \qquad QA\herm{Q} = H
\]
Si osserva subito che sia $Q$ che $T$ sono unitarie e quindi una condizione necessaria per il verificarsi
della prima eventualità è che anche $A$ sia hermitiana\footnote{in quanto la stiamo trasformando per congruenza,
che conserva l'hermitianità}
 
\begin{de}[Matrici di Householder]
 Una matrice $P$ si dice \emph{matrice elementare di Householder} se esistono $\sigma \in \R \setminus \{0\}$
 e $u \in \R^n$ tali che $P = I - \sigma u \herm{u}$ e $\sigma = \frac{2}{||u||_2}$.
\end{de}
 
Sia $P$ una matrice di Householder. Allora valgono le seguenti:
\begin{description}
 \item[$P$ è Hermitiana] Se abbiamo $P = I -\sigma u \herm{u}$ allora $p_{ij} = u_i\con{u_j}$, e quindi
  $\con{p_{ji}} = \con{u_j\con{u_i}} = u_i\con{u_j} = p_{ij}$.
 \item[$P$ è unitaria] Se consideriamo che $P$ è hermitiana abbiamo che $P\herm{P} = P^2 =
  (I - \sigma u \herm{u})^2 = I -2\sigma u \herm u + \sigma^2 \herm u u u \herm u = I$.
 \item[$\deter{P} = -1$] Consideriamo una base dello spazio ottenuta imponendo come primo
  vettore $u$ e costruendo gli altri ortogonali a lui. Si osserva facilmente che la matrice
  associata a $P$ diventa come la matrice identità ad eccezione del posto $(1,1)$ dove si trova
  un $-1$ (infatti $Pu = -u$) e quindi $\det{P} = -1$.
\end{description}
 
Consideriamo ora una generica matrice $A$ e mostriamo che esiste una matrice unitaria $P$ tale che
$PA\herm{P}$ ha tutti gli elementi delle prima colonna con indice maggiore di $1$ uguali a $0$.
Questo sarà il passaggio che poi ci permetterà di mostrare per induzione che si può portare una
qualsiasi matrice in forma di Hessenberg superiore. \\
Data la seguente matrice generica $A$
\[
 A = \left[ \begin{array}{c|cc}
      a_{11} & \multicolumn{2}{|c}{\herm{w}} \\
  \hline
      \multirow{2}{*}{$v$}    & \sblocke{\; \hat{A}\;}{2}  \\
        & &
     \end{array} \right]
\]
So che esiste una matrice $\hat P$ di Householder tale che $\hat{P}v = \beta e_1$ da cui si ottiene che
\[
 P = \left[ \begin{array}{c|cc}
  1 & \multicolumn{2}{c}{\herm{0}} \\
  \hline
  \multirow{2}{*}{$0$} & \sblocke{ \quad \hat P \quad}{2} \\
  & &
      \end{array} \right]
\qquad
 PA\herm{P} = \left[ \begin{array}{c|cc}
                      a_{11} & \multicolumn{2}{|c}{\herm{w} \herm{\hat{P}}} \\
\hline
		      \multirow{2}{*}{$\hat Pv$} & \sblocke{\hat P \hat A \herm{\hat{P}}}{2} \\
                      & &
                     \end{array} \right]
\]
Ricordando che $\hat{P}v = \beta e_1$ si ottiene che in $n-2$ passi la matrice di partenza si può ridurre
in forma di Hessenberg superiore. \\
Si può osservare che se la matrice di partenza era hermitiana anche la matrice ridotta lo sarà,
dato che la trasformazione per matrici di Householder è unitaria, e quindi la matrice ottenuta
sarà tridiagonale.
 
\subsection{Valutazione del costo computazionale}
Il costo computazionale di ogni passo del procedimento sopra descritto è dato da
\begin{enumerate}
 \item Calcolo di $\hat P$;
 \item Calcolo di $\herm{w} \hat{P}$ (qualora sia necessario, cioè quando $A$ non è
  hermitiana);
 \item Calcolo di $\hat{P}\hat{A}\herm{\hat{P}}$;
\end{enumerate}
I primi due sono $O(n)$ mentre il terzo è il più grande, $O(n^2)$. Il procedimento completo
risulta quindi con un costo computazionale di $O(n^3)$.
 
\subsection{I vantaggi della riducibilità}
Data la matrice in forma tridiagonale o in forma di Hessenberg superiore è facile verificare che
la condizione di riducibilità è verificata solo se $\exists i \: \beta_i = 0$ dove i $\beta_i$ sono
gli elementi della sottodiagonale. Non è però vero il contrario, ovvero se i $\beta_i$ sono tutti
diversi da $0$ non è certo che la matrice sia irriducibile\footnote{questa implicazione vale solo
nel caso hermitiano tridiagonale}. D'ora in poi diremo che la matrice è \emph{non riducibile}
se tutti i $\beta_i$ non sono $0$, mentre useremo il termine \emph{irriducibile} per
indicare la condizione usuale di irriducibilità. \\
La riducibilità porta notevoli vantaggi computazionali alla risoluzione del problema in quanto
si ottiene una matrice del tipo
\[
 M = \left[ \begin{array}{c|c}
             A & B \\
  \hline
             0 & C \\
            \end{array} \right]
\]
e quindi è immediato verificare che gli autovalori di $M$ sono quelli di $A$ uniti a quelli di $C$.
 
\begin{pr}
 Sia $A$ una matrice tridiagonale hermitiana irriducibile. Allora tutti i suoi autovalori hanno molteplicità $1$.
\end{pr}
\begin{proof}
 Sia $\lambda$ un autovalore di $A$. Sappiamo che $A - \lambda I$ non è un isomorfismo, e che la molteplicità
 geometrica di $\lambda$ è pari al rango di $A - \lambda I$.
 Se consideriamo il minore di sud-ovest $J$ possiamo osservare che:
 \begin{itemize}
  \item $J$ è triangolare superiore
  \item la diagonale $J$ è composta dagli elementi $\beta_1 \ldots \beta_n$ della sottodiagonale di $A$
 \end{itemize}
Queste due osservazioni ci permettono di concludere che $\deter{A - \lambda I} = \prod_{i=0}^{n}~\beta_i$ che
è diverso da $0$, e quindi la molteplicità geometrica di $\lambda$ è $1$. Sapendo che la matrice è
hermitiana possiamo anche essere sicuri che sia diagonalizzabile, e quindi che per ogni autovalore
la molteplicità geometrica coincida con quella algebrica. In particolare l'autovalore $\lambda$ ha
molteplicità $1$.
\end{proof}
 
Osserviamo che se la matrice invece che essere tridiagonale hermitiana è in forma di Hessenberg superiore,
possiamo solo affermare che ogni autovalore ha molteplicità gemetrica $1$. Non possiamo però controllare
la molteplicità algebrica e quindi non possiamo essere certi della diagonalizzabilità della matrice.
 
\section{Il polinomio caratteristico}
Il primo metodo che si può pensare di applicare cercando gli autovalori di una data matrice $A$ è
quello di cercare gli zeri del polinomio caratteristico. Nonostante questo sia raramente applicabile,
alcune analisi sulla ``struttura'' del polinomio potranno fornirci dei risultati teorici che ci saranno
utili in seguito.
 
\subsection{Il caso delle matrici Hermitiane tridiagonali} \label{subsec:hermdiag}
Consideriamo una matrice $A \in \mat{\C}{n}$ in forma tridiagonale hermitiana.
In tutta la sezione indicheremo con
\begin{description}
 \item[$A_k$: ] Il minore di nord-ovest di ordine $k$ della matrice $A$. Osserviamo in particolare
 che si tratta ancora di una matrice hermitiana tridiagonale per ogni $k$.
 \item[$p_k(z)$: ] Il polinomio caratteristico delle matrice $A_k$, ed in particolare $p_n = p$;
 \item[$\lambda_i^{(k)}$: ] L'$i$-esimo autovalore della matrice $A_{k}$. L'ordinamento non ha importanza
 dove non è espressamente specificato;
\end{description}
Se proviamo a calcolare il polinomio caratteristico di $A_k$ sviluppando sull'ultima riga (o, analogamente,
sull'ultima colonna) otteniamo la seguente relazione ricorrente e tre termini:
\[
p_k(z) = \deter{A - zI} = (\alpha_k - z) p_{k-1}(z) - |\beta_{k-1}|^2 p_{k-2}(z)
\]
Questa relazione ha senso anche nel caso $k = 1, 2$ a patto di porre $p_{0}(z) = 1$ e $p_{-1}(z) = 0$.
Una volta nota questa relazione valutare il polinomio caratteristico di $A = A_n$ in un punto diventa molto
meno oneroso (computazionalmente) rispetto al calcolare tutti i coefficienti. \\
Si può infatti stimare la complessità del calcolo $p_k(z)$ a partire da $p_{k-1}(z)$ e $p_{k-2}(z)$
con circa $5$ operazioni aritmetiche, e quindi
la valutazione del polinomio in un qualsiasi punto $z$ risulta costare $O(n)$.
\begin{os} \label{os:autovalpol}
 Dalla formula possiamo dedurre che se $\xi$ è un autovalore della matrice $A_k$ allora non può essere
 anche autovalore della matrice $A_{k-1}$.
\end{os}
Supponiamo per assurdo che $p_{k-1}(\xi) = 0 = p_k(\xi)$. Dunque si avrebbe
$p_k(\xi) = 0 = (\alpha_k - \xi) p_{k-1}(\xi) - |\beta_{k-1}|^2 p_{k-2}(\xi) = |\beta_{k-1}|^2 p_{k-2}(\xi)$
e quindi anche $p_{k-2}(\xi)$ deve essere nullo. Ripetendo questa considerazione si ottiene che anche $p_0(\xi)$
deve essere nullo, ma $p_0(\xi) = 1$ (il polinomio costante) che è assurdo.
In definitiva per ogni $k \neq j$ si ha che $\spe{A_k} \cap \spe{A_j} = \emptyset$.
 
\subsection{L'equazione secolare} \label{sec:eqsecolare}
Una domanda che sorge spontanea dopo queste considerazioni è: ``Che relazione possiamo trovare
fra gli autovalori di due minori $A_k$ e $A_{k-1}$ di una matrice $A$?''. \\
Il polinomio come scritto nella sezione precedente ci permette solamente di notare che
gli autovalori sono distinti. Possiamo però estrapolare delle informazioni più dettagliate rappresentandolo
in una opportuna base (di polinomi).
Per questo paragrafo possiamo limitarci, per semplicità di notazione, al caso di una matrice simmetrica
in $\mat{\R}{n}$, anche se il caso complesso si tratta con gli stessi passaggi.
Dividiamo la matrice $A$ in blocchi nel modo seguente
\[
 A= \left[ \begin{array}{cc|c}
          \sblocko{A_{n-1}}{2} & \\
           & & \beta_{n-1} \\ \hline
           &  \beta_{n-1} & \alpha
        \end{array}
 \right]
\]
Dato che la matrice $A_{n-1}$ è simmetrica esiste una matrice ortogonale $Q_{n-1}$ tale che
$D_{n-1} = Q_{n-1}A\trasp{Q_{n-1}}$ dove $D$ è la matrice con gli autovalori di $A$ sulla
diagonale. \\
Consideriamo dunque la matrice $\hat Q$ così composta:
\[
 \hat Q = \left[
\begin{array}{cc|c}
 \sblocko{Q_{n-1}}{2} & \\
  & & \\ \hline
  & & 1
\end{array} \right]
\]
$\hat Q$ è sempre ortogonale e si verifica che
\[
 \left[ \begin{array}{cc|c}
  \sblocko{Q_{n-1}}{2} & \\
  & & \\ \hline
  & & 1
 \end{array} \right]
 \left[ \begin{array}{cc|c}
         \sblocko{A_{n-1}}{2} & \\
         & &  \beta_{n-1}\\ \hline
         & \beta_{n-1} & \alpha_{n} \\
        \end{array} \right]
 \left[ \begin{array}{cc|c}
         \sblocko{\trasp{Q_{n-1}}}{2} & \\
         & & \\ \hline
         & & 1
        \end{array} \right]
=
\left[ \begin{array}{cc|c}
        \sblocko{D_{n-1}}{2} & \multirow{2}{*}{$w$} \\
        & & \\ \hline
        \multicolumn{2}{c|}{\trasp{w}} & 1
       \end{array} \right] = B_n
\]
Una matrice come $B_n$, ovvero una diagonale ``orlata'' sull'ultima riga e sull'ultima
colonna si dice \emph{matrice a freccia}\footnote{Penso che il motivo sia piuttosto
evidente guardando la forma degli elementi non nulli}.
Dato che questa trasformazione viene realizzata tramite matrici ortogonali anche il
polinomio caratteristico rimane invariato e quindi si ha che
\[
 p_n(z) = \deter{B_n - zI}
\]
Ricordiamo ora un risultato di Analisi Numerica
\begin{pr}
 Sia $M$ una matrice a blocchi come la seguente
 \[
  M = \left[ \begin{array}{c|c}
              A & B \\ \hline
              C & D \\
             \end{array} \right]
 \]
dove $A$ e $D$ sono matrici quadrate. Allora Esiste una matrice $\Gamma$ delle stesse dimensioni di $D$
tale che
\[
 M = \left[ \begin{array}{c|c}
      I & 0 \\ \hline
      \times & I
     \end{array} \right]
 \left[ \begin{array}{c|c}
         A & 0 \\ \hline
         0 & \Gamma
        \end{array} \right]
\left[ \begin{array}{c|c}
        I & \times \\ \hline
        0 & I
       \end{array} \right]
\]
ed in particolare $\Gamma = D - C A^{-1} B$ è detta \emph{complemento di Schur di $A$ in $M$}.
\end{pr}
\begin{proof}
 Provando a scrivere la relazione più esplicitamente otteniamo
\[
 \begin{bmatrix}
  I & 0 \\
  \trasp{\alpha} & I
 \end{bmatrix}
 \begin{bmatrix}
  A & 0 \\
  0 & \Gamma
 \end{bmatrix}
 \begin{bmatrix}
  I & \beta \\
  0 & I
 \end{bmatrix} =
 \begin{bmatrix}
   A & B \\
   C & D
 \end{bmatrix}
\]
dove $\trasp \alpha$, $\beta$ e $\Gamma$ sono le incognite. Sviluppando si ottengono le seguenti equazioni
\[
 \left\{
 \begin{array}{l}
  A \beta = B \\
  \trasp \alpha A = C \\
  \trasp \alpha A \beta + \Gamma = D
 \end{array} \right.
\]
Ricordando che $\deter{A} \neq 0$ e considerando le prime due equazioni come degli insiemi di
sistemi lineari si ottiene che esistono e sono unici $\alpha$ e $\beta$ che soddisfano le richieste, ed
in particolare sono
\[
\left\{ \begin{array}{l}
 \trasp \alpha = C A^{-1} \\
 \beta = A^{-1} B
\end{array} \right.
\]
In conclusione $\Gamma = D - \trasp \alpha A \beta = D - C A^{-1} A A^{-1} B = D - C A^{-1} B$
e quindi la tesi è provata.
\end{proof}
\begin{os}
 Questa proposizione ci è utile perché ci permette di calcolare il determinante di una matrice di questo
tipo calcolando semplicemente il prodotto del determinante di $A$ per quello di $\Gamma$.
\end{os}
Osserviamo prima di tutto che la matrice $B_n - zI$, per $z$ fissato, è in questa forma. Possiamo
scrivere
\[
 B_n - zI = \left[ \begin{array}{ccc|c}
                    \lambda_1^{(n-1)} - z & & & \multirow{3}{*}{$w$} \\
		    & \ddots & &  \\
		    & & \lambda_{n-1}^{(n-1)} -z& \\ \hline
		    \multicolumn{3}{c|}{\trasp{w}} & \alpha_n -z
                   \end{array} \right] =
\left[ \begin{array}{cc|c}
        \sblocko{E_{n-1}}{2} & \multirow{2}{*}{$w$} \\
        & &  \\ \hline
        \multicolumn{2}{c|}{\trasp{w}} & \alpha_n -z
       \end{array} \right]
\]
dove $E_{n-1}$ ed $[ \alpha_n -z ]$ sono quadrate\footnote{la seconda in particolare è
semplicemente uno scalare}.
Calcoliamo dunque il polinomio caratteristico della matrice (in tutti i punti dove $E_{n-1}$ è
invertibile, ovvero in tutti gli $z$ che sono diversi dagli autovalori di $A_{n-1}$)
$B_n$
\[
p_n(z)=\deter{B_n - zI}=\deter{A} (\alpha_n - z - \trasp{w}E_{n-1}^{-1}w)
\]
E quindi possiamo scrivere
\[
 p_n(z) = \Bigg[ \prod_{j=1}^{n-1} (\lambda_j^{(n-1)} - z) \Bigg] \cdot
 \Bigg[ \alpha_n - z  - \sum_{i=1}^{n} \frac{w_i^2}{\lambda_i^{(n-1)} - z}\Bigg]
\]
e per continuità possiamo estenderlo a tutto $\C$, ottenendo
\[
 p_n(z) = (\alpha_n - z)\cdot \prod_{j=1}^{n-1} (\lambda_j^{(n-1)} - z) - \sum_{i=1}^{n}w_i^2\prod_{\substack{i=1\\j\neq i}}^{n}(\lambda_i^{(n-1)}-z)
\]
\begin{os}
 Nel definire il polinomio siamo stati costretti ad escludere una quantità finita di punti (precisamente
 gli autovalori di $A_{n-1}$), ma è evidente che
 due funzioni polinomiali su $\C$ o su $\R$ che sono uguali a meno di una quantità finita di punti devono coincidere.
\end{os}
Questa forma del polinomio ci permette di valutarlo negli autovalori $\lambda_i^{(n-1)}$ della matrice
$A_{n-1}$. Otteniamo la seguente
\[
 p_n( \lambda_i^{(n-1)} )  = 0 - w_i^2\prod_{\substack{i=1\\i\neq j}}^{n} (\lambda_i^{(n-1)} - z) \neq 0
\]
e quindi, in particolare, per ogni $i$ si ottiene $w_i \neq 0$.
Siamo ora interessati a cercare le radici del polinomio, sfruttando le informazioni che supponiamo
di avere sugli autovalori della matrice di ordine $n-1$. \\
Consideriamo che $\forall j=1 \ldots n-1 \quad p(\lambda_j^{(n-1)}) \neq 0$, per quanto visto nell'~Osservazione~\ref{os:autovalpol},
e quindi le radici del polinomio sono le radici della funzione
\[
 g(\xi) = \alpha_n - \xi-  \sum_{j=1}^{n} \frac{w_i^2}{\lambda_j^{(n-1)} - \xi}
\]
Questa equazione ($g(\xi) = 0$) è detta \emph{equazione secolare}. Le ragione del nome curioso non
sono note, anche se esistono due teorie principali. Una sostiene che l'appellativo deriva dall'usanza
diffusa nei primi del novecento di chiamare \emph{polinomio secolare} il polinomio caratteristico
di una matrice, mentre l'altra sostiene che invece il nome sia dovuto ad una sua utilità
in alcune teorie di descrizione del moto di pianeti (che tipicamente hanno tempi piuttosto lunghi). \\
Ricordando che annullare $g$ è la stessa cosa che annullare $p_n$ possiamo tracciare un grafico
qualitativo di $g$ (come si vede in Figura~\ref{fig:eqsecolare}) e notare che ad ogni asintoto verticale
di $g$ corrisponde un autovalore di $A_{n-1}$ e che gli autovalori della matrice $A_n$ sono separati
da quelli di $g$, in quanto la derivata di $g$ è sempre negativa (e quindi la funzione monotona).
\begin{figure}[ht]
  \begin{center}
 \begin{tikzpicture}
\fill[blue!8] (-6.5,-3.5) rectangle (5.5,2.5);
  %% Disegnamo gli assi
\begin{scope}[very thin]
  \draw[->] (-6,0) -- (5,0) node[anchor=north] {$\xi$};
  \draw[->] (-0.5,-3) -- (-0.5,2) node[anchor=east] {$g(\xi)$};
\end{scope}
  \begin{scope}[thick]
  %% Prima curva
  \draw (-6,2) .. controls (-5,1.75) and (-4.2,0.5) .. (-4,0);
  \draw (-4,0) .. controls (-3.8,-0.5) and (-3.5,-2) .. (-3.5,-3);
 
  %% Seconda curva
  \draw (-3.2,2) .. controls (-3.2,1.5) and (-2,1) .. (-1,0);
  \draw (-1,0) .. controls (0,-1) and (0.5,-2) .. (0.55,-3);
 
  %% Terza curva
  \draw (1,2) .. controls (1,1) and (1.5,0.5) .. (2,0);
  \draw (2,0) .. controls (2.5,-0.5) and (4,-2) .. (5,-3);
\end{scope}
  %% Asintoti (che corrispondono agli autovalori)
\begin{scope}[blue]
  \draw (-3.4,-3) -- (-3.4,0) node[anchor=south west] {$\lambda_1$} -- (-3.4,2);
  \draw (0.8,-3) -- (0.8,0) node[anchor=south east] {$\lambda_2$} -- (0.8,2);
\end{scope}
 \end{tikzpicture}
\end{center}
  \caption{Un grafico qualitativo di una possibile equazione secolare di una matrice con due autovalori}
\label{fig:eqsecolare}
\end{figure}
 
Ovviamente queste considerazioni valgono in $\R$, e hanno senso dal momento che
gli autovalori della matrice hermitiana devono essere reali. La stessa richiesta potrebbe addirittura
non avere senso per una matrice in forma di Hessenberg che, a priori, potrebbe avere autovalori complessi.
\subsection{Metodi di iterazione funzionale per il calcolo degli autovalori}
Questa conoscenza di $g$ ci porterebbe a pensare di utilizzare metodi di iterazione funzionale
per determinare gli autovalori della nostra matrice. \\
Se consideriamo il caso Hermitiano, infatti, potremmo applicare il metodo di \emph{bisezione}.
L'unica difficoltà in questo caso sta nel definire l'intervallo in cui sta una ed una sola radice
per poter cominciare l'iterazione. Notiamo però che presi gli autovalori di $A_{n-1}$ in modo
che $\lambda_i^{(n-1)} < \lambda_j^{(n-1)}
\iff i < j$ si ha che ogni autovalore di $A$ sta fra $\lambda_i$ ed un $\lambda_{i+1}$, ad eccezione degli
autovalori estremali. Anche in quel caso è facile trovare dei limiti su cui applicare la bisezione, considerando
la diseguaglianza di Hirsch: $|\lambda| \leq ||A||$ (dalla definizione di norma matriciale).
\begin{os}
 Tutto questo procedimento ci fornirebbe un metodo per calcolare gli autovalori di $A$ a patto di conoscere
 quelli di $A_{n-1}$, e quindi il problema non sembra (per ora) semplificato di molto. Prossimamente il teorema
 di Sturm ci fornirà uno strumento per completare queste considerazioni, arrivando ad un risultato più pratico.
\end{os}
Infine si potrebbe pensare di applicare anche altri metodi di iterazione funzionale noti, come ad esempio
il metodo delle tangenti; purtroppo quest'ultimo non ci può dare (in questo caso) nessuna garanzia di convergenza,
e quindi non sembra adatto allo scopo. In realtà viene usato nella pratica per ``affinare'' stime di autovalori
forniti con altri metodi. \\
\subsection{Il polinomio caratteristico delle matrici di Hessenberg}
Tutte le proprietà che siamo riusciti a trovare sulle matrici Hermitiane tridiagonali non valgono
purtroppo per le matrici di Hessenberg. Nonostante questo possiamo però mostrare un metodo
per valutare il polinomio caratteristico in un punto particolarmente vantaggioso dal punto
di vista computazionale\footnote{Non quanto quello trovato per le matrici Hermitiane tridiagonali, purtroppo}.
Cominciamo col fare alcune considerazioni; possiamo supporre che la nostra matrice sia nella forma
\[
 H = \left[ \begin{array}{cccc}
         \times & \cdots & \cdots  & \times \\
         \beta_{1}   & \ddots &   & \vdots \\
                  & \ddots & \ddots & \vdots \\
         & & \beta_{n-1} & \times
        \end{array} \right]
\]
con $\beta_i \neq 0$ per ogni $i$ (altrimenti sarebbe riducibile, e quindi potremmo ridurci a risolvere
dei sottoproblemi con delle Hessenberg irriducibili). \\
Fissato $z$, consideriamo il sistema lineare $(H - zI)x = \alpha e_1$. Se consideriamo $x$ e $\alpha$
come incognite e poniamo $x_n = 1$ ci accorgiamo che possiamo risolvere il sistema facilmente con
una sostituzione all'indietro partendo dal fondo, e determinare $x$ e $\alpha$ con complessità $O(n^2)$. \\
Applicando poi la regola di Cramer all'ultima componente di $x$ e chiamando $H'$ la matrice di Hessenberg
a cui è stata sostituita l'ultima colonna con il vettore $x$ otteniamo
\[
 1 = x_n = \frac{\deter{H'}}{\deter{H-zI}} = \frac{(-1)^{n+1}\alpha \prod_{i=1}^{n-1} \beta_i}{p(z)}
\]
e quindi $p(z) = (-1)^{n+1}\alpha \prod_{i=1}^{n-1} \beta_i$; osserviamo che in questa espressione
$\alpha$ è in realtà funzione di $z$ e quindi sarebbe più corretto scrivere
\[
p(z) = (-1)^{n+1}\alpha(z) \prod_{i=1}^{n-1} \beta_i
\]
Considerando che $\alpha$ può venir calcolata partendo da $z$ con complessità $O(n^2)$ abbiamo determinato
un metodo relativamente poco oneroso di calcolare il polinomio caratteristico di $H$ in un punto. \\
Possiamo quindi considerare ora la possibilità di applicare dei metodi di iterazione funzionale.
\begin{os}
 Per applicare, ad esempio, il metodo delle tangenti, avremmo bisogno di calcolare la derivata di $p(z)$.
 Possiamo fare anche questo con poco sforzo, a patto di calcolare la derivata di $a(z)$. \\
 Osserviamo che derivando la relazione di partenza si ottiene
 \[
  (H - zI)x'(z) = \alpha'(z)e_1 + x(z)
 \]
da cui si può ottenere $\alpha'(z)$ differenziando tutte le operazioni aritmetiche che portano ad ottenere
$x(z)$. Una volta effettuato questo si avrà
\[
 p'(z) = (-1)^{n+1}\alpha'(z) \prod_{i=1}^{n-1} \beta_i
\]
\end{os}
 
Possiamo osservare che i metodi di iterazione funzionale non sono particolarmente convenienti per determinare
gli autovalori, anche se si utilizzano di fatto per qualche richiesta ``specifica''.\\
Nel caso, ad esempio, di una matrice hermitiana tridiagonale, si può osservare che nel calcolo degli autovalori
estremali le condizioni di convergenza del metodo di Newton sono soddisfatte e quindi possiamo ottenere
la soluzione con poche operazioni aritmetiche osservando che sia $p$ che $p'$ si possono calcolare
con poco sforzo dalle loro relazioni ricorrenti a tre termini (viste nella Sezione~\ref{subsec:hermdiag}).
 
\begin{os}
 Consideriamo $p_n(x)$ polinomio caratteristico; possiamo osservare facilmente che se $x \to -\infty$ allora
 $p_n(x) \to \infty$. In generale, infatti, la parte principale del polinomio è $(-1)^{n} z^n$, che va all'infinito
 sia nel caso $n$ pari sia nel caso $n$ dispari.
\end{os}