Condizionamento e stabilità

Condizionamento

Il condizionamento fa riferimento all'errore inerente. Se $|c_{x_{i}}|$$|c_{x_{i}}|$ sono elevati in modulo, allora a un piccolo errore $\varepsilon _{x_{i}}$$\varepsilon _{x_{i}}$ sulla rappresentazione dei dati corrisponde un grande errore su $f(x)$$f(x)$, e il problema è mal condizionato.

Esempio 1.7

Consideriamo un'equazione del tipo

$$ax^{2}+bx+c=0,\quad \delta =b^{2}-4ac$$

$$ax^{2}+bx+c=0,\quad \delta =b^{2}-4ac$$

Per calcolare le radici si ha la formula $x_{1,2}={\frac {-b\pm {\sqrt {\delta }}}{2a}}$$x_{1,2}={\frac {-b\pm {\sqrt {\delta }}}{2a}}$.

Se ${\sqrt {\delta }}=b$${\sqrt {\delta }}=b$, per calcolare $x_{1}$$x_{1}$ sto sommando due quantità quasi uguali, e quindi c'è un grande errore di cancellazione. Invece il calcolo di $x_{2}$$x_{2}$ non dà problemi.

Viceversa, se ${\sqrt {\delta }}=-b$${\sqrt {\delta }}=-b$, l'errore di cancellazione si ha per $x_{2}$$x_{2}$. Allora posso rimodellizzare il problema: se ${\sqrt {\delta }}\simeq -b$${\sqrt {\delta }}\simeq -b$, allora calcolo $x_{2}$$x_{2}$ con la formula solita senza avere problemi, invece calcolo $x_{1}$$x_{1}$ ricordando che

$$x_{1}x_{2}=c/a$$

$$x_{1}x_{2}=c/a$$

quindi

$$x_{1}={\frac {c}{ax_{2}}}$$

$$x_{1}={\frac {c}{ax_{2}}}$$

e il problema torna ad essere stabile, dopo essere stato rimodellizzato.

 

Stabilità

La stabilità è connessa all'errore algoritmico, e riguarda l'ordine esatto con cui vengono fatte le operazioni. L'errore algoritmico viene generato nella valutazione di $\psi (\mathrm {fl} (x))$$\psi (\mathrm {fl} (x))$.

$\psi$$\psi$ è una funzione razionale, cioè ha un'espressione analitica data da un numero finito di operazioni di somma e sottrazione. L'errore algoritmico è una combinazione lineare degli errori locali generati nelle singole operazioni.

Simbolicamente,

$$|e_{alg}|>\theta (u)+O(u^{2})$$

$$|e_{alg}|>\theta (u)+O(u^{2})$$

dove $\theta$$\theta$ è indipendente dalla round of unit, e tiene conto della combinazione lineare dei coefficienti.

Osservazione 1.3

Se ho un problema mal condizionato, l'analisi dell'errore algoritmico è inutile, perché questo errore è trascurabile rispetto all'errore inerente.

 

Esempio di rimodellizzazione di un problema

Esercizio 1.2

Analizzare l'errore nel calcolo della funzione

$$f(x,y)=x^{2}-y^{2}=(x+y)(x-y).$$

$$f(x,y)=x^{2}-y^{2}=(x+y)(x-y).$$

Chiamiamo $a_{1}$$a_1$ l'algoritmo $f=x^{2}-y^{2}$$f=x^{2}-y^{2}$ che è dato dai seguenti passi:

1. Pongo $z_{1}=x*x$$z_{1}=x*x$;
2. Pongo $z_{2}=y*y$$z_{2}=y*y$
3. eseguo l'operazione $z_{3}=z_{1}-z_{2}$$z_{3}=z_{1}-z_{2}$.

Nella moltiplicazione tengo conto che $c_{x}=c_{y}=1$$c_{x}=c_{y}=1$, mentre nella sottrazione si ha $c_{x}={\frac {x}{x-y}}$$c_{x}={\frac {x}{x-y}}$ e $c_{y}={\frac {-y}{x-y}}$$c_{y}={\frac {-y}{x-y}}$.

Rappresento graficamente l'algoritmo:

$${\begin{array}{ccccc}x&x&&y&y\\\uparrow (1)&\uparrow (1)&&\uparrow (1)&\uparrow (1)\\&z_{1}&&z_{2}&\\&\uparrow ({\frac {z_{1}}{z_{3}}})&&\uparrow ({\frac {-z_{2}}{z_{3}}})&\\&&z_{3}=z_{1}-z_{2}&&\\\end{array}}$$

$${\begin{array}{ccccc}x&x&&y&y\\\uparrow (1)&\uparrow (1)&&\uparrow (1)&\uparrow (1)\\&z_{1}&&z_{2}&\\&\uparrow ({\frac {z_{1}}{z_{3}}})&&\uparrow ({\frac {-z_{2}}{z_{3}}})&\\&&z_{3}=z_{1}-z_{2}&&\\\end{array}}$$

$$\varepsilon _{z_{3}}+{\frac {z_{1}}{z_{3}}}(\varepsilon _{z_{1}}+\varepsilon _{x}+\varepsilon _{x})-{\frac {z_{2}}{z_{3}}}(\varepsilon _{z_{2}}+\varepsilon _{y}+\varepsilon _{y})$$

$$\varepsilon _{z_{3}}+{\frac {z_{1}}{z_{3}}}(\varepsilon _{z_{1}}+\varepsilon _{x}+\varepsilon _{x})-{\frac {z_{2}}{z_{3}}}(\varepsilon _{z_{2}}+\varepsilon _{y}+\varepsilon _{y})$$

Vogliamo rappresentare la formula generale come somma di errore algoritmico e inerente.

$$e_{r}=\varepsilon _{z_{3}}+2{\frac {z_{1}}{z_{3}}}*\varepsilon _{x}-2{\frac {z_{2}}{z_{3}}}*\varepsilon _{y}+{\frac {z_{1}}{z_{3}}}*\varepsilon _{z_{1}}-{\frac {z_{2}}{z_{3}}}*\varepsilon _{z_{2}}$$

$$e_{r}=\varepsilon _{z_{3}}+2{\frac {z_{1}}{z_{3}}}*\varepsilon _{x}-2{\frac {z_{2}}{z_{3}}}*\varepsilon _{y}+{\frac {z_{1}}{z_{3}}}*\varepsilon _{z_{1}}-{\frac {z_{2}}{z_{3}}}*\varepsilon _{z_{2}}$$

