Condizionamento e stabilità

Condizionamento[modifica | modifica wikitesto]

Il condizionamento fa riferimento all'errore inerente. Se sono elevati in modulo, allora a un piccolo errore sulla rappresentazione dei dati corrisponde un grande errore su , e il problema è mal condizionato.
Esempio 1.7

Consideriamo un'equazione del tipo

Per calcolare le radici si ha la formula .

Se , per calcolare sto sommando due quantità quasi uguali, e quindi c'è un grande errore di cancellazione. Invece il calcolo di non dà problemi.

Viceversa, se , l'errore di cancellazione si ha per . Allora posso rimodellizzare il problema: se , allora calcolo con la formula solita senza avere problemi, invece calcolo ricordando che

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

 

Stabilità[modifica | modifica wikitesto]

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 .

è 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,

dove è 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[modifica | modifica wikitesto]

Esercizio 1.2

Analizzare l'errore nel calcolo della funzione

Chiamiamo l'algoritmo che è dato dai seguenti passi:

  1. Pongo ;
  2. Pongo
  3. eseguo l'operazione .

Nella moltiplicazione tengo conto che , mentre nella sottrazione si ha e .

Rappresento graficamente l'algoritmo:

Vogliamo rappresentare la formula generale come somma di errore algoritmico e inerente.
e sostituendo a le loro espressioni in termini di si ha:
I primi due termini rappresentano l'errore inerente, mentre gli altri tre rappresentano l'errore algoritmico.

Se è piccolo, il problema è mal condizionato, e l'errore inerente domina.
 
Esercizio 1.3

Ricavare lo stesso risultato per via analitica.

e al primo ordine:
Valuto l'errore relativo:
e si ottiene lo stesso risultato di prima.

Rimodellizzo il problema applicando l'algoritmo 2.

Assumo che sto facendo conti sui numeri macchina, perché l'errore inerente si può calcolare a parte, cioè pongo . Graficamente ottengo:

quindi
e allora, siccome ottengo:

 
Esercizio 1.4

Ricavare lo stesso risultato per via analitica.

Al primo ordine

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

 

Nel primo algoritmo:

invece
Il secondo algoritmo è stabile e indipendente dai dati, ma quando è piccolo il problema diventa mal condizionato quindi questo vantaggio non serve a niente, tranne nel caso in cui e 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[modifica | modifica wikitesto]

Calcolo l'errore della funzione

e considero
L'errore inerente dipende dai dati e dal loro numero.
Se sono nella situazione in cui gli hanno tutti segni concordi, allora:
Quindi, tenendo anche conto che , si ha:
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 ponendo:

  1. ,
  2. ;

Il grafico è

Suppongo che siano numeri macchina, quindi , e rimane:
e sostituendo ai coefficienti le loro espressioni:
Sostituisco le espressioni di espressi in funzione delle :
allora anche l'errore algoritmico dipende dai dati.

Esercizio 1.5

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

Suppongo che gli siano numeri macchina, cioè che .

Eseguendo i prodotti e trascurando i termini di ordine superiore al primo:
Allora
e si ottiene il risultato precedente.

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

Se invece gli sono di segno concorde, allora

quindi, applicando la disuguaglianza triangolare, ottengo:

Allora l'errore algoritmico non dipende dai dati.
 

Ottimizzazione dell'algoritmo per la somma di n numeri[modifica | modifica wikitesto]

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 numeri, si ha:

quindi

Esercizio 1.6

Verificare che

Verifico per induzione: per , si ha:
Suppongo vero l'asserto per , e lo dimostro per .
Isolando l'ultimo termine della somma:
e applicando il passo induttivo al secondo addendo ottengo:
Applicando l'esercizio e sostituendo nella formula 1 ottengo:
e l'errore è dell'ordine di .

Procedimento 2: Supponiamo di avere numeri da sommare. Allora

 

Errore nel calcolo dell'esponenziale[modifica | modifica wikitesto]

Calcoliamo

In questo caso c'è una funzione di libreria tale che per ogni , , dove .

  1. Calcoliamo l'errore inerente:
    quindi
  2. Applicando l'algoritmo si ha:
    Rappresento il grafo:
    Sapendo che si ha:
    Questo è un algoritmo stabile qualsiasi siano i due numeri e .
  3. Per via analitica, supponendo che e calcolo l'errore del primo algoritmo:
    e al primo ordine:
    quindi
  4. Applico l'algoritmo 2 e pongo
    e assumendo , e sapendo che si ha:
    Quando è piccolo, l'algoritmo 2 è più stabile, mentre è meno stabile quando è grande.
  5. Per via analitica, calcolo l'errore algoritmico del secondo algoritmo.
    Al primo ordine:
    Calcolo l'errore relativo:
    e al primo ordine rimane:
 PrecedenteSuccessivo