Analisi numerica - Appunti

Notazione Esponenziale Normalizzata

Dato un numero x ∈ ℝ_N la sua notazione esponenziale normalizzata è data da:

x = (-1)^s Σ a_i·B^-i

con: s = 0,1; 0 ≤ a_i ≤ B-1; B ∈ ℕ \ {0}

In particolare, se x ∈ ℝ \ {0} e x = ± (0.a₁a₂a₃...)_B allora il numero minimo e massimo rappresentabili nella parte decimale sono:

min Σ a_i·B^-i

max Σ a_i·B^-i

In conclusione:

1/B ≤ Σ a_i·B^-i ≤ 1

Rappresentazione dei Numeri Reali sul Calcolatore

Parola: | segno | mantissa | caratteristica | n bit

In doppia precisione, a ciascuna parola sono riservati 64 bit:

• 1 bit per il segno
• 52 bit per la mantissa
• 11 bit per la caratteristica

In singola precisione, a ciascuna parola sono riservati 32 bit:

• 1 bit per segno
• 23 bit per la mantissa
• 8 bit per la caratteristica

Insieme dei Numeri Macchine

L'insieme dei numeri macchina F è descritto da quattro elementi:

• B: base
• L: numero di cifre memorizzabili
• t: numero min di cifre exp
• U: numero max di cifre exp

Dunque: F(B, t, L, U) = {0} ∪ x ∈ ℝ / x = (-1)^s Σ a_i·B^-i

La cardinalità è data da:

Card(F) = 2(B-1)B^t + (U-L+1) + 1

Ad esempio, se B=2, t=2, L=3 e U=3, allora il numero rappresentabili sono:

card(F) = 2(2-1)2¹·(3-3+1) + 1 = 28 + 1 = 29

In particolare, se x∈F_t (x=∑_i=1^ta_iB^i-t B^e allora il numero massimo e minimo rappresentabili nella — parte decimale sono:

min:

max:

In conclusione:

Considerando anche la parte esponenziale, si ha:

A legare (w cuitissa (sesta virgola)) e la parte decimale e la relazione:

=> m=a₁a₂a₃…a_t f.: (…a_ia_i+1…a_t) .B^t = dB^t

Quindi, in generale, per un numero x∈F_t con x=dB^e si ha:

_B ≤ x =≤ (1-B^-t)B^u

Rappresentazione del numero-macchina fl(x)

Il numero-macchina relativo ad un numero x∈R e fl(x)∈F. Tale numero è il suo approssima rispetto a quello di partenza secondo un

e_x = dove il numeratore rappresenta “l’errore assoluto”

Dunque tale numero-macchina si può scrivere come:

fl(x) = x(1 ± e_x) =

Errori nella rappresentazione del numero-macchina

Supponiamo che dato un x=dβ^e si hai: e∈{L, U}⊆Z

In particolare, se e≥U, si parla di errore di “Overflow”

Se invece, ej).

(A₁₁ A₁₂ ... A_1n

A₂₁ A₂₂ ... A_2n

... A_n1 A_n2 ... A_nn

) => U = (U₁₁ U₁₂ ... U_1n

0 U₂₂ ... U_2n 0 0 ... U_nn)

Ax=b      Ux=y ottenendo il sistema: U₁₁x₁ + U₁₂x₂ + ... + U_1nx_n = y₁   con soluzioni:   x₁ = (y₁ - U₁₂x₂t.-tu_1n) / U₁₁ U₂₂x₂ + ... + U_2nx_n = y₂ ... U_nnx_n = y_n

In generale, le soluzioni: x_i = (y_i - ∑_j=i+1ⁿu_ijx_j) / u_ii Con i = n, n-1, ..., 1

Il numero di operazioni (costo computazionale) necessario per determinare le soluzioni di un sistema triangolare è: addizioni (i2+...+i(n-1)=n(n-1) / 2) + molt. (n(n-1) / 2) + divisioni(n) = O(n²) = c₁n² (cf. 0 ε c>0)

Metodo di Gauss Naive

Descriviamo ora il procedimento di eliminazione nell'ipotesi che siano già elementi di diagonale principale (elementi pivot).valgono ad ogni passo la condizione: a_ii(t) ≠ 0, I = 1,2, .., n. Consideriamo dunque il sistema A⁽⁰⁾x = b⁽⁰⁾ e otteniamo il primo sistema equivalente attraverso queste operazioni: m_2i = a_i1⁽⁰⁾ / a₁₁⁽⁰⁾ se i=0,1   a_ij⁽¹⁾ = a_ij⁽⁰⁾ - m₂₁ * a_1j⁽⁰⁾ se i=1, j=2,3,..n. b₁⁽¹⁾ = b₁⁽⁰⁾ - m₂₁ * b_i⁽⁰⁾ c_ij = >1

ossia:

A⁽¹⁾ (a₁₁⁽⁰⁾ a₁₂⁽¹⁾ ... a_1n⁽¹⁾)

0 a₂₂⁽¹⁾ ... a_2n⁽¹⁾

0 0 ... a_nn⁽⁰⁾

) (X₁ )

(X₂)

(X_n)

= (b₁⁽¹⁾ )

(b₂⁽¹⁾)

(b_n⁽¹⁾)

Poiché per ipotesi a₂₂⁽¹⁾ ≠ 0, è possibile ripetere il procedimento dalla terza equazione in poi edi, in generale dopo K passi, utilizzando le operazioni: