Appunti di "Calcolo Numerico"

I numeri nell'elaboratore elettronico

Conversioni di Base

1. La rappresentazione di un numero a in una base N è unica.

a = a_N^M-1N^M-1 + ... + a₀N⁰ + a_-1N^-1 + a_-mN^-m

• es.: L'elaboratore riconosce solo le rappresentazioni binarie: esse si fato su due soli possibili elementi: numeroso e destroso (0 e 1).
• La rappresentazione in base 16 usa le cifre 0-9: A B C D E F.

2. Per quanto riguarda la parte intera, per pensare di a = a_N^M ... a₀M ed le basi di arrivo N a = b_nNⁿ + b_n-1N^n-1 + ... + b₀N⁰

... si divide per N (a_mM^m + ... + a₀M⁰) = b_NNⁿ + ... + a₁N¹ + ... + a_boN

non fatte in base M, per trovare il resto delle divisione è che è b_o, espr. così, dividendo nuovemente per N di risultante si ottenio b_n come certo ecc...

es.: (2028)₁₀ = ( ? )₄ 2028 : 4 = 507   r 0  -> b_o = 0 507 : 4 = 126   r 3  -> b₁ = 3 126 : 4 = 31   r 2  -> b₂ = 2 31 : 4 = 7   r 3  -> b₃ = 3 7 : 4 = 1   r 3  -> b₄ = 3 1 : 4 = 0   r 1  -> b₅ = 1 =  (7EC)₁₆

3. Per quanto riguarda le parte frazionarie, per pensare della base di partenza M di a = a₁M¹ + ... + a_mM^-1 alle basi di arrivo N a = b_sN¹ + ... + b_n5

... base moltiplicata per N ... N (a_mM¹ + ... + a_qM^m) = b₁ + b₂N⁺ + b_s+1 ... avante le parte intere b_n, che è semsse in base M. Ovvero, si eliminie le parti intere e n moltiplica di nuovo ecc...

→ es.: (0,123)₁₀ = ( ? )₄ 0,123 · 4 = 0,492   b_o = 0 0,492 · 4 = 1,368   b₂ = 1 0,368 · 4 = 3,872   b_n = 3 0,872 · 4 = 3,488   b₃ = 3 (0,123)₁₀ =  (0,033)₄

Rappresentazione interna dei numeri

1. Memorizzazione di un numero intero

1. Precisione singola a 32 bit, viene usata una rappresentazione in virgola fissa in cui una posizione è per il segno e le rimanenti 31 sono per il numero:

Max = 2³¹ - 1 = 2.147.483.648 - 1

Min = ±0

2. Precisione doppia a 64 bit, la rappresentazione a virgola fissa permette di avere 1 bit per il segno e 63 per il numero:

Max = 2 - 2^-63 - 1 = 9,22337 · 10¹⁸

II. Memorizzazione di un numero reale

Una rappresentazione normalizzata di un numero è quando è scritta nelle forme m · β^e con m < β.

Lo standard IEEE prevede una rappresentazione in virgola mobile normalizzata con accesso (biased) per i numeri reali.

1. Precisione singola a 32 bit, prevede 23 bit per la mantissa (- parte frazionaria) ed 8 per l'esponente.

e ha codifica in formato biased con valore di offset: esponente + 127 (per codificare i numeri sia negativi che positivi).

• (i) lo 0 codificato da ± 1 00000000 00000000000000000000000 → 1,0 0,2
• (ii) il Inf codificato da ± 1 11111111 00000000000000000000000 → 1,0 e = 2

K_k+1 = x_k - 2 ^f'(x_k)/_f''(xk) = g₁^NR - (x_k)

Questo schema modificato converge quadraticamente a

