From e9c253fe2a507d17b672d29d8263d3f931eaa6e8 Mon Sep 17 00:00:00 2001 From: Leonardo Robol Date: Wed, 21 Oct 2009 22:58:49 +0200 Subject: [PATCH] Aggiunta lezione del 21 ottobre e corretto l'uso di stackrel{}{} per i doppi indici in sommatorie e produttorie con substack{} che sembra la cosa giusta da usare --- CalcoloScientifico.tex | 6 +-- capitolo1.tex | 4 +- capitolo2.tex | 107 ++++++++++++++++++++++++++++++++++++++++++++++++- 3 files changed, 111 insertions(+), 6 deletions(-) diff --git a/CalcoloScientifico.tex b/CalcoloScientifico.tex index c929e02..9af0bd0 100644 --- a/CalcoloScientifico.tex +++ b/CalcoloScientifico.tex @@ -67,7 +67,7 @@ %% Condizionamento e spettro %% \newcommand{\cond}[1]{\mathcal{K}(#1)} -\newcommand{\spe}[1]{Sp(#1)} +\newcommand{\spe}[1]{\mathrm{Sp}(#1)} \newcommand{\rs}[1]{\rho(#1)} @@ -106,8 +106,8 @@ %% %% Determinante -%% -\newcommand{\deter}[1]{det(#1)} +% +\newcommand{\deter}[1]{\mathrm{det}(#1)} %% diff --git a/capitolo1.tex b/capitolo1.tex index 28936eb..57e0d29 100644 --- a/capitolo1.tex +++ b/capitolo1.tex @@ -543,7 +543,7 @@ E quindi possiamo scrivere \] 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_{\stackrel{i=1}{j\neq i}}^{n}(\lambda_i^{(n-1)}-z) + 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 @@ -553,7 +553,7 @@ e per continuità possiamo estenderlo a tutto $\C$, ottenendo 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_{\stackrel{i=1}{i\neq j}}^{n} (\lambda_i^{(n-1)} - z) \neq 0 + 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 diff --git a/capitolo2.tex b/capitolo2.tex index 1f5c5d6..80d24ff 100644 --- a/capitolo2.tex +++ b/capitolo2.tex @@ -358,4 +358,109 @@ si abbia A_{k+1} = \herm{Z} A_k Z \] ed è possibile dimostrare che questa iterazione produce una matrice simile a meno di una matrice di fase reale -rispetto a quella presentata in precedenza. \ No newline at end of file +rispetto a quella presentata in precedenza. + +\section{Divide et Impera} +\subsection{L'idea} +Introdurremo ora un altro metodo, piuttosto recente, per il calcolo di tutti gli autovalori della matrice. +Questo è stato introdotto nel 1980 da Cuppen. Il metodo permette il calcolo di autovalori solo per matrici +tridiagonali hermitiane e l'osservazione che ne sta alla base è che una matrice tridiagonale è ``quasi'' +diagonale a blocchi, più precisamente se $H$ è la nostra matrice +\[ + H = \left[ \begin{array}{cc|cc} + \sblocko{T_1}{2} & & \\ + & & & \\ \hline + & & \sblocke{T_2}{2} \\ + & & & \\ + \end{array} \right] ++ \left[ \begin{array}{cc|cc} + & & & \\ + & \beta_{n-1} & & \\ \hline + & & \beta_{n-1} & \\ + & & & + \end{array} \right] +\] +Ovvero è una diagonale a blocchi più una correzione di rango 2. A ben vedere, però, si può fare anche di meglio. +Se sostituiamo in $T_1$ il valore $\alpha_{\frac{n}{2}}$ con $\hat \alpha_{\frac{n}{2}} = \alpha_{\frac{n}{2}} - \beta_{n-1}$ +e in $T_2$ il valore $\alpha_{\frac{n}{2} + 1}$ con $\hat \alpha_{\frac{n}{2} + 1} = \alpha_{\frac n 2 + 1} - \beta_{n-1}$, otteniamo +una matrice a blocchi tridiagonali più un correzione di rango $1$: +\[ + H = \left[ \begin{array}{cc|cc} + \sblocko{\hat T_1}{2} & & \\ + & & & \\ \hline + & & \sblocke{\hat T_2}{2} \\ + & & & \\ + \end{array} \right] ++ \left[ \begin{array}{cc|cc} + & & & \\ + & \beta_{n-1} & \beta_{n-1}& \\ \hline + & \beta_{n-1} & \beta_{n-1} & \\ + & & & + \end{array} \right] +\] +Supponiamo ora di conoscere gli autovalori di $\hat T_1$ e di $\hat T_2$, ed in particolare le matrici +unitarie $Q_1$ e $Q_2$ che ci permettono di diagonalizzarle, ovvero +\[ + T_1 = Q_1 D_1 \herm Q_1 \qquad + T_2 = Q_2 D_2 \herm Q_2 +\] +con $D_1$ e $D_2$ le matrici con gli autovalori sulla diagonale e $0$ altrove. + +Tutto questo può funzionare se +riusciamo a mostrare che siamo veramente in grado di calcolare facilmente gli autovalori della matrice a blocchi +con la correzione. + +Se consideriamo ora la matrice $D$ così formata +\[ + \hat D = \left[ \begin{array}{cc|cc} + \sblocko{D_1}{2} & & \\ + & & & \\ \hline + & & \sblocke{D_2}{2} \\ + & & & + \end{array} \right] +\] +e calcoliamo $B = \herm Q A Q$ otteniamo +\[ + B = \herm Q A Q = \hat D + \beta_{\frac{n}{2}}z\herm z +\] +con $z = \left[ \begin{array}{c} q_1 \\ q_2 \end{array}\right]$ dove $q_i$ è l'ultima colonna di $\herm Q_i$. + +\subsection{La ricerca degli autovalori} +Abbiamo quindi ricondotto il problema a calcolare gli autovalori di una matrice $D + w\herm w$ dove $D$ +è diagonale e $w$ è un vettore qualsiasi. Calcolando il polinomio caratteristico di $B$ ed assumendo +che $\lambda \neq \hat d_i$ otteniamo +\[ + p(\lambda) = \deter{\lambda I - B} = \deter{ \lambda I - D }\cdot \deter{I + \theta(\lambda I - D)^{-1} z\herm z} +\] +Osserviamo che stiamo assumendo che $\lambda I - D$ sia invertibile, e quindi questa formula per il calcolo +del polinomio caratteristico vale solo per $\lambda \in \C \setminus (\spe{D_1} \cup \spe{D_2})$. Sapendo che $p$ +è continuo possiamo però concludere che vale per tutto $\C$. \\ +Notiamo inoltre che $( I + \theta(\lambda I - D)^{-1}z\herm z)$ è una matrice elementare e quindi ha determinante\footnote{% +Ricordiamo che in genearale una matrice elementare $I - \sigma u \herm v$ ha determinante $1 - \sigma \herm v u$} +$1 - \theta (\lambda I - D)^{-1} \herm zz$; sviluppando ulteriormente si ottiene +\[ + p(\lambda) = \prod_{j=1}^{n} (\lambda - \hat d_j) ( 1 + \theta (\lambda I - D)^{-1} \herm zz ) + = \prod_{j=1}^{n} (\lambda - \hat d_j) ( 1 + \theta \sum_{k=1}^{n} \frac{z_k^2}{\lambda - \hat d_k} ) +\] +ed estendendo per continuità a tutto $\C$ si ottiene infine +\[ + p(\lambda) = \prod_{j=1}^n (\lambda - \hat d_j) + \theta\sum_{k=1}^n z_k \prod_{\substack{s=1 \\ s\neq k}}^n (\lambda - \hat d_s) +\] +che è una sorta di equazione secolare come quella che si era ottenuta partendo dalle relazioni ricorrenti a tre +termini nella Sezione~\ref{sec:eqsecolare}. + +Siamo ora costretti a fare delle assunzioni sulla struttura di $z$ e di $\hat D$. In realtà ci renderemo conto +in seguito che queste non sono restrittive perché nei casi in cui non saranno verificate ci troveremo con un +problema semplificato, che potremo riportare a questo caso qua\footnote{Penso, perché in realtà non mi è ancora +molto chiaro come si dovrebbe fare}. \\ +Assumiamo dunque che +\begin{itemize} + \item $z_j \neq 0$ per ogni $j = 1 \ldots n$; + \item $\hat d_k \neq \hat d_j$ per ogni $k \neq j$, ovvero che tutti gli autovalori siano distinti; +\end{itemize} +A questo punto dalle relazioni precedenti ricaviamo che +\[ + p(\lambda) = 0 \iff 1 + \theta \sum_{j=1}^n \frac{z_j^2}{\lambda - \hat d_j} = 0 +\] +e quindi gli autovalori delle matrici di ordine $\frac{n}{2}$ separano quelli della matrice grande, e si +può applicare (ad esempio) il metodo di bisezione. -- 2.1.4