Riassunto esame Calcolo Numerico e programmazione, prof. Putti

Fondamenti di calcolo numerico e programmazione

Appunti presi dalle lezioni del prof. Mario Putti

Alessandro Ramon

Indice

• Parte 1
• Funzionamento del calcolatore................................................................................................................1
• Risoluzione di equazioni non lineari..........................................................................................................................6
• Interpolazione e approssimazione polinomiale..........................................................................................................27
• Quadratura numerica e approssimazione degli integrali definiti.............................................................................38
• Parte 2
• Problemi di algebra lineare............................................................................................................................43
• Appendice
• Matematica in base 2...............................................................................................................................................51
• Errore di Lagrange – Dimostrazione..................................................................................................................52
• Algebra lineare e geometria – Cenni..................................................................................................................53

Funzionamento del calcolatore

L'elemento alla base del funzionamento di un calcolatore è la CPU – Central Processing Unit – che lavora secondo un ciclo Fetch – Decode – Execute (FDE):

1. Fetch: la CPU preleva da una memoria (v. memoria) i dati da elaborare
2. Decode: la CPU decodifica il dato
3. Execute: la CPU esegue, se possibile, l'operazione richiesta

Esempio: Si vuole eseguire il calcolo “2 + 3 = 5”

1° Ciclo:

• Fetch: la CPU preleva il dato “2”
• Decode: la CPU traduce il dato nel numero “2”
• Execute: non si hanno tutti i dati disponibili, quindi non avviene la fase Execute

2° Ciclo:

• Fetch: la CPU preleva il dato “3”
• Decode: la CPU traduce il dato nel numero “3”
• Execute: non si hanno tutti i dati disponibili, quindi non avviene la fase Execute

3° Ciclo:

• Fetch: la CPU preleva l'istruzione “+”
• Decode: la CPU traduce il dato nel termine “+”
• Execute: la CPU esegue l'istruzione “2+3” e fornisce il risultato “5”

Il ciclo FDE è denominato “ciclo di clock”. Come si è visto, il ciclo di clock è un'operazione continua, perciò, se non avviene una delle fasi del ciclo, questo ricomincia. La velocità del ciclo di clock è la velocità del processore (es. 1 GHz = 10⁹ cicli/secondo).

Per consentire il salvataggio dei risultati delle operazioni nella memoria, la fase di Fetch è bidirezionale. Per memorizzare i dati, la CPU ricorre a sequenze di numeri in linguaggio binario: una cifra binaria è detta “bit”. Per il calcolo della memoria, si utilizzano le seguenti equivalenze:

• 8 bit = 1 byte (B)
• 1024 B = 1 KB
• 1024 KB = 1 MB
• 1024 MB = 1 GB
• 1024 GB = 1 TB

I calcolatori lavorano su “pacchetti di bit” di dimensioni variabili – es. i calcolatori più vecchi lavorano a pacchetti da 32 bit, i moderni calcolatori a pacchetti da 64 bit, i telefoni cellulari lavorano a pacchetti tra i 12 e i 24 bit.

Memoria

La prima memoria è detta RAM – Random Access Memory – e la CPU interagisce con essa tramite i cosiddetti “bus”.

Problema 1: i bus lavorano a una frequenza compresa tra i 200 e 400 MHz, perciò la CPU non può lavorare alla sua velocità effettiva. Inoltre, produrre bus capaci di lavorare alla velocità della CPU richiede costi di produzione non indifferenti!

Per risolvere il problema in maniera più economica, alla memoria RAM si affianca un'ulteriore memoria, di tipo RAM, più piccola ma più veloce, detta “memoria cache”, dotata di algoritmi di previsione delle operazioni: attraverso i buffer della memoria Cache, la CPU può lavorare ad una velocità più prossima alla sua velocità effettiva.

Problema 2: la memoria RAM è una componente elettronica, quindi non è capace di mantenere i dati senza una continua alimentazione! Per motivi pratici, quindi, alla memoria di tipo RAM si affianca una seconda memoria, più lenta ma indipendente dall'elettricità, poiché magnetica: questa memoria è detta Hard Disk.

