Analisi numerica e Statistica

Rappresentazione dei Numeri

Segno | Mantissa | Esponente

x = S · m · B^P

Normalizzata: 0.0372 · 10³

Scientifica: 0.00372 · 10⁴

Pag. Direzioni Successive

Da int base 10 → B base

Moltiplicazioni successive

• Parte decimale r ∈ [0,1]
• Parte X.B= intero frazionaria

Interi Fisso Point

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

insieme non chiuso risc. operazioni → overflow/underflow

Real Floating Point

• Base
• Firme mantissa
• Esponente

• 32 bit
• 23
• Bias 127
• Emin -126
• Emax 127

• 64 bit
• 52
• Bias 1023
• Emin -1022
• Emax 1023

Operazioni di Macchina

1. Normalizz. a segno
2. Sottraz. m
3. Troncam/arrotodam, normaliz. risulta

1. Prodotto m
2. Troncam/ar
3. Contrario
4. Sottraz esponenti

1. Confranto m
2. Divisione m
3. Calcolo p

ERRORE RELATIVO

_{2 parti} ERR. INERENTE (Dati) ERR. ALGORITMICO (Algoritmo)

CONDIZIONAMENTO

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

• Errore condizionamento = Err. dati / Err. inerente
• Errore algoritmico = Err. operazioni / Err. algoritmico

Errore inerente = ε_PS = l errore

Errore relativo = ϒ_dati = ^{σ_d ε_d}

Errore totale = Err. inerente + Err. algoritmico

Err. algoritmico = un progr. si dice stabile se non è troppo sensibile agli errori avvenuti con le operaz. in macchina

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⁻¹ Δb

Oss. 2

A x = b ⇒ b = A x ⇒ ||b|| = ||A x|| ⇒ ||b|| ≤ ||A|| · ||x||

^{||A|| · ||x − x*||}/_||x|| = ^||Δb||/_||b||

Numero di condizionamento

Moltiplico ambo i membri × A⁻¹

^||Δ₁Δb||/_||x|| ≤ ^{||A−1|| · ||Δb||}/_||b||

⊲ ^||x-x*||/_||x|| < |^A| ||Δb||/||b||

Fornisce una stima della stabilità del problema, se molto → instabile

PIVOTING

• PILOT PICCOLO ➔ MOLTIPLICATORE MOLTO GRANDE ➔ INSTABILITÀ ➔ LIBERO SCELTA DEL PIVOT • MATRICE ➔ PERMUTAZIONE (PRODOTTO DI MAT. DI PERMUTAZIONE) ➔ ORTOGONALI ➔ PRODOTTO DI MAT. ORTOGONALI

ALGORITMO DI GAUSS CON PIVOTING

Ax = b PAx = Pb LUx = Pb Ly = Pb Ux = y

[ PA = LU ] PARZIALE ^n2_/2

[ PAQ = LU ] TOTALE ^n3_/3

NORME

VETTORIALI

|| . || è una norma che soddisfa le proprietà: ||k * x|| = |k| * ||x|| ||x + y|| ≤ ||x|| + ||y||

• Norma ∞ : ||x||∞ = max |x_i| _{i = 1} ⁿ
• Norma 1 : ||x||₁ = ∑ |x_i| _{i = 1} ⁿ
• Norma 2 (Euclidea) : ||x||₂ = √ (∑ x_i²) _{i = 1} ⁿ

NORME MATRICIALI

Proprietà:

• Norma ∞ : ||A||∞ = max ∑ |a_i,j| _{i = 1} ⁿ _{j = 1} ^m
• Norma 1 : ||A||₁ = max ∑ |a_i,j| _{j = 1} ⁿ
• Norma 2 (Euclidea) : ||A||₂ = √ (ρ(A^TA))
• Norma di Frobenius : ||A||_F = √ (∑ ∑ |a_i,j|² _i=1 ⁿ _j=1 ^m)

Teorema di Fattorizzazione di Cholesky

Una matrice simmetrica A ∈ ℝ^nxn è definita positiva se e solo se esiste una matrice triangolare inferiore R con elementi diagonali positivi tale che A = R R^T

Dimostrazione 1: Ipotesi A s.d.p.

A = L D L^T e D > 0

Sia x ≠ 0 e y = D^1/2. Siccome L è nonsingolare, y ≠ 0.

Sostituendo, y^T D y > 0 se e solo se A è definita positiva, ossia y^T D y = x^T A x.

La tesi si ottiene ponendo R = L D^1/2, dove A è la matrice diagonale con elementi √d_ii.

Dimostrazione 2: Ipotesi A = R R^T

x^T A x = x^T R R^T x = ||R^T x||²

Dalle proprietà delle norme segue che x^T A x ≥ 0 per ogni x ∈ ℝⁿ se e solo se y = R^T x = 0. Siccome R^T ha diagonale positivi, in particolare è nonsingolare e R^T x = 0 implica x = 0. Abbiamo quindi dimostrato che A è definita positiva.

Algoritmo di Fattorizzazione di Cholesky

A = L D L^T = R R^T

Indichiamo con r_ij gli elementi di R. Dal teorema sappiamo che R = L Δ, che significa

• r_kk = √d_kk, r_kj = l_kj √d_jj/ √d_kk, j = 1,...,k-1

Utilizziamo le regole di pavimentazione della fattorizzazione L D L^T per ottenere l’algoritmo Cholesky, sostituendo le relazioni precedenti.

for k = 1,...,n

• d_kk = a_kk - ∑_j=1^k-1 l² _kj d_jj
• for i = k+1,...,n
• l_ik = (a_ik - ∑_j=1^k-1 l_ij l_kj d_jj)/d_kk
• for k = 1,...,n
• d_kk = (a_kk - ∑_j=1^k-1 l² _kj d_jj) / √r_kk

d_kk = (a_ik - ∑_j=1^k-1 l_ij l_kj d_jj)/r_kk

Complessità computazionale: O(n³) a cui si aggiungono n estrazioni di radice quadrata.

Codice