###### tags: `Calcolo Numerico`

# **Calcolo Numerico ed Analisi degli Errori**

## Definizione Calcolo Numerico
Branca della matematica che fornisce strumenti efficienti per il calcolo numerico di quantità continue sono utili per poter risolvere problemi non risolvibili con la matematica simbolica.

> Es. di quantità continua: soluzione di un’equazione

## Calcolo simbolico VS Calcolo numerico
Dall'equazione determiniamo un certo risultato. Questo risultato può essere un risultato simbolico, oppure un risultato determinato mediante una semplificazione o un’approssimazione data da un’iterazione.

L’approssimazione determinata dal calcolo numerico risulta un sistema meno elegante, ma può essere utile in quanto rappresenta un risultato generale e non un risultato che può rappresentare anche una soluzione piuttosto complessa da utilizzare.

Inoltre il risultato simbolico non è sempre rappresentabile mediante un effettivo simbolo
> (ad esempio ci sono equazioni che non hanno nessuna soluzione reale).

Infatti secondo il ***th. di Ruffini-Abel***:
`Non esiste una formula che permetta di trovare le soluzioni di tutte le equazioni di quinto grado e che utilizzi solamente le operazioni elementari e le radici.`

Con il calcolo numerico è invece possibile determinare un generico risultato approssimato per qualsiasi quantità continua. Strumenti del calcolo numerico:
1. teorie matematiche
1. algoritmi matematici (analisi e progettazione)

## Differenza tra analisi matematica e analisi numerica

L’analisi matematica ha come scopo quello di determinare una formula ai problemi continui. Però è necessario anche un algoritmo che è basato sul funzionamento finito di un calcolatore.
Pertanto si cerca di "trattare" una quantità continua (infinita) con strumenti finiti Facendo ciò però si determinano risultati fatti di margini di errore che non devono essere troppo grandi ma l’algoritmo dovrà commettere un errore più piccolo possibile.

## Algoritmo efficiente

1. numericamente stabile, cioè non propagare gli errori
2. avere un basso costo computazionale in tempo

## Relazioni tra calcolo numerico e analisi matematica

In entrambi i casi si studia il continuo, ma con differenti modalità.
In entrambi i casi si utilizzano assiomi e teoremi.

## Relazioni tra calcolo numerico e matematica discreta

Si studiano cose in comune con lo stesso linguaggio (assiomi e teoremi).

## Relazioni tra calcolo numerico e algoritmi

Entrambi hanno l’obiettivo di fornire algoritmi efficienti. In algoritmi si calcolano però quantità discrete non continue.


Dal mondo reale si hanno dei problemi. Questi problemi vengono modellizzati e studiati con vari concetti matematici al fine di risolvere i problemi stessi. Queste applicazioni si effettuano in ambiti come:

1. L’informatica
2. Grafica vettoriale e 3d
3. Multimedialità
4. Discipline scientifiche
5. Elementi tecnici nello sport

Si parla di applicazioni di algoritmi determinati attraverso il calcolo numerico

## Analisi degli Errori

Che cos'è un numero reale? I numeri reali sono limiti di sequenze di numeri razionali che possono essere approssimati in numeri razionali.

I numeri razionali sono infiniti ma possiamo trattarli solamente con un set finito di numeri

`PROBLEMA: Seleziona un num. finito di rappresentanti per approssimare i numeri reali.`

Si definisce una distribuzione uniforme su cui possiamo fare delle approssimazioni.
La distribuzione uniforme costituisce il set di numeri macchina che sono definiti da i due estremi(ε).

Dall'approssimazione di numero reale si va in contro a degli errori che vengono commessi quando si approssima con valori all'infuori dell'intervallo.
All'interno del set le approssimazioni sono corrette, al di fuori di esso invece non si hanno corrette approssimazioni.
Ovviamente si deve considerare che nel fare delle approssimazioni si creano degli errori che devono essere relativamente piccoli, solitamente alla scelta dei set dei numeri razionali da approssimare a numeri reali ci dobbiamo ricordare che non lavoreremo troppo spesso con numeri molto grandi.

Ci sono due tipi di errori. gli errori assoluti e gli errori relativi:

1. errore assoluto $\bar x - x$ approssimazione di meno la stessa
2. errore relativo $(\bar x - x)/x$ rapporto tra errore assoluto e $x$

Gli errori assoluti possono creare dei problemi, infatti:

