Calcolo numerico - teoria del corso

Calcolo numerico

Algoritmi

Un algoritmo è una successione finita di istruzioni che ci permette di passare da una situazione iniziale (dati) ad una situazione finale (risultati).

Dati → Algoritmo → Risultati

• Successione finita di istruzioni
• Modo non ambiguo (preciso e ordinato)
• Fa passare da dati a risultati
• Tempo finito

Un buon algoritmo deve avere 2 requisiti:

• Generalità → deve risolvere una classe di problemi
• Ottimalità → deve essere un algoritmo "ottimale", cioè il migliore rispetto al tempo, rispetto al numero di operazioni, ecc.

Es.:

Somma di n numeri

Somma di n numeri a₁, a₂, ..., a_n

1. Leggi: n, a₁, a₂, ..., a_n
2. Poni S = 0
3. Per i = 1, 2, ..., n
4. Poni S = S + a_i
5. Scrivi S
6. Stop

Prodotto di n numeri

Prodotto di n numeri a₁, a₂, ..., a_n

1. Leggi: n, a₁, a₂, ..., a_n
2. Poni P = 1
3. Per i = 1, 2, ..., n
4. Poni P = P * a_i
5. Scrivi P
6. Stop

Calcolo numerico

Algoritmi

Un algoritmo è una successione finita di istruzioni che ci permette di passare da una situazione iniziale (dati) ad una situazione finale (risultati).

Dati → Algoritmo → Risultati

Algoritmo

• Successione finita di istruzioni
• Modo non ambiguo (preciso e ordinato)
• Fa passare da dati a risultati
• Tempo finito

Un buon algoritmo deve avere 2 requisiti:

• Generalità: deve risolvere una classe di problemi
• Ottimalità: deve essere un algoritmo "ottimale", cioè il migliore rispetto al tempo, rispetto al numero di operazioni ecc.

Es.

Somma di n numeri

Somma di n numeri a₁, a₂, ..., a_n

1. Leggi: n, a₁, a₂, ..., aₙ
2. Poni S = 0
3. Per i = 1, 2, ..., n
4. Poni S = S + aᵢ
5. Scrivi S
6. Stop

Prodotto di n numeri

Prodotto di n numeri a₁, a₂, ..., a_n

1. Leggi: n, a₁, a₂, ..., aₙ
2. Poni P = 1
3. Per i = 1, 2, ..., n
4. Poni P = P * aᵢ
5. Scrivi P
6. Stop

Problema: determinare √N

Adesso prendiamo come problema il seguente: determinare √N, N > 0 mediante un procedimento iterativo.

Procedimento iterativo

Procedimento che si basa su una sequenza di istruzioni ripetute continuamente con lo scopo di trovare una soluzione o di avvicinarsi il più possibile ad essa.

Non è certo che sia un numero finito di istruzioni.

→ Non è un algoritmo (dato che può non finire)

Determinare √N, N > 0

1. Individuare m, h > 0 tale che: m² < N < h²
2. Calcolare c = (m+h)/2
3. Se c² = N, c = √N → Stop
4. Se c² < N → sostituire c con m e tornare al punto 2
5. Se c² > N → sostituire c con h e tornare al punto 2

Dato che per molti numeri non esiste un valore preciso di radice quadrata, dobbiamo trovare un numero di iterazioni dopo le quali fermarsi.

Questo "numero finito" renderebbe il nostro procedimento iterativo un algoritmo a tutti gli effetti.

A differenza del procedimento iterativo il controllo dell'uguaglianza viene sostituito da un controllo di approssimazione dopo aver superato il numero di iterazioni di esempio.

Criterio di arresto

Decidiamo di fermarci se:

|c² - N| ≤ ε, ε > 0

dove c è un'approssimazione di √N

c = (m+n)/2

Quando il problema determinare √N, N > 0 sarebbe risolto dal seguente algoritmo:

1. Leggi N, m, n, ε
2. Calcola c = (m+n)/2
3. Se |c² - N| ≤ ε → Vai al punto 6
4. Se c² < N poni m = c e vai al punto 2
5. Se c² > N poni h = c e vai al punto 2
6. Scrivi c
7. Stop

Con il criterio d'arresto c'è un rischio:

I numeri m, n troppo grandi oppure il valore ε troppo piccolo potrebbero implicare troppo tempo di calcolo.

Può essere giusto fissare un numero massimo di iterazioni:

Esempio:

1. Leggi h, m, N, ε, N_max
2. Per n = 1, 2, ... N_max

Calcola c = (m+n)/2

Se |c² - N| ≤ ε → Vai al 6

Se c² &