From 34fe9a24c7eea75910830d6fb27cd356057e4518 Mon Sep 17 00:00:00 2001 From: Leonardo Robol Date: Sat, 21 Nov 2009 16:41:38 +0100 Subject: [PATCH] Lezione di Gemignani del 20 novembre --- capitolo4.tex | 102 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 101 insertions(+), 1 deletion(-) diff --git a/capitolo4.tex b/capitolo4.tex index 47462a6..3f4c06f 100644 --- a/capitolo4.tex +++ b/capitolo4.tex @@ -5,7 +5,7 @@ iterativi specifici per alcune classi di matrici particolarmente interessanti; q solitamente sistemi troppo grandi per essere risolti tramite metodi diretti e in cui la convergenza dei metodo classici (Jacobi e Gauss Seidel) è quasi assente. -\section{Il metodo del gradiente coniugato} +\section{Sitemi lineari con matrici definite positive} \subsection{Metodo del gradiente} Supponiamo di avere una matrice $A \in \mat{\R}{n}$ definita positiva ed un sistema lineare @@ -239,4 +239,104 @@ un costo complessivo del metodo del gradiente coniugato di $O(n^2\log(n))$. % di matrici, come ad esempio le matrici elementari e le matrici con nugoli di autovalori appiccicati. +\subsection{Matrici di Toeplitz tridiagonali simmetriche} +Vorremmo ora mostrare un'analisi di un caso paricolare, ovvero dei sistemi lineari con +una matrice di Toeplitz simmetrica tridiagonale. \\ +Questo è ad esempio il caso che discretizza il problema differenziale $\triangle u = f$ nel caso di +$u$ in una variabile reale. Le conclusione che otteremo su questo caso particolare ci permetteranno poi +di analizzare anche i casi in più variabili. + +Supponiamo ora di avere una qualsiasi matrice $T$ tridiagonale simmetrica di Toeplitz di dimensione $n$; chiamiamo $a$ gli +elementi sulla diagonale e $b$ quelli sulla sotto e sopradiagonale\footnote{in effetti queste due scelte +individuano completamente la matrice di cui stiamo parlando.}. \\ +Siamo interessati a studiare le proprietà spettrali di questa matrice per poter dare una stima +del suo condizionamento in norma 2, che come abbiamo visto influenza la convergenza del metodo del +gradiente coniugato. + +Osserviamo ceh se $\lambda$ è un autovalore per $T$ allora la matrice $T - \lambda I$ deve essere singolare +e in particolare deve esistere una soluzione non banale del sistema lineare +\[ + (T - \lambda I)x = 0 \iff \left[ \begin{array}{ccccc} + a - \lambda & b & & & \\ + b & a -\lambda & b & & \\ + & \ddots & \ddots & \ddots & \\ + & & b & a - \lambda & b \\ + & & & b & a + \end{array} \right] + \left[ \begin{array}{c} + x_1 \\ + x_2 \\ + \vdots \\ + x_{n-1} \\ + x_n + \end{array} \right] = +\left[ \begin{array}{c} + 0 \\ + 0 \\ + \vdots \\ + 0 \\ + 0 + \end{array} \right] +\] +Preso un qualsiasi $j$ compreso fra $2$ e $n-1$ possiamo scrivere la relazione sopra come +\[ + bx_{j-1} + (a- \lambda)x_j + bx_{j+1} = 0 +\] +Ponendo $x_0 = x_{n+1} = 0$ la relazione vale anche per $j = 1$ e $j=n$. Apparentemente non abbiamo +chiarito molto e trovare una soluzione esplicita sembra complicato. Possiamo però provare a porre +$x_j = x^{j}$, e vedere se riusciamo a trovare una soluzione particolare di questo tipo. Sostituendo +nelle relazioni sopra (per $j$ fra $2$ e $n-1$) si ottiene +\[ + bx^{j-1} + (a- \lambda)x^j + bx^{j+1} = 0 +\] +e ricordando che l'autovettore non può essere nullo e quindi $x^j \neq 0$ per ogni $j$, questa è soddisfatta +se e solo se +\[ + b + (a-\lambda)x + bx^2 = 0 \iff 1 + \frac{a - \lambda}{b} + x^2 = 0 +\] +Passiamo ora ad analizzare il caso che ci interessa, ovvero $a = 2$ e $b = 1$\footnote{ovvero la matrice che discretizza +il problema differenziale di Laplace.}; per il terzo teorema di Gerschgorin sappiamo che $|\lambda - 2| < 2$ e +quindi +\[ + \left| \frac{a - \lambda}{b} \right|< 2 +\] +Possiamo allora porre $\frac{a - \lambda}{b} = -2 \cos\theta$ per $\theta \in (0,\pi)$ e otteniamo l'equazione +\[ + 1 - 2x\cdot\cos \theta + x^2 = 0 +\] +Risolvendola otteniamo +\[ + x_{1,2} = \cos \theta \pm \sqrt{\cos^2\theta - 1} = \cos \theta \pm i \cdot \sin \theta = e^{\pm i \theta} +\] +Abbiamo quindi ottenuto due soluzioni che andrebbe bene per tutte le $j = 2, \ldots, n-1$ ma nessuna delle due +soddisfa le condizione per $j = 0$ e $j = n$. Osserviamo però che una qualsiasi combinazione lineare +$\alpha x_1 + \beta x_2$ soddisfa le condizione interne, e cerchiamo quindi di determinare $\alpha$ e $\beta$ +in modo che anche le condizioni al contorno siano soddisfatte. Si ottiene +\[ + x_0 = 0 = \alpha + \beta +\] +e quindi $\beta = -\alpha$; ponendo poi $j = n+1$ si ottiene +\[ + x_{n+1} = 0 = \alpha e^{i\cdot(n+1) \theta} - \alpha e^{-i \cdot (n+1) \theta} = \alpha( 2 i \sin ((n+1)\theta) ) +\] +e quindi $\theta_k = \frac{k\pi}{n+1}$ con $k = 1, \ldots, n$. Abbiamo trovato quindi $n$ autovettori distinti +e siamo in grado di calcolare i relativi autovalori ricordando che +\[ + \frac{a - \lambda_k}{b} = -2 \cos \theta_k = -2 \cos (\frac{k\pi}{n+1}) \Rightarrow \lambda_k = a + 2b\cos \theta_k +\] +Se costruiamo la matrice degli autovettori +\[ + U = \left[ \begin{array}{c|c|c|c} + \multirow{3}{*}{$x_1$} & \multirow{3}{*}{$x_2$} & \multirow{3}{*}{$\ldots$} & \multirow{3}{*}{$x_n$} \\ + & & & \\ + & & & + \end{array} \right] +\] +possiamo osservare che $\trasp UU = D$ con $D = \gamma I$. Abbiamo quindi che $U$ è quasi unitaria, in particolare +$\frac{1}{\gamma} U$ lo è. Inoltre possiamo osservare che gli elementi di $U$ non dipendono da $a$ e da $b$ e che +$u_{ij} = sin(\frac{ij\pi}{n+1}}) = u_{ji}$ e quindi $U$ è simmetrica. In altre parole abbiamo una decomposizione +spettrale $T = UDU$ dove tutta l'informazione sulla matrice è contenuta nella parte diagonale. + +Osserviamo infine che $D = \diag{a + 2b\cos(\theta_1) , \ldots, a + 2b \cos(\theta_n)}$ e quindi l'autovalore più +piccolo è $a + 2b\cos(\theta_1)$. -- 2.1.4