Calcolo numerico/Sistemi lineari e errore inerente (condizionamento)

Perturbazioni del termine noto

Consideriamo un sistema della forma

$A{\boldsymbol {x}}={\boldsymbol {b}},\quad A\in \mathrm {Mat} _{n,\mathbb {R} }$

e supponiamo che $A$ sia non singolare.

Consideriamo il caso in cui

$A{\boldsymbol {x}}={\bar {\boldsymbol {b}}}$

${\bar {\boldsymbol {b}}}={\boldsymbol {b}}+\delta _{b}$

che ha soluzione ${\bar {\boldsymbol {x}}}={\boldsymbol {x}}+\delta _{x}$. Ci chiediamo quale sia la relazione tra $\delta _{x}$ e $\delta _{b}$.

Considerando le relazioni

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

$A{\bar {\boldsymbol {x}}}={\bar {\boldsymbol {b}}}$

Sottraiamo membro a membro:

$A{\bar {\boldsymbol {x}}}-A{\boldsymbol {x}}={\bar {\boldsymbol {b}}}-{\boldsymbol {b}}$

${\bar {\boldsymbol {x}}}-{\boldsymbol {x}}=A^{-1}[{\bar {\boldsymbol {b}}}-{\boldsymbol {b}}]=A^{-1}\delta _{b}$

passando alle norme

$\vert {\bar {\boldsymbol {x}}}-{\boldsymbol {x}}\vert =\vert A^{-1}\delta _{b}\vert \leq \vert A^{-1}\vert *\vert \delta _{b}\vert$

$\vert {\bar {\boldsymbol {x}}}-{\boldsymbol {x}}\vert \leq \vert A^{-1}\vert *\vert \delta _{b}\vert \quad {\hbox{relazione}}\circ$

ma

$\vert {\boldsymbol {b}}\vert \leq \vert A\vert *\vert {\boldsymbol {x}}\vert$

allora

${\frac {1}{\vert {\boldsymbol {x}}\vert }}\leq {\frac {\vert A\vert }{\vert {\boldsymbol {b}}\vert }}\quad {\hbox{relazione}}\circ \circ$

e unendo le relazioni $\circ$ e $\circ \circ$:

${\frac {\vert {\bar {\boldsymbol {x}}}-{\boldsymbol {x}}\vert }{\vert {\boldsymbol {x}}\vert }}\leq {\frac {\vert A\vert *\vert A^{-1}\vert *\vert \delta _{b}\vert }{\vert {\boldsymbol {b}}\vert }}$

quindi

${\frac {\vert {\bar {\boldsymbol {x}}}-{\boldsymbol {x}}\vert }{\vert {\boldsymbol {x}}\vert }}\leq K(A)*{\frac {\vert \delta _{b}\vert }{\vert {\boldsymbol {b}}\vert }}$

e in termini degli errori:

$\varepsilon _{x}\leq K(A)\varepsilon _{b}$

Caso generale

Consideriamo un sistema in cui ci sia una perturbazione anche sui coefficienti della matrice. Risolviamo quindi l'equazione

${\bar {A}}{\bar {\boldsymbol {x}}}={\bar {\boldsymbol {b}}},\quad {\bar {A}}=A+\delta _{A},\quad {\bar {\boldsymbol {b}}}={\boldsymbol {b}}+\delta _{b}$

Sono necessari i due seguenti teoremi tecnici.

Teorema 2.1

Data una norma matriciale indotta, tale che $\vert A\vert <1$ allora $I+A$ è non singolare, e $\vert (I+A)^{-1}\vert \leq {\frac {1}{1-\vert A\vert }}$.

Dimostrazione

Dimostriamo che $I+A$ è non singolare.

$\vert A\vert <1\,\longrightarrow \,\rho (A)<1,$

gli autovalori di $I+A$ sono della forma $1+\lambda _{i}$ con $\lambda _{i}$ autovalori di $A$.

Consideriamo la relazione

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

ed espandendo il prodotto:

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

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

$\vert (I+A)^{-1}\vert \leq \vert I-A(I+A)^{-1}\vert \leq \vert I\vert +\vert A\vert *\vert (I+A)^{-1}\vert$

$\vert I\vert =1$ perché sto considerando una norma matriciale indotta.

$(1-\vert A\vert )*\vert (I+A)^{-1}\vert \leq 1$

$1-\vert A\vert >0$, allora

$\vert (I+A)^{-1}\vert \leq {\frac {1}{1-\vert A\vert }}$

cvd

Teorema 2.2

Se $\vert A^{-1}\vert *\vert \delta _{A}\vert <1$ allora ${\bar {A}}$ è non singolare, e

$\vert (I+A^{-1}\delta _{A})^{-1}\vert \leq {\frac {1}{1-\vert A^{-1}\vert *\vert \delta _{A}\vert }}$

Dimostrazione

