Sistemi lineari quadrati

Consideriamo inizialmente il sistema lineare

$$\mathbf{A}\mathbf{x}=\mathbf{b},$$ (1.25)

dove $\mathbf{A}\in\mathbb{R}^{n\times n}$ è non singolare e $\mathbf {x}$ rappresenta la soluzione esatta del problema.

Supponiamo che il vettore dei termini noti sia affetto da una perturbazione $\delta\mathbf{b}$ e indichiamo con $\tilde{\mathbf{x}}$ la soluzione del sistema perturbato. Si ha quindi

$$\mathbf{A}\tilde{\mathbf{x}} = \tilde{\mathbf{b}} = \mathbf{b}+\delta\mathbf{b}.$$ (1.26)

Poiché il sistema non perturbato soddisfa $\mathbf{A}\mathbf{x}=\mathbf{b}$, sottraendo le due equazioni si ottiene

$$\mathbf{A}(\tilde{\mathbf{x}}-\mathbf{x}) = \delta\mathbf{b}.$$ (1.27)

Definendo la perturbazione della soluzione come

$$\delta\mathbf{x} = \tilde{\mathbf{x}}-\mathbf{x},$$ (1.28)

risulta quindi

$$\mathbf{A}\delta\mathbf{x} = \delta\mathbf{b}.$$ (1.29)

Nel caso in cui $\mathbf{A}$ sia quadrata e invertibile, si può infine scrivere

$$\delta\mathbf{x} = \mathbf{A}^{-1}\delta\mathbf{b}.$$ (1.30)

La norma dell'errore sulla soluzione può pertanto essere limitata da

$$\Vert\delta\mathbf{x}\Vert \leq \Vert\mathbf{A}^{-1}\Vert\,\Vert\delta\mathbf{b}\Vert.$$ (1.31)

Per confrontare l'errore relativo sulla soluzione con quello sui dati, si osserva inoltre che

$$\vert\mathbf{b}\vert = \vert\mathbf{A}\mathbf{x}\vert \leq \vert\mathbf{A}\vert,\vert\mathbf{x}\vert.$$ (1.32)

Combinando le due relazioni si ottiene

$$\boxed{ \frac{\vert\delta\mathbf{x}\vert}{\vert\mathbf{x}\ve... ...ert \frac{\vert\delta\mathbf{b}\vert}{\vert\mathbf{b}\vert} }.$$ (1.33)

Il prodotto

$$\kappa(\mathbf{A}) = \vert\mathbf{A}\vert,\vert\mathbf{A}^{-1}\vert$$ (1.34)

viene definito numero di condizionamento della matrice $\mathbf{A}$. Esso fornisce quindi un limite al fattore con cui una perturbazione relativa dei dati può essere amplificata nella soluzione.

Il numero di condizionamento dipende dalla norma utilizzata. Nel seguito, quando non diversamente specificato, si considera la norma euclidea $\vert\cdot\vert _2$. In questo caso, se $\sigma_1$ e $\sigma_n$ sono rispettivamente il massimo e il minimo valore singolare di $\mathbf{A}$, si ha

$$\boxed{ \kappa_2(\mathbf{A}) = \frac{\sigma_1}{\sigma_n} }.$$ (1.35)

La relazione mostra immediatamente il ruolo della decomposizione SVD: un valore singolare piccolo identifica una direzione nella quale il sistema è poco vincolato e nella quale una perturbazione dei dati può produrre una variazione relativamente grande della soluzione.

Se $\mathbf{A}$ è singolare, almeno un valore singolare è nullo e il numero di condizionamento viene posto pari a

$$\kappa_2(\mathbf{A})=\infty.$$ (1.36)

Il numero di condizionamento presenta alcune proprietà importanti:

• $\kappa(\mathbf{A})=\kappa(\mathbf{A}^{-1})$;
• $\kappa(c\mathbf{A})=\kappa(\mathbf{A})$ per ogni $c\neq0$;
• $\kappa(\mathbf{A})\geq1$;
• nella norma 2,

  
  

  $$\kappa_2(\mathbf{A}) = \frac{\sigma_1}{\sigma_n};$$
  
  

• se $\mathbf{A}$ è ortogonale, allora

  
  

  $$\kappa_2(\mathbf{A})=1.$$
  
  

Un valore di $\kappa$ prossimo all'unità indica quindi che il problema è poco sensibile alle perturbazioni, mentre valori elevati indicano una maggiore sensibilità.