Calcolo numerico/Norme di vettori e di matrici

Norma di vettori

Nella risoluzione di sistemi lineari si ha l'obiettivo di misurare quantità non scalari.

Esempio 2.1

Esempi di norme sono:

1. $|𝒙|=\sqrt{\sum _{i=1}^n{x}_i^2}\text{norma 2}$
2. $|𝒙|=\sum _{i=1}^n|x_i|\text{norma 1}$
3. $|𝒙{|}^{\mathrm{\infty }}=maxi|x_i|\text{norma infinito}$

e gli intorni in queste tre norme sono rispettivamente un cerchio, un rombo e un quadrato.

Proprietà 1: la norma è una funzione uniformemente continua, cioè

$\mathrm{\forall }\epsilon >0\mathrm{\exists }\delta t.c.|𝒙-𝒚|<\delta ⟶|𝒙|-|𝒚|\le \epsilon$

A vettori vicini corrispondono norme vicine indipendentemente dagli ordini di grandezza.

Proprietà 2: vale la proprietà di equivalenza topologica delle norme. Supponiamo di prendere due norme qualsiasi $|𝒙{|}_1$ e $|𝒙{|}_2$, con $n$ fissato. Allora esistono $\alpha ,\beta \in ℝ$ con $0<\alpha <\beta$ tali che

$\alpha |𝒙{|}_2\le |𝒙{|}_1\le \beta |𝒙{|}_2$

Allora, siccome tutte le norme sono equivalenti, si può scegliere la norma che dà meno errori.

Proprietà 3: per ogni $𝒙\in {ℂ}^n$, considerate le norme 1,2 e $\mathrm{\infty }$ dell'esempio precedente, si ha:

$|𝒙{|}^{\mathrm{\infty }}\le |𝒙{|}_2\le \sqrt{n}|𝒙{|}^{\mathrm{\infty }}$

$|𝒙{|}_2\le |𝒙{|}_1\le \sqrt{n}|𝒙{|}_2$

e, unendo le due relazioni:

$|x{|}^{\mathrm{\infty }}\le |𝒙{|}_2\le |𝒙{|}_1$

Norma matriciale

Proprietà 1,2: valgono l'uniforme continuità e l'equivalenza delle norme come conseguenze dei punti 1,2,3.

Esempio 2.2

È necessario imporre anche la quarta proprietà. Infatti, data la matrice

$A=\left(\begin{array}{cc}1& 2\\ 2& 4\end{array}\right)$

$B=\left(\begin{array}{cc}1& 6\\ 1& 8\\ 3& 4\end{array}\right)$

si ha che $AB$ è la matrice nulla, e quindi vale

$0<|A|\ast |B|$

Relazioni tra norme vettoriali e norme matriciali

Proprietà 3: Una norma vettoriale indotta è una norma matriciale compatibile.

Dim. Se $𝒙=0$, la definizione di norma matriciale compatibile è verificata. Se $𝒙\ne 0$, si ha

$|A𝒙{|}_v=\frac{|A𝒙{|}_v}{|𝒙{|}_v}\ast |𝒙{|}_v$

$=|𝒙{|}_v\ast |A\frac{𝒙}{|𝒙{|}_v}{|}_v=$

$=|𝒙{|}_v\ast |A𝒚{|}_v$

$\le |𝒙{|}_v\ast \underset{𝒚t.c.|𝒚{|}_v=1}{max}|A𝒚{|}_v$

$\le |𝒙{|}_v\ast |A|$

cvd

Proprietà 4: La norma matriciale indotta è la più piccola tra le norme matriciali compatibili con la norma vettoriale considerata.

Dim.

$|A|=\underset{𝒙t.c.|𝒙|=1}{max}|A𝒙{|}_v$

e per la compatibilità della norma $\ast$:

$\le \underset{𝒙t.c.|𝒙{|}_v=1}{max}|A{|}^{\ast }|𝒙{|}_v$

$\le |A{|}^{\ast }$

cvd

Norme matriciali indotte dalle principali norme vettoriali

Proprietà 5:

$\begin{array}{c}\\ \text{norma vettoriale}& \text{norma matriciale compatibile}\\ \text{norma 1}& {max}_{j=1}^n[\sum _{i=1}^n|A_{ij}|]\\ \text{norma infinito}& {max}_{i=1}^n[\sum _{j=1}^n|A_{ij}|]\\ \text{norma 2}& {\rho }^{1/2}(A_h\ast A)\end{array}$