e sostituendo a $z_{1},z_{2},z_{3}$$z_{1},z_{2},z_{3}$ le loro espressioni in termini di $x,y,z$$x,y,z$ si ha:

$$={\frac {2x^{2}}{x^{2}-y^{2}}}\varepsilon _{x}-{\frac {2y^{2}}{x^{2}-y^{2}}}*\varepsilon _{y}+\varepsilon _{z_{3}}+{\frac {x^{2}}{x^{2}-y^{2}}}\varepsilon _{z_{1}}-{\frac {y^{2}}{x^{2}-y^{2}}}\varepsilon _{z_{2}}$$

$$={\frac {2x^{2}}{x^{2}-y^{2}}}\varepsilon _{x}-{\frac {2y^{2}}{x^{2}-y^{2}}}*\varepsilon _{y}+\varepsilon _{z_{3}}+{\frac {x^{2}}{x^{2}-y^{2}}}\varepsilon _{z_{1}}-{\frac {y^{2}}{x^{2}-y^{2}}}\varepsilon _{z_{2}}$$

I primi due termini rappresentano l'errore inerente, mentre gli altri tre rappresentano l'errore algoritmico.

Se $x^{2}-y^{2}$$x^{2}-y^{2}$ è piccolo, il problema è mal condizionato, e l'errore inerente domina.

 

Esercizio 1.3

Ricavare lo stesso risultato per via analitica.

$$f(x,y)=x^{2}-y^{2}$$

$$f(x,y)=x^{2}-y^{2}$$

$$=\mathrm {fl} \{\mathrm {fl} [\mathrm {fl} (x)*\mathrm {fl} (x)]-\mathrm {fl} [\mathrm {fl} (y)*\mathrm {fl} (y)]\}$$

$$=\mathrm {fl} \{\mathrm {fl} [\mathrm {fl} (x)*\mathrm {fl} (x)]-\mathrm {fl} [\mathrm {fl} (y)*\mathrm {fl} (y)]\}$$

$$=\mathrm {fl} \{\mathrm {fl} [(1+\varepsilon _{x})*|x|*(1+\varepsilon _{x})*|x|]-\mathrm {fl} [(1+\varepsilon _{y})*|y|*(1+\varepsilon _{y})*|y|]\}$$

$$=\mathrm {fl} \{\mathrm {fl} [(1+\varepsilon _{x})*|x|*(1+\varepsilon _{x})*|x|]-\mathrm {fl} [(1+\varepsilon _{y})*|y|*(1+\varepsilon _{y})*|y|]\}$$

$$=\mathrm {fl} \{(1+\varepsilon _{z_{1}})(1+\varepsilon _{x})*|x|*(1+\varepsilon _{x})*|x|-(1+\varepsilon _{z_{2}})(1+\varepsilon _{y})*|y|*(1+\varepsilon _{y})*|y|\}$$

$$=\mathrm {fl} \{(1+\varepsilon _{z_{1}})(1+\varepsilon _{x})*|x|*(1+\varepsilon _{x})*|x|-(1+\varepsilon _{z_{2}})(1+\varepsilon _{y})*|y|*(1+\varepsilon _{y})*|y|\}$$

$$=(1+\varepsilon _{z_{3}})\{(1+\varepsilon _{z_{1}})(1+\varepsilon _{x})*|x|*(1+\varepsilon _{x})*|x|-(1+\varepsilon _{z_{2}})(1+\varepsilon _{y})*|y|*(1+\varepsilon _{y})*|y|\}$$

$$=(1+\varepsilon _{z_{3}})\{(1+\varepsilon _{z_{1}})(1+\varepsilon _{x})*|x|*(1+\varepsilon _{x})*|x|-(1+\varepsilon _{z_{2}})(1+\varepsilon _{y})*|y|*(1+\varepsilon _{y})*|y|\}$$

$$=(1+\varepsilon _{z_{3}})\{x^{2}(1+\varepsilon _{z_{1}})(1+\varepsilon _{x})^{2}-y^{2}(1+\varepsilon _{z_{2}})(1+\varepsilon _{y})^{2}\}$$

$$=(1+\varepsilon _{z_{3}})\{x^{2}(1+\varepsilon _{z_{1}})(1+\varepsilon _{x})^{2}-y^{2}(1+\varepsilon _{z_{2}})(1+\varepsilon _{y})^{2}\}$$

e al primo ordine:

$$=(1+\varepsilon _{z_{3}})\{x^{2}(1+\varepsilon _{z_{1}})(1+2\varepsilon _{x})-y^{2}(1+\varepsilon _{z_{2}})(1+2\varepsilon _{y})\}$$

$$=(1+\varepsilon _{z_{3}})\{x^{2}(1+\varepsilon _{z_{1}})(1+2\varepsilon _{x})-y^{2}(1+\varepsilon _{z_{2}})(1+2\varepsilon _{y})\}$$

$$=(1+\varepsilon _{z_{3}})\{x^{2}(1+\varepsilon _{z_{1}}+2\varepsilon _{x})-y^{2}(1+\varepsilon _{z_{2}}+2\varepsilon _{y})\}$$

$$=(1+\varepsilon _{z_{3}})\{x^{2}(1+\varepsilon _{z_{1}}+2\varepsilon _{x})-y^{2}(1+\varepsilon _{z_{2}}+2\varepsilon _{y})\}$$

$$=x^{2}(1+\varepsilon _{z_{1}}+2\varepsilon _{x}+\varepsilon _{z_{3}})-y^{2}(1+\varepsilon _{z_{2}}+2\varepsilon _{y}+\varepsilon _{z_{3}})$$

$$=x^{2}(1+\varepsilon _{z_{1}}+2\varepsilon _{x}+\varepsilon _{z_{3}})-y^{2}(1+\varepsilon _{z_{2}}+2\varepsilon _{y}+\varepsilon _{z_{3}})$$

Valuto l'errore relativo:

$$E_{r}={\frac {\mathrm {fl} (x^{2}-y^{2})-(x^{2}-y^{2})}{x^{2}-y^{2}}}$$

$$E_{r}={\frac {\mathrm {fl} (x^{2}-y^{2})-(x^{2}-y^{2})}{x^{2}-y^{2}}}$$

$$={\frac {x^{2}(\varepsilon _{z_{1}}+2\varepsilon _{x}+\varepsilon _{z_{3}})-y^{2}(\varepsilon _{z_{2}}+2\varepsilon _{y}+\varepsilon _{z_{3}})}{x^{2}-y^{2}}}$$

