Calcolo numerico/Sistemi lineari e errore inerente (condizionamento)

Perturbazioni del termine noto

Consideriamo un sistema della forma

$A𝒙=𝒃,A\in {\mathrm{M}\mathrm{a}\mathrm{t}}_{n,ℝ}$

e supponiamo che $A$ sia non singolare.

Consideriamo il caso in cui

$A𝒙=\overline{𝒃}$

$\overline{𝒃}=𝒃+{\delta }_b$

che ha soluzione $\overline{𝒙}=𝒙+{\delta }_x$. Ci chiediamo quale sia la relazione tra ${\delta }_x$ e ${\delta }_b$.

Considerando le relazioni

$A𝒙=𝒃$

$A\overline{𝒙}=\overline{𝒃}$

Sottraiamo membro a membro:

$A\overline{𝒙}-A𝒙=\overline{𝒃}-𝒃$

$\overline{𝒙}-𝒙=A^{-1}[\overline{𝒃}-𝒃]=A^{-1}{\delta }_b$

passando alle norme

$|\overline{𝒙}-𝒙|=|A^{-1}{\delta }_b|\le |A^{-1}|\ast |{\delta }_b|$

$|\overline{𝒙}-𝒙|\le |A^{-1}|\ast |{\delta }_b|\text{relazione}\circ$

ma

$|𝒃|\le |A|\ast |𝒙|$

allora

$\frac{1}{|𝒙|}\le \frac{|A|}{|𝒃|}\text{relazione}\circ \circ$

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

$\frac{|\overline{𝒙}-𝒙|}{|𝒙|}\le \frac{|A|\ast |A^{-1}|\ast |{\delta }_b|}{|𝒃|}$

quindi

$\frac{|\overline{𝒙}-𝒙|}{|𝒙|}\le K(A)\ast \frac{|{\delta }_b|}{|𝒃|}$

e in termini degli errori:

${\epsilon }_x\le K(A){\epsilon }_b$

Caso generale

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

$\overline{A}\overline{𝒙}=\overline{𝒃},\overline{A}=A+{\delta }_A,\overline{𝒃}=𝒃+{\delta }_b$

Sono necessari i due seguenti teoremi tecnici.

Teorema 2.1

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

Dimostrazione

Dimostriamo che $I+A$ è non singolare.

$|A|<1⟶\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}$

$|(I+A{)}^{-1}|\le |I-A(I+A{)}^{-1}|\le |I|+|A|\ast |(I+A{)}^{-1}|$

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

$(1-|A|)\ast |(I+A{)}^{-1}|\le 1$

$1-|A|>0$, allora

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

cvd

Teorema 2.2

Se $|A^{-1}|\ast |{\delta }_A|<1$ allora $\overline{A}$ è non singolare, e

$|(I+A^{-1}{\delta }_A{)}^{-1}|\le \frac{1}{1-|A^{-1}|\ast |{\delta }_A|}$

Dimostrazione

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

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

ma $|A^{-1}{\delta }_A|\le |A^{-1}|\ast |{\delta }_A|<1$ per ipotesi. Allora $\overline{A}$ è non singolare, per il teorema precedente.

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

cvd

Risultato di analisi a priori

Teorema 2.3

Dato il sistema $A𝒙=𝒃$, con $A$ non singolare, $𝒃\ne 0$, con le perturbazioni sui dati ${\delta }_A,{\delta }_b$, allora consideriamo il sistema

$(A+{\delta }_A)(𝒙+{\delta }_x)=𝒃+{\delta }_b$

nell'ipotesi che

$|A^{-1}|\ast |{\delta }_A|<1$

allora

$\overline{A}=A+{\delta }_A$

è non singolare e per l'errore relativo

${\epsilon }_x=\frac{|{\delta }_x|}{|𝒙|}=\frac{|\overline{𝒙}-𝒙|}{|𝒙|}$

vale la relazione

${\epsilon }_x\le \frac{K(A)\ast ({\epsilon }_b+{\epsilon }_A)}{1-K(A)\ast {\epsilon }_A}$

con

${\epsilon }_A=\frac{|{\delta }_A|}{|A|}$

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)(𝒙+{\delta }_x)=𝒃+{\delta }_b$

$A𝒙+𝒙{\delta }_A+A{\delta }_x+{\delta }_A{\delta }_x=𝒃+{\delta }_b$

e siccome $A𝒙=𝒃$,

