From af4abb0d8d378af0b7eb0d35401630443a9d27c5 Mon Sep 17 00:00:00 2001
From: Leonardo Robol <leo@robol.it>
Date: Fri, 20 Nov 2009 16:33:15 +0100
Subject: [PATCH] Lezione di Gemignani del 18 novembre

---
 CalcoloScientifico.tex |  1 +
 capitolo4.tex          | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 50 insertions(+)

diff --git a/CalcoloScientifico.tex b/CalcoloScientifico.tex
index 8ab4b89..000b3a8 100644
--- a/CalcoloScientifico.tex
+++ b/CalcoloScientifico.tex
@@ -125,6 +125,7 @@
 \newcommand{\svd}{\texttt{SVD}}
 \newcommand{\tsvd}{\texttt{TSVD}}
 \newcommand{\qr}{\texttt{QR}}
+\newcommand{\fft}{\textttt{FFT}}
 \newcommand{\matlab}{\texttt{Matlab}}
 \newcommand{\lapack}{\texttt{Lapack}}
 \newcommand{\Span}[1]{<(#1)>}
diff --git a/capitolo4.tex b/capitolo4.tex
index 4151df3..4e24b15 100644
--- a/capitolo4.tex
+++ b/capitolo4.tex
@@ -191,3 +191,52 @@ Sottolineamo solo alcune problematiche che potrebbero nascere usando questo appr
  fare accontentandosi di approssimazioni dell'inversa piuttosto vaghe, ma poco invasive (come ad esempio una matrice diagonale); 
 \end{enumerate}
 
+\subsection{Le matrici di Toeplitz}
+Molte delle matrici con cui avremo a che fare risolvendo sistemi lineari in pratica sono matrici di Toeplitz. 
+\begin{de}
+ Sia $A$ una matrice $n \times n$; $A$ si dice di \emph{Toeplitz} se le sue diagonali sono costanti, ovvero se per
+ ogni $i,j$ e per ogni $k \in \Z$ per cui ha senso
+ \[
+  a_{ij} = a_{i+k,j+k}
+ \]
+\end{de}
+Queste matrici hanno una struttura molto particolare, ed esiste un modo piuttosto comodo di effettuare il
+prodotto matrice per vettore. Consideriamo il caso seguente con una matrice di Toeplitz triangolare inferiore
+\[
+ \left[ \begin{array}{cccc}
+         t_0 &  &  &  \\
+         t_1 & \ddots &  &  \\
+          \vdots & \ddots & \ddots &  \\
+          t_n & \cdots & t_1 & t_0 \\
+        \end{array} \right] 
+ \left[ \begin{array}{c}
+         p_0 \\
+         p_1 \\
+         \vdots  \\
+         p_n
+        \end{array} \right] 
+= \left[ \begin{array}{l}
+          t_0p_0 \\
+          t_1p_0 + t_0p_1 \\
+          \vdots\\ 
+          t_np_0 + t_{n-1}p_1 + \ldots + t_0p_n
+         \end{array} \right] 
+\]
+Si osserva che il vettore che si ottiene ha i coefficienti che sono quelli del prodotto di questi due polinomi
+\[
+ \left\{ \begin{array}{lll}
+          t(x) &=& t_0 + t_1 z + \ldots + t_n z^n \\
+          p(x) &=& p_0 + p_1 z + \ldots + p_n z^n 
+         \end{array} \right.
+\]
+Possiamo quindi calcolare il prodotto matrice vettore nello stesso modo in cui calcoleremmo i coefficienti del
+polinomio prodotto, ovvero con la trasformata discreta di Fourier. 
+
+Avremo quindi un costo delle moltiplicazione $O(n\log(n))$\footnote{utilizzando la \fft.} e quindi
+un costo complessivo del metodo del gradiente coniugato di $O(n^2\log(n)).
+
+% TODO: Inserire gli esempi delle applicazioni del metodo del gradiente a qualche caso particolare
+% di matrici, come ad esempio le matrici elementari e le matrici con nugoli di autovalori appiccicati. 
+
+
+
-- 
2.1.4