Risoluzione di sistemi con errori nel termine noto

Si rammenti per prima cosa:

Teorema 6.5   $\det(A) = 0$ se e solo se $A$ è singolare

Si consideri:

$$Ax = b \qquad A \in R^{n\times m}, \det(A) \neq 0, x \in R^n, b \in R^n$$

Si supponga ora che il termine noto sia tale solo in una forma approssimata $\tilde{b}$. Ci si troverebbe dunque in realtà a risolvere:

$$A\tilde{x} = \tilde{b}$$

È possibile scrivere l'errore sul risultato come:

$$\delta x = \tilde{x} - x \qquad \delta b = \tilde{b} - b$$

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

Interessa naturalmente sapere in che modo l'errore sul termine noto $\delta b$ influenzi l'errore sul risultato $\delta x$.

Definizione 6.18 (Indice di condizionamento)  

$$k(A) = \Vert A\Vert \Vert A^{-1} \Vert$$

Lemma 6.3   $k(A)$ dipende solo dalla matrice $A$ una volta fissata la norma vettoriale.

Lemma 6.4   $k(A) \ge 1$ (=1 quando $A =\mathscr{I}$)

Può succedere che $k(A)$ sia molto grande. In questo caso si parla di sistemi malcondizionati, ovvero di instabilità intrinseca del problema: la risoluzione di siffatti sistemi interessa fino a un certo punto.

Teorema 6.6   Siano $e_r(b) = \frac{\Vert\delta b\Vert}{\Vert b\Vert}$ e $e_r(x) = \frac{\Vert\delta x\Vert}{\Vert x\Vert}$ errori relativi fissata una certa norma $\Vert\cdot\Vert$.

Allora:

$$e_r(x) \leq k(A) \, e_r(b)$$

$&sstarf#star;$ Dimostrazione 6.1   Per un sistema

$$Ax = b$$

vale:

$$\delta x = A^{-1} \delta b$$

Infatti:

$$\begin{split} A(x + \delta x) & = b + \delta b \\ Ax + A ... ... & = b + \delta b \\ \delta x & = A^{-1} \delta b \end{split}$$

Dunque fissata una norma $\Vert\cdot\Vert$ è possibile scrivere:

$$\begin{split}\delta x = A^{-1} \delta b \Rightarrow \Vert\del... ...t &\le \Vert A^{-1}\Vert \cdot \Vert\delta b \Vert \end{split}$$

Ora, poichè

$$\Vert x\Vert \ge k > 0 \Rightarrow \frac{1}{\Vert x\Vert} \le \frac{1}{k}$$

Dunque:

$$\Vert\delta x \Vert \le \Vert A^{-1}\Vert \cdot \Vert\delta b \Ve... ...\Vert x\Vert} \leq \frac{\Vert A^{-1}\Vert \Vert\delta b \Vert}{\Vert x\Vert }$$

Poichè inoltre $Ax = b \Rightarrow \Vert Ax\Vert = \Vert b\Vert$:

$$\begin{split}\underbrace{\Vert Ax\Vert}_{\leq \Vert A\Vert \c... ...Vert x\Vert} &\le \frac{\Vert A\Vert}{\Vert b\Vert} \end{split}$$

Sostituendo:

$$\frac{\Vert\delta x \Vert}{\Vert x\Vert} \leq \frac{\Vert A^{-1}\... ...delta b \Vert}{\Vert b \Vert } = k(A) \frac{\Vert\delta b \Vert}{\Vert b\Vert}$$

$\qedsymbol$

Esempio 6.3  

Si consideri il sistema

$$\begin{cases} 7x_1+10x_2 = 1\\ 5x_1+7x_2 = 0.7 \end{cases}$$

con:

$$A = \begin{bmatrix}7 & 10 \\ 5 & 7 \end{bmatrix} \\ \qquad b = \begin{bmatrix}1 \\ 0.7 \end{bmatrix}$$

Sia $\tilde b$ il vettore dei dati perturbati:

$$\tilde{b} = \begin{bmatrix}1 \\ 0.069 \end{bmatrix}, \qquad \delta b = \begin{bmatrix}0.01 \\ 0.01 \end{bmatrix}$$

Scelta come norma la norma infinito si ottiene:

$$\Vert b\Vert _\infty = \max \lbrace \lvert 1\rvert, \rvert 0.7 \lvert \rbrace = 1$$

$$\Vert\delta b \Vert _\infty = \max \lbrace 10^{-2}, 10^{-2} \rbrace = 10^{-2}$$

L'errore sul termine noto è il seguente:

$$\frac{\Vert \delta b \Vert _\infty }{\Vert b \Vert _\infty } = \frac{10^{-2}}{1} = 10^{-2} = 1\%$$

Si calcola allora la soluzione:

$$x = \begin{bmatrix}0 \\ 0.1 \end{bmatrix} \qquad \tilde{x} = \be... ... 0.22\end{bmatrix}\qquad \delta x = \begin{bmatrix}-0.17 \\ 0.12 \end{bmatrix}$$

Le norme sono le seguenti:

$$\Vert x\Vert _\infty = 0.1$$

$$\Vert \delta x \Vert _{\infty} = \max\lbrace 0.17, 0.12 \rbrace = 0.17$$

Si ottiene un'errore sulla soluzione pari a:

$$\frac{\Vert \delta x \Vert }{\Vert x\Vert}= \frac{0.17}{0.1} = 1.7 = 170\%$$

$$\Vert A\Vert _\infty = \{ 17, 12 \} = 17$$

Calcolando $A^{-1}$ si ha:

$$A^{-1} = \begin{bmatrix}-7 & 10 \\ 5 & -7 \end{bmatrix}$$

$$\Vert A^{-1}\Vert = \max \{17,12\} = 17$$

L'indice di condizionamento è:

$$k(A) = 17 \cdot 17 = 17^2 = 289$$

La soluzione è quindi inaccettabile.