M = ^1/2/_6/3 |^f'''(3)/_f'(3)| lim ^k_k+1/_C2

Metodo delle tegle fisse

È il metodo della secante variabile. Nelle formule del metodo di N-R si

sostituisce f'(x) con il rapporto incrementale

g₁^NR = x_i= x_k - ^{x_i - x_k}/_{f(xk-1) - f(xk)} f(x_k)

Converge superlinearmente, con p_RF = 1.618 = M_1/2|^f''(3)/_f'(3)|^0.618

5) Altri metodi

1. Si definisce il metodo della tangente fissa:

x_k+1 = x_i - ^f(x_i)/_f'(x0) He p=1

2. Si definisce metodo delle secante fisse:

x_k+1 = x_i - ^{f(x_i) (x_i - x₀)}/_{f(xi) f(x0)}

- INTERPOLAZIONE E APPROSSIMAZIONE DI DATI

a) Interpolazione polinomiale

Dati m+1 punti d'appoggio (x_i, y_i), esiste sempre un unico P(X) di grado m

t.c. P(x_i) = y_i per i = d₁, m+1

Il polinomio di Lagrange interpola gli m+1 punti:

F(x) = (x - x_O) (x - x_l) ... (x - x_m) = ∏_k=0^dot(x-x_k) e consider F_l(x) = ^F(x)/_{x - xl} = ∏_t=O^*(x-x_t)

Costruisco pn(x)=∑l=0k=mClLt (x) t.c. (Pn(xc) = yd | (Pn(xx)=0 or x ≠ xl

→ c_l = y_f \/ i = 0, ... m

Ma allora L_i(x) = ^F_I(x)/_Fl(xi) poiche L_i(x_k) = 1 nil = j

p_n(x) = a_z + y₀ {^k=dot/_k=0+ (x - x_t) P_{t ≠ c}^*l_{t ≠ j, i ≠l ≠ l} ^{(x - x_t)}} + y₄ . ^(x-x_L)/_(x-xf) ^(x-x_t)/_(x-xm)+ ..... + y_m ^(x-x_z)

= ∑l=0m((t ≠∪ l=0) z)/z

Sottuttimo ore l'errore di interpolazione (E_m):

Sia x^*** ∈ [min x_i, max x_i], x_i x ≠ x₈, x₇, x_{t ≠}0, ... m

x) Una matrice è diagonalmente dominante se soddisfa

(i) a_ii > 0 ∀ i ∈ [1, m]

(ii) |a_ii| ≥ Σ |a_ij| ∀ i = 1,...,m => Re(λ_k) ≥ 0

x) Una matrice è definita positiva (resp. semidefinita) se per ogni

vettore x ≠ 0, allora x^TAx > 0 (resp. x^TAx ≥ 0)

Oss) Se M definito positivo, gli autovalori sono positivi;

se 2 x = Ax => x^T(Ax) = x^T(λx) = λ x^Tx > 0 essendo x^Tx =

= Σ x_i² > 0; onde tutti: λ_k > 0 => Re(λ_k) > 0 (strettamente)

x) Un insieme di vettori è ortonormale se x_i^Tx_j =

= 1 per i = j

= 0 per i ≠ j

p) Matrici simili hanno gli stessi polinomi caratteristici e stessi autovalori.

p_A(t) = det(A - tI) = det(K^-1) det(A - tI_n) det(K) = det(K^-1(A - tI_n)K) =

= det(K^-1AK - t¹K^-1K) = det(B - tI_n) = p_B(t)

Allora p_A(t) = p_B(t) => se Au = λu e Bv = μv =>

La relazione tra gli autovettori è:

A(Kx) = λ(Kx) => x = 2 => K(K^-1AKx) = K λx =>

Bv = 2 v => u = Kx autovett. di autoval.: λ

p) Gli autovalori di A·B sono gli stessi di B·A

Sia u/ABu = λu => A^-1(AB)A = simile ad AB =>

=>(per dim.) λ(AB) = λ (A^-1ABA) = λ (I B A) = λ(BA)

e) Gli autovalori di D^-1A sono gli stessi di D^-1/2AD^1/2

λ(D^-1A) = λ( (D^-1/2A D^-1/2) = (D^1/2A D^1/2) perchè d_ii > 0

&A fosse simmetrica D^-1A non sarebbe più simmetrica

Oss) Se A è simmetrica, gli autovalori sono reali ed ∃ ∆, U / A = U^-1∆U

con U = r₁, r₂ ..., r_n e ≃ (U^t)_r r_i r_j < 0 se i < j

p) Le norme spettrale è compatibile con la norma euclidea.

DIM.

Sia H = A^TA simmetrica e si e {u₁, ..., u_n} _{ortonormali di autovettori di H}

Scrivo x = Σ c_iu_i = c₁u₁ +...+ c_nu_n =>