Nell'espressione della norma matriciale indotta dalla norma 2, cioè dalla norma euclidea, $\rho$ rappresenta il raggio spettrale.

Proprietà 6: Per ogni $A\in {ℂ}^n$ valgono le seguenti disuguaglianze:

$\begin{array}{ccc}\frac{1}{\sqrt{n}}|A{|}^{\mathrm{\infty }}& \le |A{|}_2& \le \sqrt{n}|A{|}^{\mathrm{\infty }}\\ \frac{1}{\sqrt{n}}|A{|}_1& \le |A{|}_2& \le \sqrt{n}|A{|}_1\\ \underset{i,j}{max}|A_{ij}|& \le |A{|}_2& \le \underset{i,j}{max}|A_{ij}|???\\ |A{|}_2& \le \sqrt{n}|A{|}_2& \le |A{|}^{\mathrm{\infty }}\end{array}$

Osservazione 2.1

Se $A=A_h$, allora $|A{|}^{\mathrm{\infty }}=|A{|}_1$, e

$|A{|}_2={\rho }^{1/2}(A^2).$

ma siccome per gli autovalori vale la relazione $A𝒙=\lambda 𝒙$, moltiplicando per $A$ ottengo:

$A^2𝒙=\lambda A𝒙={\lambda }^2𝒙$

cioè gli autovalori di $A^2$ sono i quadrati degli autovalori di $A$.

Quindi

$|A{|}_2=\rho (A)$

Se $A$ è hermitiana definita positiva, cioè $\mathrm{\forall }𝒙\ne 0$, $𝒙\cdot A𝒙>0$, allora gli autovalori sono positivi, e si ha

$|A{|}_2=\underset{i}{max}{\lambda }_i(A)$

Nota: il raggio spettrale non è una norma matriciale, a meno che non mi limiti a sottoclassi di matrici.

Esistono infatti $A,B$ tali che

$\rho (A+B)>\rho (A)+\rho (B)$

Esempio 2.3

Considerando

$A=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$

$B=\left(\begin{array}{cc}0& 0\\ 1& 0\end{array}\right)$

Allora si verifica che

$\rho (A)=\rho (B)=0$

mentre

$\rho (A+B)=1$

e la disuguaglianza triangolare è violata.

Altre proprietà della norma matriciale indotta

Proprietà 7: per ogni norma matriciale indotta, vale che $\rho (A)\le |A{|}^{\ast }$.

Dim. Consideriamo la relazione

$A𝒙=\lambda 𝒙$

$|\lambda 𝒙|=|A𝒙{|}_v$

$⟶|\lambda ||𝒙{|}_v=|A𝒙{|}_v$

$⟶|\lambda |=|A\frac{𝒙}{|𝒙{|}_v}{|}_v$

$|\lambda |\le \underset{𝒗t.c.|𝒗|=1}{max}|A𝒗{|}_v=|A{|}^{\ast }$

cioè

$|\lambda |\le |A{|}^{\ast }$

vale per ogni autovalore, e quindi anche per quello che realizza il raggio spettrale, cioè

$\rho (A)\le |A{|}^{\ast }$

cvd

Numero di condizionamento

Consideriamo una funzione $g:{ℝ}^n\to {ℝ}^n$, tale che $Ag(P)=P$.

$\overline{P}=P+{\delta }_P,⟶g(\overline{P})\simeq g(P)+J_g(P)\ast {\delta }_P$

Valutando l'errore relativo

$|E_r|=\frac{|g(\overline{P})-g(P)|}{|g(P)|}$

$=\frac{|g(P)+J_g(P)\ast {\delta }_P-g(P)|}{|g(P)|}$

$=\frac{|J_g(P){\delta }_P|}{|g(P)|}$

$\le \frac{|J_g(P)|\ast |{\delta }_P|}{|G(P)|}$

Moltiplichiamo e dividiamo per $|P|$.

$E_r\le |J_g(P)|\ast \frac{|P|}{|g(P)|}\ast \frac{|{\delta }_P|}{|P|}$

Siccome stiamo supponendo di risolvere il sistema

$Ag(P)=P$

segue che

$J_g(P)=A^{-1}$

$g(P)=A^{-1}P$

quindi

$E_r\le |A^{-1}|\ast \frac{|Ag(P)|}{|g(P)|}\ast {\epsilon }_P$

