Esercitazioni python eng

Calcolo numerico 1 - Aritmetica

Rappresentazione floating-point

a ∈ ℜ = (-1)^s p N^q

N = base   p = mantissa   q = esponente   s = segno

N^-1 ≤ p < 1   La prima cifra di p è sempre diversa da 0, ma p è minore di 1

Numero macchina più piccolo

m = 0.1 * N^L

(0.1 numero più piccolo possibile della mantissa)

L: minimo esponente accettabile nell'aritmetica macchina

Numero macchina più grande

Avrà tutte le cifre della mantissa uguali a N-1 ed esponente uguale a L.

Ad esempio, se t = 5, N = 10 ⇒ M = 0.99999 * 10^u_t=5

Underflow e overflow

Se a ∈ (-m, m) si dice che a = 0 (regione di underflow)

Se a ∈ (-∞, -M) ∪ (M, +∞) si dice che a = ±∞ (regione di overflow)

Rounding to even

Dato un numero macchina a, è necessario analizzare la mantissa p:

• 1) Se p è equidistante alle 2 mantisse macchina più vicine, _¯p e _¯p₂, va approssimato alla mantissa _¯p con ultima cifra pari
• 2) Altrimenti:

• A) Si somma a p il termine ½ N^-t
• B) Si tronca il risultato della somma alla t-esima cifra

Se N = 10, t = 3, p = 0.1585432

_¯p₁ = 0.158   _¯p₂ = 0.159 non sono equidistanti da p ⇒

0.1585432 &plus; ½ * 10^-3 = 0.1585432 &plus;0.0005 =0.1590432 ← _¯p = 0.159

Calcolo numerico 1 - Aritmetica

Rappresentazione floating-point

a ∈ ℝ = (-1)^s ρ N^q

N = base   ρ = mantissa   q = esponente   s = segno

N^-1 ≤ ρ La prima cifra di ρ è sempre diversa da 0, ma ρ è minore di 1

N ∈ ℕ

ℝ = ℝ p.z.

q ∈ ℤ

s ∈ {0,1}

Numero macchina più piccolo

m = 0.1 * N_L

(0.1 numero più piccolo possibile della mantissa)

L: minimo esponente accettabile nell'aritmetica macchina

Numero macchina più grande

Averà tutte le cifre della mantissa uguali a N-1 ed esponente uguale a L

Ad esempio, se t = 5, N = 10 ⇒ M = 0.99999 * 10^U

t = 5

Underflow e overflow

Se a ∈ (-m, m) si dice che a = 0 (regione di underflow)

Se a ∈ (-∞, -M) ∪ (M, +∞) si dice che a = ±∞ (regione di overflow)

Rounding to even

Dato un numero macchina a, è necessario analizzare la mantissa p:

• Se p è equidistante alle 2 mantisse macchina più vicine, p̄ e p̄₂, va approssimato alla mantissa p̄ con ultima cifra pari
• Altrimenti:

• A) Si somma a p il termine 1/N⁺
• B) Si tronca il risultato della somma alla t-esima cifra

Se N = 10, t = 3, p = 0.1585432

p̄₁ = 0.158, p̄₂ = 0.153 non sono equidistanti da p ⇒ 0.1585432 + 1/2 * 10^-3 = 0.1585432 +0.0005 = 0.1580432

t = 3 ⇒ p̄ = 0.158

Espressioni equivalenti nell'aritmetica dell'elaboratore

Due espressioni/quantità e₁, e₂ si definiscono equivalenti nell'aritmetica dell'elaboratore quando l'errore relativo è dell'ordine della precisione di macchina ε_m o minore:

|e₂ - e₁| / |e₁| ≲ ε_m oppure |e₂ - e₁| / |e₂| ≲ ε_m

Esempio

N ≈ 10     l: 5     allora 0.99999 e 1 sono equivalenti nell'aritmetica f.p. fissato ε_m = 1 / 2 * 10^-4

|1 - 0.99999| = 0.1 * 10^-4 ≲ ε_M = 0.5 * 10^-4

Cancellazione numerica

Siano:

r̅₁ = (-1)^s₁ p₁ N^q₁,      r̅₂ = (-1)^s₂ p₂ N^q₂

le rappresentazioni di macchina associate rispettivamente ai numeri reali:

r₁ = (-1)^s₁ p₁ N^q₁      r₂ = (-1)^s₂ p₂ N^q₂

