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.

Definizione

Una norma vettoriale è una funzione da $\mathbb {C} ^{n}$ $\mathbb {R} ^{+}\smallsetminus 0$ tale che

1. $\vert {\boldsymbol {x}}\vert \geq 0$ e $\vert {\boldsymbol {x}}\vert =0\iff {\boldsymbol {x}}=0$
2. $\vert \alpha {\boldsymbol {x}}\vert =|\alpha |*\vert {\boldsymbol {x}}\vert$ (omogeneità)
3. $\vert {\boldsymbol {x}}+{\boldsymbol {y}}\vert \leq \vert {\boldsymbol {x}}\vert +\vert {\boldsymbol {y}}\vert$ (disuguaglianza triangolare)

Esempio 2.1

Esempi di norme sono:

1. $\vert {\boldsymbol {x}}\vert ={\sqrt {\sum _{i=1}^{n}x_{i}^{2}}}\quad {\hbox{norma 2}}$
2. $\vert {\boldsymbol {x}}\vert =\sum _{i=1}^{n}|x_{i}|\quad {\hbox{norma 1}}$
3. $\vert {\boldsymbol {x}}\vert ^{\infty }=\max {i}|x_{i}|\quad {\hbox{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è

$\forall \varepsilon >0\,\exists \delta \,t.c.\vert {\boldsymbol {x}}-{\boldsymbol {y}}\vert <\delta \,\longrightarrow \vert {\boldsymbol {x}}\vert -\vert {\boldsymbol {y}}\vert \leq \varepsilon$

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 $\vert {\boldsymbol {x}}\vert _{1}$ e $\vert {\boldsymbol {x}}\vert _{2}$, con $n$ fissato. Allora esistono $\alpha ,\beta \in \mathbb {R}$ con $0<\alpha <\beta$ tali che

$\alpha \vert {\boldsymbol {x}}\vert _{2}\leq \vert {\boldsymbol {x}}\vert _{1}\leq \beta \vert {\boldsymbol {x}}\vert _{2}$

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

Proprietà 3: per ogni ${\boldsymbol {x}}\in \mathbb {C} ^{n}$, considerate le norme 1,2 e $\infty$ dell'esempio precedente, si ha:

$\vert {\boldsymbol {x}}\vert ^{\infty }\leq \vert {\boldsymbol {x}}\vert _{2}\leq {\sqrt {n}}\vert {\boldsymbol {x}}\vert ^{\infty }$

$\vert {\boldsymbol {x}}\vert _{2}\leq \vert {\boldsymbol {x}}\vert _{1}\leq {\sqrt {n}}\vert {\boldsymbol {x}}\vert _{2}$

e, unendo le due relazioni:

$\vert x\vert ^{\infty }\leq \vert {\boldsymbol {x}}\vert _{2}\leq \vert {\boldsymbol {x}}\vert _{1}$

Norma matriciale

Definizione

Una norma matriciale è una funzione $\colon \mathbb {C} ^{n^{2}}\to \mathbb {R} ^{+}\smallsetminus 0$ tale che

1. $\vert X\vert =0$ solo se $X$ è la matrice nulla
2. $\vert \alpha X\vert =|\alpha |\vert X\vert$
3. $\vert X+Y\vert \leq \vert X\vert +\vert Y\vert$
4. $\vert XY\vert \leq \vert X\vert *\vert Y\vert$

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<\vert A\vert *\vert B\vert$

Relazioni tra norme vettoriali e norme matriciali

Definizione

La norma $\vert \dots \vert _{\ast }$ è una norma matriciale compatibile con una certa norma vettoriale $\vert \dots \vert _{v}$ se

$\vert A{\boldsymbol {x}}\vert _{v}\leq \vert A\vert _{\ast }*\vert {\boldsymbol {x}}\vert _{v},\forall {\boldsymbol {x}}\in \mathbb {C} ^{n},\,\forall A\in \mathbb {C} ^{n^{2}}$

Definizione

Definiamo la norma matriciale indotta da una norma vettoriale fissata come

$\vert A\vert =\max _{{\boldsymbol {x}}\in \mathbb {C} ^{n}\,t.c.\,\vert {\boldsymbol {x}}\vert _{v}=1}\,\vert A{\boldsymbol {x}}\vert _{v}$

equivalentemente

$\vert A\vert =\sup _{{\boldsymbol {x}}\in \mathbb {C} ^{n}}\vert {\frac {A{\boldsymbol {x}}}{\vert A{\boldsymbol {x}}\vert _{v}}}\vert _{v}$

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

Dim. Se ${\boldsymbol {x}}=0$, la definizione di norma matriciale compatibile è verificata. Se ${\boldsymbol {x}}\neq 0$, si ha

$\vert A{\boldsymbol {x}}\vert _{v}={\frac {\vert A{\boldsymbol {x}}\vert _{v}}{\vert {\boldsymbol {x}}\vert _{v}}}*\vert {\boldsymbol {x}}\vert _{v}$

$=\vert {\boldsymbol {x}}\vert _{v}*\vert A{\frac {\boldsymbol {x}}{\vert {\boldsymbol {x}}\vert _{v}}}\vert _{v}=$

$=\vert {\boldsymbol {x}}\vert _{v}*\vert A{\boldsymbol {y}}\vert _{v}$

$\leq \vert {\boldsymbol {x}}\vert _{v}*\max _{{\boldsymbol {y}}\,t.c.\vert {\boldsymbol {y}}\vert _{v}=1}\vert A{\boldsymbol {y}}\vert _{v}$

$\leq \vert {\boldsymbol {x}}\vert _{v}*\vert A\vert$

cvd

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

Dim.

$\vert A\vert =\max _{{\boldsymbol {x}}\,t.c.\,\vert {\boldsymbol {x}}\vert =1}\vert A{\boldsymbol {x}}\vert _{v}$

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

$\leq \max _{{\boldsymbol {x}}\,t.c.\,\vert {\boldsymbol {x}}\vert _{v}=1}\vert A\vert ^{\ast }\vert {\boldsymbol {x}}\vert _{v}$

$\leq \vert A\vert ^{\ast }$

cvd

Norme matriciali indotte dalle principali norme vettoriali

Proprietà 5:

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

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

Definizione

Consideriamo $B\in \mathrm {Mat} _{n,n}$, allora

$\rho =\max _{i}|\lambda _{i}|,$

cioè il raggio spettrale è il massimo dei moduli degli autovalori della matrice.

Definizione

$A_{h}$ è la trasposta coniugata, cioè se $A$ ha elementi reali, si ha $(A_{h})_{ij}=A_{ji}$, mentre se $A\in {\mathcal {C}}$, $(A_{h})_{ij}={\bar {A}}_{ji}$.

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

${\begin{aligned}{\frac {1}{\sqrt {n}}}\vert A\vert ^{\infty }&\leq \vert A\vert _{2}&\leq {\sqrt {n}}\vert A\vert ^{\infty }\\{\frac {1}{\sqrt {n}}}\vert A\vert _{1}&\leq \vert A\vert _{2}&\leq {\sqrt {n}}\vert A\vert _{1}\\\max _{i,j}|A_{ij}|&\leq \vert A\vert _{2}&\leq \max _{i,j}|A_{ij}|???\\\vert A\vert _{2}&\leq {\sqrt {n}}\vert A\vert _{2}&\leq \vert A\vert ^{\infty }\end{aligned}}$

Osservazione 2.1

Se $A=A_{h}$, allora $\vert A\vert ^{\infty }=\vert A\vert _{1}$, e

$\vert A\vert _{2}=\rho ^{1/2}(A^{2}).$

ma siccome per gli autovalori vale la relazione $A{\boldsymbol {x}}=\lambda {\boldsymbol {x}}$, moltiplicando per $A$ ottengo:

$A^{2}{\boldsymbol {x}}=\lambda A{\boldsymbol {x}}=\lambda ^{2}{\boldsymbol {x}}$

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

Quindi

$\vert A\vert _{2}=\rho (A)$

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

$\vert A\vert _{2}=\max _{i}\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)\leq \vert A\vert ^{\ast }$.

Dim. Consideriamo la relazione

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

$\vert \lambda {\boldsymbol {x}}\vert =\vert A{\boldsymbol {x}}\vert _{v}$

$\longrightarrow |\lambda |\vert {\boldsymbol {x}}\vert _{v}=\vert A{\boldsymbol {x}}\vert _{v}$

$\longrightarrow |\lambda |=\vert A{\frac {\boldsymbol {x}}{\vert {\boldsymbol {x}}\vert _{v}}}\vert _{v}$

$|\lambda |\leq \max _{{\boldsymbol {v}}\,t.c.\,\vert {\boldsymbol {v}}\vert =1}\vert A{\boldsymbol {v}}\vert _{v}=\vert A\vert ^{\ast }$

cioè

$|\lambda |\leq \vert A\vert ^{\ast }$

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

$\rho (A)\leq \vert A\vert ^{\ast }$

cvd

Numero di condizionamento

Definizione

Si dice numero di condizionamento di una matrice rispetto ad una fissata norma la quantità

$K(A)=\vert A\vert *\vert A^{-1}\vert$

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

${\bar {P}}=P+\delta _{P},\,\longrightarrow \,g({\bar {P}})\simeq g(P)+J_{g}(P)*\delta _{P}$

Valutando l'errore relativo

$\vert E_{r}\vert ={\frac {|g({\bar {P}})-g(P)|}{|g(P)|}}$

$={\frac {\vert g(P)+J_{g}(P)*\delta _{P}-g(P)\vert }{\vert g(P)\vert }}$

$={\frac {\vert J_{g}(P)\delta _{P}\vert }{\vert g(P)\vert }}$

$\leq {\frac {\vert J_{g}(P)\vert *\vert \delta _{P}\vert }{\vert G(P)\vert }}$

Moltiplichiamo e dividiamo per $\vert P\vert$.

$E_{r}\leq \vert J_{g}(P)\vert *{\frac {\vert P\vert }{\vert g(P)\vert }}*{\frac {\vert \delta _{P}\vert }{\vert P\vert }}$

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}\leq \vert A^{-1}\vert *{\frac {\vert Ag(P)\vert }{\vert g(P)\vert }}*\varepsilon _{P}$

