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. $\lVert x \rVert \geq 0$ per ogni $x \in \mathbb{R}^{n}$
2. $\lVert x \rVert = 0 \iff x = 0$
3. $\lVert \alpha x \rVert = \lvert \alpha \rvert \lVert x \rVert$ 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}, \lVert x + y \rVert \leq \lVert x \rVert + \lVert y \rVert$.

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) \leq 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\leq i \leq 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|| \leq || \cdot || _x \leq 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|| = \sup_{x \neq 0} \dfrac{||Ax||}{||x||} = ||Ay||, y = \dfrac{x}{||x||} $$

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

$$ ||A||_\infty = \max_{1 \leq i \leq m} \sum_{j = 1}^n|a_{ij}| $$

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

$$ ||A||_1 = \max_{j} \sum_{i = 1}^n|a_{ij}| $$

Norma 2, o norma spettrale:

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

Con $A^TA$ simmetrica e semidefinita positiva. con $\Lambda$ gli autovalori di $A^TA$ 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^2_{ij}} $$

$||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

$$ \dfrac{||\Delta x||}{||x||} \leq k(A) \dfrac{||\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}|| \geq ||AA^{-1}|| = ||I|| = 1 $$

• Slide ricavo relazioni condizionamento