tenendo conto che la norma matriciale utilizzata è compatibile:

$E_r\le |A|\ast \frac{|A^{-1}|\ast |G(P)|}{|g(P)|}\ast \frac{|{\delta }_P|}{|P|}$

e ponendo ${\epsilon }_x=\frac{|{\delta }_P|}{|P|}$ si ottiene

$E_r\le K(A)\ast {\epsilon }_X$

Proprietà del numero di condizionamento

Lemma 2.1: Per ogni norma, $K(A)\ge 1$.

Dim.

$K(A)=|A|\ast |A^{-1}|\ge |A^{-1}A|=|I|\ge 1$

cvd

Condizionamento spettrale

$A_{H}A$ è definita positiva, se $A$ è non singolare. Infatti $𝒙\cdot (A_{h}A𝒙)=𝒙\cdot (A_H𝒚)\ge 0\mathrm{\forall }𝒙\ne 0,𝒚=A𝒙\ne 0$.

Se $A$ è definita positiva, allora ha tutti autovalori reali positivi, e

${\rho }^{1/2}(A_{h}A)=\sqrt{\underset{i}{max}{\lambda }_i(A_{h}A)}=\sqrt{{\lambda }_{max}(A_{h}A)}$

dove i ${\lambda }_i$ sono autovalori di $A_{h}A$.

Inoltre

$|A^{-1}{|}_2={\rho }^{1/2}(A_h^{-1}{A}^{-1})={\rho }^{1/2}(A{A}_h{)}^{-1}=\sqrt{max{\lambda }_i((A{A}_h{)}^{-1}},{\lambda }_i\text{autovalori di}(A{A}_h{)}^{-1}$

Allora

$|A^{-1}{|}_2=\underset{i}{max}[\frac{1}{{\lambda }_i(A{A}_H)}]=\frac{1}{{\lambda }_{min}(A{A}_h)}$

e siccome $A$ h $A{A}_h$ e $A_{h}A$ sono simili e hanno quindi gli stessi autovalori, allora

$|A^{-1}{|}_2=\frac{1}{{\lambda }_{min}(A_{h}A)}.$

Allora, se $A$ è non singolare,

$K_2(A)=\sqrt{\frac{{\lambda }_{max}(A_{h}A)}{{\lambda }_{min}(A_{h}A)}}.$

Se $A_h=A$, allora

$K_2(A)=\frac{max|\lambda (A)|}{min|\lambda (A)|}$

e se $A$ è anche definita positiva

$K_2(A)=\frac{{\lambda }_{max}(A)}{{\lambda }_{min}(A)}$

Stime del numero di condizionamento

Consideriamo una norma matriciale indotta. Vale la seguente proprietà: ${\rho }^{1/2}(A)\le |A|$, allora

$K(A)=|A|\ast |A^{-1}|\ge \rho (A)\ast \rho (A^{-1})=\frac{max|\lambda (A)|}{min|\lambda (A)|}$

Determiniamo le matrici con numeri di condizionamento molto alti o molto bassi.

Esempio 2.4 [matrice di Hilbert]

La matrice di Hilbert ha entrate della forma

$H_{ij}=\frac{1}{i+j-1}$

Ad esempio, in dimensione 3

$H_3=\begin{array}{ccc}1& 1/2& 1/3\\ 1/2& 1/3& 1/4\\ 1/3& 1/4& 1/5\end{array}$

Nella tabella rappresento l'aumentare del numero di condizionamento al crescere di $n$:

$\begin{array}{cc}\text{valore di n}& \text{condizionamento}\\ 2& 10^0\\ 3& 10^3\\ 5& 10^5\\ 6& 10^7\\ 10& 10^{13}\end{array}$

Esempio 2.5

Tra le matrici per cui $K(A)=1$ c'è la matrice identica.

$K_2(id)=1$

Anche le matrici tali che

$A_{h}A=A{A}_h=id$

cioè tali che

$A^{-1}=A_h$

sono perfettamente condizionate, infatti:

$|A{|}_2=1$

$|A^{-1}{|}_2=1$

Osservazione 2.2

Vale la proprietà

$det\alpha A={\alpha }^{n}detA,A\in {\mathrm{M}\mathrm{a}\mathrm{t}}_n$

$det[0.1\ast A]=(0.1{)}^{n}A\to 0$

ma la matrice non è singolare.

Il determinante non è una buona misura della singolarità della matrice.