Un esercizio sul numero di condizionamento

[dissonance]

Sia [tex]A[/tex] una matrice complessa [tex]n \times n[/tex]. Scelta una norma [tex]\lVert \cdot \rVert[/tex] su [tex]\mathbb{C}^n[/tex], usiamo lo stesso simbolo per indicare la corrispondente norma di matrice, ovvero

[tex]$\lVert A \rVert= \max_{ 0\ne x \in \mathbb{C}^n } \frac{ \lVert Ax \rVert}{\lVert x \rVert}$[/tex].

Nell'ipotesi che [tex]A[/tex] sia non singolare è definita allora anche la norma della matrice inversa e il numero di condizionamento

[tex]\kappa(A)=\lVert A \rVert \lVert A^{-1} \rVert[/tex].

E' facile mostrare che valgono le disuguaglianze

[tex]\forall x \in \mathbb{C}^n,\ \frac{1}{\lVert A^{-1} \rVert} \lVert x \rVert \le \lVert Ax \rVert \le \lVert A \rVert \lVert x \rVert[/tex]

nelle quali le costanti [tex]\lVert A^{-1} \rVert, \lVert A \rVert[/tex] sono le migliori possibili, nel senso che valgono le uguaglianze (non simultaneamente) per opportune scelte delle [tex]x[/tex].

__________________________________

Consideriamo il sistema lineare [tex]Ax=b[/tex]. Detto [tex]\delta b \in \mathbb{C}^n[/tex] un vettore di perturbazione della [tex]b[/tex], indichiamo con [tex]x + \delta x[/tex] la soluzione del sistema perturbato, ovvero

[tex]A(x + \delta x)=b+\delta b[/tex].

Dimostrare che:

1) Vale la stima dell'errore relativo [tex]\frac{\lVert \delta x \rVert}{\lVert x \rVert} \le \kappa(A) \frac{ \lVert \delta b\rVert }{\lVert b \rVert}[/tex];
2) Esistono sempre un [tex]b[/tex] e un [tex]\delta b[/tex] che rendono la stima precedente una uguaglianza.

[_luca.barletta]

1)

Dal sistema lineare [tex]b=A\cdot x[/tex] si ha [tex]||b||=||Ax||\le ||A||\cdot ||x||[/tex], e dal sistema lineare [tex]A\cdot \delta x=\delta b[/tex] si ha
[tex]||\delta x|| =|| A^{-1}\cdot\delta b|| \le ||A^{-1}||\cdot ||\delta b||[/tex].
Da questa coppia di diseguaglianze segue che
[tex]||\delta x||\cdot || b||\le \kappa(A) ||\delta b ||\cdot ||x||[/tex],
vale a dire
[tex]$\frac{||\delta x||}{||x||}\le \kappa(A) \frac{||\delta b||}{||b||}[/tex].

2)

La diseguaglianza si può leggere come
[tex]$||A||\cdot||A^{-1}||=\kappa(A)\ge\frac{||b||}{||x||}\frac{||\delta x||}{||\delta b||}=\frac{||Ax||}{||x||}\frac{||A^{-1}\delta b||}{||\delta b||}[/tex] per ogni [tex]x\ne 0, \delta b\ne 0 \in \mathbb{C}^n[/tex].
Dalla norma di matrice
[tex]$||A||=\max_{0\ne x\in\mathbb{C}^n}\frac{||Ax||}{||x||}[/tex]
prendiamo quel vettore [tex]\tilde{x}[/tex] che rende massimo il rapporto nella formula precedente, ovvero
[tex]\tilde{x}=\arg\max_{0\ne x\in\mathbb{C}^n}\frac{||Ax||}{||x||}[/tex],
a cui corrisponde il [tex]\tilde{b}=A\tilde{x}[/tex]. Analogamente, esiste il [tex]\tilde{\delta b}[/tex] tale che
[tex]\tilde{\delta b}=\arg\max_{0\ne \delta b\in\mathbb{C}^n}\frac{||A^{-1}\delta b||}{||\delta b||}[/tex],
e per cui
[tex]$||A^{-1}||=\frac{||A^{-1}\tilde{\delta b}||}{||\tilde{\delta b}||}[/tex].

Infine si ha
[tex]$\kappa(A)=\frac{||\tilde{b}||}{||A^{-1}\tilde{b}||}\frac{||A^{-1}\tilde{\delta b}||}{||\tilde{\delta b}||}[/tex].

[dissonance]

Perfetto.

Quindi ne traiamo la conclusione che il numero di condizionamento fornisce una stima della propagazione dell'errore dovuto alla perturbazione del dato iniziale [tex]b[/tex] e che questa stima è la migliore possibile. In effetti sui libri di analisi numerica si fa una analisi più accurata tenendo conto anche di eventuali perturbazioni sulla matrice [tex]A[/tex]:

[tex]$(A + \delta A)(x+\delta x)=b+\delta b[/tex]

e si ottengono stime per [tex]\dfrac{ \lVert \delta x \rVert}{\lVert x \rVert}[/tex] relativamente a [tex]\dfrac{ \lVert \delta A \rVert}{\lVert A \rVert},\ \dfrac{\lVert \delta b \rVert}{\lVert b \rVert}[/tex]. Le formule sono più complicate e meno intuitive ma la sostanza è sempre la stessa: [tex]\kappa(A)[/tex] fornisce una indicazione, ancora la migliore possibile per certi punti di vista, del modo in cui [tex]A[/tex] propaga le perturbazioni sui dati iniziali. (@luca: Queste sono cose che tu sai benissimo, certamente meglio di me; le sto scrivendo per eventuali altri lettori.)

Grazie per l'attenzione!