$$={\frac {x^{2}(\varepsilon _{z_{1}}+2\varepsilon _{x}+\varepsilon _{z_{3}})-y^{2}(\varepsilon _{z_{2}}+2\varepsilon _{y}+\varepsilon _{z_{3}})}{x^{2}-y^{2}}}$$

$$={\frac {(x^{2}-y^{2})\varepsilon _{z_{3}}+2x^{2}\varepsilon _{x}+x^{2}\varepsilon _{z_{1}}-y^{2}\varepsilon _{z_{2}}-2y^{2}\varepsilon _{y}}{x^{2}-y^{2}}}$$

$$={\frac {(x^{2}-y^{2})\varepsilon _{z_{3}}+2x^{2}\varepsilon _{x}+x^{2}\varepsilon _{z_{1}}-y^{2}\varepsilon _{z_{2}}-2y^{2}\varepsilon _{y}}{x^{2}-y^{2}}}$$

$$={\frac {2x^{2}}{x^{2}-y^{2}}}\varepsilon _{x}-{\frac {2y^{2}}{x^{2}-y^{2}}}*\varepsilon _{y}+{\frac {x^{2}}{x^{2}-y^{2}}}\varepsilon _{z_{1}}-{\frac {y^{2}}{x^{2}+y^{2}}}\varepsilon _{z_{2}}+\varepsilon _{z_{3}}$$

$$={\frac {2x^{2}}{x^{2}-y^{2}}}\varepsilon _{x}-{\frac {2y^{2}}{x^{2}-y^{2}}}*\varepsilon _{y}+{\frac {x^{2}}{x^{2}-y^{2}}}\varepsilon _{z_{1}}-{\frac {y^{2}}{x^{2}+y^{2}}}\varepsilon _{z_{2}}+\varepsilon _{z_{3}}$$

e si ottiene lo stesso risultato di prima.

Rimodellizzo il problema applicando l'algoritmo 2.

1. $w_{1}=x+y$$w_{1}=x+y$
2. $w_{2}=x-y$$w_{2}=x-y$
3. $w_{3}=w_{1}*w_{2}$$w_{3}=w_{1}*w_{2}$

Assumo che sto facendo conti sui numeri macchina, perché l'errore inerente si può calcolare a parte, cioè pongo $\varepsilon _{x}=\varepsilon _{y}=0$$\varepsilon _{x}=\varepsilon _{y}=0$. Graficamente ottengo:

$${\begin{array}{cc|c|cc}x&y&&x&y\\\uparrow (c_{x})&\uparrow (c_{y})&&\uparrow (c_{x})&\uparrow (c_{y})\\&w_{1}&&w_{2}&\\&\uparrow (1)&&\uparrow (1)&\\&&z&&\end{array}}$$

$${\begin{array}{cc|c|cc}x&y&&x&y\\\uparrow (c_{x})&\uparrow (c_{y})&&\uparrow (c_{x})&\uparrow (c_{y})\\&w_{1}&&w_{2}&\\&\uparrow (1)&&\uparrow (1)&\\&&z&&\end{array}}$$

quindi

$$e_{alg}=\varepsilon _{3}+1*(\varepsilon _{1}+c_{x}*\varepsilon _{x})+1*(\varepsilon _{2}+c_{y}*\varepsilon _{y})$$

$$e_{alg}=\varepsilon _{3}+1*(\varepsilon _{1}+c_{x}*\varepsilon _{x})+1*(\varepsilon _{2}+c_{y}*\varepsilon _{y})$$

e allora, siccome $\varepsilon _{x}=\varepsilon _{y}=0$$\varepsilon_x=\varepsilon_y=0$ ottengo:

$$e_{alg}=\varepsilon _{3}+1*(\varepsilon _{1}+0)+1*(\varepsilon _{2}+0)$$

$$e_{alg}=\varepsilon _{3}+1*(\varepsilon _{1}+0)+1*(\varepsilon _{2}+0)$$

$$=\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3}$$

$$=\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3}$$

 

Esercizio 1.4

Ricavare lo stesso risultato per via analitica.

$$\mathrm {fl} (x^{2}-y^{2})=$$

$$\mathrm {fl} (x^{2}-y^{2})=$$

$$\mathrm {fl} [\mathrm {fl} (x(1+\varepsilon _{x})+y(1+\varepsilon _{y}))*\mathrm {fl} (x(1+\varepsilon _{x})-y(1+\varepsilon _{y}))]=$$

$$\mathrm {fl} [\mathrm {fl} (x(1+\varepsilon _{x})+y(1+\varepsilon _{y}))*\mathrm {fl} (x(1+\varepsilon _{x})-y(1+\varepsilon _{y}))]=$$

$$(1+\varepsilon _{3})[(1+\varepsilon _{1})(x(1+\varepsilon _{x})+y(1+\varepsilon _{y}))*(1+\varepsilon _{2})*[x(1+\varepsilon _{x})-y(1+\varepsilon _{y})]]=$$

$$(1+\varepsilon _{3})[(1+\varepsilon _{1})(x(1+\varepsilon _{x})+y(1+\varepsilon _{y}))*(1+\varepsilon _{2})*[x(1+\varepsilon _{x})-y(1+\varepsilon _{y})]]=$$

Al primo ordine

$$(1+\varepsilon _{3})[(1+\varepsilon _{1})*(1+\varepsilon _{2})*[x^{2}(1+2\varepsilon _{x})-y^{2}(1+2\varepsilon _{y})]=$$

$$(1+\varepsilon _{3})[(1+\varepsilon _{1})*(1+\varepsilon _{2})*[x^{2}(1+2\varepsilon _{x})-y^{2}(1+2\varepsilon _{y})]=$$

$$(1+\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})*[x^{2}(1+2\varepsilon _{x})-y^{2}(1+2\varepsilon _{y})]=$$

$$(1+\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})*[x^{2}(1+2\varepsilon _{x})-y^{2}(1+2\varepsilon _{y})]=$$

$$x^{2}(1+2\varepsilon _{x}+\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})-y^{2}(1+2\varepsilon _{y}+\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})$$

$$x^{2}(1+2\varepsilon _{x}+\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})-y^{2}(1+2\varepsilon _{y}+\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})$$

$$E_{r}={\frac {x^{2}(1+2\varepsilon _{x}+\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})-y^{2}(1+2\varepsilon _{y}+\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})-x^{2}+y^{2}}{|x^{2}-y^{2}|}}$$

$$E_{r}={\frac {x^{2}(1+2\varepsilon _{x}+\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})-y^{2}(1+2\varepsilon _{y}+\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})-x^{2}+y^{2}}{|x^{2}-y^{2}|}}$$

