Sistemi lineari e errore inerente (condizionamento)

Perturbazioni del termine noto

Considero un sistema della forma

e suppongo che sia non singolare.


Considero il caso in cui

che ha soluzione . Mi chiedo quale sia la relazione tra e .


Considerando le relazioni

Sottraggo membro a membro:
passando alle norme
ma
allora
e unendo le relazioni e :
quindi
e in termini degli errori:

Caso generale

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

Sono necessari i due seguenti teoremi tecnici.


Teorema 2.1

Data una norma matriciale indotta, tale che allora è non singolare, e .

 
Dimostrazione

Dim. Dimostriamo che è non singolare.

gli autovalori di sono della forma con autovalori di .


Considero la relazione

ed espandendo il prodotto:
e perché sto considerando una norma matriciale indotta.
, allora

cvd

 


Teorema 2.2

Se allora è non singolare, e

 
Dimostrazione

Dim. , e siccome è non singolare posso raccogliere e scrivere:

ma per ipotesi. Allora è non singolare, per il teorema precedente.

cvd

 

Risultato di analisi a priori

Teorema 2.3

(importante) Dato il sistema , con non singolare, , con le perturbazioni sui dati , allora considero il sistema

nell'ipotesi che
allora
è non singolare e per l'errore relativo
vale la relazione
con

 


Il teorema afferma che se il numero di condizionamento di è piccolo, a errori piccoli sui dati corrisponde un errore piccolo nella soluzione, e il problema è ben condizionato, se invece è 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

Dim.

e siccome ,
e isolando :
e siccome è non singolare
e portando a primo membro i termini moltiplicati per :
e equivalentemente
Passando alla norma:
e per i due teoremi dimostrati prima possiamo maggiorare :
Divido entrambi i membri per :
ponendo e sapendo che
allora
Moltiplicando e dividendo l'ultimo addendo per ottengo:
infine, sapendo che
si ha

cvd

 

Risultato di analisi a posteriori

Teorema 2.4

Sia , non singolare, , e soluzione calcolata in aritmetica floating-point. Allora l'errore relativo su è

dove (residuo).

 


Si considera il sistema lineare come un'equazione vettoriale di cui cerco la radice. Se chiamo la soluzione esatta, .


Se il residuo è piccolo ma il è grande, allora la maggiorazione non dà informazioni importanti.


Dimostrazione

Dim.

ovvero .


Passando alla norma

e siccome
sostituendo
e dividendo ambo i membri della disuguaglianza per

cvd

 
 PrecedenteSuccessivo