Appunti del corso Calcolo numerico e programmazione

Calcolo numerico e programmazione

C. Bracco – Scienze chimiche I anno II semestre – A.A. 2021-22 Calcolo numerico e programmazione

Il calcolo numerico

Il calcolo numerico si occupa di metodi numerici per approssimare le soluzioni di problemi matematici con:

• Accuratezza: garantisce, analizzando le proprietà del metodo, che la soluzione approssimata sia vicina a quella esatta;
• Semplicità d’implementazione: facile da tradurre in un algoritmo che può essere gestito da un computer.

Una volta costruito un metodo numerico e dimostrate le proprietà, va tradotto in un algoritmo, cioè un procedimento descritto in modo non ambiguo che consenta di passare da un insieme di dati ad un risultato in un tempo finito. Le istruzioni per acquisire i dati prendono il nome di INPUT, mentre la restituzione dei dati costituisce gli OUTPUT. In un linguaggio di programmazione, INPUT e OUTPUT sono contenuti in oggetti chiamati variabili.

Le istruzioni di assegnazione

Il nome di una variabile può essere scelto arbitrariamente, con alcune eccezioni.

Le istruzioni di scelta

Le istruzioni di scelta servono a prevedere l’esecuzione di diverse istruzioni a seconda del verificarsi o meno di una o più condizioni.

L’istruzione di scelta base è “if”; per prevedere due alternative si utilizza “else”; se invece le istruzioni sono annidate si utilizza “elseif”.

Università degli studi di Firenze 1

C. Bracco – Scienze chimiche I anno II semestre – A.A. 2021-22 Calcolo numerico e programmazione

Le istruzioni di ripetizione

Le istruzioni di ripetizione “ciclo for” servono a ripetere l’esecuzione di un gruppo di istruzioni un numero definito di volte.

Le istruzioni di ripetizione “ciclo while” servono a ripetere l’esecuzione di un gruppo di istruzioni finché una certa condizione è verificata.

Tutte queste istruzioni elementari possono essere combinate. Il costo computazionale si misura in operazioni aritmetiche.

Alcuni esempi

La notazione scientifica normalizzata

∈ ℕ, = ± , … ∙ ≠ 0

Fissata una base b il numero reale x viene rappresentato come con 0 1 2 0 (normalizzazione), dove: {0,1, , … ∈ … , − 1}, = 1, … è la mantissa, formata dalle cifre del sistema di numerazione in 0 1 2 base b; è l’esponente (o caratteristica) intero espresso in base b.

Università degli studi di Firenze 2

C. Bracco – Scienze chimiche I anno II semestre – A.A. 2021-22 Calcolo numerico e programmazione

Standard ANSI/IEEE 754/1985

{0,1}=2 = cifre q: intero binario

Le locazioni di memoria destinate alla memorizzazione di un numero reale sono suddivise in campi di lunghezza prefissata.

Le configurazioni estreme dell’esponente sono:

• →̂ = ≠ esponente e mantissa notazione scientifica denormalizzata
• →̂ = = esponente e mantissa numero 0 →() ()̂ ̂ = = ≠ esponente e mantissa Nan (indeterminato)
• →() ()̂ ̂ = = = +∞ esponente, mantissa e segno 0 →() ()̂ ̂ = = = −∞ esponente, mantissa e segno 1.

Le configurazioni intermedie dell’esponente sono:

• 1 ≤ ̂ ≤ 254 per la precisione semplice
• 1 ≤ ̂ ≤ 2046 per la precisione doppia = ̂ − 127 = ̂ − 1023.

Vengono utilizzate per rappresentare l’esponente con shift o Esiste una soglia || ≤ ≤ di underflow e overflow tale che −126 −38 127 38 ≈ 2 ≈ 10 ≈ 2 ≈ 10 (PS) −1022 −308 1023 308 ≈ 2 ≈ 10 ≈ 2 ≈ 10 (PD).

La mantissa ha le seguenti caratteristiche:

• 1, … se è del tipo allora è a numeri normalizzati; 1 2
• 0, … se è del tipo allora è a numeri denormalizzati; 1 2
• La prima cifra non viene mai memorizzata (bit nascosto); è il numero di bit a essa dedicati, incluso il bit nascosto (m=24 per PS e m=53 per PD);
• , = = ⋯ = 0. fissato si possono memorizzare tutti i numeri per i quali +1

L’insieme dei numeri di macchina è finito e discreto (floating point numbers).

Floating di x

(): ℝ → ℳ ∈ [min(ℳ) , max(ℳ)]

Si definisce floating di x che associa a un numero di macchina () ∈ ℳ ∈ [min(ℳ) , max(ℳ)], che lo approssima. Dato che si tratta di approssimare la mantissa ad cifre per:

• Troncamento (round toward zero)
• Arrotondamento (round to nearest).

15 = 10 = 5,1437 ∙ 10 = 4

Esempio. cifre di mantissa 15() = 5,143 ∙ 10 TRONCAMENTO 15() = 5,144 ∙ 10 ≥ perché la prima cifra scartata è . ARROTONDAMENTO 2

Università degli studi di Firenze 3

C. Bracco – Scienze chimiche I anno II semestre – A.A. 2021-22 Calcolo numerico e programmazione

Errori e precisione di macchina

() | = − ()|.

Errore di rappresentazione assoluto: |−()|

(): = Errore di rappresentazione relativo: . ||

TEOREMA: Sia un numero reale diverso da zero e il numero di cifre usate per la rappresentazione della per il troncamento −+1() < = { = 2 mantissa. Allora dove è l’epsilon di per l'arrotondamento 2 macchina (distanza fra il numero 1 e il successivo numero di macchina). è maggiore o uguale dell’errore relativo di rappresentazione, pertanto viene detta precisione di macchina.

Operazioni in aritmetica finita

⊕⊝⊙⊘.

Le operazioni di macchina sono A meno di fenomeni di underflow e overflow, il risultato di un’operazione di macchina può essere affetto da errori di arrotondamento dovuti alla necessità di ⊙ = approssimare il risultato. Lo standard IEEE 754 richiede che tale errore sia compatibile con: ( || ||( ∙ ) ⇔ ⊙ = ∙ )(1 + ) con ≤ , dove è l’errore relativo introdotto dall’operazione di macchina. ( || ⊙ = ( ∙ ) ⇔ ⊙ = ∙ )(1 + ) con ≤ Per soddisfare la relazione si usano registri, . cioè locazioni di memoria dove il numero di cifre per la memorizzazione della mantissa è maggiore di In generale, vale:

Concetti di base (elemento neutro per la somma, etc.) e proprietà algebriche (commutativa, associativa, etc.) non sono più valide lavorando in aritmetica finita.

Università degli studi di Firenze 4

C. Bracco – Scienze chimiche I anno II semestre – A.A. 2021-22 Calcolo numerico e programmazione

Calcolo dell’epsilon di macchina

1. La mantissa è assunta nella forma (notazione scientifica normalizzata) e viene memorizzata solo la −+1 = 2 # frazione f. Epsilon di macchina: , dove sono il di bit utilizzati per memorizzare la mantissa. −23 −7 ⇒ = 24 ⇒ = 2 ≈ 1,1921 ∙ 10 Singola precisione: 23 bit per la frazione ; −52 −16 ⇒ = 53 ⇒ = 2 ≈ 2,2204 ∙ 10 Doppia precisione: 52 bit per la frazione.

Una definizione alternativa è quella che definisce l’epsilon di macchina come il più piccolo numero floating point che sommato ad 1 restituisce un risultato maggiore 1.

= 1 ∀ < 1 ⊕ {Se è un numero di macchina, . > 1 ∀ ≥

Ordine delle operazioni e influenza di

=1 24 ∑ = 2 + 1

Supponiamo di lavorare in PS (=24) e dover calcolare con e −24 = 1, = = ⋯ = = 2 1) 1 2 3 −24 . = = ⋯ = = 2 , = 1 2) 1 2 −1

