Errore inerente

Bisogna cercare di generalizzare il concetto di errore e lo si fa con la norma

Norma vettoriale

È una funzione da $f:{\mathbb{R}}^n\to \mathbb{R}$ indicata con due barrette, questa funzione mi dà un concetto di distanza.

Proprietà della norma

Si definisce una norma una funzione che soddisfa queste proprietà

1. $\Vert x\Vert \ge 0$ per ogni $x\in {\mathbb{R}}^n$
2. $\Vert x\Vert =0⟺x=0$
3. $\Vert \alpha x\Vert =|\alpha |\Vert x\Vert$ per ogni $x\in {\mathbb{R}}^n$ e $\alpha \in \mathbb{R}$
4. Vale la disuguaglianza triangolare, ossia $\forall x,y\in {\mathbb{R}}^n,\Vert x+y\Vert \le \Vert x\Vert +\Vert y\Vert$.

L'intuizione che mi devo portare dietro è che dà una idea di grandezza, e ha links su topologie e spazi vettoriali. Se hai queste cose puoi poi andare a definire un concetto di convergenza. Moltissime funzioni soddisfano quelle proprietà.

Convessità

Analizzato meglio in Analisi di Convessità. Si può dimostrare tramite la proprietà 3 e 4 che la norma è una funzione convessa. Infatti sia $f$ la funzione che soddisfa le proprietà della norma (quindi effettivamente si può chiamare norma). Allora:

$$f(\theta x+(1-\theta )y)\le f(\theta x)+f((1-\theta )y)=\theta f(x)+(1-\theta )f(x)$$

Che finisce la dimostrazione.

Norma p

$$(\sum _{i=1}^n|x_i{|}^p{)}^{1/p}$$

Nel caso in cui $p=2$ si chiama norma euclidea o viva

Nel caso $p=1$ è la distanza di manhattan

Norma di chebichev

quando ho $p=+\infty$ è definita come ${\max }_{1\le i\le n}|x_i|$ e si indica con $||x|{|}_{\infty }$

Equivalenza fra le norme

Questo è un teorema che ci permette di asserire che più o meno tutte le norme hanno la stessa proprietà di definire il concetto di distanza fra due punti poiché

Siano $||\cdot ||,||\cdot |{|}_x$ due norme differenti, allora $\exists m,M:m||\cdot ||\le ||\cdot |{|}_x\le M||\cdot ||$, ma questo vale solo se siamo in un campo finito.

Norma matriciale

Proprietà

Vogliamo riprendere tutte le proprietà descritte per la norma vettoriale, in più vogliamo andare ad aggiungere un quinto punto ossia

Norma naturale (o indotte)

$$||A||=\underset{x\ne 0}{\sup }\frac{||Ax||}{||x||}=||Ay||,y=\frac{x}{||x||}$$

Considero solamente le righe, come se compattassi tutte le colonne in una

$$||A|{|}_{\infty }=\underset{1\le i\le m}{\max }\sum _{j=1}^n|a_{ij}|$$

Norma Indotta

La norma-1 indotta è molto simile, solo che ora compatto sulle colonne

$$||A|{|}_1=\underset{j}{\max }\sum _{i=1}^n|a_{ij}|$$

Norma Spettrale

Norma 2, o norma spettrale:

$$||A|{|}_2=\sqrt{\Lambda (A^{T}A)}$$

Con $A^{T}A$ simmetrica e semidefinita positiva. con $\Lambda$ gli autovalori di $A^{T}A$ Se $A$ ha rango massimo allora è definita positiva, che è il rango qui? Le norme dell’identità in tutte queste cose indotte è 1

Norma di frobenius

$$||A|{|}_F=\sqrt{\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}^2}$$

$||I|{|}_F=\sqrt{n}$

• Slide relazione fra le norme matriciali

  

Condizionamento

Vogliamo andare a definire il concetto di condizionamento per il sistema lineare.