$𝒙{\delta }_A+A{\delta }_x+{\delta }_A{\delta }_x={\delta }_b$

e isolando $A{\delta }_x$:

$A{\delta }_x={\delta }_b-𝒙{\delta }_A-{\delta }_A{\delta }_x$

e siccome $A$ è non singolare

${\delta }_x=A^{-1}[{\delta }_b-𝒙{\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-𝒙{\delta }_A]$

e equivalentemente

${\delta }_x=(I+A^{-1}{\delta }_A{)}^{-1}\ast A^{-1}[{\delta }_b-𝒙{\delta }_A]$

Passando alla norma:

$|{\delta }_x|\le |(I+A^{-1}{\delta }_A{)}^{-1}|\ast |A^{-1}[{\delta }_b-𝒙{\delta }_A]|$

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

$|{\delta }_x|\le \frac{1}{1-|A^{-1}|\ast |{\delta }_A|}\ast |A^{-1}[{\delta }_b-𝒙{\delta }_A]|$

$(1-|A^{-1}|\ast |{\delta }_A|)|{\delta }_x|\le |A^{-1}|\ast [|{\delta }_b|+|𝒙|\ast |{\delta }_A|]$

Dividiamo entrambi i membri per $|𝒙|$:

$(1-|A^{-1}|\ast |{\delta }_A|)\ast \frac{|{\delta }_x|}{|𝒙|}\le \frac{|A^{-1}|\ast [|{\delta }_b|+|𝒙|\ast |{\delta }_A|]}{|𝒙|}$

$(1-|A^{-1}|\ast |{\delta }_A|)\ast \frac{|{\delta }_x|}{|𝒙|}\le |A^{-1}|\ast [\frac{|{\delta }_b|}{|𝒙|}+|{\delta }_A|]$

ponendo ${\epsilon }_x=\frac{|{\delta }_x|}{|𝒙|}$ e sapendo che

$\frac{1}{|𝒙|}\le \frac{|A|}{|𝒃|}$

allora

$(1-|A^{-1}|\ast |{\delta }_A|)\ast {\epsilon }_x\le |A^{-1}|\ast [\frac{|A||{\delta }_b|}{|𝒃|}+|{\delta }_A|]$

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

$(1-|A^{-1}|\ast |{\delta }_A|)\ast {\epsilon }_x\le |A^{-1}|\ast |A|[\frac{|{\delta }_b|}{|𝒃|}+\frac{|{\delta }_A|}{|A|}]$

$(1-|A^{-1}|\ast |{\delta }_A|)\ast {\epsilon }_x\le K(A)\ast ({\epsilon }_A+{\epsilon }_b)$

infine, sapendo che

$|A^{-1}|\ast |{\delta }_A|=\frac{|{\delta }_A|}{|A|}\ast K(A)=K(A)\ast {\epsilon }_A$

si ha

${\epsilon }_x\le \frac{K(A)\ast ({\epsilon }_A+{\epsilon }_b)}{1-K(A){\epsilon }_A}$

cvd

Risultato di analisi a posteriori

Teorema 2.4

Sia $A𝒙=𝒃$, $A$ non singolare, $𝒃\ne 0$, e $\overline{𝒙}$ soluzione calcolata in aritmetica floating point. Allora l'errore relativo su $𝒙$ è

${\epsilon }_x\le K(A)\frac{|r|}{|𝒃|}$

dove $r=r(\overline{𝒙})=𝒃-A\overline{𝒙}$ (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=𝒃-A\overline{𝒙}$

$𝒃=A𝒙⟶r=A𝒙-A\overline{𝒙}=A(𝒙-\overline{𝒙})$

ovvero $𝒙-\overline{𝒙}=A^{-1}r$.

Passando alla norma

$|𝒙-\overline{𝒙}|\le |A^{-1}||r|$

$|𝒙-\overline{𝒙}|\le K(A)\ast \frac{|r|}{|A|}$

e siccome $𝒃=A𝒙$

$|𝒃|\le |A||𝒙|$

$\frac{1}{|A|}\le \frac{|𝒙|}{|𝒃|}$

sostituendo

$|𝒙-\overline{𝒙}|\le K(A)\frac{|r||𝒙|}{|𝒃|}$

e dividendo ambo i membri della disuguaglianza per $|𝒙|$

$E_r\le K(A)\frac{|r|}{|𝒃|}$

cvd