Quindi il fattoriale di N al denominatore abbatte rapidamente l’errore iniziale εN, che pu`o anche essere elevato.
Sia ad esempio N = 13 ed I13= 1000. Si ottiene
i I00i i I00i
12 −7.6846153 × 101 6 1.2668674 × 10−1 11 6.4871793 × 100 5 1.4555222 × 10−1 10 −4.9883449 × 10−1 4 1.7088956 × 10−1 9 1.4988345 × 10−1 3 2.0727761 × 10−1 8 9.4457395 × 10−2 2 2.6424080 × 10−1 7 1.1319283 × 10−1 1 3.6787960 × 10−1
con |I01− I001| = 1.4901161 × 10−7 (I01 `e l’approssimazione del valore esatto I1 = e−1). Come si vede, pur partendo da un valore iniziale completa-mente arbitrario, l’integrale I001 (approssimazione di I1) risulta essere ac-curato per almeno 6 cifre significative decimali. Qualora l’errore |I01− I001| fosse stato troppo elevato, ovvero maggiore di una certa tolleranza toll prefissata, si aumenta il valore di N e si ripete il procedimento sino ad ottenere la precisione desiderata.
Naturalmente i primi integrali calcolati, rispetto agli integrali esatti, saranno affetti da un errore non trascurabile. Nella tabella precedente si vede, ad esempio, che l’effetto di diminuzione dell’errore inizia solamente nel calcolo di I008. Ripetiamo il procedimento prendendo N = 20 ed ancora I20= 1000 e mostrando solo gli integrali a partire da I0012.
i I00i i I00i
12 7.1773447 × 10−2 6 1.2680236 × 10−1 11 7.7352211 × 10−2 5 1.4553294 × 10−1 10 8.3877072 × 10−2 4 1.7089342 × 10−1 9 9.1612294 × 10−2 3 2.0727664 × 10−1 8 1.0093196 × 10−1 2 2.6424113 × 10−1 7 1.1238351 × 10−1 1 3.6787945 × 10−1 In tal caso, I001 coincide esattamente con I01.
2.6 Analisi degli errori
Abbiamo visto quante problematiche possono essere presenti quando vogliamo risolvere un problema matematico utilizzando un computer
(condizionamento, errori di assegnazione, dovuti alle operazioni macchina, stabilit`a dell’algoritmo, . . . ). A tutte queste si aggiunge anche il fatto che, per produrre il modello numerico di un problema matematico, siamo talvolta obbligati a ricorrere a metodi numerici che forniscono solo una soluzione approssimata del problema matematico (ad esempio nell’inte-grazione finita).
Quando possibile, pu`o essere interessante studiare la propagazione degli errori. `E quanto in effetti `e stato fatto nell’esempio dell’integrale della sezione precedente. Non intendiamo approfondire tale argomento, ma molti semplici esempi possono essere trovati nei vari testi della let-teratura.
Quando si studia come l’errore si propaga per effetto dell’errore di assegnazione e delle successive operazioni, si parla di analisi dell’errore in avanti. Nei casi reali tale analisi risulta difficilmente realizzabile (a causa soprattutto del numero importante delle operazioni che vengono svolte).
Inoltre si effettuano delle semplificazioni dei calcoli che conducono spesso a delle stime poco accurate dell’errore finale.
Una tecnica alternativa, molto usata, `e quella dell’analisi dell’errore all’indietro. In tale caso si considera la soluzione approssimata ottenuta, come se fosse soluzione esatta di un problema P che sia modificato rispetto al problema iniziale P. Poi si studia quanto sia grande la mo-difica del problema iniziale al fine di ottenere tale soluzione. Il risultato finale ottenuto sar`a accettabile solo se esso `e soluzione esatta di un pro-blema modificato che possa essere considerato prossimo a quello originale.
In termini di errori, si considera quale dovrebbe essere l’errore sui dati iniziali originari per produrre tale risultato finale.
Terminiamo con alcune definizioni che riguardano gli errori:
Sia ε0 l’errore iniziale, ed εn l’errore dopo n passi di un certo algoritmo.
La crescita dell’errore `e detta lineare
se εn ' n ε0
esponenziale
se εn ' cnε0
Se c > 1 l’errore cresce (εn → ∞, per n → ∞) Se 0 < c < 1 l’errore descresce (εn→ 0, per n → ∞)
2.7. Esempi 43
2.7 Esempi
In questa sezione vogliamo fornire alcuni esempi tratti dalla letteratura per illustrare maggiormente le varie problematiche, soprattutto quelle relative alla precisione finita dell’aritmetica del computer.
2.7.1 Esempio 1
Spesso si ritiene che se un risultato calcolato con precisioni diverse resta invariato, `e obbligatoriamente ben calcolato. Questo esempio mostra che tale convinzione `e errata.
Sia da calcolare il valore di
333.75b6+ a2(11a2b2− b6− 121b4− 2) + 5.5b8+ a
2b. (2.6) Per a2− 1 = 11b2/2 l’espressione vale analiticamente −2 + a/2b.
Consideriamo i valori a = 77617.0 e b = 33096.0 tali che a2− 1 = 11b2/2.
Calcolando numericamente l’espressione (2.6) si ottiene
Semplice precisione Doppia precisione Precisione estesa 0.5764607×1018 0.5764607523034235×1018 0.57646075230342350345×1018 Tuttavia il risultato con tali valori dovrebbe essere
−2 + a/2b = −0.82739605994682 . . .
I risultati in tale problema dipendono fortemente anche dal computer su cui si lavora e dal modo in cui si programma la formula. Infatti, su di un altro computer si `e ottenuto circa −9.87 × 1029 in semplice precisione, e circa −1.18 × 1021 in doppia precisione!
2.7.2 Esempio 2 Consideriamo il polinomio
x3− 111x2+ 1130x − 3000.
Le sue radici sono 5, 6 e 100. `E possibile dimostrare che la successione xn+1= 111 − 1130
xn
+ 3000 xnxn−1
, n = 0, 1, . . . converge a 6 se si prendono come valori iniziali
x−1= 11
2 = 5.5 e x0= 61
11 = 5.54
0 5 10 15 20 25
−600
−500
−400
−300
−200
−100 0 100 200
n
xn
Figura 2.4: xn+1 = 111 − 1130 xn
+ 3000 xnxn−1
In figura 2.4 si vede invece che, utilizzando un computer, la successione converge al valore 100 anzich`e a 6. Questo fenomeno sembra prodursi su tutti i computer. Infatti, ad esempio, se si prendono come valori iniziali
x−1= 2.0 e x0 = −4.0 facendo i calcoli con 100 cifre decimali si trova
x89= 99.999804031654181616554 . . .
mentre il valore esatto dovrebbe essere 6.0000000996842706 . . ..
2.7.3 Esempio 3
Consideriamo la seguente successione che converge al valore x = 1 x0 = 1.510005072136258
xn+1 = 3x4n− 20x3n+ 35x2n− 24
4x3n− 30x2n+ 70xn− 50, n = 0, 1, . . .
A seconda del numero di cifre decimali k utilizzate nei calcoli, si otten-gono risultati molto diversi.
2.7. Esempi 45 k Valore di convergenza
10 4.000000033 12 1.00000000000 14 3.0000000000000 16 4.000000000000033 18 1.00000000000000000 2.7.4 Esempio 4
Si consideri il seguente schema iterativo x0 assegnato y0 = p
1 − x20
t0 = x20+ y20 = 1
xn+1 = 2xnyn
yn+1 = x2n− y2n
tn+1 = x2n+1+ y2n+1
per n = 0, 1, . . .
Matematicamente si ha tn+1 = (x2n + y2n)2 = t2n = 1 (per induzione, essendo t0= 1).
In figura 2.5, si sono visualizzate le curve ottenute su di un computer, nei due casi:
x0 = 0.6 tn linea continua x0 = 0.8 tn linea tratteggiata
Come si vede, dopo essersi mantenuto uguale a 1, nel primo caso tncresce, mentre nel secondo tende a zero.
2.7.5 Esempio 5
Consideriamo la successione {xn} calcolata come
xn+1 = 2.25 xn− 0.5 xn−1, n = 2, 3, . . . (2.7) con x1 e x2 assegnati. La teoria delle equazioni alle differenze lineari omogenee, a coefficienti costanti, ci dice che
xn = a 0.25n+ b 2n, n = 1, 2, . . . (2.8) dove a e b sono delle costanti i cui valori sono determinati da x1 e x2. Se noi prendiamo x1 = 1/3 e x2 = 1/12, si ha a = 4/3 et b = 0. Di
0.6 0.8 1 1.2 1.4 1.6 1.8 2 2.2 2.4
0 5 10 15 20 25
n
t_n
Figura 2.5: tn+1= (x2n+ yn2)2 = t2n
10-12 10-9 10-6 10-3 100 103 106 109
0 10 20 30 40 50 60 70
Figura 2.6: xn+1= 2.25xn− 0.5xn−1
2.8. Algoritmi 47 conseguenza da (2.8) si ha xn = 41−n/3 e tale quantit`a tende a zero quando n tende verso l’infinito.
I risultati ottenuti su computer, utilizzando la formula (2.7) sono visua-lizzati in figura 2.6.
Cerchiamo di capire cosa `e accaduto. A causa degli errori di assegna-zione iniziali su x1 e x2, il valore b implicitamente definito da (2.7) non `e esattamente nullo, ma solo molto piccolo. Nella prima parte della curva, l’apporto del termine b 2n`e trascurabile, ma diviene preponderante nella parte destra della curva.
2.8 Algoritmi
2.8.1 Stima di eps
Un semplice algoritmo (dovuto a Cleve Moler) per la stima del valore eps`e il seguente:
x = 4.0/3.0 y = x − 1.0 z = y + y + y eps= |z − 1.0|
2.8.2 Calcolo della base
Abbiamo gi`a detto che non tutti i computer lavorano con normalizzazione nella base 2. Se si lavora con computer che utilizzano basi diverse, non
`e inusuale che i risultati di uno stesso programma risultino essere diversi (anche di molto) su computer differenti.
Un semplice algoritmo per il calcolo della base utilizzata da un computer
`e il seguente:
a = 1.0 b = 1.0
while ((a + 1.0) − a) − 1.0 = 0.0 do a = 2.0 × a
end while
while ((a + b) − a) − b 6= 0.0 do b = b + 1.0
end while print b
Il valore di b rappresenta la base interna utilizzata dal computer.
2.8.3 Equazione di secondo grado
Si vuole un algoritmo che permetta di risolvere un’equazione di secondo grado, i cui coefficienti reali sono indicati con a, b e c, effettuando tutti i possibili controlli. Nel caso di due soluzioni reali distinte, l’algoritmo utilizza la formula usuale. Come si `e detto (vedi sezione 2.4.3), per evitare eventuali errori di cancellazione, `e preferibile utilizzare le formule alternative. L’algoritmo proposto pu`o essere facilmente modificato in tal senso come esercizio.
[x1, x2] = Eq grado2 (a, b, c)
if a = 0 then if b = 0 then
ifc = 0 then
printEquazione indeterminata else
printEquazione impossibile end if
else
x1= −c/b
printEquazione di grado 1 (unica soluzione x1) end if
else
∆ = b2− 4ac if ∆ < 0 then
printNessuna soluzione reale else if ∆ = 0 then
printDue soluzioni coincidenti (x1= x2) x1= −b/(2a)
x2= x1
else
printDue soluzioni distinte (x16= x2) x1= (−b −√
∆)/(2a) x2= (−b +√
∆)/(2a) end if
end if
2.9. Esercizi 49
2.9 Esercizi
Esercizio 2.1 Si scriva un algoritmo ed il relativo programma che, dati amin e amax, calcoli il primo numero positivo a ∈ F che sia maggiore di amin, ed il primo numero positivo a ∈ F che sia minore di amax, sia in semplice che in doppia precisione..
Esercizio 2.2 Si deve eseguire la somma di n numeri reali x1, . . . xn di cui non si conoscono a priori n`e i segni n`e l’ordine di grandezza. Se si lavorasse con precisione infinita un possibile algoritmo sarebbe
for i = 1, . . . , n read xi
end for somma = x1
for i = 2, . . . , n
somma = somma + xi
end for print somma
Si scriva un algoritmo che esegua la somma in modo da evitare i possibili errori dovuti all’aritmetica del computer. Si realizzi poi il programma che calcola la somma nei due modi, e si confrontino i risultati.
Esercizio 2.3 Si scriva un algoritmo per il calcolo del valore reale della seguente espressione (algebricamente uguale ad 1 per ogni valore di n), senza effettuare alcuna semplificazione:
Ãs n
n − 1×n − 1
n − 2 × · · · × n − (n − 2)
n − (n − 1)× n − (n − 1) 1
!2
× n − 1
n ×n − 2
n − 1 × · · · ×n − (n − 1)
n − (n − 2) × 1 n − (n − 1). Si realizzi poi un programma che effettui tale calcolo per n = 2, . . . , 100, sia in semplice che in doppia precisione, calcolando anche, per ogni n, l’errore assoluto, l’errore relativo ed il numero di cifre significative esatte.
Si analizzino poi i risultati trovati e si dica quali di essi sono affetti da errore dovuto all’aritmetica del computer e quali sono le possibili ragioni.
Esercizio 2.4 Si realizzi un programma che, utilizzando due funzioni corrispondenti ai due algoritmi di calcolo (diretto ed Horner), calcoli il valore di un polinomio P (x) in un punto ¯x (si veda la sezione 1.2.3).
Si confrontino i due risultati ottenuti al variare di ¯x ed al variare dei coefficienti del polinomio P (x).
Esercizio 2.5 Modificando opportunamente l’algoritmo proposto nella sezione 2.8.3, si introducano le formule stabili per la determinazione delle soluzioni reali di un’equazione di secondo grado a coefficienti reali (vedi sezione 2.4.3). Si scrivano poi i relativi programmi e si ritrovino i risul-tati della Figura 2.3.
Esercizio 2.6 Prendendo spunto dall’algoritmo proposto nella sezione 2.8.3, si scriva un algoritmo per il calcolo delle soluzioni (reali e/o com-plesse) di un’equazione di secondo grado a coefficienti reali.