${\bar {A}}=A+\delta _{A}$, e siccome $A$ è non singolare posso raccogliere $A$ e scrivere:

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

ma $\vert A^{-1}\delta _{A}\vert \leq \vert A^{-1}\vert *\vert \delta _{A}\vert <1$ per ipotesi. Allora ${\bar {A}}$ è non singolare, per il teorema precedente.

$\vert (I+A^{-1}\delta _{A})^{-1}\vert \leq {\frac {1}{1-\vert A^{-1}\delta _{A}\vert }}\leq {\frac {1}{1-\vert A^{-1}\vert \vert \delta _{A}\vert }}$

cvd

Risultato di analisi a priori

Teorema 2.3

Dato il sistema $A{\boldsymbol {x}}={\boldsymbol {b}}$, con $A$ non singolare, ${\boldsymbol {b}}\neq 0$, con le perturbazioni sui dati $\delta _{A},\delta _{b}$, allora consideriamo il sistema

$(A+\delta _{A})({\boldsymbol {x}}+\delta _{x})={\boldsymbol {b}}+\delta _{b}$

nell'ipotesi che

$\vert A^{-1}\vert *\vert \delta _{A}\vert <1$

allora

${\bar {A}}=A+\delta _{A}$

è non singolare e per l'errore relativo

$\varepsilon _{x}={\frac {\vert \delta _{x}\vert }{\vert {\boldsymbol {x}}\vert }}={\frac {\vert {\bar {\boldsymbol {x}}}-{\boldsymbol {x}}\vert }{\vert {\boldsymbol {x}}\vert }}$

vale la relazione

$\varepsilon _{x}\leq {\frac {K(A)*(\varepsilon _{b}+\varepsilon _{A})}{1-K(A)*\varepsilon _{A}}}$

con

$\varepsilon _{A}={\frac {\vert \delta _{A}\vert }{\vert A\vert }}$

