25 Preliminari: raggio spettrale, serie di Neumann, M-matrici
Questa sezione raccoglie i risultati di teoria delle matrici non negative che servono per studiare la convergenza dei metodi iterativi, e che vengono ripresi nell’appendice Appendice B. Non vengono dimostrati: sono risultati classici, e per ciascuno è indicato dove trovarne la dimostrazione.
25.1 Raggio spettrale
Corollario 25.1 (Formula di Gelfand) Sia \bm{A} una matrice quadrata e \|\cdot\| una qualunque norma matriciale indotta. Allora
\varrho(\bm{A}) = \lim_{k\mapsto\infty}\|\bm{A}^k\|^{1/k}.
In particolare \varrho(\bm{A}) \leq \|\bm{A}\| per ogni norma indotta.
Dimostrazione in [2], capitolo sulle norme matriciali e il raggio spettrale.
25.2 Serie di Neumann
Lemma 25.1 (Convergenza della serie di Neumann) Sia \bm{B} una matrice quadrata. Le seguenti affermazioni sono equivalenti:
- la serie \sum_{k=0}^{\infty}\bm{B}^k converge;
- \lim_{k\mapsto\infty}\bm{B}^k=\bm{0};
- \varrho(\bm{B})<1.
Se valgono, allora \bm{I}-\bm{B} è non singolare e
(\bm{I}-\bm{B})^{-1}=\sum_{k=0}^{\infty}\bm{B}^k.
Se inoltre \bm{B}\geq\bm{0}, tutti i termini della serie sono non negativi e quindi (\bm{I}-\bm{B})^{-1}\geq\bm{I}\geq\bm{0}.
L’equivalenza fra 2. e 3. è ripresa più avanti in questo capitolo come Teorema 26.1; per il resto si veda [3], oppure [2].
25.3 M-matrici
Definizione 25.1 (M-matrice) Una matrice \bm{A}\in\mathbb{R}^{n\times n} è una M-matrice se
- ha elementi fuori diagonale non positivi, a_{ij}\leq 0 per i\neq j;
- è non singolare e la sua inversa è non negativa, \bm{A}^{-1}\geq\bm{0}.
Le M-matrici sono la classe naturale in cui i metodi iterativi per sistemi lineari si comportano bene: la non negatività dell’inversa è ciò che rende monotoni i confronti fra raggi spettrali usati nel seguito. Per una trattazione sistematica si veda [1].
Lemma 25.2 (Diagonale di una M-matrice) Se \bm{A} è una M-matrice allora i suoi elementi diagonali sono strettamente positivi, a_{ii}>0 per ogni i=1,\ldots,n.
Dimostrazione in [1], capitolo sulle M-matrici.
Lemma 25.3 (Caratterizzazione per traslazione) Sia \bm{A} con elementi fuori diagonale non positivi. Allora \bm{A} è una M-matrice se e solo se esistono \sigma>0 e \bm{B}\geq\bm{0} tali che
\bm{A}=\sigma\bm{I}-\bm{B}, \qquad \varrho(\bm{B})<\sigma.
Si può sempre prendere \sigma\geq\max_i a_{ii}.
Dimostrazione in [3], capitolo sulle matrici non negative, oppure in [1].
Teorema 25.1 (Criterio di splitting per le M-matrici) Sia \bm{A}=\bm{D}-\bm{B} con \bm{D} diagonale a elementi strettamente positivi e \bm{B}\geq\bm{0} con diagonale nulla. Posto \bm{H}=\bm{D}^{-1}\bm{B}, se
\varrho(\bm{H})<1
allora \bm{A} è una M-matrice e
\bm{A}^{-1}=\left(\sum_{k=0}^{\infty}\bm{H}^k\right)\bm{D}^{-1}\geq\bm{0}.
La formula per \bm{A}^{-1} segue da Lemma 25.1 applicato a \bm{H}; per il resto si veda [3] o [1].
In sintesi
- Il raggio spettrale \rho(\bm{B}) governa il comportamento asintotico di \bm{B}^{k}; la formula di Gelfand lo lega alle norme: \rho(\bm{B})=\lim_k\|\bm{B}^k\|^{1/k}.
- La serie di Neumann \sum_k \bm{B}^k converge a (\bm{I}-\bm{B})^{-1} se e solo se \rho(\bm{B})<1: è il criterio di convergenza di tutti i metodi iterativi del capitolo.
- Una M-matrice ha elementi extradiagonali \leq 0 e inversa non negativa; ha diagonale positiva ed è caratterizzabile per traslazione, \bm{A}=s\bm{I}-\bm{B} con \bm{B}\geq\bm{0} e s>\rho(\bm{B}).
- Il criterio di splitting per le M-matrici garantisce la convergenza senza calcolare autovalori: è lo strumento operativo del capitolo successivo.