tenendo conto che la norma matriciale utilizzata è compatibile:

$E_{r}\leq \vert A\vert *{\frac {\vert A^{-1}\vert *\vert G(P)\vert }{\vert g(P)\vert }}*{\frac {\vert \delta _{P}\vert }{\vert P\vert }}$

e ponendo $\varepsilon _{x}={\frac {\vert \delta _{P}\vert }{\vert P\vert }}$ si ottiene

$E_{r}\leq K(A)*\varepsilon _{X}$

Proprietà del numero di condizionamento

Definizione

Il numero di condizionamento di una matrice $A$, supposta non singolare, è $K(A)=\vert A\vert *\vert A^{-1}\vert$. Si dice che $K(A)$ è infinito se $A$ è singolare.

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

Dim.

$K(A)=\vert A\vert *\vert A^{-1}\vert \geq \vert A^{-1}A\vert =\vert I\vert \geq 1$

cvd

Condizionamento spettrale

Definizione

Si definisce condizionamento spettrale la quantità $K_{2}(A)=\vert A\vert _{2}*\vert A^{-1}\vert _{2}$ (infatti $\vert A\vert _{2}=\rho ^{1/2}(A_{h}A)$ con $\rho$ raggio spettrale).

$A_{H}A$ è definita positiva, se $A$ è non singolare. Infatti ${\boldsymbol {x}}\cdot (A_{h}A{\boldsymbol {x}})={\boldsymbol {x}}\cdot (A_{H}{\boldsymbol {y}})\geq 0\forall {\boldsymbol {x}}\neq 0,\quad {\boldsymbol {y}}=A{\boldsymbol {x}}\neq 0$.

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

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

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