In entrambi i casi, sia i dati che il risultato sono numeri di macchina, ma utilizzando l’algoritmo per il calcolo della somma di n numeri:

•  −24 241 + 2 2 nel primo caso si ottiene il risultato sbagliato (1), poiché eseguo per volte ma ogni volta il risultato è 1;
•  Nel secondo caso si ottiene il risultato giusto (2), poiché tutte le operazioni avvengono tra numeri di macchina e producono risultati intermedi esattamente rappresentabili in macchina.

Università degli studi di Firenze 5

C. Bracco – Scienze chimiche I anno II semestre – A.A. 2021-22 Calcolo numerico e programmazione

Propagazione di errori - condizionamento

= (),

Un problema matematico può essere formalizzato come dove

•  dati del problema →
•  descrizione del problema →
•  risultato, soluzione del problema. →

(1 )̃ = + ̃ = (1 + ), Supponiamo di utilizzare dati affetti da errore: e dove e sono i |,| | ≈ | corrispondenti errori relativi. Sono legati secondo la relazione dove si chiama numero di ≈ 1 ≫ 1 condizionamento. Se gli errori non sono amplificati (problema ben condizionato), mentre se gli errori sono amplificati (problema mal condizionato).

̃̃Esempio: propagazione di errori nelle operazioni aritmetiche. Siano dati e , approssimazioni (1 ) . ̃ = + rispettivamente di e Indicando con ed i corrispondenti errori relativi, abbiamo che ̃ ̃ 22(1 ).= + ̃ , , ∙ e È ragionevole supporre che e siano “buone” approssimazioni e quindi ̃ ̃ siano trascurabili rispetto ad , . Se utilizzo e in ulteriori calcoli:

• = 2. PRODOTTO l’errore sul risultato è dello stesso ordine di quelli iniziali e →
• = 2. DIVISIONE l’errore sul risultato è dello stesso ordine di quelli iniziali e →
• ||+|| = SOMMA . →

|+| ||+||| || || ||+ | < + ⟹ = > 1. ≈ Gli errori sono amplificati se Se e hanno segno opposto e |+|||, | + | allora è molto piccolo e gli errori vengono amplificati; questo fenomeno prende il nome di cancellazione numerica.

Università degli studi di Firenze 6

C. Bracco – Scienze chimiche I anno II semestre – A.A. 2021-22 Calcolo numerico e programmazione

Zeri di funzioni

: ℝ → ℝ: Si vogliono determinare gli zeri di una funzione dobbiamo quindi calcolare i valori tali che () = 0. Se non è lineare i metodi diretti di risoluzione del problema possono essere costosi e, in generale, possono non esistere. Sfruttiamo quindi i metodi iterativi, cioè dobbiamo scegliere:

•  Il punto d’innesco, ovvero l’approssimazione iniziale 0
•  ): = (la funzione di iterazione +1
•  E il criterio di arresto.

{ }Un metodo iterativo genera, a partire da , una successione di approssimazioni successive .0 =1,…,() = 0

Due parametri standard per confrontare metodi iterativi diversi per la risoluzione numerica di sono:

• Il costo computazionale ovvero il costo di una singola iterazione misurato in base al numero di → valutazioni della funzione e, se necessario, della sua derivata;
• La velocità di convergenza legata al # di iterazioni necessarie per ottenere un’approssimazione della → soluzione con una certa accuratezza assumendo un dato errore iniziale.

∗ ∗ ∗ )lim = ( = 0.

Un metodo si dice convergente se dove è tale che →∞ ∗{ } La successione deve convergere ad una radice dell’equazione considerata. I tre aspetti che =1,2,… caratterizzano un metodo iterativo determinano:

• ◆ La convergenza della successione (il punto di innesco);
• ◆ La velocità di convergenza (la funzione di iterazione);
• ◆ L’accuratezza dell’approssimazione (il criterio di arresto).

Scelta del punto di innesco

L’approssimazione iniziale considerata può influire o meno sulla convergenza del metodo. Un metodo iterativo converge:

•  Localmente se la convergenza della successione dipende in modo critico da ; →
•  Globalmente se la convergenza della successione non dipende da . →

Scelta della funzione di iterazione

∗La scelta del metodo iterativo influisce sulla velocità di convergenza ad una soluzione , ovvero sul numero di iterazioni necessarie per avvicinarsi alla radice dell’equazione. Un metodo iterativo è convergente di | | ∗+1 lim = < ∞ = − ordine se , dove è il fattore di convergenza. | |→∞ è il più grande valore che soddisfa il limite, mentre è la costante (reale) asintotica dell’errore diversa da = 1 = 2 zero. Se si parla di convergenza lineare, mentre se la convergenza è quadratica. In generale

Università degli studi di Firenze 7

C. Bracco – Scienze chimiche I anno II semestre – A.A. 2021-22 Calcolo numerico e programmazione

≥ 1 l’ordine di convergenza può assumere anche valori non interi, ma deve comunque essere affinché il metodo sia convergente.

Scelta del criterio di arresto

∗ ∗ Si vuole determinare un’approssimazione della soluzione che disti da al più una tolleranza fissata. Ci sono due condizioni:

∗ ∗| | | | = − ≤ .

1. si deve arrestare il metodo quando (ma non è nota)

)() = 0 ( = 0

2. un criterio di arresto per il problema deve tener conto che la condizione potrebbe non verificarsi mai:

∗ ∗) ( = , () se è continua e in aritmetica esatta, in un punto sufficientemente vicino a , dovrà essere sufficientemente vicino a 0;

) |( )|( = < il controllo può essere sostituito con uno del tipo , dove è una tolleranza tale che la prima condizione sia verificata.

, ( )Per trovare assumendo sufficientemente regolare, si considera lo sviluppo di Taylor di nel )||(∗ ∗ ∗ ∗ ∗ ∗ ) ) )( ) )( ) | | ( ≈ ( + ′( − = ′( − ≈ < punto al primo ordine: quindi ′ ∗| ( )|′ ∗ ′ ∗|( )| | ⇔ < ≈ ( )| ( )con anche se in generale non è noto e se ne considera un’approssimazione:

• ′ ∗| ≪ ( )| ≈ se (funzione molto piatta);
• ′ ∗| ≫ ( )| ≫ se (la tangente a ha un grosso coefficiente angolare).

Criteri di salvaguardia

È buona norma usare sempre un criterio di salvaguardia: si fissano a priori un numero massimo di iterazioni da eseguire indipendentemente dall’aver raggiunto l’accuratezza desiderata (per evitare loop infiniti). Questo è importante per i metodi:

• Globalmente convergenti nel caso in cui il programmatore abbia impostato una tolleranza non → considerando la precisione di macchina;
• Localmente convergenti per i quali la successione di approssimazioni può divergere se il punto di → ∗ innesco non è sufficientemente vicino a , non soddisfando mai alcun criterio di arresto possibile.0

Università degli studi di Firenze 8

C. Bracco – Scienze chimiche I anno II semestre – A.A. 2021-22 Calcolo numerico e programmazione

Condizionamento del problema

′ ∗ ∗| ( )|. | |, | | ≈ ≈ − ≈ Riprendiamo in considerazione la relazione Essendo si ha che 1 1 ∗ ∗ ∗ ∗|( ) )|, | | |( ) )| ) )| ≈ − ( − ≈ − ( = |( − (e, dato che ′ ∗ ′ ∗( )| ( )|| |1 = dove è il numero di condizionamento del problema. ′ ∗( )||

Metodo di bisezione

[, ], ∈ ([, ]), < , () ∙ () < ⇒Se è una funzione conti