From cf4404b07baa21da31794397c74b145d2737d775 Mon Sep 17 00:00:00 2001 From: Leonardo Robol Date: Wed, 14 Oct 2009 21:55:56 +0200 Subject: [PATCH] Aggiunta l'ultima parte della lezione del 14, anche se mancano delle precisazioni. --- capitolo1.tex | 3 +-- capitolo2.tex | 12 ++++++++++++ 2 files changed, 13 insertions(+), 2 deletions(-) diff --git a/capitolo1.tex b/capitolo1.tex index 78ba212..6f75f8d 100644 --- a/capitolo1.tex +++ b/capitolo1.tex @@ -571,7 +571,6 @@ di $g$ corrisponde un autovalore di $A_{n-1}$ e che gli autovalori della matrice da quelli di $g$, in quanto la derivata di $g$ è sempre negativa (e quindi la funzione monotona). \begin{figure}[ht] \begin{center} - %% \includegraphics[width=\textwidth]{equazionesecolare.pdf} \begin{tikzpicture} %% Disegnamo gli assi \draw[very thin,->] (-6,0) -- (5,0) node[anchor=north] {$\xi$}; @@ -588,7 +587,7 @@ da quelli di $g$, in quanto la derivata di $g$ è sempre negativa (e quindi la f \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); - %% Asintoti + %% Asintoti (che corrispondono agli autovalori) \draw[blue] (-3.4,-3) -- (-3.4,0) node[anchor=south west] {$\lambda_1$} -- (-3.4,2); \draw[blue] (0.8,-3) -- (0.8,0) node[anchor=south east] {$\lambda_2$} -- (0.8,2); \end{tikzpicture} diff --git a/capitolo2.tex b/capitolo2.tex index d5f2244..bc2b293 100644 --- a/capitolo2.tex +++ b/capitolo2.tex @@ -194,4 +194,16 @@ sono gli autovalori di $A$ e quindi abbiamo provato che il metodo converge. \end{os} \subsection{Il costo computazionale} +Vorremmo ora valutare il costo computazionale di questo metodo. Consideriamo dapprima il caso di una matrice +generale. Sappiamo che il costo di una fattorizzazione $QR$ è $O(n^3)$ e sperimentalmente si ottiene che il +numero di passi per avere convergenza cresce linearmente con la dimensione. Questo ci permette di concludere +che in un caso totalmente generale il costo computazionale del metodo QR è $O(n^4)$. +Facciamo ora qualche supposizione sulla matrice. Prendiamo ad esempio una matrice tridiagonale hermitiana. +In questo caso ci ricordiamo che il costo del calcolo della fattorizzazione QR (almeno della prima) è $O(n)$. +Possiamo osservare che la matrice ottenuta dopo il primo passo è ancora tridiagonale hermitiana, e quindi +le considerazioni fatte sul primo passo valgono anche per i seguenti. In particolare il costo del metodo +è $O(n^2)$. + +Analogamente per le matrici di Hessenberg (anche se non lo mostriamo ora) il costo è di $O(n^3)$ perché +il calcolo della scomposizione QR è $O(n^2)$. -- 2.1.4