Calcolo Numerico - Teoria

Calcolo Numerico

Definizione: Un algoritmo è una successione finita di istruzioni scritte in modo chiaro, le quali partono imponendo dei dati iniziali al fine di ottenere dei risultati. L'algoritmo, per essere definito tale, deve essere risolvibile in un tempo finito (istruzioni finite non implicano esecuzioni finite; a causa di eventi di loop).

Vi sono tre tipi di istruzioni per un algoritmo:

• INGRESSO
• INTERNE
• USCITA

• ASSEGNAZIONE
• SCELTA
• RIPETIZIONE

Per istruzioni di assegnazione si intendono quelle generali tipo "poni a=b" oppure "poni b=a".

Per istruzioni di scelta si intende "se a > 0 fai".

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

Gli algoritmi possono presentare istruzioni espresse:

• ITALIANO (con ripeti...)
• LINGUA A BLOCCHI ({...})
• PSEUDOPROGRAMMAZIONE (for)

Esempio:

Calcolo 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+a_i
5. Scrivi s
6. Stop

L'inizializzazione può essere di qualunque valore, onde s=a₁ o s=a_i-a₂, base per partire da valori congruenti di i, tipo s=a_i, i=3, n

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

1

• Leggi n, a₀, a₁, ..., aₙ, x
• Poni p := a₀
• Per i := 1, 2, ..., n
• 3 . 1 p := p · x + aᵢ
• Scrivi p
• Stop

Questo programma, nonostante sia corretto, impiega troppo tempo per l'intervallo di un polinomio per n grande. Infatti, ad ogni passaggio bisogna calcolare le potenze di x.

2

• Leggi n, a₀, a₁, ..., aₙ, x
• Poni p := 1
• Poni s := a₀
• Per i := 1, 2, ..., n
• 4 . 1 Poni p := x · p
• 4 . 2 s := s + aᵢ · p
• Scrivi s
• Stop

In questa versione, si è già utilizzato nella scrittura di s il valore delle potenze già calcolato come p. Possiamo ancora migliorare l'algoritmo riducendo il numero di operazioni da tre a due.

3

• Leggi n, a₀, a₁, ..., aₙ, x
• Poni s := aₙ
• Per i := n-1, n-2, ..., 0
• 3 . 1 s := s · x + aᵢ
• Scrivi s
• Stop

Questo algoritmo usa la formulazione di Horner, grazie alla quale si riesce a ridurre le operazioni a due. Si note che invece di partire dal valore più piccolo siamo partiti dal valore massimo per via via diminuire. Al terzo passaggio otteniamo una formula del tipo: s := (a₀ · x + aₙ) · x + aₙ.

Tale formulazione precede la raccolta di fattori comune dal termine xs m questo caso di m quando è possibile. Ad esempio dato P(x) = x³ + x² + 2x² - x - 5

P(x) = x(x(x + 2) - 1) + 5

Errori di arrotondamento e precisione di macchina

Vi sono due tipi di erore di rappresentazione.

• ASSOLUTO E_a = |x_fl - x_vero| cioè valore vero - valore approssimato
• RELATIVO E_r = |x_fl - x_i|

L'errore relativo è più significativo poiché è un sinonimo dell'ordine di grandezza del dato mentre è legato solo alla mantissa dei numeri e non dipende in alcun modo dalla caratteristica.

Possiamo quindi definire la precisione della macchina E_m come la limitazione superiore degli errori relativi o, in altre parole, come il peggior errore relativo che si può commettere con la rappresentazione dei numeri.

Nel caso in cui la macchina operi per troncamento E_r ≤ E_m dove E_m = b^-m

dove b e la base usate e m e il numero di cifre della mantissa.

Non è possibile che la precisione sia maggiore dell'errore relativo poiché E_r ≤ E_m per definizione.

Esempio: Dati a = 1/3 , m = 4, Trovare fl(a), E_r, E_m

macchina a troncamento

intanto portiamo a nella notazione esponenziale normalizzata

a = 0.333333 · 10⁰

a = 3.333333 · 10^-1

fl(a) = 3.333 · 10^-1

E_r = |a - fl(a)| / |a| = |1/3 - 3.333 · 10^-1| / 1/3 = 0.0001 = 1 · 10^-4

E_m = b^-m = 10^-4 = 10^-4 e come volevasi dimostrare E_r ≤ E_m

10^-4 ≤ 10^-3

Il metodo di bisezione

Il metodo di bisezione consiste nel dividere l'intervallo scelto a metà e valutare una variazione di mezzo val. a cui non si avvicina il risultato reale, quello con cui si selezionano i segni di f(a) e f(b) sono opposti. Valore minimo inizia all'interno di f in un punto zero.

Osserviamo che per n molte divisioni, intervallo [a,b] tende a zero agli k (b_n-a_n), (b_n-a_n) /2^k dove k indica che minimo rappresenta il numero di divisioni fatte.

Il algoritmo otteniamo

• Dati a,b , f, una
• Per i:=1,2 lasciare
• c = (a_i+b_i) /2
• Se |c_i| ≤ |bi