La cancellazione numerica consiste in una perdita di cifre della mantissa e si verifica quando si esegue un'operazione di sottrazione tra due rappresentazioni di macchina r̅₁ e r̅₂ dello stesso se**** e almeno una delle quali sia affetta dall'errore di arrotondamento.

Dunque avviene quando:

s₁ = s₂

q₁ ≈ q₂

p̅₁ ≉ p̅₂

p₃ ≠ p₃    e/o   p̅₂/p₂

A volte è possibile evitare questo fenomeno manipolando le espressioni matematiche.

Se ciò non è possibile si dice che la cancellazione è insita nel problema.

Condizionamento di un problema numerico

Problema numerico: relazione funzionale tra i dati x (input) e i risultati y (output)

x → f → y          Esplicita: y = f(x)      Implicita: f(x, y) = 0

Dato un generico problema numerico, si denotino con:

x̃ perturbazione dei dati x di input

ẙ risultati ottenuti a partire dai dati x̃ in precisione infinita di calcolo

In generale x ≉ x̃, ma ≈

Calcolo numerico 2 - Approssimazione

Approssimazione di una funzione

Data una funzione f, approssimarla significa sostituirla con una funzione _f^~ che le somigli su cui si possa facilmente operare.

Approssimare un insieme di dati

Dato un insieme di dati (x_i, y_i), approssimare significa determinare una funzione _f^~ che stabilisca un nesso simile a quello dei dati.

Osservazione

Se f è sufficientemente regolare, può essere approssimata nell'intervallo (x₀ - δ, x₀ + δ) con δ > 0 da un polinomio di Taylor.

Talvolta può essere insoddisfacente in alcune applicazioni.

Criterio dell'interpolazione

Consiste nella scelta come approssimante dei dati (x_i, y_i) i = 1, ..., n + 1 una funzione f_n soddisfacente le seguenti condizioni:

f(x_i) = y_i i = 1, ..., n + 1 che impongono il passaggio di _f^~ per i punti (x_i, y_i).

Condizioni di interpolazione

• F(x) polinomiale se la funzione è regolare.
• F(x) polinomiale: tratti.

Teorema

Assegnati n + 1 punti (x_i, y_i) con le ascisse distinte tra loro (x_i ≠ x_j per i ≠ j) esiste ed è unico il polinomio P_n(x) di grado minimo e uguale a n interpolante i dati assegnati ovvero che soddisfa le condizioni:

P_n(x_i) = y_i i = 1, ..., n + 1

Rappresentazione monomiale

P_n(x) = c_nxⁿ + ... + c₁x + c₀

I coefficienti c_i, i = 0, ..., n + 1 sono determinati in modo che P_n(x) soddisfi le condizioni di interpolazione.

Rappresentazione di Newton

Siano assegnati n+2 dati (x_i,y_i), i=1,...n+2 con x_i ≠ x_j per i≠j, eventualmente yi=f(xi)

Differenza divisa di ordine 1

Si definisce differenz 3 5 4 5 Lez. 52

Convergenza del polinomio di interpolazione

P_n(x) = polinomio interpolante la funzione f(x) nei punti: x₁, ..., x_n+1

Errore di interpolazione: E_n(x) = f(x) - p_n(x)

E_n(x) = 0 per x = x_i

E_n(x) ≠ 0 per ogni x ∈ [a,b] e per ogni funzione f polinomiale di grado ≤ n

Norma infinito

g(x) continuo in [a,b] norma infinito: ||g||_∞ = max_x∈[a,b] |g(x)|

Supponendo che f sia continuo in [a,b] e che i punti x_i siano tutti in [a,b], una misura naturale dell'errore è ||E_n^∞||_∞

Una successione di polinomi { P_n } converge uniformemente a f lim_n→∞ ||f - P_n||_∞ = 0

Teorema

Data una qualunque successione di nodi distinti ∈ [a,b] esiste sempre una funzione f(x) continua in [a,b] che interpolata su quei nodi, i genera una successione di polinomi di interpolazione { P_n(x) } non uniformemente convergente a f in [a,b]

Nodi di: Chebyshev-Lobatto

Una possibile alternativa ai nodi equispaziati:

Sono i punti z_i = -cos( (i-1)/n ) ∈ [-1,1], i = 1, ..., n+1

Nodi di: Chebyshev

Una possibile alternativa ai nodi equispaziati:

Sono i punti z_i = -cos( (i-2)/ (2(n+1)) )π ∈ (-1,1), i = 1, ..., n+1

I nodi sono più densi agli estremi e più radi al centro