$$E_{r}={\frac {x^{2}(2\varepsilon _{x}+\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})-y^{2}(2\varepsilon _{y}+\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})}{|x^{2}-y^{2}|}}$$

$$E_{r}={\frac {x^{2}(2\varepsilon _{x}+\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})-y^{2}(2\varepsilon _{y}+\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})}{|x^{2}-y^{2}|}}$$

$$E_{r}={\frac {(x^{2}-y^{2})(\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})+2x^{2}*\varepsilon _{x}-2y^{2}*\varepsilon _{y}}{|x^{2}-y^{2}|}}$$

$$E_{r}={\frac {(x^{2}-y^{2})(\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})+2x^{2}*\varepsilon _{x}-2y^{2}*\varepsilon _{y}}{|x^{2}-y^{2}|}}$$

$$E_{r}\leq {\frac {(x^{2}-y^{2})(\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})}{x^{2}-y^{2}}}+{\frac {2x^{2}*\varepsilon _{x}}{x^{2}-y^{2}}}+{\frac {2y^{2}*\varepsilon _{y}}{|x^{2}-y^{2}|}}$$

$$E_{r}\leq {\frac {(x^{2}-y^{2})(\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})}{x^{2}-y^{2}}}+{\frac {2x^{2}*\varepsilon _{x}}{x^{2}-y^{2}}}+{\frac {2y^{2}*\varepsilon _{y}}{|x^{2}-y^{2}|}}$$

$$E_{r}\leq \varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3}+{\frac {2x^{2}*\varepsilon _{x}}{x^{2}-y^{2}}}+{\frac {2y^{2}*\varepsilon _{y}}{|x^{2}-y^{2}|}}$$

$$E_{r}\leq \varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3}+{\frac {2x^{2}*\varepsilon _{x}}{x^{2}-y^{2}}}+{\frac {2y^{2}*\varepsilon _{y}}{|x^{2}-y^{2}|}}$$

Gli ultimi due addendi rappresentano l'errore inerente, uguale a quello del primo algoritmo, mentre

$$E_{alg}=\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3}\leq 3u$$

$$E_{alg}=\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3}\leq 3u$$

 

Nel primo algoritmo:

$$|E_{alg,1}|\leq u(1+{\frac {x^{2}+y^{2}}{x^{2}-y^{2}}})$$

$$|E_{alg,1}|\leq u(1+{\frac {x^{2}+y^{2}}{x^{2}-y^{2}}})$$

invece

$$|E_{alg,2}|\leq 3u$$

$$|E_{alg,2}|\leq 3u$$

Il secondo algoritmo è stabile e indipendente dai dati, ma quando $|x^{2}-y^{2}|$$|x^{2}-y^{2}|$ è piccolo il problema diventa mal condizionato quindi questo vantaggio non serve a niente, tranne nel caso in cui $x$$x$ e $y$$y$ sono numeri macchina.

La cosa migliore è quella di fare subito le operazioni rischiose (somma e sottrazione), e di lasciare moltiplicazioni e divisioni per ultime, in modo che l'errore accumulato sia minore.

Errore nel calcolo della somma di n numeri

Calcolo l'errore della funzione

$$f(x)=\sum _{i=1}^{n}x_{i}$$

$$f(x)=\sum _{i=1}^{n}x_{i}$$

e considero

$$c_{i}={\frac {x_{i}}{f(x)}}*{\frac {\partial f}{\partial x_{i}}}={\frac {x_{i}}{f(x)}}$$

$$c_{i}={\frac {x_{i}}{f(x)}}*{\frac {\partial f}{\partial x_{i}}}={\frac {x_{i}}{f(x)}}$$

$$E_{in}=\sum _{i=1}^{n}\varepsilon _{x_{i}}*{\frac {x_{i}}{f(x_{1},\dots ,x_{n})}}$$

$$E_{in}=\sum _{i=1}^{n}\varepsilon _{x_{i}}*{\frac {x_{i}}{f(x_{1},\dots ,x_{n})}}$$

$$=|{\frac {1}{f(x)}}*\sum _{i=1}^{n}x_{i}*\varepsilon _{x_{i}}|$$

$$=|{\frac {1}{f(x)}}*\sum _{i=1}^{n}x_{i}*\varepsilon _{x_{i}}|$$

$$\leq |{\frac {nu}{f(x)}}|*\max |x_{i}|$$

$$\leq |{\frac {nu}{f(x)}}|*\max |x_{i}|$$

L'errore inerente dipende dai dati e dal loro numero.
Se sono nella situazione in cui gli $x_{i}$$x_i$ hanno tutti segni concordi, allora:

$$|\sum _{i}x_{i}|=\sum _{i}|x_{i}|$$

$$|\sum _{i}x_{i}|=\sum _{i}|x_{i}|$$

Quindi, tenendo anche conto che $f(x)=|\sum _{i=1}^{n}x_{i}|$$f(x)=|\sum _{i=1}^{n}x_{i}|$, si ha:

$$E_{in}={\frac {1}{|\sum _{i}x_{i}|}}*|\sum _{i}x_{i}\varepsilon _{x_{i}}|$$

$$E_{in}={\frac {1}{|\sum _{i}x_{i}|}}*|\sum _{i}x_{i}\varepsilon _{x_{i}}|$$

$$\leq {\frac {1}{|\sum x_{i}|}}*\sum _{i}|x_{i}||\varepsilon _{x_{i}}|$$

$$\leq {\frac {1}{|\sum x_{i}|}}*\sum _{i}|x_{i}||\varepsilon _{x_{i}}|$$

$$\leq {\frac {1}{\sum _{i}|x_{i}|}}*u*\sum _{i}|x_{i}|<u$$

$$\leq {\frac {1}{\sum _{i}|x_{i}|}}*u*\sum _{i}|x_{i}|<u$$

Allora in questo caso il problema è ben condizionato, mentre nel caso generale l'errore inerente dipende dal valore dei dati e dal loro numero.

Rappresento il grafo dell'errore relativo nel caso della somma di quattro numeri $x_{1},x_{2},x_{3},x_{4}$$x_{1},x_{2},x_{3},x_{4}$ ponendo:

1. $z_{1}=x_{1}+x_{2}$$z_{1}=x_{1}+x_{2}$,
2. $z_{2}=z_{1}+x_{3}=(x_{1}+x_{2})+x_{3}$$z_{2}=z_{1}+x_{3}=(x_{1}+x_{2})+x_{3}$;
3. $z_{3}=x_{4}+z_{2}=x_{4}+(x_{1}+x_{2}+x_{3})$$z_{3}=x_{4}+z_{2}=x_{4}+(x_{1}+x_{2}+x_{3})$