L'architettura del calcolatore che si delinea è detta Architettura di Van Neumann.

Memorizzazione dei numeri

A 32 bit

Ipotesi 1: il pacchetto da 32 bit viene diviso in due blocchi, ossia un blocco da 1 bit per il segno e un blocco da 31 bit per il numero. In questo modo, il numero più alto descrivibile è:

N_max = 2³¹ - 1 = 2,147,483,647

A 64 bit

Ipotesi 1: il pacchetto da 64 bit viene diviso in due blocchi, ossia un blocco da 1 bit per il segno e un blocco da 63 bit per il numero. In questo modo, il numero più alto descrivibile è:

N_max = 2⁶³ - 1 = 9,223,372,036,854,775,807

Problema 1: se si lavora con numeri prossimi a N_max, il calcolatore è soggetto al cosiddetto “max Integer Overflow”.

Esempio: a 32 bit, sommiamo N_max e 1: il risultato vero sarebbe 1, ma per il calcolatore il risultato è -0.

Problema 2: memorizzando ogni cifra, compresi gli 0 prima della prima cifra non nulla, si memorizzano informazioni inutili, con conseguente spreco di memoria. Es: (-1)₃₂ = 10000000000000000000000000000001

Si utilizza, quindi, la Notazione in Virgola Mobile Normalizzata o “floating point”: in base 2, f(b) = ±1.m · 2^f, dove m è detto “mantissa” e 1 è il cosiddetto “hidden bit”.

A 32 bit, i dati sono disposti in tre blocchi, di cui uno da 1 bit per il segno, uno da 8 bit per l'esponente f, e uno da 23 bit per la descrizione del numero 1.m.

A 64 bit, i dati sono disposti in tre blocchi, di cui uno da 1 bit per il segno, uno da 11 bit per l'esponente f, e uno da 52 bit per la descrizione del numero 1.m.

Problema: f può essere negativo, ma tra i bit dedicati all'esponente non vi è il bit del segno! Si utilizza quindi il “biased exponent”: poiché a 32 bit f è compreso tra 0 e 255, e a 64 bit f è compreso tra 0 e 2047, si pone f_trasposto = 127 (32), f_reale = 1023 (64).

A 32 bit, il numero massimo e il numero minimo descrivibili diventano quindi:

N_max, N_min ≈ 1.7 · 10³⁸, 10^-38

A 64 bit il numero massimo e il numero minimo descrivibili diventano:

N_max, N_min ≈ 3 · 10³⁰⁸, 10^-308

Struttura dell'elaboratore

Cos'è un file?

Un file è un insieme di indirizzi di celle di memoria, che si presenta nella forma:

nome.estensione

dove “.estensione” fa riferimento a un preciso programma di lettura.

Esempio:

• nome.doc → Word
• nome.pdf → Adobe Reader

Cos'è una directory?

Una directory è una collezione di file, ossia un file che contiene una lista di altri file.

Struttura delle directory – File System

La struttura delle directory è una struttura ramificata detta File System, leggibile tramite appositi programmi di lettura.

Esempio:

• Microsoft Windows → Gestione Risorse
• Fedora → Comandi al Terminale

(In Fedora) i simboli “.” e “..” sono interpretati dal calcolatore come “directory corrente” e “directory precedente”.

Compilazione in Fedora

Un file del tipo: nome.f è un codice scritto in linguaggio FORTRAN tramite un apposito editor di testo (Gedit).

Un file nome.f può, ad esempio, essere:

program Salutami
write(*,*) 'Buongiorno!'
stop
end

Un file nome.f non è eseguibile: per questo, deve essere convertito in linguaggio binario da un compilatore, ossia un programma che analizza il file nome.f, lo converte e lo trascrive in un nuovo file eseguibile del tipo: nome.out

In Fedora, la compilazione viene eseguita tramite il comando:

gfortran file.f -o file.out

