Numero di condizionamento di una matrice

Numero di condizionamento §

Abbiamo già visto che il numero di condizionamento di una matrice invertibile è definito come:

$$K_{p(A)}:=\Vert A^{-1}{\Vert }_p\Vert A{\Vert }_p$$

dove abbiamo messo in evidenza che in generale dipende dalla norma scelta. Mostriamo alcune proprietà:

1. $K(A)\ge 1$

$$1=\Vert Id{\Vert }_p=\Vert A^{-1}A{\Vert }_p\le \Vert A^{-1}{\Vert }_p\Vert A{\Vert }_p=K_p(A)$$

2. $K(A)=K(A^{-1})$
3. $\forall z\in \mathbb{C}$ $z\ne 0$ si ha $K(zA)=K(A)$
4. Se $A$ è unitaria, $K(A)=1$.

Definiamo il numero di condizionamento di una matrice singolare $S$ come infinito: $K(S)=\infty$.

Quando usiamo la norma $p=2$, possiamo caratterizzare ulteriormente il numero di condizionamento $K_2(A)$, sfruttando la relazione:

$$\Vert A{\Vert }_2=\sqrt{\rho (A^{T}A)}=$$

In generale vale, per ogni norma indotta da una vettoriale, vale

$$\rho (A)\le \Vert A\Vert$$

Nel caso della norma due, l’ugualgianza vale per matrici normali. In questo caso, siccome gli autovalori dell’inversa sono l’inverso degli autovalori, quindi per i moduli:

$$K_2(A)=\frac{|{\lambda }_{max}|}{|{\lambda }_{min}|}$$

Un’altra caratterizzazione del numero di condizionamento, è vederlo come l’inverso di una distanza tra le matrici singolari. Definendo una distanza:

$$dis{t}_{p(A)}:=\left\{\frac{\Vert \delta A{\Vert }_p}{\Vert A{\Vert }_p:}A+\delta A\text{ eˋ singolare }\right\}$$

vale:

$$dis{t}_{p(A)}=\frac{1}{K_p(A)}$$

Da questa definizione segue come corollario: Corollario Se $\Vert A^{-1}\Vert \Vert \delta A\Vert <1$ Allora $A+\delta A$ non è singolare. Siccome vale $K_p(A)dis{t}_p(A)=1$, e $dis{t}_p(A)$ è un minimo sull’insieme delle matrici, quando $A+\delta A$ è singolare si ha:

$$1\le \Vert \delta A{\Vert }_p\Vert A^{-1}\Vert$$

quindi se vale il complementare, la matrice deve essere non singolare.

Sensibilità alle perturbazioni §

A causa degli errori di arrotondamento un metodo numerico impiegato per la risoluzione di un sistema lineare non fornirà una soluzione esatta del sistema di partenza, ma soltanto una soluzione approssimata che verifica un sistema perturbato. In altre parole, un metodo numerico genera una soluzione (esatta) $x+\delta x$ del sistema perturbato

$$(A+\delta A)(x+\delta x)=b+\delta b$$

vogliamo stimare $\delta x$ in funzione delle perturbazioni $\delta A$ e $\delta b$. E’ facile capire che entrerà in gioco il numero di condizionamento della matrice.

Teorema Siano $A\in {\mathbb{C}}^{n\times n}$ una matrice non singolare e $\delta A\in {\mathbb{C}}^{n\times n}$ tale che $A+\delta A$ rimane non singolare. Allora se $x\in {\mathbb{C}}^n$ è soluzione di $Ax=b$, con $b\ne 0$, e $\delta x$ tale che $x+\delta x$ risolve il sistema perturbato, si ha che:

$$\frac{\Vert \delta x\Vert }{\Vert x\Vert }\le \frac{K(A)}{1-K(A)\Vert \delta A\Vert /\Vert A\Vert }\left(\frac{\Vert \delta b\Vert }{\Vert b\Vert }+\frac{\Vert \delta A\Vert }{\Vert A\Vert }\right)$$

Dim Dal corollario precedente segue che $\Vert A^{-1}\delta A\Vert <1$, siccome per ipotesi $A+\delta A$ è non singolare. Quindi anche la matrice $Id+A^{-1}\delta A$ è non singolare, e valgono i bound sulla sua inversa:

$$\Vert (I+A^{-1}\delta A{)}^{-1}\Vert \le \frac{1}{1-\Vert A^{-1}\delta A\Vert }\le \frac{1}{1-\Vert A^{-1}\Vert \Vert \delta A\Vert }$$

ricavando $\delta x$ dal sistema si ha:

$$\delta x=(A+\delta A{)}^{-1}(\delta b-\delta Ax)$$

Riscrivendo il primo fattore:

$$(A+\delta A{)}^{-1}=(I+\delta A^{-1}A)A^{-1}$$

e passando alle norme, ottengo:

$$\Vert \delta x\Vert \le \frac{\Vert A^{-1}\Vert }{1-\Vert A^{-1}\Vert \Vert \delta A\Vert }(\Vert \delta b\Vert +\Vert \delta A\Vert \Vert x\Vert )$$

Corollario Segue un corolllario utile. Assumendo di essere nelle stessi ipotesi del teorema, vale:

$$\frac{1}{K(A)}\frac{\Vert \delta b\Vert }{\Vert b\Vert }\le \frac{\Vert \delta x\Vert }{\Vert x\Vert }\le K(A)\frac{\Vert \delta b\Vert }{\Vert b\Vert }$$

Corollario Per matrici unitarie, per le quali $K(U)=1$, la perturbazione relativa sulla soluzione è proprio uguale a quella sui dati.