Il grafico è

$${\begin{array}{cccc}&&x_{2}&x_{1}\\&&\uparrow (c_{x_{2}})&\uparrow (c_{x_{1}})\\&x_{3}&z_{1}&\\&\uparrow (c_{x_{3}})&\uparrow (c_{z_{1}})&\\x_{4}&z_{2}&&\\\uparrow (c_{x_{4}})&\uparrow (c_{z_{2}})&&\\z_{3}&&&\end{array}}$$

$${\begin{array}{cccc}&&x_{2}&x_{1}\\&&\uparrow (c_{x_{2}})&\uparrow (c_{x_{1}})\\&x_{3}&z_{1}&\\&\uparrow (c_{x_{3}})&\uparrow (c_{z_{1}})&\\x_{4}&z_{2}&&\\\uparrow (c_{x_{4}})&\uparrow (c_{z_{2}})&&\\z_{3}&&&\end{array}}$$

Suppongo che $x_{1},x_{2},x_{3},x_{4}$$x_{1},x_{2},x_{3},x_{4}$ siano numeri macchina, quindi $\varepsilon _{x_{i}}=0$$\varepsilon _{x_{i}}=0$, e rimane:

$$E_{alg}=\varepsilon _{3}+c_{z_{2}}*(\varepsilon _{2}+c_{z_{1}}*\varepsilon _{1})$$

$$E_{alg}=\varepsilon _{3}+c_{z_{2}}*(\varepsilon _{2}+c_{z_{1}}*\varepsilon _{1})$$

e sostituendo ai coefficienti le loro espressioni:

$$=\varepsilon _{3}+{\frac {z_{2}}{z_{3}}}*(\varepsilon _{2}+{\frac {z_{1}}{z_{2}}}\varepsilon _{1})$$

$$=\varepsilon _{3}+{\frac {z_{2}}{z_{3}}}*(\varepsilon _{2}+{\frac {z_{1}}{z_{2}}}\varepsilon _{1})$$

$$=\varepsilon _{3}+{\frac {z_{2}}{z_{3}}}*\varepsilon _{2}+{\frac {z_{2}}{z_{3}}}*{\frac {z_{1}}{z_{2}}}\varepsilon _{1}$$

$$=\varepsilon _{3}+{\frac {z_{2}}{z_{3}}}*\varepsilon _{2}+{\frac {z_{2}}{z_{3}}}*{\frac {z_{1}}{z_{2}}}\varepsilon _{1}$$

$$=\varepsilon _{3}+{\frac {z_{2}}{z_{3}}}*\varepsilon _{2}+{\frac {z_{1}}{z_{3}}}*\varepsilon _{1}$$

$$=\varepsilon _{3}+{\frac {z_{2}}{z_{3}}}*\varepsilon _{2}+{\frac {z_{1}}{z_{3}}}*\varepsilon _{1}$$

Sostituisco le espressioni di $z_{i}$$z_i$ espressi in funzione delle $x_{i}$$x_i$:

$$=\varepsilon _{3}+{\frac {x_{1}+x_{2}+x_{3}}{x_{1}+x_{2}+x_{3}+x_{4}}}*\varepsilon _{2}+{\frac {x_{1}+x_{2}}{x_{1}+x_{2}+x_{3}+x_{4}}}*\varepsilon _{1}$$

$$=\varepsilon _{3}+{\frac {x_{1}+x_{2}+x_{3}}{x_{1}+x_{2}+x_{3}+x_{4}}}*\varepsilon _{2}+{\frac {x_{1}+x_{2}}{x_{1}+x_{2}+x_{3}+x_{4}}}*\varepsilon _{1}$$

allora anche l'errore algoritmico dipende dai dati.

Esercizio 1.5

Trovare l'espressione dell'errore algoritmico per via analitica.

Suppongo che gli $x_{i}$$x_i$ siano numeri macchina, cioè che $\mathrm {fl} (x_{i})=x_{i}$$\mathrm {fl} (x_{i})=x_{i}$.

$$x_{1}+x_{2}+x_{3}+x_{4}=$$

$$x_{1}+x_{2}+x_{3}+x_{4}=$$

$$\{[(x_{1}+x_{2})+x_{3}]+x_{4}\}$$

$$\{[(x_{1}+x_{2})+x_{3}]+x_{4}\}$$

$$\mathrm {fl} \{\mathrm {fl} [\mathrm {fl} (x_{1}+x_{2})+x_{3}]+x_{4}\}$$

$$\mathrm {fl} \{\mathrm {fl} [\mathrm {fl} (x_{1}+x_{2})+x_{3}]+x_{4}\}$$

$$=\{[(x_{1}+x_{2})(1+\varepsilon _{1})+x_{3}](1+\varepsilon _{2})+x_{4}\}(1+\varepsilon _{3})$$

$$=\{[(x_{1}+x_{2})(1+\varepsilon _{1})+x_{3}](1+\varepsilon _{2})+x_{4}\}(1+\varepsilon _{3})$$

Eseguendo i prodotti e trascurando i termini di ordine superiore al primo:

$$=\{[x_{1}+x_{2}+x_{3}+x_{1}\varepsilon _{1}+x_{2}\varepsilon _{1}](1+\varepsilon _{2})+x_{4}\}(1+\varepsilon _{3})$$

$$=\{[x_{1}+x_{2}+x_{3}+x_{1}\varepsilon _{1}+x_{2}\varepsilon _{1}](1+\varepsilon _{2})+x_{4}\}(1+\varepsilon _{3})$$

$$=\{x_{1}+x_{2}+x_{3}+x_{4}+x_{1}\varepsilon _{1}+x_{2}\varepsilon _{1}+x_{1}\varepsilon _{2}+x_{2}\varepsilon _{2}+x_{3}\varepsilon _{2}\}(1+\varepsilon _{3})$$

$$=\{x_{1}+x_{2}+x_{3}+x_{4}+x_{1}\varepsilon _{1}+x_{2}\varepsilon _{1}+x_{1}\varepsilon _{2}+x_{2}\varepsilon _{2}+x_{3}\varepsilon _{2}\}(1+\varepsilon _{3})$$

