Condizionamento di una funzione

Si supponga di dover risolvere un problema rappresentabile nella forma $x = f(x)$, dove $x$ sono i dati in ingresso, $y$ rappresenta il risultato e $f$ è un metodo numerico.

Quello che ci si troverà a risolvere in macchina è in reltà un problema:

$$\tilde{y} = \tilde{f}(\tilde{x})$$

$\tilde{f}$ è una funzione perturbata (a causa di operazioni eseguite in aritmetica finita, con possibili errori di di discretizzazione e/o convergenza) su un dato a sua volta perturbato (a causa dell'errore di rappresentazione sempre presente o dell'origine sperimentale del dato).

Per semplicità si studierà il problema $\tilde{y} = f(\tilde{x})$, considerando il metodo numerico come eseguito in artimetica esatta.

Definizione 2.12 (Condizionamento di un problema)   Un problema è ben condizionato quando piccole perturbazioni nei dati iniziali hanno un piccolo effetto sul risultato finale.

Contrariamente, un problema mal condizionato è un problema in cui la soluzione è molto sensibile a piccole perturbazioni nei dati.

Osservazione 2.1   Il condizionamento è una proprietà intrinseca della funzione, indipendente dall'algoritmo utilizzato (coincidente con la forma in cui è scritta), mentre la stabilità è una proprietà degli algoritmi.

Definizione 2.13 (Funzione di condizionamento)  

$$\mathit{cond}f(x) = \frac{\varepsilon_f}{\varepsilon_x}$$

Dove $\varepsilon_x$ è l'errore relativo sull'input, $\varepsilon_f$ è l'errore relativo sul risultato.

Teorema 2.14   Sia $f : \mathbb{R}\to \mathbb{R}, f \in C'$ (ad una variabile, differenziabile).

$$\mathit{cond}f(x) = \Bigl\lvert \frac{xf'(x)}{f(x)} \Bigr\rvert$$

Dimostrazione 2.5   Se $f : \mathbb{R}\to \mathbb{R}, f \in C'$ è noto che:

$$f'(x) = \lim_{h \to 0} {f(x+h) - f(x)}{h} = 0$$

E quindi nelle vicinanze di $x$:

$$f(x+h) \approx f(x)+f'(x) \cdot h$$

Allora

$$f(\tilde{x}) \approx f(x) + f'(x)(\tilde{x}-x)$$

Applicando la consueta definizione di errore relativo $\varepsilon$:

$$\varepsilon_f = \frac{\vert f(\tilde{x}) - f(x)\vert}{\vert f(x)\vert} \qquad f(x) \ne 0$$

È possibile riscrivere:

$$\begin{split}\varepsilon_f & \approx \frac{\vert f'(x)(\tilde{x}-... ...t\tilde{x} - x\vert}{\vert x\vert} = \mathit{cond}f(x)\varepsilon_x \end{split}$$

$\qedsymbol$

Definizione 2.14   Sia $f : \mathbb{R}^2 \to R, f \in C'$.

$$f(\tilde{x}, \tilde{y}) \approx f(x,y) + \frac{\delta f}{\delta x} (x,y)(\tilde{x}-x)+ \frac{\delta f}{\delta x} (x,y)(\tilde{y}-y)$$

$$\varepsilon_f = \frac{\vert f(\tilde{x},\tilde{y})-f(x,y)\vert} ... ...\underbrace{\frac{\lvert \tilde{y}-y \rvert}{\lvert y \rvert}}_{\varepsilon_y}$$

Definizione 2.15 (Formula degli errori)  

$$\varepsilon_{f(x,y)} \approx \underbrace{\Bigl \lvert x \frac{\de... ...gl \lvert y \frac{\delta f(x,y) } {\delta y} \Bigr \rvert}_{w_2} \varepsilon_y$$

Esempio 2.8  

$$f(x,y) = x + y$$

$$\varepsilon_{x+y} \lesssim \frac{\vert x\vert}{\vert x+y\vert} \varepsilon_x + \frac{\vert y\vert}{\vert x+y\vert}\varepsilon_y$$

$$\frac{\delta f}{\delta x} = 1 + 0 = 1$$

$$\frac{\delta f}{\delta y} = 1$$

$$w_1 = \frac {\vert x \cdot 1\vert}{\vert x + y\vert}$$

$$w_2 = \frac{\vert y \cdot 1 \vert}{\vert x + y\vert}$$

Come visto in precedenza, la somma algebrica è una funzione ben condizionata se non è vero che $\vert x + y\vert \to 0$.

Esempio 2.9  

$$f(x,y) = x y$$

$$\frac{\delta f}{\delta x} = y$$

$$\frac{\delta f}{\delta y} = x$$

$$w_1 = \frac{\vert x y\vert}{\vert x y\vert} = 1$$

$$w_2 = \frac{\vert y x\vert}{\vert x y\vert} = 1$$

Il prodotto risponde bene agli errori sui dati.

Esempio 2.10   Si consideri

$$f(x) = 1-x$$

Calcolando $f(x)$ in $x \approx 1$:

$$cond f(x) = \Bigl\lvert \frac{x(-1)}{1-x}\Bigr\rvert = \Bigl\lvert \frac{x}{1-x}\Bigr\rvert$$

$$lim_{x\to1}\Bigl\lvert\frac{x}{1-x}\Bigr\rvert = \infty$$

$f(x)$ è una funzione mal condizionata (per $x \approx 1$)

Esempio 2.11  

$$f(x) = \frac{(1+x)-1}{x} \equiv 1 \qquad x \neq 0$$

$$condf(x) = \Bigl\lvert\frac{x \cdot 0}{f(x)}\Bigr\rvert = 0$$

Va osservato che $f(x)$ è diversa da $x \longmapsto 1$. Molte funzioni possono non essere mal condizionate ma possiamo avere problemi nel processo di calcolo a causa dell'algoritmo utilizzato.

In questo caso, ad esempio la funzione è in una forma notoriamente instabile per $x \approx 0$.

Esempio 2.12  

$$f(x) = 1-\sqrt{1-x^2} \qquad \vert x\vert \leq 1$$

$$f'(x) = \not{-}\frac{1}{\not{2}\sqrt{1-x^2}}\not{-}\not{2}x = \frac{x}{\sqrt{1-x^2}}$$

$$cond f(x) = \frac{\lvert x \cdot \frac{x}{\sqrt{1-x^2}} \rvert}{\... ...2}} \cdot \frac{1}{1-\sqrt{1-x^2}} \cdot \frac{1+\sqrt{1-x^2}}{1+\sqrt{1-x^2}}$$

$$= \frac{\not{x^2}}{\sqrt{1-x^2}} \cdot \frac{1+\sqrt{1-x^2}}{\not... ...{1}-\not{x^2})} = \frac{1+\sqrt{1-x^2}}{\sqrt{1-x^2}} \underset{x\to 0}{\to} 2$$

Questa $f$ è ben condizionata, ma l'algoritmo è instabile. E' possibile correggerlo cosi':

$$f(x)=1-\sqrt{1-x^2}\cdot \frac{1+\sqrt{\cdots}}{1+\sqrt{\cdots}} = \frac{x^2}{1+\sqrt{1-x^2}}$$

L'algoritmo è allora stabile (per $x \approx 0$).