Inoltre

$\vert A^{-1}\vert _{2}=\rho ^{1/2}(A_{h}^{-1}A^{-1})=\rho ^{1/2}(AA_{h})^{-1}={\sqrt {\max \lambda _{i}((AA_{h})^{-1}}},\quad \lambda _{i}{\hbox{autovalori di}}(AA_{h})^{-1}$

Allora

$\vert A^{-1}\vert _{2}=\max _{i}[{\frac {1}{\lambda _{i}(AA_{H})}}]={\frac {1}{\lambda _{min}(AA_{h})}}$

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

$\vert A^{-1}\vert _{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)\leq \vert A\vert$, allora

$K(A)=\vert A\vert *\vert A^{-1}\vert \geq \rho (A)*\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}{\hbox{valore di n}}&{\hbox{condizionamento}}\\2&10^{0}\\3&10^{3}\\5&10^{5}\\6&10^{7}\\10&10^{13}\end{array}}$

Definizione

Se $K_{2}(A)=1$ si dice che la matrice è perfettamente condizionata.

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=AA_{h}=id$

cioè tali che

$A^{-1}=A_{h}$

sono perfettamente condizionate, infatti:

$\vert A\vert _{2}=1$

$\vert A^{-1}\vert _{2}=1$

Osservazione 2.2

Vale la proprietà

$\det \alpha A=\alpha ^{n}\det A,\quad A\in \mathrm {Mat} _{n}$

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

ma la matrice non è singolare.

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