$$=x_{1}+x_{2}+x_{3}+x_{4}+x_{1}\varepsilon _{1}+x_{2}\varepsilon _{1}+x_{1}\varepsilon _{2}+x_{2}\varepsilon _{2}+x_{3}\varepsilon _{2}+x_{1}\varepsilon _{3}+x_{2}\varepsilon _{3}+x_{3}\varepsilon _{3}+x_{4}\varepsilon _{3}$$

$$=x_{1}+x_{2}+x_{3}+x_{4}+x_{1}\varepsilon _{1}+x_{2}\varepsilon _{1}+x_{1}\varepsilon _{2}+x_{2}\varepsilon _{2}+x_{3}\varepsilon _{2}+x_{1}\varepsilon _{3}+x_{2}\varepsilon _{3}+x_{3}\varepsilon _{3}+x_{4}\varepsilon _{3}$$

Allora

$$E_{alg}={\frac {|\mathrm {fl} (x_{1}+x_{2}+x_{3}+x_{4})-x_{1}-x_{2}-x_{3}-x_{4}|}{|x_{1}+x_{2}+x_{3}+x_{4}|}}$$

$$E_{alg}={\frac {|\mathrm {fl} (x_{1}+x_{2}+x_{3}+x_{4})-x_{1}-x_{2}-x_{3}-x_{4}|}{|x_{1}+x_{2}+x_{3}+x_{4}|}}$$

$$={\frac {x_{1}+x_{2}+x_{3}+x_{4}+x_{1}\varepsilon _{1}+x_{2}\varepsilon _{1}+x_{1}\varepsilon _{2}+x_{2}\varepsilon _{2}+x_{3}\varepsilon _{2}+x_{1}\varepsilon _{3}+x_{2}\varepsilon _{3}+x_{3}\varepsilon _{3}+x_{4}\varepsilon _{3}-x_{1}-x_{2}-x_{3}-x_{4}}{x_{1}+x_{2}+x_{3}+x_{4}}}$$

$$={\frac {x_{1}+x_{2}+x_{3}+x_{4}+x_{1}\varepsilon _{1}+x_{2}\varepsilon _{1}+x_{1}\varepsilon _{2}+x_{2}\varepsilon _{2}+x_{3}\varepsilon _{2}+x_{1}\varepsilon _{3}+x_{2}\varepsilon _{3}+x_{3}\varepsilon _{3}+x_{4}\varepsilon _{3}-x_{1}-x_{2}-x_{3}-x_{4}}{x_{1}+x_{2}+x_{3}+x_{4}}}$$

$$={\frac {x_{1}\varepsilon _{1}+x_{2}\varepsilon _{1}+x_{1}\varepsilon _{2}+x_{2}\varepsilon _{2}+x_{3}\varepsilon _{2}+x_{1}\varepsilon _{3}+x_{2}\varepsilon _{3}+x_{3}\varepsilon _{3}+x_{4}\varepsilon _{3}}{x_{1}+x_{2}+x_{3}+x_{4}}}$$

$$={\frac {x_{1}\varepsilon _{1}+x_{2}\varepsilon _{1}+x_{1}\varepsilon _{2}+x_{2}\varepsilon _{2}+x_{3}\varepsilon _{2}+x_{1}\varepsilon _{3}+x_{2}\varepsilon _{3}+x_{3}\varepsilon _{3}+x_{4}\varepsilon _{3}}{x_{1}+x_{2}+x_{3}+x_{4}}}$$

$$=\varepsilon _{3}+{\frac {x_{1}\varepsilon _{1}+x_{2}\varepsilon _{1}}{x_{1}+x_{2}+x_{3}+x_{4}}}+{\frac {x_{1}\varepsilon _{2}+x_{2}\varepsilon _{2}+x_{3}\varepsilon _{2}}{x_{1}+x_{2}+x_{3}+x_{4}}}$$

$$=\varepsilon _{3}+{\frac {x_{1}\varepsilon _{1}+x_{2}\varepsilon _{1}}{x_{1}+x_{2}+x_{3}+x_{4}}}+{\frac {x_{1}\varepsilon _{2}+x_{2}\varepsilon _{2}+x_{3}\varepsilon _{2}}{x_{1}+x_{2}+x_{3}+x_{4}}}$$

$$=\varepsilon _{3}+{\frac {\varepsilon _{1}(x_{1}+x_{2})}{x_{1}+x_{2}+x_{3}+x_{4}}}+{\frac {\varepsilon _{2}(x_{1}+x_{2}+x_{3})}{x_{1}+x_{2}+x_{3}+x_{4}}}$$

$$=\varepsilon _{3}+{\frac {\varepsilon _{1}(x_{1}+x_{2})}{x_{1}+x_{2}+x_{3}+x_{4}}}+{\frac {\varepsilon _{2}(x_{1}+x_{2}+x_{3})}{x_{1}+x_{2}+x_{3}+x_{4}}}$$

e si ottiene il risultato precedente.

Nel caso della somma di $n$$n$ numeri si ottiene la formula generale:

$$E_{alg}=|{\frac {1}{f(x)}}\sum _{i=1}^{n-1}\sum _{j=1}^{i+1}x_{j}\varepsilon _{i}|$$

$$E_{alg}=|{\frac {1}{f(x)}}\sum _{i=1}^{n-1}\sum _{j=1}^{i+1}x_{j}\varepsilon _{i}|$$

Se invece gli $x_{i}$$x_i$ sono di segno concorde, allora

$$\sum _{j=1}^{i+1}|x_{j}|\leq |f(x)|$$

$$\sum _{j=1}^{i+1}|x_{j}|\leq |f(x)|$$

quindi, applicando la disuguaglianza triangolare, ottengo:

$$E_{alg}\leq |{\frac {1}{f(x)}}|\sum _{i=1}^{n-1}\sum _{j=1}^{i+1}|x_{j}|\varepsilon _{i}|$$

$$E_{alg}\leq |{\frac {1}{f(x)}}|\sum _{i=1}^{n-1}\sum _{j=1}^{i+1}|x_{j}|\varepsilon _{i}|$$

$$E_{alg}\leq \sum _{i=1}^{n-1}|\varepsilon _{i}|\leq (n-1)u$$

$$E_{alg}\leq \sum _{i=1}^{n-1}|\varepsilon _{i}|\leq (n-1)u$$

Allora l'errore algoritmico non dipende dai dati.

 

Ottimizzazione dell'algoritmo per la somma di n numeri

Procedimento 1: Per ridurre l'errore nella somma, conviene ordinare i numeri per valore assoluto, dal più piccolo al più grande. In questo modo risulta che, se considero le medie aritmetiche dei primi $i+1$$i+1$ numeri, si ha:

