Corso completo metodi analitici e numerici

Floating Point e Sistemi Lineari

Floating Point

FLOATING POINTx_FL = (-1)^s m β^e-t e ∈ [L, U] L < 0 U > 0 m = mantissa = a₁, a₂, ... a_t a₁ ≠ 0 0 ≤ a_i ≤ β - 1 ∀ i = 0, ..., t β = base s = sign t = numero cifre in mantissa

π₀ (β, t, L, U) F₀ ⊂ ℝ Ɛ_m = 2^1-t rappresenta ogni numero frazionario e ogni numero positivo punto prossimo ai 1|x - x_FL| ≤ 1/2 Ɛ_m|x| x_FL (1 + Ɛ_m) ≥ 1 x_min = β^L-1 x_max = (β^t-1) β^U-t = β^U (1-β^-t)

Floating Pointx_re = (-1)^s m β^e-t e ∈ [L, U] L ≤ U > 0 m = mantissa = a₁, a₂, ... a_t a₁ > 0 0 ≤ a_i ≤ β-1 ∀i = 0, ..., t β = base s = segno t = numero termini mantissa

f_o(β, t, L, U) F_o ⊂ ℝ Ε_m = e^1-t rappresenta ε a mantissa finita, ν e νmeri positivi punto prossimo ai 1|x - x_RE|/|x| ≤ 1/2 Ε_m x_min = β^L-1 x_max = (β^t-1) β^U-t = β^U(1-β^-t)

Sistemi Lineari

A ∈ ℝ^nxn matrice coefficienti b ∈ ℝⁿ vettore termini noti x ∈ ℝⁿ vettore incognite Ax = b detA ≠ 0 ⇒ soluzione unica

Cramer's Rule

x_i = det(A_i) / det(A) costo computazionale O((N+1)!)

Sostituzione all'indietro (sostituzione)

Metodi diretti per risolvere sistemi con matrici triangolari superiori (U) x_n = b_n / u_nn u_ii ≠ 0 ∀ i=1,...,n i = n-1,...,1 x_i = 1/u_ii ( b_i - ∑_j=i+1ⁿa_ijx_j )

Sostituzione in avanti (sostituzione)

Per risolvere sistemi con matrici triangolari inferiori (L) x₁ = b₁ / l_ii ∀ i=1,...,n i = 2,...,n x_i = 1/l_ii (b_i - ∑_j=1ⁱa_ijx_j )

Costo computazionale

(numero operazioni elementari) ∑_i=0^n-1(1 + (1 + 2i)) = n + 2 ∑_i=0^n-1i = n + 2 (n-x)nO(n²)

MATLAB

fwsub (Ly=Pb) b = P*b; y(i) = b(i) / L(i,i); y(i) = (b(i) - ∑ L(i,1:i-1).*y(1:i-1))/L(i,i); end bksub (Ux = y) x = zeros(n,1); x(n) = y(1:1:n)*x(i+1:n))/U(i,i); for i = n-1:-1:1 end

Metodo di eliminazione di Gauss (MEG)

Calcolo per permutare un sistema equivalente a quello iniziale A² = M₁A₁ A³ = M₂M₁A₂ = M₂(M₁A₁)... Aⁿ = M_n-1...M₁A₁ A₁ = (M_n-1...M₁)^-1Aⁿ (equivalente fattorizzazione LU) A = LU

Algoritmo MEG

M_ik = α_ik^(k) / α_kk^(k) i = k+1,...,n k = 1,...,n-1 ∀kk ≠ 0 ∀k q_i^k+1 = q_i^k - M_ikq_k^k h_i^k+1 = h_i^k - M_ikb^(k)

Cono computazionale

m(n-1) + (n-2) + ... + 1 = (n-1)∑_i=1i = ((n-1)n)/2

1. 2[(n-1)² + (n-2)² + ... + 1] = 2(n-1)∑_i=1i² = (2(n+1)n(n-1))/6
2. 2[(n-1) + (n-2) + ... + 1] = 2 (n-1)∑_i=1i = (n(n-1))

Cono computazionale totale, somma n², due è il costo per risolvere il sistema con matrice triangolare 3/3(n-1)n + (2(n-1)(n-1)1 + n² = O(2/3 n³)

Fattorizzazione LU

LUx = b Ux = y Lûy = b^{di Gauss} Si ottiene applicando il MEG per eliminare le matrici di coefficienti A ove il supporto tira due matrici triangolari LU. Per renderla unica è imposto che gli elementi diagonali di L siano tutti pari a 1. Gli elementi sottodiagonali di L sono per Mik mentre gli elementi di U sono i coefficienti di Aⁿ ottenuto con MEG

Condizione Sufficiente e Fattorizzazione

1. πολική διάβολη οχνάτη pu φιλέ ∀i=1,...,n |aii| > ∑ _{j=1, j≠ι}ⁿ |a_ij| for i=1:na_ii=abs(A(i,i)); for j=1:nai(j)=abs(A(i,j)); end