Teoria Calcolo numerico

NOTEBOOK

Numeri macchina e propagazione degli errori

Rappresentazione floating-point dei numeri reali

Fissato un numero naturale β > 1 ogni numero reale x ≠ 0 ha un’unica rappresentazione tipo: x = sgn(x) β^e _k=0 ∑^+∞ d_k β^-k, 0 ≤ d_k < β; e ∈ Z

sgn è la funzione segno e sgn(y) = 1 se y > 0 -1 se y < 0 0 se y = 0

-In base 2 (Base binaria) β=2. x = sgn(x) 2^e _k=1 ∑^+∞ d_k 2^-k, d_k = 0,1; e ∈ Z

-In base 10 (Base decimale) β=10 x = sgn(x) 10^e _k=1 ∑^+∞ d_k 10^-k, d_k = 0,...,9; e ∈ Z

Particolarità della sommatoria

Un numero per essere rappresentabile esattamente deve avere un numero finito di d_k.

Questo riguarda i numeri irrazionali (ex. π) e alcuni numeri razionali in base 10 (ex. 1/3)

Numeri macchina/Numeri floating-point

Definizione: F(β, L, U)

L’insieme dei numeri macchina di R è costituito da quei numeri x che sono 0 oppure sono rappresentati con il floating-point normalizzato da: x = sgn(x) (0.d₁d₂...d_t) β^e; sgn(y) β^e t_k=1 ∑^t d_k β^-k con d_k ≠ 0, 0 < d_k < β-1

- β^-t è un numero naturale di base t ed è numero prefissato di cifre di mantissa

- e ∈ Z è l’esponente tale che L ≤ e < U | | L lower, U upper _k=1 ∑^t d_k β^-k < 1 che può ottenere che la mantissa è minore di 1.

Ogni elemento di F(β, L, U) è detto numero macchina, ogni numero macchina è RAZIONALE

Operazioni con i Numeri Macchina

Indichiamo con d(x) il numero macchina che corrisponde a x

• x⊕y := fl(fl(x)+fl(y))
• x⊗y := fl(fl(x)•fl(y))

Proprietà commutativa e associativa e distributiva

Una operazione a scelta tra quelle di macchina

op Una operazione a scelta tra quelle matematiche

ε_x-y := ^{|x-y-(x⊖y)|}/_|x-y|

ε_x⊕y := ^{|(x⊕y)-(x+y)|}/_|x+y|

Esiste sia l’elemento neutro sia l’opposto di ogni numero floating point

Teorema

valgono le seguenti stime:

• ε_x⊕y ≈ ^|x-y|/_|x+y|, x+y≠0
• ε_x⊖y ≈ ^|x-y|/_|x-y|, x-y≠0
• ε_x⊗y ≈ ^{|(x/y)-(x⊗y)|}/_|x/y| = |ε_x + ε_y|, x,y ≠ 0
• ε_εx⊖y ≈ ^|x-y|/_|x-y|, x,y ≠ 0

Nelle operazioni ε_x⊗y e ε_εx⊖y, abbiamo che per x±y≈0 a piccoli errori sui dati corrispondono grandi errori sui risultati; questo fenomeno è noto come cancellazione e questo è causato dai fattori di amplificazione ^|x|/_|x±y| e ^|y|/_|x+y|.

EQUAZIONI NONLINEARI

SOLUZIONE NUMERICA DI EQUAZIONI NONLINEARI

Data una funzione continua \(f:I \rightarrow \mathbb{R}\) si desidera calcolare \(x*\) tale che \(f(x*)=0\). Questo problema richiede l’utilizzo di un metodo iterativo che genera una sequenza di numeri x₁, x₂, x₃... che si desidera convergano a una soluzione x*.

Se prendiamo per esempio un polinomio \(f:P_n(x)\) avremo che per n>5 non esistono formule risolutive mediante le 4 operazioni e estrazione di radice per determinare gli zeri della funzione (Pn(x)=0).

È possibile però approssimare tali radici con un metodo numerico compiendo un errore inferiore alla tolleranza (valore predefinito dall’utente).

Queste equazioni possono:

• Non avere una soluzione reale
• Avere più di una soluzione
• Avere soluzioni semplici ovvero \(x*\) tale che M_α(x*)=1
• Avere soluzioni multiple ovvero \(x*\) tale che M_α(x*)>1

Fare il grafico per studiare gli zeri della funzione non è sempre efficace

METODI ITERATIVI E CONVERGENZA

Un metodo iterativo è un tipo di metodo numerico nel quale l’approssimazione \(x_n\) della soluzione al problema è ottenuta partendo dai valori:

x₀, x₁, ..., x_n-1 con n=1,2,... *

I due aspetti fondamentali sono:

• Garanzia della convergenza alla soluzione (x_n deve tendere a x*)
• Ordine di convergenza (la velocità con cui x_n tende a x*)

Teorema (Convergenza Globale) - Newton

Sia f∈C²([a,b]) con f'(a)0 ∀x∈[a,b], allora f'(x) è continua e strettamente crescente in [a,b]

1. f' ha segno costante in [a,b]
2. Dato che f'(a)0)
3. f' non ha segno costante in [a,b]

Dato f strettamente crescente ha un unico zero e dato f'(x)