$$|1/i*\sum _{j=1}^{i}x_{j}|\leq {\frac {1}{i+1}}*|\sum _{j=1}^{i+1}x_{j}|\leq {\frac {1}{n-1}}|f(x)|$$

$$|1/i*\sum _{j=1}^{i}x_{j}|\leq {\frac {1}{i+1}}*|\sum _{j=1}^{i+1}x_{j}|\leq {\frac {1}{n-1}}|f(x)|$$

$${\frac {\sum _{j=1}^{i+1}|x_{j}|}{|f(x)|}}\leq {\frac {i+1}{n-1}}$$

$${\frac {\sum _{j=1}^{i+1}|x_{j}|}{|f(x)|}}\leq {\frac {i+1}{n-1}}$$

quindi

$$e_{alg}={\frac {1}{|f(x)|}}\sum _{i=1}^{n-1}|\sum _{j=1}^{i+1}x_{j}|*|\varepsilon _{i}|$$

$$e_{alg}={\frac {1}{|f(x)|}}\sum _{i=1}^{n-1}|\sum _{j=1}^{i+1}x_{j}|*|\varepsilon _{i}|$$

$$\leq u{\frac {1}{|f(x)|}}\sum _{i=1}^{n-1}|\sum _{j=1}^{i+1}x_{j}|$$

$$\leq u{\frac {1}{|f(x)|}}\sum _{i=1}^{n-1}|\sum _{j=1}^{i+1}x_{j}|$$

$$\leq {\frac {u}{n-1}}\sum _{i=1}^{n-1}(i+1)$$

$$\leq {\frac {u}{n-1}}\sum _{i=1}^{n-1}(i+1)$$

Esercizio 1.6

Verificare che

$$\sum _{i=1}^{n-1}(i+1)=(n^{2}+n-2)/2$$

$$\sum _{i=1}^{n-1}(i+1)=(n^{2}+n-2)/2$$

Verifico per induzione: per $n=2$$n=2$, si ha:

$$\sum _{i=1}^{2-1}(i+1)=2=(2*2+2-2)/2=2$$

$$\sum _{i=1}^{2-1}(i+1)=2=(2*2+2-2)/2=2$$

Suppongo vero l'asserto per $n-1$$n-1$, e lo dimostro per $n$$n$.

$$\sum _{i=1}^{n-1}(i+1)=$$

$$\sum _{i=1}^{n-1}(i+1)=$$

Isolando l'ultimo termine della somma:

$$n+\sum _{i=1}^{(n-1)-1}(i+1)=$$

$$n+\sum _{i=1}^{(n-1)-1}(i+1)=$$

e applicando il passo induttivo al secondo addendo ottengo:

$$n+[(n-1)^{2}+(n-1)-2]/2=$$

$$n+[(n-1)^{2}+(n-1)-2]/2=$$

$$n+[n^{2}+1-2n+n-1-2]/2=$$

$$n+[n^{2}+1-2n+n-1-2]/2=$$

$$n+[n^{2}-n-2]/2=$$

$$n+[n^{2}-n-2]/2=$$

$$[n^{2}+2n-n-2]/2={\frac {n^{2}+n-2}{2}}$$

$$[n^{2}+2n-n-2]/2={\frac {n^{2}+n-2}{2}}$$

Applicando l'esercizio e sostituendo nella formula 1 ottengo:

$$e_{alg}<{\frac {u}{n-1}}\sum _{i=1}^{n-1}(i+1)$$

$$e_{alg}<{\frac {u}{n-1}}\sum _{i=1}^{n-1}(i+1)$$

$$<(n^{2}+n-2)/2*{\frac {u}{n-1}}<(n+1)/2u$$

$$<(n^{2}+n-2)/2*{\frac {u}{n-1}}<(n+1)/2u$$

e l'errore è dell'ordine di $u/2$$u/2$.

Procedimento 2: Supponiamo di avere $n=2^{3}$$n=2^{3}$ numeri da sommare. Allora

$$x_{1}+x_{2}=z_{1},\,x_{3}+x_{4}=z_{2},\,x_{5}+x_{6}=z_{3},\,x_{7}+x_{8}=x_{4}$$

$$x_{1}+x_{2}=z_{1},\,x_{3}+x_{4}=z_{2},\,x_{5}+x_{6}=z_{3},\,x_{7}+x_{8}=x_{4}$$

$$z_{1}+z_{2}=z_{5},\,z_{3}+z_{4}=z_{6}$$

$$z_{1}+z_{2}=z_{5},\,z_{3}+z_{4}=z_{6}$$

$$z_{5}+z_{6}=z_{7}$$

$$z_{5}+z_{6}=z_{7}$$

$$|E_{r}|>\log n$$

$$|E_{r}|>\log n$$

 

Errore nel calcolo dell'esponenziale

Calcoliamo

$$f(x,y)=e^{x+y}=e^{x}*e^{y}$$

$$f(x,y) = e^{x+y} = e^x*e^y$$

In questo caso c'è una funzione di libreria $\exp(z)$$\exp (z)$ tale che per ogni $z$$z$, $\exp(z)=e^{z}*(1+\varepsilon _{z})$$\exp(z) = e^z*(1+\varepsilon_z)$, dove $\varepsilon =|e_{an}+e_{alg}|\leq u$$\varepsilon = |e_{an}+e_{alg}| \le u$.

1. Calcoliamo l'errore inerente:
   $$c_{x}={\frac {x}{f(x,y)}}*{\frac {\partial f}{\partial x}}={\frac {x}{e^{x+y}}}*e^{x+y}=x$$

   $$c_x = \frac{x}{f(x,y)}*\frac{\partial f}{\partial x} = \frac{x}{e^{x+y}}*e^{x+y} = x$$
   $$c_{y}=y$$

   $$c_y = y$$
   quindi
   $$e_{in}=x*\varepsilon _{x}+y*\varepsilon _{y}$$

   $$e_{in} = x*\varepsilon_x+y*\varepsilon_y$$
