Numeri Macchina e Errori

Cheatsheet Content

### Rappresentazione dei Numeri Reali Sia $\beta \in \mathbb{N}, \beta \geq 2$, allora ogni numero reale $x, x \neq 0$, può essere rappresentato univocamente in base $\beta$ nel seguente modo: $$x = \pm \beta^p \sum_{i=1}^{\infty} d_i \beta^{-i}$$ dove $p \in \mathbb{Z}$, e i valori $d_i \in \mathbb{N}$ (detti **cifre**), verificano le seguenti proprietà: 1. $d_i \in \{0, 1, 2, 3, \ldots, \beta - 1\}$; 2. $d_1 \neq 0$; 3. le cifre $d_i$ non sono definitivamente uguali a $\beta - 1$. ### L'insieme dei numeri macchina Assegnati i numeri $\beta, t, m, M \in \mathbb{N}$ si definisce **insieme dei numeri di macchina con rappresentazione normalizzata in base $\beta$ con $t$ cifre significative**: $$F(\beta, t, m, M) = \left\{ x \in \mathbb{R} : x = \pm \beta^p \sum_{i=1}^{t} d_i \beta^{-i} \right\} \cup \{0\}$$ dove: 1. $t \geq 1, \beta \geq 2, m, M > 0$; 2. $d_i \in \{0, 1, \ldots, \beta - 1\}$; 3. $d_1 \neq 0$; 4. $p \in \mathbb{Z}, -m \leq p \leq M$. È stato necessario aggiungere il numero zero all'insieme in quanto non ammette rappresentazione in base normalizzata. #### Locazione di memoria Osserviamo che un elaboratore la cui memoria abbia le seguenti caratteristiche: - $t$ campi di memoria per la mantissa, ciascuno dei quali può assumere $\beta$ differenti configurazioni (e perciò può memorizzare una cifra $d_i$), - un campo di memoria che può assumere $m + M + 1$ differenti configurazioni (e perciò può memorizzare i differenti valori $p$ dell'esponente), - un campo che può assumere due differenti configurazioni (e perciò può memorizzare il segno $+$ o $-$), #### Overflow e Underflow Se $p M$ allora vuol dire che $x$ è più grande del più grande numero di macchina e in questo caso si dice che si è verificato un **overflow** (anche in questo caso l'elaboratore si ferma e segnala l'overflow, anche se tale eccezione può anche essere gestita via software in modo tale che l'elaborazione continui). ### Approssimazione di numeri reali Sia un numero reale $x = \pm \beta^p \sum_{i=1}^{n} d_i \beta^{-i}$ con l'esponente $-m \leq p \leq M$ ma $n > t$ ed inoltre esiste un indice $k, t 0$ si ha che $$tr(x) = a$$ mentre se $x \geq (a+b)/2$ allora $$arr(x) = b$$ altrimenti $$arr(x) = a$$ L'arrotondamento è un'operazione che fornisce sicuramente un risultato più preciso, ma può dar luogo ad overflow. Infatti se $x = 0.dddd \ldots ddd \times \beta^M$ con $d = \beta - 1$, allora $arr(x) = 1.0 \beta^M = 0.1 \beta^{M+1} \notin F(\beta, t, m, M)$. La rappresentazione di $x \in \mathbb{R}$ attraverso $\tilde{x} \in F(\beta, t, m, M)$ si dice **rappresentazione in virgola mobile di $x$** o **rappresentazione floating point**, con troncamento se $\tilde{x} = tr(x)$, con arrotondamento se $\tilde{x} = arr(x)$. Talvolta il numero macchina che rappresenta $x \in \mathbb{R}$ viene indicato con $fl(x)$. ### Errore Assoluto ed Errore Relativo Una volta definite le modalità per associare ad un **numero reale $x$** la sua **rappresentazione macchina $\tilde{x}$** si tratta di stabilire l'errore che si commette in questa operazione di approssimazione. Si possono definire due tipi di errori, l'errore assoluto e l'errore relativo. Se $x \in \mathbb{R}$ ed $\tilde{x}$ è una sua approssimazione allora si definisce **errore assoluto** la quantità $$E_a = |\tilde{x} - x|$$ mentre se $x \neq 0$ si definisce **errore relativo** la quantità $$E_r = \frac{|\tilde{x} - x|}{|x|}$$ #### Stima dell'errore di rappresentazione Per maggiorare l'errore relativo nel caso del troncamento osserviamo che $$|tr(x) - x| ### Aritmetica di Macchina Se $x, y \in F(\beta, t, M)$ non è detto che il risultato di un'operazione aritmetica tra $x$ e $y$ non sia un numero macchina. Per esempio se $x = 0.11 \times 10^0$ e $y = 0.11 \times 10^{-2}$ in $F(10, 2, m, M)$, allora $x+y = 0.1111 \notin F(10, 2, m, M)$. Si pone il problema di definire le operazioni aritmetiche in modo tale che ciò non accada. Se $\circ$ è una delle quattro operazioni aritmetiche di base, l'operazione macchina corrispondente $\circledcirc$ è definita come: $$x \circledcirc y = fl(x \circ y)$$ Questa operazione macchina deve soddisfare la relazione: $$x \circledcirc y = (x \circ y)(1+\varepsilon), \quad \text{con } |\varepsilon| ### Definizione di Molteplicità di una Radice **Definizione 2.1.1** Sia $f \in C^r([a,b])$ per un intero $r > 0$. Una radice $\alpha$ di $f(x)$ si dice di **molteplicità r** se $$\lim_{x \to \alpha} \frac{f(x)}{(x - \alpha)^r} = \gamma, \quad \gamma \neq 0, \gamma \neq \pm\infty. \quad (2.1)$$ Se $\alpha$ è una radice della funzione $f(x)$ di molteplicità $r$ allora risulta $$f(\alpha) = f'(\alpha) = \ldots = f^{(r-1)}(\alpha) = 0, \quad f^{(r)}(\alpha) = \gamma \neq 0.$$ ### Il Metodo di Bisezione Sia $f : [a, b] \to \mathbb{R}$, $f \in C([a, b])$, e sia $f(a)f(b) ### Il Metodo della Falsa Posizione Una variante del metodo delle bisezioni è il metodo della falsa posizione. Partendo da una funzione $f(x)$ continua in un intervallo $[a, b]$ tale che $f(a)f(b) 0 \end{cases}$$ Ad un generico passo $k$ si calcola $$c_{k+1} = a_k - f(a_k)\frac{b_k - a_k}{f(b_k) - f(a_k)}$$ e si pone $$[a_{k+1}, b_{k+1}] = \begin{cases} [a_k, c_{k+1}] & \text{se } f(a_k)f(c_{k+1}) 0 \end{cases}$$ Anche per questo metodo è possibile dimostrare la convergenza nella sola ipotesi di continuità della funzione $f(x)$. ### Metodo di Newton-Raphson Nell'ipotesi che $f$ sia derivabile ed ammetta derivata prima continua allora un altro procedimento per l'approssimazione dello zero della funzione $f(x)$ è il **metodo di Newton-Raphson**, noto anche come **metodo delle tangenti**. A partire dall'approssimazione $x_0$ si considera la retta tangente la funzione $f$ passante per il punto $P_0$ di coordinate $(x_0, f(x_0))$. Si calcola l'ascissa $x_1$ del punto di intersezione tra tale retta tangente e l'asse delle $x$ e si ripete il procedimento a partire dal punto $P_1$ di coordinate $(x_1, f(x_1))$. Per ricavare la funzione iteratrice del metodo consideriamo l'equazione della retta tangente la funzione $y = f(x)$ nel punto di coordinate $(x_k, f(x_k))$ $$y - f(x_k) = f'(x_k)(x - x_k).$$ Posto $y = 0$ ricaviamo l'espressione di $x$ che diventa il nuovo elemento della successione $x_{k+1}$: $$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} \quad k = 0, 1, 2, \ldots \quad (2.12)$$ che equivale, scegliendo in (2.7) $h(x) = f'(x)$, al metodo di iterazione funzionale in cui la funzione $g(x)$ è $$g(x) = x - \frac{f(x)}{f'(x)}. \quad (2.13)$$ Per la convergenza e l'ordine del metodo di Newton-Raphson vale il seguente teorema. ### Il Metodo della Direzione Costante Se applicando ripetutamente la formula di Newton-Raphson accade che la derivata prima della funzione $f(x)$ si mantiene sensibilmente costante allora si può porre $$M = f'(x)$$ e applicare la formula $$x_{k+1} = x_k - \frac{f(x_k)}{M} \quad (2.16)$$ anziché la (2.12). La (2.16) definisce un metodo che viene detto **metodo di Newton semplificato** oppure **metodo della direzione costante** in quanto geometricamente equivale all'applicazione del metodo di Newton in cui anziché prendere la retta tangente la curva $f$ si considera la retta avente coefficiente angolare uguale a $M$. La funzione iteratrice del metodo è $$g(x) = x - \frac{f(x)}{M}$$ ed il metodo è convergente se $$|g'(x)| = \left|1 - \frac{f'(x)}{M}\right| ### Il Metodo della Secante Il **metodo della secante** è definito dalla relazione $$x_{k+1} = x_k - f(x_k)\frac{x_k - c}{f(x_k) - f(c)}$$ dove $c \in [a,b]$. Il significato geometrico di tale metodo è il seguente: ad un generico passo $k$ si considera la retta congiungente i punti di coordinate $(x_k, f(x_k))$ e $(c, f(c))$ e si pone $x_{k+1}$ pari all'ascissa del punto di intersezione di tale retta con l'asse $x$. Dalla formula si evince che la funzione iteratrice del metodo è $$g(x) = x - f(x)\frac{x - c}{f(x) - f(c)}.$$ In base alla teoria vista nei paragrafi precedenti il metodo ha ordine di convergenza 1 se $g'(\alpha) \neq 0$. Può avere ordine di convergenza almeno 1 se $g'(\alpha) = 0$. Tale eventualità si verifica se la tangente alla curva in $\alpha$ ha lo stesso coefficiente angolare della retta congiungente i punti $(\alpha, 0)$ e $(c, f(c))$. Poiché il metodo delle secanti ha lo svantaggio di avere, solitamente, convergenza lineare mentre il metodo di Newton-Raphson, pur avendo convergenza quadratica, ha lo svantaggio di richiedere, ad ogni passo, due valutazioni di funzioni: $f(x_k)$ ed $f'(x_k)$, quindi se il costo computazionale di $f'(x_k)$ è molto più elevato rispetto a quello di $f(x_k)$ può essere più conveniente l’uso di metodi che necessitano solo del calcolo del valore della funzione $f(x)$.