Norme di matrici
Prerequisiti di algebra lineare
Definizioni
Desideriamo estendere la nozione di norma, che abbiamo introdotto per i vettori, al caso delle matrici. Poiché l’idea di lunghezza di una matrice non è immediatamente intuitiva, affronteremo il problema in modo formale.
Per iniziare, esamineremo alcune proprietà interessanti delle norme vettoriali, che ci aiuteranno a comprendere e definire le norme per le matrici.
Cos’è la norma di una matrice?
Consideriamo una matrice \boldsymbol{A}\in \Bbb{K}^{m \times n} e un vettore colonna \boldsymbol{x}\in \Bbb{K}^n. Il prodotto \boldsymbol{A}\boldsymbol{x} risulta essere un vettore colonna di dimensione m. Ora, introduciamo due norme vettoriali, che indichiamo con \|\cdot\|_a e \|\cdot\|_b, rispettivamente definite negli spazi \Bbb{K}^m e \Bbb{K}^n. L’obiettivo è trovare la più piccola costante K (ammesso che esista) tale che:
\|\boldsymbol{A}\boldsymbol{x}\|_a \leq K \|\boldsymbol{x}\|_b, \qquad \forall \, \boldsymbol{x}\in \Bbb{K}^n \tag{1}
Per \boldsymbol{x}= \mathbf{0}, la disuguaglianza precedente è soddisfatta banalmente per qualsiasi valore di K. Tuttavia, possiamo restringere la nostra attenzione ai vettori \boldsymbol{x}\neq \mathbf{0}. Per questi, si può scrivere:
\|\boldsymbol{A}\boldsymbol{x}\|_a = \frac{\|\boldsymbol{A}\boldsymbol{x}\|_a}{\|\boldsymbol{x}\|_b} \|\boldsymbol{x}\|_b \leq \left[\sup_{\boldsymbol{y}\neq \mathbf{0}} \frac{\|\boldsymbol{A}\boldsymbol{y}\|_a}{\|\boldsymbol{y}\|_b} \right] \|\boldsymbol{x}\|_b
Questa espressione ci permette di identificare K come l’estremo superiore del rapporto \frac{\|\boldsymbol{A}\boldsymbol{y}\|_a}{\|\boldsymbol{y}\|_b}, dove \boldsymbol{y} è un vettore non nullo.
Nel seguito dimostreremo che, nelle condizioni considerate, tale estremo superiore esiste ed è finito.
Osserviamo che questa quantità dipende unicamente dalla matrice \boldsymbol{A} e dalla scelta delle norme vettoriali \|\cdot\|_a e \|\cdot\|_b, come è ragionevole aspettarsi.
Pertanto, questa quantità può essere vista come una caratteristica della matrice \boldsymbol{A} e si comporta come una norma, nel senso che soddisfa le tre proprietà fondamentali richieste per la definizione assiomatica di norma.
Teorema 1 (Norma Indotta) Per ogni matrice \boldsymbol{A}\in \Bbb{K}^{m \times n}, vale la seguente relazione:
\sup_{\boldsymbol{y}\neq \mathbf{0}} \frac{\|\boldsymbol{A}\boldsymbol{y}\|_a}{\|\boldsymbol{y}\|_b} = \max_{\|\boldsymbol{y}\|_b = 1} \|\boldsymbol{A}\boldsymbol{y}\|_a.
Dimostrazione. Partiamo dalla seguente espressione:
\frac{\|\boldsymbol{A}\boldsymbol{y}\|_a}{\|\boldsymbol{y}\|_b} = \|\boldsymbol{A}\left( \frac{\boldsymbol{y}}{\|\boldsymbol{y}\|_b} \right)\|_a = \|\boldsymbol{A}\boldsymbol{z}\|_a, \quad \text{con} \quad \boldsymbol{z}= \frac{\boldsymbol{y}}{\|\boldsymbol{y}\|_b}.
Dato che \|\boldsymbol{z}\|_b = 1, possiamo riscrivere il supremum come:
\sup_{\boldsymbol{y}\neq \mathbf{0}} \frac{\|\boldsymbol{A}\boldsymbol{y}\|_a}{\|\boldsymbol{y}\|_b} = \sup_{\|\boldsymbol{z}\|_b = 1} \|\boldsymbol{A}\boldsymbol{z}\|_a.
Per dimostrare che questo supremum esiste ed è finito, procediamo in modo analogo alla dimostrazione dell’equivalenza delle norme. Introduciamo l’insieme
S = \{\boldsymbol{z}\in \Bbb{K}^n : \|\boldsymbol{z}\|_b = 1\}.
Essendo S un insieme compatto in \Bbb{K}^n e la funzione \|\boldsymbol{A}\boldsymbol{z}\|_a continua (essendo una composizione di funzioni continue), tale funzione assume un massimo su S. Sia \boldsymbol{z}_M \in S il vettore che massimizza \|\boldsymbol{A}\boldsymbol{z}\|_a, ossia:
\|\boldsymbol{A}\boldsymbol{z}_M\|_a = \max_{\|\boldsymbol{z}\|_b = 1} \|\boldsymbol{A}\boldsymbol{z}\|_a.
Poiché il supremum rappresenta il maggiorante più piccolo possibile, e non può essere strettamente maggiore del massimo trovato, concludiamo che:
\max_{\|\boldsymbol{z}\|_b = 1} \|\boldsymbol{A}\boldsymbol{z}\|_a = \|\boldsymbol{A}\boldsymbol{z}_M\|_a \leq \sup_{\|\boldsymbol{z}\|_b = 1} \|\boldsymbol{A}\boldsymbol{z}\|_a \leq \max_{\|\boldsymbol{z}\|_b = 1} \|\boldsymbol{A}\boldsymbol{z}\|_a.
Questo dimostra che il supremum coincide con il massimo.
Teorema 2 (Norma di Matrice) La quantità definita come
\|\boldsymbol{A}\| = \sup_{\boldsymbol{y}\neq \mathbf{0}} \frac{\|\boldsymbol{A}\boldsymbol{y}\|_a}{\|\boldsymbol{y}\|_b}
soddisfa le tre proprietà assiomatiche delle norme. Per questo motivo, possiamo usare il simbolo \|\boldsymbol{A}\| per indicare la norma della matrice \boldsymbol{A}.
Dimostrazione. Dimostriamo che la funzione che associa a ogni matrice \boldsymbol{A}\in \Bbb{K}^{m \times n} il valore \|\boldsymbol{A}\| soddisfa le tre proprietà fondamentali delle norme.
- Non negatività:
Per definizione, \|\boldsymbol{A}\| è non negativa. Verifichiamo ora che \|\boldsymbol{A}\| = 0 se e solo se \boldsymbol{A}= \mathbf{0} (la matrice nulla).
Se \boldsymbol{A}= \mathbf{0}, allora \boldsymbol{A}\boldsymbol{x}= \mathbf{0} per ogni vettore \boldsymbol{x}\in \Bbb{K}^n. Questo implica:
\frac{\|\boldsymbol{A}\boldsymbol{x}\|_a}{\|\boldsymbol{x}\|_b} = 0 \quad \forall \boldsymbol{x}\neq \mathbf{0},
da cui segue che \|\boldsymbol{A}\| = 0.
Viceversa, dimostriamo che \|\boldsymbol{A}\| = 0 implica \boldsymbol{A}= \mathbf{0}. Ragioniamo per contrapposizione: supponiamo che \boldsymbol{A}\neq \mathbf{0} e mostriamo che in questo caso \|\boldsymbol{A}\| > 0. Sia \boldsymbol{e}_i l’i-esimo vettore della base canonica. Se \boldsymbol{A}\neq \mathbf{0}, allora esiste almeno un indice i per cui \boldsymbol{A}\boldsymbol{e}_i \neq \mathbf{0}. Pertanto:
\frac{\|\boldsymbol{A}\boldsymbol{e}_i\|_a}{\|\boldsymbol{e}_i\|_b} > 0,
il che implica \|\boldsymbol{A}\| > 0.
- Subadditività (Disuguaglianza triangolare):
Siano \boldsymbol{A}, \boldsymbol{B}\in \Bbb{K}^{m \times n}. Dobbiamo verificare che:
\|\boldsymbol{A}+ \boldsymbol{B}\| \leq \|\boldsymbol{A}\| + \|\boldsymbol{B}\|.
Per ogni \boldsymbol{x}\in \Bbb{K}^n, vale:
\frac{\|(\boldsymbol{A}+ \boldsymbol{B}) \boldsymbol{x}\|_a}{\|\boldsymbol{x}\|_b} \leq \frac{\|\boldsymbol{A}\boldsymbol{x}\|_a}{\|\boldsymbol{x}\|_b} + \frac{\|\boldsymbol{B}\boldsymbol{x}\|_a}{\|\boldsymbol{x}\|_b}.
Prendendo il supremum su tutti i vettori \boldsymbol{x}\neq \mathbf{0}, otteniamo:
\sup_{\boldsymbol{y}\neq \mathbf{0}} \frac{\|(\boldsymbol{A}+ \boldsymbol{B}) \boldsymbol{y}\|_a}{\|\boldsymbol{y}\|_b} \leq \sup_{\boldsymbol{y}\neq \mathbf{0}} \frac{\|\boldsymbol{A}\boldsymbol{y}\|_a}{\|\boldsymbol{y}\|_b} + \sup_{\boldsymbol{y}\neq \mathbf{0}} \frac{\|\boldsymbol{B}\boldsymbol{y}\|_a}{\|\boldsymbol{y}\|_b},
ovvero:
\|\boldsymbol{A}+ \boldsymbol{B}\| \leq \|\boldsymbol{A}\| + \|\boldsymbol{B}\|.
- Omogeneità:
Sia \lambda \in \Bbb{K} uno scalare arbitrario. Verifichiamo che:
\|\lambda \boldsymbol{A}\| = |\lambda| \|\boldsymbol{A}\|.
Abbiamo:
\|\lambda \boldsymbol{A}\| = \sup_{\boldsymbol{y}\neq \mathbf{0}} \frac{\|\lambda \boldsymbol{A}\boldsymbol{y}\|_a}{\|\boldsymbol{y}\|_b}.
Poiché \|\lambda \boldsymbol{A}\boldsymbol{y}\|_a = |\lambda| \|\boldsymbol{A}\boldsymbol{y}\|_a, otteniamo:
\|\lambda \boldsymbol{A}\| = |\lambda| \sup_{\boldsymbol{y}\neq \mathbf{0}} \frac{\|\boldsymbol{A}\boldsymbol{y}\|_a}{\|\boldsymbol{y}\|_b} = |\lambda| \|\boldsymbol{A}\|.
Definizione assiomatica di norma
L’ultima osservazione suggerisce di introdurre la seguente definizione per le norme di matrice.
Definizione 1 Siano \boldsymbol{A}, \boldsymbol{B}\in \Bbb{K}^{m \times n} e \alpha uno scalare. La norma di una matrice deve soddisfare le seguenti proprietà:
Positività: \left|\left|\boldsymbol{A}\right|\right| \geq 0 e \left|\left|\boldsymbol{A}\right|\right| = 0 se e solo se \boldsymbol{A}= \boldsymbol{0}. Questo significa che la norma è sempre un numero non negativo e che è nulla solo nel caso in cui la matrice sia la matrice nulla.
Omogeneità rispetto a scalari: \left|\left|\alpha \boldsymbol{A}\right|\right| = \left\lvert\alpha\right\rvert \left|\left|\boldsymbol{A}\right|\right|. La norma di una matrice moltiplicata per uno scalare è pari al valore assoluto dello scalare moltiplicato per la norma della matrice.
Disuguaglianza triangolare: \left|\left|\boldsymbol{A}+ \boldsymbol{B}\right|\right| \leq \left|\left|\boldsymbol{A}\right|\right| + \left|\left|\boldsymbol{B}\right|\right|. La norma della somma di due matrici non supera la somma delle norme delle singole matrici.
Submoltiplicatività (se m = n): \left|\left|\boldsymbol{A}\boldsymbol{B}\right|\right| \leq \left|\left|\boldsymbol{A}\right|\right| \left|\left|\boldsymbol{B}\right|\right|. Nel caso di matrici quadrate, la norma del prodotto di due matrici è minore o uguale al prodotto delle loro norme.
Norme compatibili
Nel contesto delle matrici e dei vettori, è spesso utile considerare come le norme delle matrici e dei vettori interagiscono tra loro. In particolare, una norma matriciale può essere definita in modo da essere compatibile con le norme dei vettori sui quali agisce la matrice. Questo concetto di compatibilità garantisce che la norma di un vettore trasformato da una matrice non cresca in maniera incontrollata rispetto alla norma del vettore originale.
Definizione di norme compatibili
Definizione 2 Una norma matriciale \left|\left|\,\cdot\,\right|\right| si dice compatibile con due norme vettoriali \left|\left|\,\cdot\,\right|\right|_a e \left|\left|\,\cdot\,\right|\right|_b se, per ogni matrice \boldsymbol{M}\in \Bbb{K}^{m \times n} e per ogni vettore \boldsymbol{x}\in \Bbb{K}^n, si verifica la seguente disuguaglianza:
\left|\left|\boldsymbol{M}\boldsymbol{x}\right|\right|_a \leq \left|\left|\boldsymbol{M}\right|\right| \, \left|\left|\boldsymbol{x}\right|\right|_b.
Questa proprietà esprime il fatto che l’operazione di moltiplicare un vettore per una matrice non “amplifica” troppo la norma del vettore. In altre parole, la norma della matrice funge da limite superiore per l’effetto di \boldsymbol{M} sulla norma del vettore \boldsymbol{x}, mantenendo una coerenza tra le norme usate per la matrice e quelle per i vettori.
Un caso rilevante per l’analisi degli algoritmi che verranno discussi in seguito si presenta quando le norme \left|\left|,\cdot,\right|\right|_a e \left|\left|,\cdot,\right|\right|_b appartengono allo stesso tipo. In particolare, ciò avviene quando consideriamo le norme \left|\left|,\cdot,\right|\right|_1, \left|\left|,\cdot,\right|\right|2 e \left|\left|,\cdot,\right|\right|{\infty}.
Le corrispondenti norme applicate alle matrici vengono denotate con gli stessi simboli.
Teorema 3 La norma matriciale \left|\left|\,\cdot\,\right|\right|_{\infty}:\Bbb{K}^{m\times n}\mapsto\Bbb{R} definita da
\sup_{\boldsymbol{x}\neq\boldsymbol{0}} \dfrac{\left|\left|\boldsymbol{A}\boldsymbol{x}\right|\right|_{\infty}}{\left|\left|\boldsymbol{x}\right|\right|_{\infty}}, \tag{3}
vale
\left|\left|\boldsymbol{A}\right|\right|_{\infty} = \max_{i=1}^{m}\left(\sum_{j=1}^{n} \left\lvert A_{i,j}\right\rvert\right).
Dimostrazione. Osserviamo che se \boldsymbol{A}\in\Bbb{K}^{m\times n} vale
\begin{aligned} \left|\left|\boldsymbol{A}\boldsymbol{x}\right|\right|_{\infty} & = \max_{i=1}^{m} \left\lvert\sum_{j=1}^{n}A_{i,j}x_j\right\rvert \\ &\leq \max_{i=1}^{m} \sum_{j=1}^{n} \left\lvert A_{i,j}x_j\right\rvert\\ &\leq \max_{i=1}^{m} \left(\max_{j=n}^{m}\left\lvert x_j\right\rvert\right) \sum_{j=1}^{n} \left\lvert A_{i,j}\right\rvert, \\ &\leq \left|\left|\boldsymbol{x}\right|\right|_{\infty} \max_{i=1}^{m} \sum_{j=1}^{n} \left\lvert A_{i,j}\right\rvert, \end{aligned}
quindi
\dfrac{\left|\left|\boldsymbol{A}\boldsymbol{x}\right|\right|_{\infty}}{\left|\left|\boldsymbol{x}\right|\right|_{\infty}} \leq \max_{i=1}^{n} \sum_{j=1}^{m} \left\lvert A_{i,j}\right\rvert,
sia ora k la riga per cui
\max_{i=1}^{m} \sum_{j=1}^{n} \left\lvert A_{i,j}\right\rvert = \sum_{j=1}^{n} \left\lvert A_{k,j}\right\rvert,
e sia \boldsymbol{x} il vettore definito da
x_j = \begin{cases} +1 & A_{k,j}>0 \\ -1 & A_{k,j} \leq 0 \end{cases},
allora avremo \left|\left|\boldsymbol{x}\right|\right|_{\infty}=1 e
\begin{aligned} (\boldsymbol{A}\boldsymbol{x})_{k} &= \sum_{j=1}^{n} A_{k,j}x_j \\ &= \sum_{j=1}^{n} \left\lvert A_{k,j}\right\rvert \\ &= \max_{i=1}^{m} \sum_{j=1}^{n} \left\lvert A_{i,j}\right\rvert, \\ &\Rightarrow \\ \left|\left|\boldsymbol{A}\boldsymbol{x}\right|\right|_{\infty} & \geq \max_{i=1}^{m} \sum_{j=1}^{n} \left\lvert A_{i,j}\right\rvert, \end{aligned}
e questo implica la Equazione 3.
In modo analogo si dimostra il seguente teorema:
Definizione 3 (Norma 1) \sup_{\boldsymbol{x}\neq\boldsymbol{0}} \dfrac{\left|\left|\boldsymbol{A}\boldsymbol{x}\right|\right|_1}{\left|\left|\boldsymbol{x}\right|\right|_1},
vale
\left|\left|\boldsymbol{A}\right|\right|_1 = \max_{j=1}^{m}\left(\sum_{i=1}^{m} \left\lvert A_{i,j}\right\rvert\right).
Definizione 4 (Norma-2) La norma \left|\left|\,\cdot\,\right|\right|_2:\Bbb{K}^{m\times n}\mapsto\Bbb{R} è definita come segue
\left|\left|\boldsymbol{A}\right|\right|_2 = \sup_{\boldsymbol{x}\neq\boldsymbol{0}}\dfrac{\left|\left|\boldsymbol{A}\boldsymbol{x}\right|\right|_2}{\left|\left|\boldsymbol{x}\right|\right|_2}
Teorema 4 (Norma-2 caratterizzazione) Vale la seguente uguaglianza
\left|\left|\boldsymbol{A}\right|\right|_2 = \sqrt{\varrho(\boldsymbol{A}^H\boldsymbol{A})}.
Dimostrazione. Osserviamo che
\left|\left|\boldsymbol{A}\right|\right|_{2}^{2} = \sup_{\boldsymbol{x}\neq\boldsymbol{0}} \dfrac{\left|\left|\boldsymbol{A}\boldsymbol{x}\right|\right|_{2}^{2}} {\left|\left|\boldsymbol{x}\right|\right|_{2}^{2}} = \sup_{\boldsymbol{x}\neq\boldsymbol{0}} \dfrac{\boldsymbol{x}^H\boldsymbol{A}^H\boldsymbol{A}\boldsymbol{x}}{\boldsymbol{x}^H\boldsymbol{x}} \tag{4}
La matrice \boldsymbol{A}^H\boldsymbol{A} è una matrice hermitiana e quindi per il teorema di diagonalizzazione di matrici Hermitiane esiste una matrice unitaria \boldsymbol{U} che la diagonalizza
\boldsymbol{U}^H\boldsymbol{A}^H\boldsymbol{A}\boldsymbol{U}= \begin{pmatrix} \lambda_1 & & &\\ & \lambda_2 & &\\ && \ddots & \\ & & &\lambda_n \end{pmatrix}, \tag{5}
dove \lambda_1, \lambda_2, \ldots,\lambda_n sono gli autovalori della matrice \boldsymbol{A}^H\boldsymbol{A}. Dalla Equazione 4 segue
\begin{aligned} \left|\left|\boldsymbol{A}\right|\right|_{2}^{2} &= \sup_{\boldsymbol{x}\neq\boldsymbol{0}} \dfrac{\boldsymbol{x}^H\boldsymbol{U}\boldsymbol{U}^H\boldsymbol{A}^H\boldsymbol{A}\boldsymbol{U}\boldsymbol{U}^H\boldsymbol{x}}{\boldsymbol{x}^H\boldsymbol{U}\boldsymbol{U}^H\boldsymbol{x}} \\ &= \sup_{\boldsymbol{y}\neq\boldsymbol{0}}\dfrac{\boldsymbol{y}\boldsymbol{U}^H\boldsymbol{A}^H\boldsymbol{A}\boldsymbol{U}\boldsymbol{y}}{\boldsymbol{y}^H\boldsymbol{y}} \end{aligned}
dalla Equazione 5
\begin{aligned} \left|\left|\boldsymbol{A}\right|\right|_{2}^{2} &= \sup_{\boldsymbol{y}\neq\boldsymbol{0}} \dfrac{\sum_{i=1}{n}\lambda_i y_i^2} {\sum_{i=1}{n}y_i^2} \\ &= \max\{\lambda_1,\lambda_2,\ldots,\lambda_n\} \\ &=\varrho(\boldsymbol{A}^H\boldsymbol{A}) \end{aligned}