> -> per numeri grandi si hanno corrette cifre
> -> per numeri piccoli si hanno sbagliate cifre


L’obiettivo che si deve raggiungere è quello di avere un errore relativo più piccolo possibile

**Teorema della rappresentazione dei numeri reali**

Dato $x$ appartenente ad $R - [0]$ e dato $B \ge 2$ una base numerica, allora esiste un unico $p$ appartenente a $Z$ e una sequenza di cifre per cui:
1. Le cifre devono andare da $0$ a $B-1$
2. la prima cifra dopo la virgola deve essere diversa da $0$
3. le cifre dopo la virgola non devono essere definitivamente uguali a $B-1$

Tale che:
$$sign(x)*B^p *\sum_{i = 1}^\infty B^{-1}*d^i$$

Il numero $\sum_{i = 1}^\infty B^-1 *d^i$ è detto `mantissa`

$F(B, t, m, M)$ rappresenta l'insieme finito dei numeri a virgola mobile che vogliamo rappresentare. In questo insieme:

1. $B$ rappresenta la base numerica
2. $t$ rappresenta il numero di cifre della mantissa
3. $m$ ed $M$, rappresentano gli esponenti piu' grandi e piu' piccoli che si possono avere nella normalizzazione

$$F(B, t, m, M) = [0] \cup [+-B^p*\sum_{i=1}^t B^{-i}*di, m\le p \le M, 0 \le d_i \le B, i = 1...t, d_1 \not= 0 $$

Usiamo questo modo per rappresentare i numeri reali.
Dato $S = [x \in R : w \le x \le omega]$ così definiamo la funzione di rappresentazione:
$$fl : R \to F \cup [+- \infty]$$
Con una delle due regole, dove $x = B^p \sum_{i=1}^t B^{-i}d_i \in S$:
1. Troncamento $\bar x = fl(x) = B^p\sum_{i = 1}^t B^{-i}d_i$
2. Arrotondamento $\bar x = fl(x)$ il troncamento di $x + B^{p-t-1}/2$

per i numeri negativi è lo stesso ragionamento!

## Precisione Macchina
Definiamo precisione macchina come $u = B^{-t+1}/2$ nel caso dell'arrotondamento

**TH:**
Definendo $x \in S$:
$$\vert \frac{fl(x)-x}{x}\vert \le u$$

L'insieme $F$ ha delle proprietà algebriche. Esso Esso non è un insieme di somma, cioè la somma di due numeri macchina non per forza rientra in $F$ in quanto si andrebbe a sforare il limite superiore e inferiore di quest’ultimo.

Noi possiamo assumere che esiste una somma tra valori in floating point tale che non genera un overflow. La stessa cosa si fa con la moltiplicazione, differenza e divisione.
Le operazioni con i floating point hanno alcune proprietà:

$x⊕y = y⊕x \to$ commutatività della somma
$x⊙y = y⊙x \to$ commutatività del prodotto
$x⊘x = 1$

Non sono valide:
1. l’associatività di somma e prodotto
2. la legge di distribuzione
3. semplificazione
4. legge di annullamento del prodotto

## Problemi Ben Posti

con il calcolo numerico possiamo risolvere solamente problemi ben posti.
un problema è composto da tre parti:
1. dati
2. incognite
3. condizioni

Alcuni esempi di problemi ben posti sono:
1. problemi di sistemi lineari
2. equazione polinomiale
3. integrali

In ogni caso le incognite sono funzioni di dati, (una soluzione di problemi valutazione di una funzione) nei casi pratici possiamo solo fornire una approssimazione i problemi ben posti hanno:
1. hanno una soluzione
2. la soluzione è unica
3. la soluzione dipende continuamente dai dati

meno ovvio il fatto che la soluzione dipenda continuamente dai dati ci fa osservare che:
I dati in numeri reali sono affetti da errori la computazione è fatto di un aritmetica finita e che ci sono errori di arrotondamento
Siccome ci si occupa di problemi continui (infiniti), noi dobbiamo fare in modo di passare dal problema “grosso” al problema piccolo.
Questo è possibile solo mediante l'approssimazione ad una dimensione finita (discretizzazione) e al passaggio da una generica funzione a una funzione razionale. Questa funzione razionale valutata in aritmetica finita è definito algoritmo numerico.

## Errore Analitico

1. Errore nella serie di Taylor
2. Errore dato dall'approssimazione di Integrali

Valutare una funzione razionale per un numero reale $f(x)$ ma $x$ può essere $\bar x = fl(x)$
$$\vert \frac{\bar x - x}{x}\vert \le u$$

Quindi lavoro con $f(\bar x)$ facendo il limite con $\bar x \to x$ possiamo definire come la continuità
$$\lim_{\bar x\to x}f(\bar x) = f(x)$$
Quando $\bar x$ si avvicina a $x$ anche $f(\bar x)$ si avvicina a $f(x)$
Possiamo definire come errore assoluto sulla valutazione
$$\frac{\vert f(\bar x)- f(x)\vert}{\vert \bar x - x \vert} $$

## Errore per delle funzioni Razionali

Per le funzioni Razionali Esistono due tipi di errore.
Sia $f:R^n \to R$ razionale, che è definito come $f = p/q$ con $p$ e $q$ polinomiali
* **Errore Inerente**: errore dato dal fatto che io non valuto $f(x)$ ma $f(\bar x)$. Pertanto non viene valutato un dato esatto.
$$ ε in = \frac{f(\bar x)- f(x)}{f(x)}, f(x) \not = 0$$
* **Errore Algoritmico**: non viene valutato $f(\bar x)$ ma un'altra funzione $\bar f(\bar x)$ dato che le operazioni di f sono cmputate da operazioni macchina che approssimano.
$$ ε alg = \frac{\bar f(\bar x)- f(\bar x)}{f(\bar x)}, f(\bar x) \not = 0 $$

L'errore inerente può essere definito solo per funzioni non razionali.
L'errore algoritmico può essere definito solo per funzioni elementari, trattati come operazioni.

> Se l’errore inerente è relativamente piccolo possiamo dire che il problema è ben condizionato. Al contrario mal condizionato

> Se l’errore algoritmico è relativamente piccolo diciamo che l’algoritmo è numericamente stabile. Al contrario numericamente instabile

si può avere maggiore precisione assumendo $u \to 0$ dicendo che:
$$\lim_{u\to 0}ε alg,in = 0$$

* **Errore Totale**: (detto anche in avanti):
$$ ε tot = \frac{\bar f(\bar x)- f(x)}{f(x)}, f(x) \not = 0 $$

Ci da una genuina valutazione dell'errore preso in considerazione

> la situazione ideale è che $\vert ε tot \vert \le u$, dove $u$ è la precisione macchina

Ma in realtà è sufficiente che $\vert ε tot \vert \le M...u$, con M una costante

**TH**:
Sia $x \in R^n-[0]$ e $f: R^n \to R$ razionale con $f(x) \not = 0$ e $f(\bar x) \not = 0$, dove $\bar x = fl(x)$ allora:
$$ ε tot = ε in + ε alg + εin * εalg $$ la $εin*εalg$ ci da problemi ma se $εin$ e $εalg$ sono piccoli (tendono a zero se $u \to 0$) allora abbiamo: $$εtot = εin + εalg + o(u) \bar = εin + εalg$$

> $\bar =$ significa che al primo ordine per $u \to 0$ sono uguali

## Analisi Dell'errore

L’analisi dell'errore consiste nel mettere in relazione l’errore in avanti con l’errore nella rappresentazione. Le formule non possono essere utilizzate direttamente:
1. Per l'errore inerente si usa la derivazione
2. Per l’errore algoritmico si usano dei diagrammi di analisi

## Errore inerente
L'errore inerente è l'errore che si commette rappresentando un numero reale con un numero finito di cifre. Deve essere controllato (condizionato) in modo tale da evitare il propagarsi degli errori (stabilità numerica dell'algoritmo).

Per definizione, presa una funzione $f: R^n \to R$
$$ ε in = \frac{f(\bar x)- f(x)}{f(x)}, f(x) \not = 0 $$
se $x_i \not = 0$, for $i = 1...n$ vogliamo collegare εin con l'errore di rappresentazione
$$ ε_i = \frac{\bar x_i - x_i}{x_i} $$ e facciamo la solita assunzione che
$$ \vert ε_i \vert \le u$$

dove $u$ è la precisione macchina. Si ignora l’overflow e l’underflow per semplicità. Sfruttando la definizione, se l’ordine della funzione è limitata superiormente dalla precisione macchina , allora vuol dire che l’errore inerente è ben condizionato. Per l'uso pratico si usa il seguente teorema che rende il tutto più semplice.