Errori nelle Funzioni Razionali

uni
Poiché come abbiamo detto un Calcolatore non ha a disposizione l’astrazione delle infinite cifre sappiamo di avere bisogno di arrotondamento, a monte e a valle (Numeri di Macchina,Rappresentazione in Virgola Mobile).

Quello che si fa su un calcolatore infatti è approssimare i dati ed approssimare il risultato dell’operazione se questo non rientra in $F(\beta ,mL,U)$.
Eg. $x+y\to x\oplus y=Rn(x+y)$.

Così facendo ovviamente introduciamo errori.

Studiamo quindi ora come calcolare l’errore durante il calcolo di una Funzione Razionale $f:{\mathbb{R}}^n\to \mathbb{R}$ nel punto$P_0=(x_1^{(0)},x_2^{(0)},\dots ,x_n^{(0)})\in {\mathbb{R}}^n$ dove le $x$ sono componenti del punto in $n$ dimensioni.

Fonti dell’Errore

1. $P_0$ potrebbe non appartenere a $F(\beta ,m,L,U)$ quindi viene approssimato, componente per componente, con $RN(P_0)=P_1$.
2. $\tilde{f}$ viene “tradotta” in una funzione $f_a$ in aritmetica floating point, quindi in un polinomio che coinvolge operazioni floating point ($\oplus ,\ominus ,\odot ,\oslash$).

In sostanza noi vorremmo calcolare $f(P_0)$ ma in realtà calcoliamo $f_a(P_1)$

Esempio

calcoliamo $e^{\pi }$:

1. approssimiamo con Formula di Taylor: $e^x\approx 1+x+\frac{x^2}{2}=\tilde{f}(x)$ (vedi Errori nelle Funzioni Non Razionali)
2. $RN(\pi )=3,1415=P_1$
3. “traduco” ${\tilde{f}}_a(P_1)=1\oplus (P_1((P_1\odot P_1)\oslash 2))$

Errore Totale

data $f:{\mathbb{R}}^n\to \mathbb{R},P_0\in {\mathbb{R}}^n$ e un algoritmo: l’Errore Totale è dato da $\begin{array}{c}\\ {\delta }_f={\tilde{f}}_a(P_1)-f(P_0)\\ \text{con}{P}_1=Rn(P_0)\end{array}$

Errori Algoritmico e Inerente

L’Errore Assoluto Totale (${\delta }_f$) è definito come:${\delta }_f={\tilde{f}}_a(P_1)-f(P_0)=\underset{{\delta }_a}{\underbrace{{\tilde{f}}_a(P_1)-f(P_1)}}+\underset{{\delta }_d}{\underbrace{f(P_1)-f(P_0)}}={\delta }_a+{\delta }_d$
${\delta }_a$ = Errore Assoluto Algoritmico
${\delta }_d$ = Errore Assoluto Inerente (ai dati)

Allo stesso modo definiamo l’Errore Relativo Totale (${ϵ}_f$), ricordandoci che $ϵ=\frac{\delta }{f(P_0)}$ :$\begin{array}{c}{ϵ}_f=\frac{{\delta }_f}{f(P_0)}=\frac{f_a(P_1)-f(P_0)}{f(P_0)}=\frac{f_a(P_1)-f(P_1)}{f(P_0)}+\underset{{ϵ}_d}{\underbrace{\frac{f(P_1)-f(P_0)}{f(P_0)}}}=\\ =\frac{f_a(P_1)-f(P_1)}{f(P_1)}\cdot \frac{f(P_1)}{f(P_0)}+{ϵ}_d={ϵ}_a\cdot (1+\frac{f(P_1)-f(P_0)}{f(P_0)})+{ϵ}_d=\\ ={ϵ}_a\cdot (1+{ϵ}_d)+{ϵ}_d={ϵ}_a+{ϵ}_d+\underset{\ll \min \{{ϵ}_a,{ϵ}_d\}}{\underbrace{{ϵ}_a{ϵ}_d}}={ϵ}_a+{ϵ}_d\end{array}$
${ϵ}_a$ = Errore Relativo Algoritmico
${ϵ}_d$ = Errore Relativo Inerente

Tips: i termini di grado superiore al primo durante un calcolo di errori li elimino perché significherebbe avere un errore irrilevante rispetto agli altri termini.

In generale per limitare $|{\delta }_f|$ si cercheranno disuguaglianze del tipo:$|{\delta }_a|<{\tau }_1,|{\delta }_d|<{\tau }_2⟹|{\delta }_f|<{\tau }_1+{\tau }_2$

Errore Inerente

• Assoluto: $f(P_1)-f(P_0)$
• Relativo: $\frac{f(P_1)-f(P_0)}{f(P_0)}$
  Possiamo definirlo anche così:
• Assoluto$\begin{array}{c}{\delta }_d=f(P_1)-f(P_0)={\sum }_{j=1}^m\underset{A_j}{\underbrace{\frac{\partial f}{\partial x_j}(P_0)}}\cdot {\delta }_j={\sum }_{j=1}^m{A}_j\cdot {\delta }_j\\ \text{con}\\ {\delta }_{x_j}:=x_j^{(1)}-x_j^{(0)}=x_j^{(0)}\cdot U\\ A_j=\text{Coefficienti di Amplificazione dell’errore assoluto}=\frac{\partial f}{\partial x_j}(P_0)\\ \text{calcolato come}|A_j|={\sup }_{x_j\in D}|\frac{\partial f}{\partial x_j}(x)|\end{array}$
• Relativo${ϵ}_d=\frac{{\delta }_d}{f(P_0)}=\frac{{\sum }_{j=1}^m\frac{\partial f}{\partial x_j}(P_0)\cdot {\delta }_j}{f(P_0)}={\sum }_{j=1}^n\underset{{\rho }_j}{\underbrace{\frac{\partial f}{\partial x_j}(P_0)\cdot \frac{x_j^{(0)}}{f(P_0)}}}\cdot \underset{{ϵ}_j}{\underbrace{\frac{x_j^{(1)}-x_j^{(0)}}{x_j^{(0)}}}}={\sum }_{j=1}^m{\rho }_j\cdot {ϵ}_j$
  ${\rho }_j$= Coefficiente di Amplificazione dell’errore Relativo, definisce 2 classi di problemi:
• Malcondizionati (almeno un $|{\rho }_j|$ grande)
• Bencondizionati ($|{\rho }_j|\approx 1\forall j$ ovvero se ${ϵ}_d$ è di un ordine di grandezza comparabile a $max|{ϵ}_i|coni=1,\dots ,m$)

Errore Algoritmico

Consideriamo subito gli errori inerenti alle 4 operazioni in aritmetica floating point:

$$\begin{array}{ccc}\text{operazione}& {\delta }_d& {ϵ}_d\\ x\oplus y& {\delta }_x+{\delta }_y& \frac{x}{x+y}{ϵ}_x+\frac{y}{x+y}{ϵ}_y\\ x\ominus y& {\delta }_x-{\delta }_y& \frac{x}{x-y}{ϵ}_x-\frac{y}{x-y}{ϵ}_y\\ x\otimes y& y\cdot {\delta }_x+x\cdot {\delta }_y& {ϵ}_x+ϵy\\ x\oslash y& \frac{1}{y}\cdot {\delta }_x+\frac{\delta x}{y^2}\cdot {\delta }_y& {ϵ}_x-ϵy\end{array}$$

• cancellazione numerica: quando sottraggo (o sommo a segni alterni) numeri molto simili in modulo (stesso esponente e prime cifre della mantissa uguali), di cui almeno uno soggetto ad errori di approssimazione, otteniamo una perdita di cifre significative.
  Questo per via del divisore nel calcolo dell’errore assoluto di somma e sottrazione.
• se ${ϵ}_a$ è “piccolo” il metodo numerico (o algoritmo) è stabile.

Calcolo dell’errore Algoritmico

Algoritmi diversi per la stessa operazione portano ad errori anche vastemente diversi, con valori così alti in alcuni casi da rendere inutilizzabile il risultato.
Come possiamo quindi calcolare l’errore (relativo/assoluto) di un algoritmo?

1. Partendo da un algoritmo $f_a(x)$ e vogliamo stimare ${\delta }_a=f_a(P_1)-f(P_1)$ e ${ϵ}_a=\frac{f_a(P_1)-f(P_1)}{f(P_1)}$, ignorando l’errore di arrotondamento sui dati (ovvero ${\delta }_j=0\forall j$).
2. Disegniamo il grafo (o albero) dell’algoritmo, sfruttando le relazioni per l’errore nelle 4 operazioni standard.
3. Sui “checkpoint” metto l’errore di arrotondamento, sui collegamento metto la propagazione dell’errore delle 4 operazioni.
4. Partiamo dall’ultimo checkpoint e sostituiamo via via i dati.

Esempio

<<<<<<<<<<

Problema Diretto

Data una $f$, un algoritmo per essa e una stima di ${\delta }_{x_j}$:
Stimare (maggiorare) ${\delta }_f\text{per}{P}_0\in D\subset R$.

Esempio

<<<<<<<<<<

Problema Inverso

Dato $\tau >0,f,D\in R^n$:
Determinare un algoritmo ed il relativo valore di $U$ tale che $|{\delta }_f|<\tau$.

Risoluzione:

1. stimare $|{\delta }_{x_i}|\forall i$ in funzione di $U$. (${\delta }_{x_i}=\max \{|x_i|\}\cdot U$).
2. Calcolare $A_i\forall i$ in funzione di $U$. ($A_i={\sup }_{x\in D}|\frac{\partial f}{\partial x_i}|(x)$)
3. Otteniamo

Esempio

<<<<<<<<<<