Appunti completi per l'esame di Calcolo numerico

28.02

aritmetica di precisione finita

ALGORITMO

definizione

• istruzioni chiare (non ambigue)
• algoritmo di base

es: algoritmo della somma di n numeri:

ALGORITMO Dati a₁, a₂, …, a_n calcola S = ∑_i=1ⁿ a_i

Scrivi S

ALGORITMO Dati a₁, a₂, …, a_n calcola P = a₁a₂…a_n

ALGORITMO Dati a₁, a₂, …, a_n calcola M = max d_i

apponiamo il valore del massimo

GLI ALGORITMI devono essere generali!

M = 0Per i = 1, …, n

ALGORITMO

Dati A ∈ ℝ^m×n , x ∈ ℝⁿ

Per i = 1, ..., m

• y_i := 0
• Per j = 1, ..., n
• y_i := y_i + a_ij · x_j

y := (y₁, y₂, ..., y_m)

y_i = ∑_j=1ⁿ a_ij x_j

per i = 1, ..., m

(j invece varia da 1 a n)

ALGORITMO

Dato x calcola e^x = ∑_k=0^∞ x^k / k!

exp := 1

k := 1 resto := x^k / k!

Fin tanto che |resto| > tol

• while exp := exp + resto
• k := k + 1 resto := x^k / k!

(quando |resto| ≤ tol esco) !!

e^x = 1 + x + x² / 2! + x³ / 3! ...

Una norma misura la lunghezza di un vettore

NORME DI VETTORE

Una norma in ℝⁿ è una funzione ‖.‖ che associa ad un vettore x ∈ ℝⁿ, uno scalare ‖x‖ ∈ ℝ ed è tale

1. ‖x‖ ≥ 0 se ‖x‖ = 0 se e solo se x = 0
2. ‖α x‖ = |α| ‖x‖ ∀α ∈ ℝ
3. ‖x + y‖ ≤ ‖x‖ + ‖y‖ ∀x, y ∈ ℝ

diseguaglianza triangolare

Norma P, p ≥ 1, x = (x₁, x₂, ..., x_n) riga o colonna

‖x‖_p = (∑_i=1ⁿ |x_i|^p)^1/p

p = 1 ‖x‖₁ = ∑_i=1ⁿ |x_i|

p = 2 ‖x‖₂ = √(∑_i=1ⁿ x_i²)

p = ∞ ‖x‖_∞ = max |x_i| 1≤i≤n

Norme equivalenti

‖x‖_∞ ≤ ‖x‖₁ ≤ n ‖x‖_∞

‖x‖_∞ ≤ ‖x‖₂ ≤ √n ‖x‖_∞

