Calcolo numerico - appunti

APPUNTI

CALCOLO NUMERICO: METODI E SOFTWARE

Politecnico di Torino

Facoltà di IngegneriaCorso di laurea: Ingegneria AerospazialeDocenti: Letizia Scuderi

RAPPRESENTAZIONE FLOATING-POINT

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

• s ∈ {0,1}
• p ≥ 0 ∈ ℝ
• q intero

N base del sistema numerazione

N^-1 ≤ p < 1 → 1^a cifra di p dopo punto decimale ≠ 0

Se si rispetta la condizione ⇒ NORMALIZZATA

• l_p, p e q univocamente determinato

• l_p esponente o caratteristica
• p mantissa di e

s, p e q individuano univocamente il numero reale a

CALCOLATORE ⇒ SPAZIO FINITO di MEMORIA

s, p possono avere un num t cifre

q soddisfa limitazioni -l ^e ≤ q ≤ l^u [l_e, l_u]

• NON TUTTI I REALI sono esattamente RAPPRESENTABILI su un CALCOLATORE
• l'NUBRA con p e q esattamente rappresentabile negli spazi numerici del calcolatore
• l'NUMERI del MACCHINA

= {0} ∪ { (-1)^s 0.a₁ a₂... a_t N^q 0 ≤ a_i < N, a₁ ≠ 0, l_e ≤ q ≤ l_u }

l'insieme dei NUMERI del MACCHINA

m = 0,10...0 __{t cifre}

l_e unità definendo numero più piccolo positivo

(-m_u, m_u) REGIONE del UNDERFLOW ⇒ Approssimato con 0

CANCELLAZIONE NUMERICA

consiste nella PERDITA di cifre della MANTISSA quando si esegue SOTTRAZIONE tra 2 num. mach. dello stesso segno una grande o almeno uno dei due ha errore di arrotondamento

S1: C2 / 91: 92 / P1 ≉ P2 / 1̅ ≉ 2̅ / 1̅ ≉ 2 / 1 ≉ 2̅ /

PROBLEMA NUMERICO

una relazione funzionale f tra i dati x (INPUT) e y (OUTPUT)

x → _f → y DATI x e y devono essere RAPPRESENTABILI da

• NUMERI
• VETTORI DI DIM. FINITA
• MATRICI

CONNESSIONE

f tra x e y

• ESPLICITA y = f(x)
• IMPLICITA f(x, y) = 0

BEN CONDIZIONATO

è un problema numerico se l'errore relativo associato a ̅ è dello stesso ordine di grandezza o minore di quello di x̅

MAL CONDIZIONATO

Se errore relativo di ̅ è di grado maggiore di x̅

| - ̅| / |̅| ≤ K(f,x) |x - x̅| / |x|

NUMERO di CONDIZIONAMENTO del problema: Il più piccolo valore di K(f,x) per cui vale DISEGUAGUANZA

BEN CONDIZIONATO

se PERTURBAZIONI nei DATI non influenzano eccessivamente i RISULTATI

CONVERGENZA POL. INTERPOLANTE

ERRORE di INTEPOLAZIONE -> E_m(x) = f(x) - p_m(x)

• E_m(x_i) = 0 per x = x_i : => E_m(x_i) = f(x_i) - p_m(x_i) = 0
• E_m(x) ≠ 0 per x ∈ [a,b] ∃ f polinomiale con grado ≤ m

NORMA UNIFORME O INFINITO => Date funzione g(x) continua in [a,b], si def. norma inf. della funzione g(x) la quantità

||g||_∞ = max_x∈[a,b] |g(x)|

Una SUCCESSIONE di POLINOMI {p_m}_m∈N CONVERGE UNIFORMEMENTE a f se e solo se

lim_m→∞ ||f - p_m||_∞ = 0

TEOREMA:

Data una qualunque successione nodi distinti in [a,b],

∃ una f(x) continua in [a,b] => interpolata sui nodi genera una successione di polinomi di interpolazione {p_m(x)} non unifom. convergente a f(x) in [a,b]

OSS.

Funzione di RUNGE f_n, 1 / (1+x²)

Funzione INTERPOLATA su nodi x_i = a+(i-1)h, h=^b-a/_n, i=1,…,n+1 in [a,b]