Successivamente, si potrà eseguire il file compilato tramite il comando:

./file.out

Attraverso il quale la CPU preleverà file.out (Fetch), lo tradurrà in formato ASCII (Decode) e mostrerà i risultati dell'esecuzione sullo schermo (Execute).

Esempio:

~]$ ./file.out
Buongiorno!

Per compilare file.f, il compilatore lavora in due fasi:

1. Compilazione: viene generato il file file.o, denominato “object file”
2. Link: collega file.o e file.f, prelevando le istruzioni necessarie dal file libfortran.a per produrre l'eseguibile file.out.

Precisione di macchina

Nel momento in cui si descrive un numero nella forma esponenziale f(b) = ±1.m · 2^f, si commette un errore in m, poiché il calcolatore lavora a precisione finita: il modulo dell'errore è:

ε = 2^-(s+1), s ∈ ℝ

A 32 bit si ha ε₃₂ = 10^-8, mentre a 64 bit si ha ε₆₄ = 10^-16.

Risoluzione di equazioni non lineari – Introduzione

Quando si risolve un problema, poiché ε ≠ 0 per ogni s, è necessario valutare se l'errore è tale da distruggere l'accuratezza del conto, o se invece è possibile considerare i risultati esatti entro il limite dell'errore.

Stabilità e condizionamento

Definizione: uno schema/algoritmo si definisce stabile se la propagazione dell'errore non è distruttiva dell'accuratezza del calcolo.

Definizione: uno schema/algoritmo si definisce ben condizionato se piccole variazioni dei dati non determinano grandi variazioni dei risultati.

Esempio 1: Intersezione tra due rette r e s in questo caso la variazione del risultato è comparabile con la variazione del dato, quindi per piccole variazioni del dato si hanno piccole variazioni dei risultati: il problema è ben condizionato.

Esempio 2: Intersezione tra due rette r e t In questo caso la variazione del risultato è molto maggiore della variazione del dato, quindi per piccole variazioni del dato NON si hanno piccole variazioni dei risultati: il problema è MAL condizionato.

Esempio 3: Analizzare l'integrale:

I = ∫01 xn ex dx

Tramite l'integrazione per parti si ha la formula: I = (e^x · xⁿ − n · ∫ x^n-1 e^x dx), ossia una formula ricorsiva.

Parto quindi dal dato iniziale: I₀ = 1 - e.

Problema: I₀ ha infinite cifre decimali a causa del termine “e”.

Approssimo, quindi, il termine I₀, e pongo: I₀ ≈ ~I₀.

Poiché I₀ ≠ ~I₀, vi è un errore ε₀, da cui ~I₀ = I₀ + ε₀.

Si ha quindi: n · ~I_n = n · (I₀ + ε₀)

Problema: L'errore cresce in modo esponenziale, quindi, per n sufficientemente grande, l'accuratezza del calcolo è nulla, quindi lo schema è instabile!

Adotto, quindi, un altro metodo: poiché lim_n→+∞ I_n = 0, scelgo un termine N sufficientemente grande e pongo:

~In = In

Ottengo quindi ε_N = ε₀ · 1/N!, ovvero, ho un errore che si riduce progressivamente: lo schema è stabile.

Problema del punto fisso

La risoluzione di equazioni non lineari è correlata al classico problema:

"Data la funzione f, trovare x ∈ ℝ tali che f(x) = 0"

Tale problema può dare una o più soluzioni in numero finito (es. f(x)=x²-4, f(x)=x-3), infinite soluzioni (es. f(x)=sen(x)) o nessuna soluzione (es. f(x)=x+3).

Per valutare se la mia soluzione x tende al valore vero in modo sufficientemente accurato, valuto f(x):

Se f(x) ≈ 0, allora x ≈ soluzione.

ATTENZIONE! Il metodo di verifica non è sempre valido!

Esempio: f(x) = x² + τ · 10^-8

Ponendo x = 0, si ha f(x=0) = τ · 10^-8 ≪ τ, ma il problema originario non ha soluzioni!