(x = (x₁, x₂, ..., x_n)

x = (2, -3, 0)

‖x‖₁ = 2 + 3 = 5

‖x‖₂ = √(13), 3.6

‖x‖_∞ = 3

Tuttavia nelle situazioni reali conosciamo solo X, non X.

⇒ Volte conoscere X ma ho trovato solo una sua approssimazione X

quindi non posso confrontarlo con quello esatto

Concetto di cifre significative

Definizione: sono le cifre nell'X che sono affidabili.

quando X e X sono espressi in virgola mobile normalizzata e l'errore

e allora X approssima X con cifre significative, ovvero cifre

il calcolatore commette errori e io so lavorare con cui opera

esempio 1 (da esempio precedente)

e_R = 7 · 10^-5 ≤ 10^-4

= 0,58954

esempio 2

X = 10,000

X = 9999

= 10^-4

esempio 3

X = 0,42720

e_R ≤ 10^-2

X = 0,62563

e_R = 3,7 · 10^-2

Errore relativo e assoluto fra vettori

x, x ∈ X

norma vettoriale

X = ‖‖ → lunghezza della differenza tra i vettori

e_R = ‖‖ / ‖‖

1^o effetto della precisione finita

non tutti i numeri vengono rappresentati

(ci sono dei limiti)

Spazio finito per la mantissa

intanto so che -(β^p-1) ≤ b ≤ β^p-1 (no underflow / overflow)

ma se il numero ha bisogno di più di m cifre per la mantissa

0.x ± 0.2d2...dm dm+1 dm+2...β^p β m cifre

La macchina memorizza un'approssimazione del numero

si dice FLOATING fl(x)

Regola del troncamento

tolgo le cifre dopo dm

fl(x) = ± 0.2d2...dm β^b

Regola dell'arrotondamento

fl(x) = ± 0.2d2...dm β^p se dm+1 < β/2

± 0.2d2...dm + 1β^b se dm+1 ≥ β/2

{ tiene conto della prossimità del primo numero troncato e "approssima al numero più vicino" }

+-1 e non è il pedice (incremento di un'unità l'ultima cifra)

questi tipi di approssimazioni non vengono segnalati dalla macchina

Precisione di macchina E_m

rappresenta quanto è accurata la macchina nella rappresentazione dei numeri

se voglio rappresentare x ma non posso => viene rappresentato fl(x)

x ≠ 0

|x-fl(x)| _{ERRORE RELATIVO}

nel caso migliore

fl(x) = x numero di macchina

non ho errore

^|x-fl(x)|/_|x| ≤ E_m

E_m mi dice il massimo errore possibile

{ E_m = β^1-m regola del troncamento

E_m = 1/2 β^1-m dell'arrotondamento più accurato

(poiché la limitazione superiore è inefficace (piccola)) }

E_m dipende da:

• numero di cifre per la mantissa
• non dipende dall'ordine di grandezza

Proprietà: Stabilità di un algoritmo

Un algoritmo si dice stabile se restituisce risultati accurati nei limiti della precisione di macchina. Instabile altrimenti. Esempio: Em ≅ 10^-16 se l'accuratezza dei risultati è compatibile con 10^-16

L'algoritmo è stabile perché fa meno calcoli.

• Tra le norme quello che propaga meno errori di arrotondamento è la norma ∞
• ||x||₁ = Σ |x_i|
• ||x||₂ = ^√Σx_i²
• ||x||_∞ = max |x_i|

Calcolo degli zeri (o radici) di funzioni

f(x) = 0 , f: IR → IR non lineare → non possiamo conoscere le radici con un'espressione in forma chiusa

Metodo: definizione generale

• Sono iterativi → non esistono procedimenti di natura differente
• (Il procedimento fornisce la soluzione al limite punto da cui partire viene scelto con X₀ (approssimazione iniziale))
• Viene generata una successione {X_k} detta successione di iterate
• Che sotto opportune ipotesi converge ad uno zero x*; d'altronde ciascun punto di xx
• È detto iterate

lim _k→∞ X_k = x*

Iterazione: L'insieme delle istruzioni che consente di passare da X_k a X_k+1 (parto con X₀ generato X₃ generato X_k)

Metodo di bisezione

Si basa su un Teorema Teorema di esistenza degli zeri per una funzione continua se f ∈ C ([a,b]), [a,b] chiuso e limitato e f(a).f(b) < 0

Allora esiste almeno uno zero di f in [a,b] È molto importante che f sia continua in [a,b]

... la retta tangente è una buona approssimazione solo in quell'intorno.

Il metodo di Newton ha convergenza locale.

Appunti 27.03

Continuo metodo di Newton — metodo di tipo iterativo

Ripasso: Metodo di Newton

lezione precedente

f(x) = 0

x₀ dato

x_k+1 = x_k - f'(x_k) / f'(x_k) , f'(x_k) ≠ 0 , k > 0

se scelgo un punto lontano dallo zero

non possiamo avere una buona approssimazione.

Il metodo è utile se scelgo x₀ in modo accurate

la retta è una buona approssimazione

se x₀ è vicino allo zero che voglio trovare

— allora la successione converge

Proprietà di convergenza locale

Esempio

arctan(x)=0

Parto da 1

x₀ = 1

x₁ = - 5.7 · 10¹

x₂ = + 1.7 · 10^-1

x₃ = - 1.1 · 10^-3

x₄ = 7.9 · 10^-10

i segni si alternano

questa successione sta tendendo allo zero

La convergenza non è sempre garantita

Parto da 2

x₀ = 2

x₁ = -3.5

x₂ = 13.9

x₃ = 279.3

x₄ = 22202

x₅ = -2.3 · 10³⁶

questa successione non sta tendendo a zero ➔ Diverge

siano vicini ad avere una tangente

as se x_i ➔ le rette si stanno allontanando dallo zero