From 6ea5398101037926e1b0c653ffafb888e2f28e82 Mon Sep 17 00:00:00 2001 From: Leonardo Robol Date: Fri, 9 Oct 2009 12:06:32 +0200 Subject: [PATCH] Agginta la lezione del 9 ottobre sul metodo di Sturm per matrici tridiagonali hermitiane --- CalcoloScientifico.tex | 6 ++++ capitolo1.tex | 19 ++++++++---- capitolo2.tex | 78 ++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 98 insertions(+), 5 deletions(-) create mode 100644 capitolo2.tex diff --git a/CalcoloScientifico.tex b/CalcoloScientifico.tex index bd49397..665b5fe 100644 --- a/CalcoloScientifico.tex +++ b/CalcoloScientifico.tex @@ -16,6 +16,7 @@ \usepackage{graphicx} \usepackage{subfigure} \usepackage{multirow} +\usepackage{enumerate} %% %% Ci piace, a causa del carattere usato (pxfonts) @@ -199,6 +200,11 @@ %% \mainmatter +%% Introduzione e calcolo del polinomio caratteristico \include{capitolo1} +%% Metodi per il calcolo di autovalori di matrici Hermitiante +%% tridiagonali +\include{capitolo2} + \end{document} diff --git a/capitolo1.tex b/capitolo1.tex index 5da2183..fb6140c 100644 --- a/capitolo1.tex +++ b/capitolo1.tex @@ -1,7 +1,10 @@ -\chapter{Calcolo degli autovalori} -In questo capitolo ci occuperemo di metodi per il calcolo degli autovalori di una matrice data. Questo -problema, come vedremo, ha molti risvolti pratici ed applicazioni, e risulterà essere di interesse anche -nel calcolo delle soluzioni di sistemi lineari. +\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 @@ -374,7 +377,7 @@ e quindi anche $p_{k-2}(\xi)$ deve essere nullo. Ripetendo questa considerazione 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} +\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 @@ -647,3 +650,9 @@ Nel caso, ad esempio, di una matrice hermitiana tridiagonale, si può osservare 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} diff --git a/capitolo2.tex b/capitolo2.tex new file mode 100644 index 0000000..f4f399f --- /dev/null +++ b/capitolo2.tex @@ -0,0 +1,78 @@ +\chapter{Il calcolo degli autovalori} + +In questo capitolo ci occuperemo di presentare i metodi principalmente usati nel calcolo +effettivo degli autovalori di matrici Hermitiane tridiagonali e in forma di Hessenberg. + +\section{Il metodo di Sturm} +Introdurremo ora un metodo efficiente per il calcolo di singoli autovalori di una matrice +hermitiana in forma tridiagonale. Per tutta la sezione tratteremo il caso di una matrice +reale per semplicità, ma il caso complesso è risolubile in modo analogo. + +Abbiamo visto nella Sezione~\ref{sec:eqsecolare} un metodo efficiente per valutare il polinomio +caratteristico di una matrice di questo tipo con costo $O(n)$. Possiamo affinare la nostra osservazione +notando che anche la valutazione di tutti i polinomi $p_k$ in un punto $x$ fissato continua +ad avere un costo $O(n)$. \\ +Consideriamo, data una matrice $T_n$ in forma tridiagonale hermitiana, la seguente funzione +\[ +\begin{array}{cccl} + f: & \R & \longto & \{ 0 , \ldots , n \} \\ + & x & \longmapsto & \sharp \{ \ \textrm{cambi di segno nel vettore} \ (p_0(x) , \ldots , p_n(x)) \ \} +\end{array} +\] +Perché $f$ sia ben definita conveniamo che se $p_j(x) = 0$ allora il suo segno è lo stesso di $p_{j-1}(x)$. +Questa è una buona definizione perché $p_0(x) = 1$ e quindi non è mai $0$. +\begin{os} + Dalla definizione di $f$ si deduce che se il suo valore di cambia in un punto, allora in quel punto ci deve + essere uno zero di (almeno) uno dei polinomi $p_j(x)$. +\end{os} +Osserviamo cosa succede quando un polinomio ``interno'', ovvero un $p_j$ con $j \in 1 \ldots n-1$ ha uno +zero in $\bar x$. +Innanzitutto sappiamo da quanto visto nel capitolo precedente che $p_{j-1}(x) \neq 0 \neq p_{j+1}(x)$; è +possibile però affinare questa affermazione osservando meglio la relazione ricorrente a tre termini: +\[ + p_{j+1}(x) = (\alpha_{j+1} - x) p_j(x) - \beta_j^2 p_{j-1}(x) +\] +Se $p_j(x) = 0$ si ottiene che $p_{j-1}(x) \cdot p_{j+1}(x) < 0$, e quindi anche in un intorno di $\bar x$. +Ricordando le definizione di $f$ si osserva che il segno di $p_j(x)$ è quindi indifferente ai fini del numero +di cambiamenti di segno. In particolare $f$ non cambia segno in $\bar x$. +Evidentemente $p_0(x)$ non può cambiare segno, quindi ci rimane da verificare cosa succede quando cambia segno +$p_n(x)$. \\ +Ricordiamo alcune particolarità dei polinomi $p_n$ viste precedentemente +\begin{enumerate}[(i)] + \item Ogni $p_j$ ha limite a $-\infty$ uguale a $+\infty$; + \item Gli zeri di $p_{j-1}$ separano gli zeri di $p_j$, nel senso visto alla fine del precedente capitolo + (Sezione~\ref{sec:eqsecolare}); + \item Tutti gli zeri di un polinomio di una matrice hermitiana tridiagonale sono semplici; +\end{enumerate} +Osserviamo quindi che per ogni radice di $p_n$ si ha che il segno della sua derivata e quello di $p_{n-1}$ sono +opposti. La condizione di semplicità sugli zeri ci assicura che la derivata sarà infatti diversa da $0$ in +$\bar x$ e quindi $p_n'(\bar x) p_{n-1}(\bar x) < 0$. In particolare la costanza locale del segno della derivata +intorno allo $0$ ci assicura anche la constanza di quello di $p_{j-1}$ e quindi il \emph{cambio di valore di $f$}. +In sintesi $f$ agisce come una sorta di ``contatore di zeri''. Dato infatti un qualsiasi intervallo $[a,b]$ si verifica, +usando le considerazioni precedenti che +\[ + f(b) - f(a) = \sharp \{ \ \text{zeri del polinomio caratteristico in } [a,b) \ \} +\] + +Possiamo dunque applicare questa considerazione per applicare il metodo di bisezione per calcolare +uno specifico autovalore di $T_n$. Queste proprietà di $f$ ci permettono di calcolare infatti singolarmente +l'$i$-esimo autovalore di $T_n$ (ordinati con l'ordinamento di $\R$) senza bisogno di calcoare tutti gli altri. +Ricordando la diseguaglianza di Hirsch ($||\lambda|| \leq ||T_n||$) e supponendo di aver fissato $i$ possiamo +applicare il seguente procedimento. + +Cominciamo col calcolare $f(0)$; il suo valore ci dirà quanti autovalori ci sono prima dello $0$, e quindi +nell'intervallo $[-||T_n||, 0)$. Se il nostro autovalore sta lì (ovvero $i \leq f(0)$) allora calcoliamo +$f(-\frac{||T_n||}{2})$ e ripetiamo il procedimento; in caso contrario procediamo analogamente con $f(\frac{||T_n||}{2})$. \\ +Iterando un numero sufficiente di volte questo procedimento otterremo alla fine il valore desiderato. + +Osserviamo che il procedimento può essere applicatoa ad una qualsiasi matrice hermitiana, a patto +di portarla in forma tridiagonale (che è sempre possibile tramite matrici unitarie). +Ricordando le stime dei costi computazionali fatte in precedenza ci rendiamo conto che il costo principale è +quello della riduzione ($O(n^3)$) rispetto a quello del calcolo dell'autovalore ($O(n^2)$). +Se si volessero calcolare tutti gli autovalori il costo rimarrebbe ancora dell'ordine di $n^3$. Nonostante questo +esistono metodi (che vedremo in seguito) che permettono di calcolare tutti gli autovalori con una complessità di +$O(n^2)$ e che quindi saranno più interessanti per il calcolo dello spettro completo della matrice. \\ +Il metodo di Sturm, comunque, trova delle applicazioni anche in questo ultimo caso nell'ambito del calcolo parallelo, +dove altri algoritmi non possono essere implementati. Si può osservare invece che, una volta ottenuta la fattorizzazione, +non sia difficile implementare il metodo di Sturm dividendo fra i vari processori gli autovalori da calcolare. + -- 2.1.4