Introduzione sull'aritmetica floating-point

Quattro parole chiave dell'aritmetica floating-point[modifica | modifica wikitesto]

Stabilità dell'algoritmo
Un algoritmo è l'implementazione del metodo che vogliamo usare per risolvere il problema matmatico che vogliamo trattare. La stabilità è in corrispondenza con l'errore algoritmico.
Condizionamento di un problema
A cui viene associato l'errore inerente (tipico del problema).
Complessità computazionale
Riguarda il tempo impiegato da un algoritmo per ottenere la soluzione. E' relazionata con il tempo di calcolo e con l'errore algoritmico.
Convergenza
associata a errore analitico o di approssimazione.

Stabilità di un algoritmo[modifica | modifica wikitesto]

Un algoritmo è una sequenza finita di operazioni. Per uno stesso problema possono esistere diversi algoritmi che portano alla soluzione. Algoritmi diversi su un calcolatore portano però a risultati diversi. L'ordine con cui vengono fatte le operazioni può portare a risultati leggermente diversi.

Si definiscono algoritmi numericamente instabili quelli in cui si ha un'elevata propagazione dell'errore, mentre si definiscono algoritmi numericamente stabili quelli in cui la propagazione dell'errore è contenuta.16 è inoltre il numero di cifre decimali rappresentabili con matlab.

Esempio

Voglio calcolare una quantità (in aritmetica esatta ).

Algoritmo 1:

Algoritmo 2: Quando è positivo ma molto piccolo, il secondo procedimento è stabile mentre l'altro no (cfr stabilità.txt), iniziano a esserci problemi per numeri dell'ordine di .

 
Esempio

Consideriamo la risoluzione del sistema lineare

con matrice quadrata . Il sistema si può risolvere con il Metodo di Kramer: la soluzione del sistema può essere calcolata come il rapporto tra due determinanti
dove, indicando con le colonne della matrice,
e
dove sostituisco alla j-esima colonna il termine noto. Il determinante si calcola con la formula dei cofattori. Chiamiamo il numero di operazioni moltiplicative per calcolare il determinante di una matrice di dimensione .

Il calcolo del determinante è ridotto al calcolo di n determinanti di matrici più piccole () moltiplicate per coefficienti. Quindi (operazione ricorsiva).

Per trovare tutte le soluzioni del sistema devo calcolare determinanti di matrici di dimensione , quindi il costo del metodo di Kramer è maggiore uguale di e richiede tempi molto lunghi. Il costo del metodo di Gauss è invece maggiore o uguale di .

Il metodo di Gauss trasforma il sistema in un sistema equivalente della forma con U matrice triangolare superiore.

Calcolo un coefficiente detto moltiplicatore, tale che al passo .

Nell'algoritmo si combinano linearmente le due equazioni.

L'elemento è detto elemento pivetale. Se in aritmetica esatta si ha un problema, perché non si può dividere per 0. In aritmetica floating-point quando è piccolo sorgono dei problemi.

Con il calcolatore si fa in modo che l' che viene usato sia il meno piccolo possibile. Applico la tecnica del pivet parziale: cerco l'indice di equazione tale che in modulo è il massimo per dei valori assoluti di .

Prima di proseguire si scambia la riga -esima con la -esima.

Il risultato di questa tecnica è che

 

Condizionamento[modifica | modifica wikitesto]

Esistono problemi in cui si ha un errore elevato indipendentemente dal metodo utilizzato per calcolare la soluzione. La difficoltà è una proprietà intrinseca del problema stesso.

Definizione 1.1

Si dice problema mal condizionato un problema in cui piccole variazioni dei dati inducono grandi variazioni nei risultati (dipendenza continua dai dati).

 


Esempio 1.1

Supponiamo di avere il sistema

e le due rette si intersecano nel punto .
Presa la prima equazione, se perturbiamo il coefficiente di x ponendolo uguale a otteniamo:
e il punto di intersezione è
cioè una piccola variazione dei dati da una grande variazione nella soluzione. (questo avviene perché le due rette sono quasi parallele).

 

Convergenza[modifica | modifica wikitesto]

Si ha a che fare con la convergenza in due casi:

  1. processi di discretizzazione. Considero ad esempio una funzione di classe almeno , e consideriamo
    La discretizzazione ha un errore che si comporta come , e va a 0 come h.
  2. metodo iterativo: ad esempio, voglio approssimare la soluzione dell'equazione . Definisco una successione con , assegnando come valore iniziale , e proseguendo così.
 PrecedenteSuccessivo