From 78091ec31008b3223b57121f1a77738eaf67ce9e Mon Sep 17 00:00:00 2001 From: Leonardo Robol Date: Thu, 15 Oct 2009 17:09:13 +0200 Subject: [PATCH] Cambio caratteri e correzioni ortografia --- CalcoloScientifico.tex | 4 +++- capitolo1.tex | 21 ++++++++++++--------- capitolo2.tex | 24 +++++++++++++++--------- 3 files changed, 30 insertions(+), 19 deletions(-) diff --git a/CalcoloScientifico.tex b/CalcoloScientifico.tex index b42680f..cfc468e 100644 --- a/CalcoloScientifico.tex +++ b/CalcoloScientifico.tex @@ -21,12 +21,14 @@ \usepackage{tikz} \usepackage{color} \usepackage[a4paper]{geometry} +\usepackage[T1]{fontenc} +\usepackage{pxfonts} %% %% Ci piace, a causa del carattere usato (pxfonts) %% avere un'interlinea piuttosto abbondante %% -\linespread{1.1} +\linespread{1.2} %% %% Qui di seguito si trovano le definizioni diff --git a/capitolo1.tex b/capitolo1.tex index e2e9379..28936eb 100644 --- a/capitolo1.tex +++ b/capitolo1.tex @@ -262,24 +262,27 @@ Questo sarà il passaggio che poi ci permetterà di mostrare per induzione che s qualsiasi matrice in forma di Hessenberg superiore. \\ Data la seguente matrice generica $A$ \[ - A = \left[ \begin{array}{c|c} - a_{11} & \herm{w} \\ + A = \left[ \begin{array}{c|cc} + a_{11} & \multicolumn{2}{|c}{\herm{w}} \\ \hline - v & \hat{A} + \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|c} - 1 & \herm{0} \\ + P = \left[ \begin{array}{c|cc} + 1 & \multicolumn{2}{c}{\herm{0}} \\ \hline - 0 & \hat P + \multirow{2}{*}{$0$} & \sblocke{ \quad \hat P \quad}{2} \\ + & & \end{array} \right] \qquad - PA\herm{P} = \left[ \begin{array}{c|c} - a_{11} & \herm{w} \herm{\hat{P}} \\ + PA\herm{P} = \left[ \begin{array}{c|cc} + a_{11} & \multicolumn{2}{|c}{\herm{w} \herm{\hat{P}}} \\ \hline - \hat Pv & \hat P \hat A \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 diff --git a/capitolo2.tex b/capitolo2.tex index bc2b293..6236ad0 100644 --- a/capitolo2.tex +++ b/capitolo2.tex @@ -47,7 +47,7 @@ Ricordiamo alcune particolarità dei polinomi $p_n$ viste precedentemente 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$}. +intorno allo $0$ ci assicura anche la costanza 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 \[ @@ -56,7 +56,7 @@ usando le considerazioni precedenti che 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. +l'$i$-esimo autovalore di $T_n$ (ordinati con l'ordinamento di $\R$) senza bisogno di calcolare tutti gli altri. Ricordando la diseguaglianza di Hirsch ($||\lambda|| \leq ||T_n||$) e supponendo di aver fissato $i$ possiamo applicare il seguente procedimento. @@ -65,7 +65,7 @@ nell'intervallo $[-||T_n||, 0)$. Se il nostro autovalore sta lì (ovvero $i \leq $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 +Osserviamo che il procedimento può essere applicato a 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)$). @@ -77,8 +77,11 @@ dove altri algoritmi non possono essere implementati. Si può osservare invece c non sia difficile implementare il metodo di Sturm dividendo fra i vari processori gli autovalori da calcolare. \section{Il metodo QR} -In questa sezione esporremo il metodo QR per il calcolo degli autovalori, che è il metodo più gettonato -al giorno d'oggi. +In questa sezione esporremo il metodo QR per il calcolo degli autovalori, che è il metodo più utilizzato +nelle moderne applicazioni del calcolo degli autovalori. Si basa sulla fattorizzazione QR già vista nel corso +di Analisi Numerica per la risoluzione di sistemi lineari. Questa può venire realizzata tramite matrici +di Householder. Cominceremo ricordando alcuni risultati riguardo la fattorizzazione, per poi esporre ed +analizzare il metodo e le sue implementazioni. \subsection{La fattorizzazione QR} \'E noto che ogni matrice $A \in \mat{\C}{n}$ si può fattorizzare nel seguente modo @@ -114,7 +117,7 @@ la successione definita nel seguente modo Cominceremo ad analizzare il metodo QR facendo delle supposizioni piuttosto restrittive, che poi allenteremo in seguito. Cominciamo col supporre che gli autovalori della matrice $A$ siano tutti distinti e ordinabili per modulo in modo strettamente crescente, ovvero $|\lambda_1| < \ldots < |\lambda_n|$. Questo in -particolare implica che la matrice $A$ è diagonlizzabile e quindi esiste una $X$ invertibile tale che +particolare implica che la matrice $A$ è diagonalizzabile e quindi esiste una $X$ invertibile tale che $A = XDX^{-1}$. Supponiamo ora che $X^{-1}$ ammetta fattorizzazione $ X^{-1} = LU$\footnote{dove supponiamo che $L$ sia triangolare inferiore con gli elementi delle diagonale uguali a $1$ e $U$ triangolare superiore}. \begin{pr} \label{pr:metpot:ak} @@ -130,6 +133,7 @@ che $L$ sia triangolare inferiore con gli elementi delle diagonale uguali a $1$ \[ \begin{array}{ll} \displaystyle A^{k+1} = \prod_{i=1}^{k+1} Q_0 R_0 = Q_0 (\prod_{i=1}^{k} R_0 Q_0) R_0 = Q_0 (\prod_{i=1}^{k} A_1) R_0 = \\ + \displaystyle = Q_0 (\prod_{i=1}^{k} Q_1 R_1) R_0 = Q_0 \prod_{i=1}^{k} Q_i \prod_{i=1}^{k} R_{k-i+1} R_0 \end{array} \] @@ -161,7 +165,7 @@ tende ad una matrice diagonale per $k$ che tende all'infinito. Più precisamente Da questo si ottiene che $P_k \to I$ e anche $T_k \to I$\footnote{questo non sarebbe vero a priori, in quanto la scomposizione QR è sempre definita a meno di una matrice di fase. Richiedere però che $P_k$ abbia elementi positivi ci permette sia di definire univocamente la scomposizione desiderata sia di avere l'esistenza del limite.} -Confontando l'equazione~\ref{eq:metpot:1} e la Proposizione~\ref{pr:metpot:ak} si ottengono due fattorizzazioni +Confrontando l'equazione~\ref{eq:metpot:1} e la Proposizione~\ref{pr:metpot:ak} si ottengono due fattorizzazioni QR della matrice $A^k$. \[ A^k = QP_k T_k R D^k U = Q_0 \ldots Q_k R_k \ldots R_0 @@ -174,7 +178,9 @@ si ottengono le due relazioni R_{k} \ldots R_0 = \herm{S_k}T_k R D^k U \end{array} \right. \] -Possiamo riscrivere ora $Q_k$ ed $R_k$ in modo da riuscire ad utilizzare queste relazioni +Possiamo riscrivere ora $Q_k$ ed $R_k$ in modo da riuscire ad utilizzare queste relazioni\footnote{Si può +osservare quanto i passaggi di questa dimostrazione siano la cosa meno intuitiva pensabile (o quasi). Presumibilmente +questa è risultato di anni di affinamento e di ``pulizia'' } \[ \left\{ \begin{array}{l} Q_k = \herm{(Q_0 \ldots Q_{k-1})}(Q_0 \ldots Q_k) = \herm{S_{k-1}}\herm{P_{k-1}}\herm{Q}Q P_k S_k = @@ -188,7 +194,7 @@ $S_{k-1} A^k \herm{S_{k-1}} = R D R^{-1}$. Possiamo quindi osservare che gli ele sono gli stessi di $D$ (grazie al fatto che $R$ è triangolare superiore). In particolare gli elementi diagonali sono gli autovalori di $A$ e quindi abbiamo provato che il metodo converge. \begin{os} - In realtà non è rilevante conoscere esplicitamente $S_k$ perché siamo interessati solo a conscere gli elementi + In realtà non è rilevante conoscere esplicitamente $S_k$ perché siamo interessati solo a conoscere gli elementi sulla diagonale di $RDR^{-1}$. Avendo che gli elementi di $S_k$ sono di modulo $1$ gli elementi diagonali vengono moltiplicati per un numero complesso e per il suo coniugato, lasciandoli invariati. \end{os} -- 2.1.4