Errore inerente

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

Norma vettoriale

È una funzione da f:RnR 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. 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

image/universita/ex-notion/Norme e Condizionamento/Untitled 1

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

    image/universita/ex-notion/Norme e Condizionamento/Untitled 2

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.

image/universita/ex-notion/Norme e Condizionamento/Untitled 3

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

    image/universita/ex-notion/Norme e Condizionamento/Untitled 4 image/universita/ex-notion/Norme e Condizionamento/Untitled 5 image/universita/ex-notion/Norme e Condizionamento/Untitled 6