Il teorema afferma che se il numero di condizionamento di $A$ è piccolo, a errori piccoli sui dati corrisponde un errore piccolo nella soluzione, e il problema è ben condizionato, se invece $K(A)$ è grande piccoli errori sui dati possono dare grandi errori sulla soluzione (in quest'ultimo caso, la quantità al secondo membro è molto grande e, su quella a primo membro, che deve essere minore, non si hanno molte informazioni).

Dimostrazione

$(A+\delta _{A})({\boldsymbol {x}}+\delta _{x})={\boldsymbol {b}}+\delta _{b}$

$A{\boldsymbol {x}}+{\boldsymbol {x}}\delta _{A}+A\delta _{x}+\delta _{A}\delta _{x}={\boldsymbol {b}}+\delta _{b}$

e siccome $A{\boldsymbol {x}}={\boldsymbol {b}}$,

${\boldsymbol {x}}\delta _{A}+A\delta _{x}+\delta _{A}\delta _{x}=\delta _{b}$

e isolando $A\delta _{x}$:

$A\delta _{x}=\delta _{b}-{\boldsymbol {x}}\delta _{A}-\delta _{A}\delta _{x}$

e siccome $A$ è non singolare

$\delta _{x}=A^{-1}[\delta _{b}-{\boldsymbol {x}}\delta _{A}-\delta _{A}\delta _{x}]$

e portando a primo membro i termini moltiplicati per $\delta _{x}$:

$(I+A^{-1}\delta _{A})\delta _{x}=A^{-1}[\delta _{b}-{\boldsymbol {x}}\delta _{A}]$

e equivalentemente

$\delta _{x}=(I+A^{-1}\delta _{A})^{-1}*A^{-1}[\delta _{b}-{\boldsymbol {x}}\delta _{A}]$

Passando alla norma:

$\vert \delta _{x}\vert \leq \vert (I+A^{-1}\delta _{A})^{-1}\vert *\vert A^{-1}[\delta _{b}-{\boldsymbol {x}}\delta _{A}]\vert$

e per i due teoremi dimostrati prima possiamo maggiorare $\vert (I+A^{-1}\delta _{A})^{-1}\vert$:

$\vert \delta _{x}\vert \leq {\frac {1}{1-\vert A^{-1}\vert *\vert \delta _{A}\vert }}*\vert A^{-1}[\delta _{b}-{\boldsymbol {x}}\delta _{A}]\vert$

$(1-\vert A^{-1}\vert *\vert \delta _{A}\vert )\vert \delta _{x}\vert \leq \vert A^{-1}\vert *[\vert \delta _{b}\vert +\vert {\boldsymbol {x}}\vert *\vert \delta _{A}\vert ]$

Dividiamo entrambi i membri per $\vert {\boldsymbol {x}}\vert$:

$(1-\vert A^{-1}\vert *\vert \delta _{A}\vert )*{\frac {\vert \delta _{x}\vert }{\vert {\boldsymbol {x}}\vert }}\leq {\frac {\vert A^{-1}\vert *[\vert \delta _{b}\vert +\vert {\boldsymbol {x}}\vert *\vert \delta _{A}\vert ]}{\vert {\boldsymbol {x}}\vert }}$

$(1-\vert A^{-1}\vert *\vert \delta _{A}\vert )*{\frac {\vert \delta _{x}\vert }{\vert {\boldsymbol {x}}\vert }}\leq \vert A^{-1}\vert *[{\frac {\vert \delta _{b}\vert }{\vert {\boldsymbol {x}}\vert }}+\vert \delta _{A}\vert ]$

ponendo $\varepsilon _{x}={\frac {\vert \delta _{x}\vert }{\vert {\boldsymbol {x}}\vert }}$ e sapendo che

${\frac {1}{\vert {\boldsymbol {x}}\vert }}\leq {\frac {\vert A\vert }{\vert {\boldsymbol {b}}\vert }}$

allora

$(1-\vert A^{-1}\vert *\vert \delta _{A}\vert )*\varepsilon _{x}\leq \vert A^{-1}\vert *[{\frac {\vert A\vert \vert \delta _{b}\vert }{\vert {\boldsymbol {b}}\vert }}+\vert \delta _{A}\vert ]$

Moltiplicando e dividendo l'ultimo addendo per $\vert A\vert$ si ottiene:

$(1-\vert A^{-1}\vert *\vert \delta _{A}\vert )*\varepsilon _{x}\leq \vert A^{-1}\vert *\vert A\vert [{\frac {\vert \delta _{b}\vert }{\vert {\boldsymbol {b}}\vert }}+{\frac {\vert \delta _{A}\vert }{\vert A\vert }}]$

$(1-\vert A^{-1}\vert *\vert \delta _{A}\vert )*\varepsilon _{x}\leq K(A)*(\varepsilon _{A}+\varepsilon _{b})$

infine, sapendo che

$\vert A^{-1}\vert *\vert \delta _{A}\vert ={\frac {\vert \delta _{A}\vert }{\vert A\vert }}*K(A)=K(A)*\varepsilon _{A}$

si ha

$\varepsilon _{x}\leq {\frac {K(A)*(\varepsilon _{A}+\varepsilon _{b})}{1-K(A)\varepsilon _{A}}}$

cvd

Risultato di analisi a posteriori

Teorema 2.4

Sia $A{\boldsymbol {x}}={\boldsymbol {b}}$, $A$ non singolare, ${\boldsymbol {b}}\neq 0$, e ${\bar {\boldsymbol {x}}}$ soluzione calcolata in aritmetica floating point. Allora l'errore relativo su ${\boldsymbol {x}}$ è

$\varepsilon _{x}\leq K(A){\frac {\vert r\vert }{\vert {\boldsymbol {b}}\vert }}$

dove $r=r({\bar {\boldsymbol {x}}})={\boldsymbol {b}}-A{\bar {\boldsymbol {x}}}$ (residuo).

Si considera il sistema lineare come un'equazione vettoriale di cui cerchiamo la radice. Se chiamiamo $x_{\ast }$ la soluzione esatta, $r(x_{\ast })=0$.

Se il residuo è piccolo ma il $K(A)$ è grande, allora la maggiorazione non dà informazioni importanti.

Dimostrazione

$r={\boldsymbol {b}}-A{\bar {\boldsymbol {x}}}$

${\boldsymbol {b}}=A{\boldsymbol {x}}\,\longrightarrow \,r=A{\boldsymbol {x}}-A{\bar {\boldsymbol {x}}}=A({\boldsymbol {x}}-{\bar {\boldsymbol {x}}})$

ovvero ${\boldsymbol {x}}-{\bar {\boldsymbol {x}}}=A^{-1}r$.

Passando alla norma

$\vert {\boldsymbol {x}}-{\bar {\boldsymbol {x}}}\vert \leq \vert A^{-1}\vert \vert r\vert$

$\vert {\boldsymbol {x}}-{\bar {\boldsymbol {x}}}\vert \leq K(A)*{\frac {\vert r\vert }{\vert A\vert }}$

e siccome ${\boldsymbol {b}}=A{\boldsymbol {x}}$

$\vert {\boldsymbol {b}}\vert \leq \vert A\vert \vert {\boldsymbol {x}}\vert$

${\frac {1}{\vert A\vert }}\leq {\frac {\vert {\boldsymbol {x}}\vert }{\vert {\boldsymbol {b}}\vert }}$

sostituendo

$\vert {\boldsymbol {x}}-{\bar {\boldsymbol {x}}}\vert \leq K(A){\frac {\vert r\vert \vert {\boldsymbol {x}}\vert }{\vert {\boldsymbol {b}}\vert }}$

e dividendo ambo i membri della disuguaglianza per $\vert {\boldsymbol {x}}\vert$

$E_{r}\leq K(A){\frac {\vert r\vert }{\vert {\boldsymbol {b}}\vert }}$

cvd