2. Applicando l'algoritmo $A_{1}=e^{x}*e^{y}$$A_1 = e^x*e^y$ si ha:
   $$z_{1}=e^{x},\,z_{2}=e^{y},\,z_{3}=z_{1}*z_{2}$$

   $$z_1 = e^x, \, z_2 = e^y, \, z_3 = z_1*z_2$$
   Rappresento il grafo:
   $${\begin{array}{ccccc}x&&&&y\\\uparrow (c_{x})&&&&\uparrow (c_{y})\\&z_{1}&&z_{2}&\\&\uparrow (c_{1})&&\uparrow (c_{2})&\\&&z_{3}&&\end{array}}$$

   $${\begin{array}{ccccc}x&&&&y\\\uparrow (c_{x})&&&&\uparrow (c_{y})\\&z_{1}&&z_{2}&\\&\uparrow (c_{1})&&\uparrow (c_{2})&\\&&z_{3}&&\end{array}}$$
   Sapendo che $c_{1}=c_{2}=1$$c_1=c_2=1$ si ha:
   $$e_{alg}=\varepsilon _{3}+1*\varepsilon _{1}+1*\varepsilon _{2}\leq |3u|$$

   $$e_{alg} = \varepsilon_3+1*\varepsilon_1+1*\varepsilon_2 \le |3u|$$
   Questo è un algoritmo stabile qualsiasi siano i due numeri $x$$x$ e $y$$y$.
3. Per via analitica, supponendo che $\mathrm {fl} (x)=x$$\mathrm{fl}(x)=x$ e $\mathrm {fl} (y)=y$$\mathrm{fl}(y) = y$ calcolo l'errore del primo algoritmo:
   $$e^{x+y}=e^{x}*e^{y}=\mathrm {fl} [\mathrm {fl} (e^{x})*\mathrm {fl} (e^{y})]$$

   $$e^{x+y}=e^{x}*e^{y}=\mathrm {fl} [\mathrm {fl} (e^{x})*\mathrm {fl} (e^{y})]$$
   $$=\mathrm {fl} [e^{x}*(1+\varepsilon _{1})*e^{y}*(1+\varepsilon _{2})]$$

   $$=\mathrm {fl} [e^{x}*(1+\varepsilon _{1})*e^{y}*(1+\varepsilon _{2})]$$
   $$=(1+\varepsilon _{3})*e^{x}*(1+\varepsilon _{1})*e^{y}*(1+\varepsilon _{2})$$

   $$= (1+\varepsilon_3)*e^x*(1+\varepsilon_1)*e^y*(1+\varepsilon_2)$$
   e al primo ordine:
   $$=e^{x}*e^{y}*(1+\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})$$

   $$= e^x*e^y*(1+\varepsilon_1+\varepsilon_2+\varepsilon_3)$$
   quindi
   $$E_{r}={\frac {\mathrm {fl} (e^{x+y})-e^{x+y}}{e^{x+y}}}$$

   $$E_r = \frac{\mathrm{fl}(e^{x+y})-e^{x+y}}{e^{x+y}}$$
   $$={\frac {e^{x}*e^{y}*(1+\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3})-e^{x}*e^{y}}{e^{x}*e^{y}}}$$

   $$= \frac{e^x*e^y*(1+\varepsilon_1+\varepsilon_2+\varepsilon_3)-e^x*e^y}{e^x*e^y}$$
   $$=|\varepsilon _{1}+\varepsilon _{2}+\varepsilon _{3}|\leq |\varepsilon _{1}|+|\varepsilon _{2}|+|\varepsilon _{3}|<3u$$

   $$= |\varepsilon_1+\varepsilon_2+\varepsilon_3| \le |\varepsilon_1|+|\varepsilon_2|+|\varepsilon_3| < 3u$$
4. Applico l'algoritmo 2 $f(x,y)=e^{x+y}$$f(x,y) = e^{x+y}$ e pongo
   $$w_{1}=x+y,\,w_{2}=e^{w_{1}}$$

   $$w_1 = x+y, \, w_2 = e^{w_1}$$
   $${\begin{array}{ccc}x&&y\\\uparrow (c_{x})&&\uparrow (c_{y})\\&w_{1}&\\&\uparrow (c_{1})&\\&w_{2}&\end{array}}$$

   $${\begin{array}{ccc}x&&y\\\uparrow (c_{x})&&\uparrow (c_{y})\\&w_{1}&\\&\uparrow (c_{1})&\\&w_{2}&\end{array}}$$
   e assumendo $\varepsilon _{x}=\varepsilon _{y}=0$$\varepsilon_x=\varepsilon_y=0$, e sapendo che $c_{1}=w_{1}$$c_1 = w_1$ si ha:
   $$|e_{alg}|=\varepsilon _{2}+w_{1}\varepsilon _{1}=\varepsilon _{2}+(x+y)\varepsilon _{1}<(1+x+y)u$$

   $$|e_{alg}| = \varepsilon_2+w_1 \varepsilon_1 = \varepsilon_2+(x+y) \varepsilon_1 < (1+x+y) u$$
   Quando $x+y$$x+y$ è piccolo, l'algoritmo 2 è più stabile, mentre è meno stabile quando $x+y$$x+y$ è grande.
5. Per via analitica, calcolo l'errore algoritmico del secondo algoritmo.
   $$e^{x+y}=\mathrm {fl} [e^{\mathrm {fl} (x+y)}]$$

   $$e^{x+y}=\mathrm {fl} [e^{\mathrm {fl} (x+y)}]$$
   $$=\mathrm {fl} (e^{(1+\varepsilon _{1})*(x+y)}$$

   $$= \mathrm{fl}(e^{(1+\varepsilon_1)*(x+y)}$$
   $$=e^{(1+\varepsilon _{1})*(x+y)}*(1+\varepsilon _{2})$$

   $$= e^{(1+\varepsilon_1)*(x+y)}*(1+\varepsilon_2)$$
   Al primo ordine:
   $$=[e^{x+y}+e^{x+y}*\varepsilon _{1}]*(1+\varepsilon _{2})$$

   $$= [e^{x+y}+e^{x+y}*\varepsilon_1]*(1+\varepsilon_2)$$
   $$=e^{x+y}+(x+y)*e^{x+y}*\varepsilon _{1}+e^{x+y}*\varepsilon _{2}$$

   $$= e^{x+y}+(x+y)*e^{x+y}*\varepsilon_1+e^{x+y}*\varepsilon_2$$
   Calcolo l'errore relativo:
   $$E_{r}={\frac {e^{x+y}+e^{x+y}*(x+y)*\varepsilon _{1}+e^{x+y}*\varepsilon _{2}-e^{x+y}}{e^{x+y}}}$$

   $$E_r = \frac{e^{x+y}+e^{x+y}*(x+y)*\varepsilon_1+e^{x+y}*\varepsilon_2-e^{x+y}}{e^{x+y}}$$
   e al primo ordine rimane:
   $$=(x+y)\varepsilon _{1}+\varepsilon _{2}$$

   $$= (x+y) \varepsilon_1+\varepsilon_2$$