viewgit/index.php:465 Only variables should be passed by reference [2048]
viewgit/index.php:466 Non-static method GeSHi::get_language_name_from_extension() should not be called statically [2048]
\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 esposti. 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. 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} \] 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.}. 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). 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. Cominciamo ad analizzare un caso relativamente semplice, ovvero quello dove $A$ è una matrice diagonalizzabile, per cui dimostreremo un risultato detto 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$. \[ y = -(A - \eta I)^{-1}( \delta A y ) \] Consideriamo dunque una norma matriciale indotta tale che data una matrice $D$ diagonale si abbia requisito, ad esempio; questo tipo di norma è detta \emph{assoluta}.} ed effettuiamo le seguenti maggiorazioni \[ \] che si verifica solo se (ricordando che essendo $y$ un autovettore $y \neq 0$ e quindi $\|y\| \neq 0$) \[ \] 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 \emph{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$, e 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. \\ 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} finito di passi, a meno dell'errore di macchina e algoritmico. 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}\footnote{A parte il caso in cui la matrice ha ordine $n$ con $n \leq 4$, che però non è un caso interessante per l'algebra lineare numerica.}. \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}$ e $\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$ \[ \] \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 + \herm{u}Fy & = \lambda \herm{u} w + \xi \herm{u} y \\ \herm{u}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 \[ \] che è la tesi. \end{proof} %% 1 ottobre 2009 In questa sezione vorremmo introdurre delle operazioni preliminari da compiere prima di applicare un qualsiasi metodo per il calcolo effettivo degli autovalori. Vedremo in seguito come non convenga, generalmente, applicare i metodi per il calcolo degli autovalori a matrici generali. \\ I metodi che solitamente vengono usati accettano infatti in input solo matrici particolari, più precisamente \begin{description} $| 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} \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. \\ 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 equazione è 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\}$ \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}$. (I - \sigma u \herm{u})^2 = I -2\sigma u \herm u + \sigma^2 \herm u u u \herm u = I$. 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}} \\ \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}} \\ \multirow{2}{*}{$0$} & \sblocke{ \quad \hat P \quad}{2} \\ & & \end{array} \right] \qquad a_{11} & \multicolumn{2}{|c}{\herm{w} \herm{\hat{P}}} \\ \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. Il costo computazionale di ogni passo del procedimento sopra descritto è dato da \begin{enumerate} hermitiana); \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)$. 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 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 \\ 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 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. 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. Consideriamo una matrice $A \in \mat{\C}{n}$ in forma tridiagonale hermitiana. In tutta la sezione indicheremo con \begin{description} che si tratta ancora di una matrice hermitiana tridiagonale per ogni $k$. \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)$. 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$. 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] \sblocko{A_{n-1}}{2} & \\ & & \beta_{n-1}\\ \hline & \beta_{n-1} & \alpha_{n} \\ \end{array} \right] \sblocko{\trasp{Q_{n-1}}}{2} & \\ & & \\ \hline & & 1 \end{array} \right] = \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 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] A & 0 \\ \hline 0 & \Gamma \end{array} \right] I & \times \\ \hline 0 & I \end{array} \right] \] \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] = \sblocko{E_{n-1}}{2} & \multirow{2}{*}{$w$} \\ & & \\ \hline \multicolumn{2}{c|}{\trasp{w}} & \alpha_n -z \end{array} \right] \] 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 \[ \] e per continuità possiamo estenderlo a tutto $\C$, ottenendo \[ \] \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 \[ \] sono note, anche se esistono due teorie: una sostiene che l'appellativo derivi dall'usanza di una matrice, mentre l'altra sostiene che 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} \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. Questa conoscenza di $g$ ci porterebbe a pensare di utilizzare metodi di iterazione funzionale per determinare gli autovalori della nostra matrice. \\ 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. \\ 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 \[ \] 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}