Ossia vorremmo valutare quanto un piccolo cambiamento della matrice influisca sul risultato finale.

Chiamiamo come errore inerente la distanza fra il risultato vero e il risultato perturbato. Questo errore dipende fortemente da una natura dei dati in input (che sono mal condizionati)

Mal condizionamento

si verifica quando a piccoli cambi della matrice di partenza, si ha un grande errore nel risultato (potremmo dire ordini di grandezza diversi, solitamente questo è una cosa che non vorremmo che ci fosse)

E la differenza fra i risultati è un errore inerente, che dipende dai dati, ma non dall'algoritmo

Perturbazione e n-condizionamento

Vogliamo ora vedere quanto siano grandi gli effetti di una perturbazione su una matrice. si può dimostrare che

$$\frac{||\Delta x||}{||x||}\le k(A)\frac{||\Delta A||}{||A||}$$

Con $k(A)$ il numero di condizione della matrice, solamente più è grande più l'errore viene amplificato., se questo valore è sempre maggiore o uguale a 1 è non singolare.

$$k(A)=||A||\cdot ||A^{-1}||\ge ||A{A}^{-1}||=||I||=1$$

• Slide ricavo relazioni condizionamento

  

  

  

New Notes

A norm is the abstraction that lets you say "how big" without committing to which notion of size. You know the instances; here is the thing they're all instances of.

What a norm is

Let $V$ be a vector space over $\mathbb{K}$ ($=\mathbb{R}$ or $\mathbb{C}$). A norm is a function $|\cdot |:V\to [0,\infty )$ satisfying three axioms:

1. Definiteness: $|v|=0⟺v=0$. (Only the zero vector has zero length.)
2. Absolute homogeneity: $|\lambda v|=|\lambda |,|v|$ for every scalar $\lambda$ and vector $v$. (Scaling the vector scales its length by the same factor.)
3. Triangle inequality: $|u+v|\le |u|+|v|$.

That's the whole definition. Nonnegativity isn't a separate axiom — it falls out: $0=|0|=|v+(-v)|\le |v|+|-v|=2|v|$, so $|v|\ge 0$.

The reason any of this matters is that a norm induces a metric $d(u,v)=|u-v|$, hence a topology, hence a notion of convergence. That's the bridge — it's why "$\sum T^n$ converges" was even a meaningful statement in the Neumann discussion. A vector space with a norm is a normed space; if every Cauchy sequence converges, it's a Banach space.

The operator norm and its defining inequality

For a bounded linear $T:X\to Y$ over two Spazi vettoriali: $|T|;=;{\sup }_{x\ne 0}\frac{|Tx{|}_Y}{|x{|}_X}.$

The single fact that does all the work is the immediate consequence: $\boxed{|Tx|\le |T|\cdot |x|\text{for all }x}$

Proof of the boxed inequality. If $x\ne 0$, then $|Tx|/|x|$ is one of the quantities in the supremum, so $|Tx|/|x|\le |T|$, i.e. $|Tx|\le |T||x|$. If $x=0$, both sides are $0$. $\square$

Read $|T|$ as the smallest constant $C$ for which $|Tx|\le C|x|$ holds universally. Keep that reading in mind — it's what makes the final step clean.

Submultiplicativity

Claim. For composable bounded operators $S:Y\to Z$ and $T:X\to Y$, $|ST|\le |S|\cdot |T|.$

Proof. Take any $x\in X$ and apply the boxed inequality twice — first to $S$ on the vector $Tx$, then to $T$ on the vector $x$: $|(ST)x|=|S(Tx)|;\le ;|S|,|Tx|;\le ;|S|,|T|,|x|.$

So $|S|,|T|$ is a constant $C$ with $|(ST)x|\le C|x|$ for all $x$. But $|ST|$ is the smallest such constant. Hence $|ST|\le |S|,|T|$. $\square$

The whole proof is "apply the defining inequality twice and read off the constant." That's the entire idea — everything else is bookkeeping.