Calcolo Numerico - Teoria

Calcolo numerico

Definizione

Un algoritmo è una successione finita di istruzioni scritte in modo chiaro, le quali partendo da dati iniziali al fine di ottenere dei risultati. Un algoritmo per essere definito tale deve essere risolvibile in un tempo finito (istruzioni finite non implicano esecuzioni finite, a causa di eventuali loop).

Tipi di istruzioni per un algoritmo

Vi sono tre tipi di istruzioni per un algoritmo:

• Ingresso
• Interno
• Uscita

Istruzioni di assegnazione

Per istruzioni di assegnazione si intendono quelle generali tipo: poni a:=b-c oppure poni s:=c.

Istruzioni di scelta

Per istruzioni di scelta si intende: se a > 0 f(a).

Istruzioni di ripetizione

Per istruzioni di ripetizione si intende: ripeti questo fino a.

Espressioni degli algoritmi

Gli algoritmi possono presentare istruzioni espresse:

• Italiano (poni, ripeti)
• Linguaggio a blocchi { } [ ]
• Pseudoprogrammazione {for }

Esempio: Calcola la somma di n numeri

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

Inizializzazione

L'inizializzazione può essere di qualunque valore, anche s:=a1 o s:=a1+a2, basta poi partire da valori congruenti di i, tipo i:=2.

Per il prodotto, l'elemento neutro non è zero ma è 1.

Esempio: Calcolate la somma di n numeri

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

Inizializzazione alternativa

L’inizializzazione può essere di qualunque valore, anche s:=a1 o s:=a1+a2. In base però partire da valori congruenti di s:=a1 i:= ....

Per il prodotto l’elemento neutro non è zero ma è 1.

Esempio 1

1. Leggi n, a_n, a_n-1,...,a₁, x
2. Poni p = a0
3. Per i = 1, 2,..., n
1. Poni p = p * x + ai
4. Scrivi p
5. Stop

Esempio 2

1. Leggi n, a₀, a₁,...,a_n, x
2. Poni p = 1
3. Poni s = a0
4. Per i = 1, 2,..., n
1. Poni p = p * x
2. s = s + ai * p
5. Scrivi s
6. Stop

Esempio 3

1. Leggi n, a₀, a₁,..., a_n, x
2. Poni s = an
3. Per i = n-1, n-2,...,0
4. s = s * x + ai
5. Scrivi s
6. Stop

Esempio: Calcolo della media aritmetica di n numeri

1. Leggi n, x₁,..., x_n
2. Poni s:=x1
3. Per i:=3,...,n
4. s:=s+xi
5. Poni media s/n
6. Scrivi media
7. Stop

Esempio: Costruire la matrice A i cui elementi a_ij = 1/(i+j)

1. Leggi n
2. Per i, j = 1, … , n
3. aij=1/(i+j)
4. Scrivi A
5. Stop

Esempio: Risolvere il sistema lineare Ax=b

1. Leggi A, b, n
2. Per i:=1, … , n
3. Se aii =0 vai all’istruzione
4. xi= bi/aii
5. Scrivi xi=(x1, x2, ..., xn)
6. Stop
7. Scrivi “sistema non risolvibile”
8. Stop

Esempio: Risolvere il sistema lineare Ax=b dove A è una matrice non triangolare superiore

1. Leggi A, b, n
2. Se ann = 0 vai all'istruzione 7
3. Altrimenti vai in sequenza
4. xn = bn/ann
5. Per i = n-1 ... 1
1. Se aii = 0 vai all'istruzione 7
2. Altrimenti vai in sequenza
3. xi = (bi - ∑j=i+1naijxj)/aii