Calcolo numerico/Localizzazione degli autovalori

Cerchi di Gerschgorin

Definizione

Sia $A\in \mathrm {Mat} _{n\times n,\mathbb {C} }$ e definiamo $i$-esimo cerchio di Gerschgorin per righe l'insieme

$K_{i}=\{z\in \mathbb {C} \,t.c.\,|z-A_{ii}|\leq \sum _{j\neq i}|A_{ij}|\}$

(sono cerchi centrati nell'entrata diagonale $i$-esima e con raggio minore della somma delle entrate fuori diagonale della stessa riga). Analogamente si definiscono i cerchi di Gerschgorin per colonna:

$\{z\in \mathbb {C} \,t.c.\,|z-A_{jj}|\leq \sum _{i\neq j}|A_{ij}|\}$

I tre teoremi di localizzazione

Teorema 3.1

Lo spettro $\sigma _{A}$ della matrice $A$, cioè l'insieme dei suoi autovalori, è contenuto nell'unione dei cerchi di Gerschgorin, cioè è contenuta in

$\bigcup _{i=1}^{n}K_{i}$

Teorema 3.2

Sia $M_{1}=\bigcup _{i=i_{1},\dots ,i_{k}}K_{i}$ (unione di $k$ cerchi) e $M_{2}=\bigcup _{i=i_{k+1},\dots ,i_{n}}K_{i}$ (unione di $n-k$ cerchi) dove $M_{1}\cap M_{2}=\emptyset$. Allora $k$ autovalori appartengono a $M_{1}$ e $n-k$ autovalori appartengono a $M_{2}$.

Esempio 3.1

Consideriamo $A\in M_{4,\mathbb {R} }$, allora se c'è un autovalore complesso anche il suo coniugato è un autovalore di $A$, e dev'essere contenuto nello stesso cerchio $K_{i}$. Supponiamo che i cerchi di Gerschgorin relativi ad $A$ sono tali che $K_{1}$ è disgiunto da $K_{2}\cup K_{3}\cup K_{4}$. Allora, siccome per il teorema 2 nel cerchio $K_{1}$ c'è solo un autovalore, si può dire che la matrice ha almeno due autovalori reali. Infatti l'autovalore contenuto in $C_{1}$ è necessariamente reale, perché $C_{1}$ non contiene il coniugato di questo autovalore. L'unione degli altri tre cerchi contiene tre autovalori, allora almeno uno di questi sarà sicuramente reale.

Teorema 3.3

Sia $A$ una matrice irriducibile. Se l'autovalore $\lambda _{A}$ appartiene alla frontiera dell'unione di tutti i cerchi, allora esso appartiene alla frontiera di ogni cerchio.

Equivalentemente, il terzo teorema può essere riscritto nel seguente modo: supponiamo di avere $\lambda \in \partial \bigcup _{i}K_{i}$, e supponiamo di avere un indice $j$ tale che $\lambda \not \in \partial K_{j}$, allora $\lambda$ non è autovalore.

Esempio 3.2

Consideriamo la matrice con 2 sulla diagonale principale e con -1 sulla sopradiagonale e sottodiagonale. Alla prima e all'ultima riga corrispondono cerchi di raggio 1 e centro 2. Invece i cerchi corrispondenti alle righe dalla seconda alla penultima sono di raggio 2 e centro 2.

Allora per il teorema 3, $A$ è non singolare (0 non è autovalore), infatti 0 non appartiene alla frontiera dei cerchi di raggio 1.

Dimostrazione del primo teorema di localizzazione

Sia $A{\boldsymbol {x}}=\lambda {\boldsymbol {x}}$, ${\boldsymbol {x}}\neq 0$. Consideriamo la $i$-esima equazione:

$\sum _{j=1}^{n}A_{ij}x_{j}=\lambda x_{i}$

e separando le entrate $A_{ii}$ otteniamo:

$(\lambda -A_{ii})x_{i}=\sum _{j\neq i}A_{ij}x_{j}\quad {\hbox{relazione }}\ast$

Consideriamo la norma infinito di ${\boldsymbol {x}}$, allora esiste $p$ tale che $\vert {\boldsymbol {x}}\vert ^{\infty }=x_{p}$.

Allora riscrivo la relazione $\ast$ come:

$|(\lambda -A_{pp})x_{p}|=|\sum _{j\neq p}A_{pj}x_{j}|$

$|x_{j}|\leq |x_{p}|\longrightarrow \quad |\lambda -a_{pp}|*|x_{p}|\leq \sum _{j\neq p}A_{pj}x_{p}|$

ed elidendo $x_{p}$:

$|\lambda -A_{pp}|\leq \sum _{j\neq p}|A_{pj}|$

allora $\lambda$ appartiene al cerchio $K_{p}$. $p$ non è noto, allora $\lambda$ appartiene all'unione di tutti i cerchi.

cvd

Osservazione 3.1

Supponiamo di avere una matrice $A$ diagonalmente dominante in senso stretto, oppure che sia diagonalmente dominante in senso debole e irriducibile. Allora $A$ è non singolare. Se inoltre $A$ è hermitiana e gli $A_{ii}$ sono reali positivi, allora $A$ è definita positiva.

Dim. Siccome $A$ è diagonalmente dominante

$|A_{ii}|>\sum _{j\neq i}|A_{ij}|$

quindi la distanza dell'autovalore dall'origine è maggiore del raggio, e i cerchi sono lontani dall'origine. Quindi 0 non appartiene alla loro frontiera.

Nel caso di dominanza diagonale debole e irriducibilità, abbiamo almeno un cerchio che tocca l'origine, perché esiste $i$ tale che

$|A_{i}|=r_{i}$

allora $0\in \partial K_{i}$. Per l'irriducibilità esiste un altro indice $s$ tale che $A_{ss}>r_{s}$, allora $0\not \in \partial K_{s}$. Allora per il terzo teorema 0 non può essere autovalore.

Se gli elementi diagonali della matrice sono positivi, i cerchi sono tutti nel semipiano positivo, gli autovalori sono positivi e la matrice è definita positiva.

cvd