Esercizio: Trovare x ∈ ℝ tali che f(x) = 0, dove f(x) = x² - 3x + 2

La risoluzione analitica del problema fornisce i seguenti risultati:

x = 3 ± √Δ / 2 ⇒ ψ₁ = 1 ∨ ψ₂ = 2

Problema: Un elaboratore non lavora analiticamente, ma solo numericamente!

Costruisco, quindi, una successione tale che:

{xk} → ψ

La successione è data dall'equazione: x_k+1 = g(x_k)

Tale equazione è un problema di punto fisso, e rappresenta l'intersezione tra curva y = g(x) e la retta y = x: la funzione g si ottiene esplicitando la variabile x nell'equazione f(x) = 0.

Esempio: x + log(x) = 0 → x = -log(x) o x = e^-x

Definizione: uno schema si definisce fortemente consistente se, sostituendo il valore vero della soluzione, si ottiene un'identità.

Lo schema del punto fisso, o di Picard, è fortemente consistente per definizione:

(x → ψ) → (ψ = g(ψ))

Nel nostro caso, f(x) = x² - 3x + 2: potrò quindi esplicitare x in due modi diversi, ottenendo dunque due funzioni g:

• g₁(x) = x - √(3x - 2)
• g₂(x) = (x + 2)/3

Definiamo, inoltre, una terza funzione, di cui si discuterà successivamente:

• g₃(x) = 2/(x - 3)

Componiamo, dunque, lo schema per la prima funzione:

x0 = 3
x1 = g1(x0) = 2.645
x2 = g1(x1) = 2.4367
x3 = g1(x2) = 2.3043
...
x∞ = g1(x∞) ≈ 2

Lo schema mi dà, effettivamente, una delle radici di f(x) = x² - 3x + 2.

Componendo lo schema con la seconda funzione di punto fisso, si ha: x_k → +∞, dunque inefficace!

Componendo lo schema con la terza funzione, si ha:

x0 = 3
x1 = g3(x0) = 2.333
x2 = g3(x1) = 2.0667
x3 = g3(x2) = 2.0039
x4 = g3(x3) = 2.000015

Già alla terza iterazione, lo schema fornisce una buona approssimazione della soluzione x = 2, migliore del valore fornito alla terza iterazione dalla prima funzione: la terza funzione risulta, quindi, MOLTO più veloce della prima funzione!

Definendo l'errore ε_k+1 = |x_k+1 - ψ| e studiando il rapporto ε_k+1/ε_k, si osserva che esso, per x_k+1 = g₁(x_k), assume un valore M approssimabile a 0.73.

Si ha quindi: ε_k+1 ≈ 0.73 · ε_k → 0 per k → +∞

Studiando il rapporto ε_k+1/ε_k per x_k+1 = g₂(x_k), si osserva che esso assume un valore M maggiore di 1: per questo motivo, lo schema è instabile, poiché ε_k+1 → +∞ per k → +∞.

Per x_k+1 = g₃(x_k), si osserva che il rapporto ε_k+1/ε_k assume un valore prossimo allo 0.

Si può dimostrare che i valori di M corrispondono ai valori delle derivate prima delle funzioni g₁, g₂ e g₃ per x = ψ.

Si osserva, quindi, che lo schema più stabile e consistente, g₃, è quello per cui si ha il valore minore della derivata prima per x = ψ.

Definizione: Convergenza

Cosa significa che uno schema funziona “fino a convergenza”? A che valore dell'iterazione k è possibile fermarsi?

lim_k→+∞ |x_k - ψ| = 0 = g(x_k), ossia:

Osservo: Se si ha una variazione |x_k+1 - x_k| = d_k < τ, calcoli ulteriori non sono utili, poiché i risultati non compaiono tra le cifre significative di x_k!

N.B: Sarà necessario verificare SE e QUANDO vale la relazione:

|ε_k+1| ≤ |x_k+1 - ψ| ⋅ C ≤ τ

Implementazione del metodo del punto fisso

Per inserire...