Non converge unif. a f(x) in cell0 [a,b] => n→∞ ||E_m||_∞ = ∞

NORMA DI VETTORE

X = (x₁, ..., x_m)^t ∈ ℝ^m vettore colonna

||X||₁ = ^m∑_i=1 |x_i|

||X||₂ = √^m∑_i=1 |x_i|²    NORMA EUCLIDEA

||X||_∞ = max_{1 ≤ i ≤ m} |x_i|

norma (X, l_p) fornisce norme specificate p ∈ ℤ/1,∞

NORME DI MATRICE

A = (a_ij) i,j = 1,...,m ∈ ℝ^m×m MATRICE QUADRATA di ordine m

||A||₁ = max_1≤j≤m ^m∑_i=1 |a_ij| SOMMA COLONNA

||A||_∞ = max_1≤i≤m ^m∑_j=1 |a_ij| SOMMA RIGA

||A||₂ NORMA SPETTRALE

norma (A, E, l_p) fornisce norme specificate p in ℤ/inf

Data norma su un vettore e una matrice → Sono COMPATIBILI se

||Ax|| ≤ ||A|| ||x||   ∀A ∈ ℝ^m×m e ∀x ∈ ℝ^m

Norme l e l_inf (come duale) sono compatibili

||AB|| ≤ ||A|| ||B||

||I|| = 1   I MATRICE IDENTITA

Costo Computazionale

Numero di operazioni aritmetiche che esso richiede per la propria esecuzione

Per sist. numerici il costo è legato a M (dim. del sistema)

• A Diagonale

con a_ii ≠ 0 i = 1, ..., m

• a₁₁ x₁ = b₁
• a₂₂ x₂ = b₂
• ...
• a_mm x_m = b_m

x_i = ^b_i/_aii i = 1, ..., m

→ M divisioni

• A Trg Sup

con a_ii ≠ 0 i = 1, ..., m

• Q₁₁ x₁ + Q₂₂ x₂ + ... + a_mm x_m = b₁
• Q₂₂ x₂ + ... + Q_mm x_m = b₂
• ...
• Q_mm x_m = b_m

x_m = ^b_m/_amm

...

x₁ = ^{b₁ - Σ_j=2m a_ij x_j}/_Q11

Costo (1/2 m²)

← Metodo da sostituzione all'indietro

• A Trg Inferiore

con a_ii ≠ 0 i = 1, ..., m

• Q₁₁ x₁ = b₁
• Q₂₁ x₁ + Q₂₂ x₂ = b₂
• ...
• Q_m1 x₁ + Q_m2 x₂ ... Q_mm x_m = b_m

x₁ = ^b₁/_Q11

...

x_m = ^{b_m - Σ_j=1m-1 a_ij x_j}/_Qmm

Costo (m²/2)

← Metodo di sostituzione in avanti

[*]

trolt → (σi x σj)

L = trol (A, l) + eye (u);

U = trol (A, 0)

Posso sotto intenderlo

Sistema Sovradeterminato

può ammettere → sol. classica se Ax - b = 0

La soluzione x per il quale vettore residuo è piccolo (Ax - b)

• Ricerca vettori che minimizzano ||Ay - b||₂ con y ∈ ℝᵐ

x ∈ sol. del sistema sovradet. Ax = b rispetto norma ||.|| se

min ||Ay - b|| = ||Ax - b||

Se ||Ax - b|| = 0 → Ax = b = Ø → sol. classica

Con norma 2 (euclidea)

min ||Ay - b||₂ problema dei minimi quadrati

e vettore x tale che min ||Ay - b||₂ = ||Ax - b||₂ soluz. nel senso dei minimi quadrati

Questo problema ammette sempre una soluzione ⇒ X, insieme vettori sol. ≠ Ø

1. x ∈ X ⇔ AᵀAx = Aᵀb sistema detto eq. normali o sistema normale
2. X si riduce a solo elemento x* se e solo se A ha rango massimo
3. ∃! x* ∈ X : ||x*||₂ = min ||x||₂ x* è detta sol. ad minima norma

Per risoluzione minimi quadrati ci sono 2 casi:

1. A ha rango massimo
2. A non ha rango massimo