Analisi numerica e Statistica

Rappresentazione dei numeri

x = S * m * B^P

Conversioni di base

Da int base 10 → k base

Rapp.

Successive

Moltiplicazioni successive

Parte decimale λ ∈ [0,1]

n * B = intero frazionaria

Interi

Predico punti X(ℤ) = ℤ_n (-2, -1, 0)

Real floating point

F(B, ε_L, ε_U)

Base

Cifre mantisse

Esponente

Errore di rappresentazione

Sia X un num. ℝ, ε≠ξo l'errore relativo che si commette approssimando x = x' è:

| E_X |= |x - x'| / |x| ≤ ε_eps

Operazioni di macchina

Somma

• Normalizz. addendi
• Sottraz. a_min. addendi
• Togli x?
• Aoppront.

Prodotto

• Prodotto m
• Troncam./app..

Divisione

• Contr. m
• Diviso. m
• Calcolo p

Considerazioni

Associativa

Distributiva

Annulla il prodotto

Rappresentazione dei numeri

x = S ⋅ M ⋅ _B^P

Conversioni di base

Da int base 10 → K base

Moltiplicazioni successive

Reale decimale → x ∈ [0,1]

Rappresentaz. interna (num. finiti)

Integri

• 1. Rapp. binaria
• 2. Inversione cifre
• 3. Si aggiunge 1

Insieme non chiuso ris. operazioni → overflow/underflow

Real floating point

F (B, e_L, e_U)

Semplice 32 bit doppia 64 bit

Segno 1 1

Bias 127 1023

E_min -126 -1022

E_max 127 1023

Errore relativo

Sia X un num. ∈ ℝ ≠ 0 l'approssimazione di macchina di X

Errore relativo che si commette approssimando x⋅x' è:

| E_x | = | X - X' | / | X | ≤ ε_EPS

Operazioni di macchina

Somma

• Normalizz. addendi
• Sottrazione m
• Troncam. / arrotondam.
• Normalizz. risult.

Prodotto

• Prodotto m
• Troncam./ar.
• Controllo / scarta esponenti

Distributiva

• Controllo m
• Divisione m
• Calcolo p

Considerazioni

Non valgono

Associativa (X1+X2) niente rel. inverti sc.

Errore relativo

Esempio

sottos.5 = x + 1

δ = (x(a + ε_x) + y(1 + ε_y)) / (1 + ε)

Un problema si dice ben condizionato se a piccole perturbazioni corrispondono piccole variazioni delle soluzioni (e viceversa)

Indice Condizionamento = Err. dati / Err. inerente

Indice Algoritmico = Err. operazioni / Err. algoritmico

Errore Inerente = ε_ps I Cond_atz

Errore Relativo (Indici e Dati cal.) = ε_ps

Errore Totale = Err. inerente + Err. algoritmico

Err. algoritmico = Un prog. si dice stabile se non è troppo sensibile agli err. introdotti con le operaz. di macchina

Studio delle perturbazioni

Studio di come variano le soluz. rispetto alle perturbazioni

Obiettivo = Calcolare una relazione tra

Err. relativo nelle soluzioni / Err. relativo ai dati

||x - x*|| / ||x|| = ?

||Δb|| / ||b||

oss. 1 A * x = b , A * x* = b + Δb → A * x = A * x* = Δb → A(x - x*) = Δb → x - x* = A^-1Δb

oss. 2 A * x = b → b - A * x → ||b|| = ||A * x||

⇒ x proprietà + triangolare norma ⇒

||b|| ≤ ||A|| · ||x||

||b|| / ||A|| ≤ ||x||

||x* - x|| = ||A^-1Δb|| = ||A^-1|| · ||Δb||

||b||

Numero di condizionamento

Multiplica ambo i membri x A^-1 · Δb

||A^-1Δb|| ↔ ||A^-1|| · ||Δb||

||x* - x||/ ||b||· ||x|| ≤ |A| · |A = II|

→ Fornisce una stima della stabilità del problema; se molto >1 → instabile

Sistemi lineari

Mat. non singolare o invertibile se ∃ 1 tali: A^-1A = I

Prop. equiv. inv. Δe non singolare det(CA) ≠ 0 righe e colonne di A sono l.i. A x = o ⇒ x = o

Th. Rouché Capelli se A è non singolare, ∃! soluz. a.s. certsin, Ax = b

Scopo

• Esistenza ed unicità: non singolare ⇒ 1 sol.
• Condizionamento ⇒ robustez relat. dei coefficienti ||A||·||A^-1||
• Algoritmi ⇒ caratteristiche computaz. stabilità   confronto fra algoritmi diretti/iterativi

Diretti

Diagonale x_i = b_i/c_i costo: n moltip.

Ortogonale A^T = A^-1 ⇒ |A⁺A = I x = A⁺b   costo n² moltip.

FOR i = 1:n FOR j ≠ 1:n x(r) = x(r) + a_(j,i) + b(s) END

Triangolo inferiore ⇒ sost. in avanti

FOR i=1:ns ← 0

FOR j=1:i-1s ← s + a_(i,j) x(i)END

x(i) = (b(i)-s)/a(i,i)FOR j