Domande e Risposte Calcolo Numerico

DOMANDE DI TEORIA CALCOLO NUMERICO

1. Rappresentazione dei numeri nel calcolatore: descrivere la rappresentazione dei numeri reali in virgola mobile. Richiamare la precisione di macchina ed il minimo/ massimo numero rappresentabile. In quale caso l'operazione di macchina x+y produce un errore relativo amplificativo? Commentare.

Nel calcolatore i numeri vengono rappresentati per convenzione attraverso la virgola mobile normalizzata, che obbedisce la seguente relazione:

m o,e,n ~ 0,1^N,

dove 0,f è la mantissa e E per R con la sua prima cifra ≠0.

Ne' la base, nel caso dei calcolatori n ha N=2 (codice binario), q è l'esponente della base.

A seconda del caso in cui il calcolatore sia a virgola o a doppia precisione (32 o 64 bit) si avrà una diversa distribuzione dei bit p la composizione del numero:

32 bit

1 bit      1 bit      7 bit      23 bit

Segno del      segno di      massimo      xmmale      minimo                        

numero 9

64 bit

1 bit      1 bit      10 bit      52 bit

Segno del 9

Il doppia precinction e maximum numero rappresentable è 2¹⁰²³:

0 ≤ |[111111111111]= ₂2⁰1-1023. Analogamente il minimo numero rappresentabile è 2^-1023

La precisione di macchina è la minima distanza tra due numeri consecutivi (,) tale che 1+η # 1 ed è il maximum errore e che n contiene nella rappresentazione

|ε_rel = | x – x1 | _{| |εrel ≤ ¹2 N – n+1}    η = ¹₂ 2^-ς+1 2^-52 N ~ 10^-16

L'operazione di macchina x+y produce un errore amplificativo se x e y sono due numeri di segno diverso ma vicini tra loro in valore assoluto. In questo caso n verifica il fenomeno della cancellazione numerica de provoca la perdita di alla presentazioni.

2) Definire i concetti di instabilità e malcondizionamento e descrivere dueproblemi/algoritmi per i quali tali fenomeni si manifestano.Un algoritmo si dice instabile se piccoli errori presenti ad un certo istante(a stadio) del processo sono amplificati negli istanti successivi sino a degradarel’accuratezza del risultato finale.Un problema si dica malcondizionato se a piccoli errori relativi sui datiiniziali corrispondono significativi errori relativi nei dati finali.Esempio di algoritmo instabile: l’errore aumenta ad ogni passo

I_n = ∫^∞_n e^-x dx ————> n ≥ 0

∫^∞₁ e^-x dx = -1¹/_e ≅ 0,632111

per n ≥ 1

I_n = 1/_e [^e-x]₁^∞ - n/∫^∞_n x^-n-1 e^-x dx = 1-M_n-1

limato I₀

I_n+1 = 1-M_n I_n n ≥ 1

(I_m+1 E_m) = 1- (I_m + E_m)

E_n = — m + e^-1 ——> E_n = (-1)ⁿ!

Il processo del termine n! fa degenerare l’errore

Esempio di malcondizionamento: y = f(x) con x —> 1 e f(x) = √ 1-x²Infatti ȳ = f(^~x) nel calcolatore è ȳ - f(x+∆x) con s_x = precisione di macchina.Taylor: f(x+∆x) = f(x) + ∆x * f’(x) + O(∆x²)Errore: f(x+∆x) — ȳ = (∆x/f(x) = x ———-> ∆y/y

|∆y/y | = | ∆x/x | | x f’(x)/y |

————> k = indice di condizionamentomaggiore è k, peggiore è il condizionamentoper f(x) = 1-x² , k= |^x²/_1-x²|

per x —> 1 x = 1-10^-5 k = 5 .10⁵x = 1-10^-15 k = 5 .10¹⁴

6) Dati n+1 punti sperimentali, ricavare il polinomio di interpolazione di Lagrange. Enunciare e dimostrare la formula del resto (errore).

_k0, _yb

_k1, _yi

n+1 punti sperimentali

_km, _ym

Polinomio di Lagrange: L_n(x) = ∑ _k=0ⁿ L_k(x)•y_k

Teorema del resto di Lagrange: fissato _x ∈ [_x0, _xm], ∃ _x̅ ∈ [_x0, _xm], per cui f è derivabile più volte. Allora: R_n(x) =

(_{f⁽ⁿ⁺¹⁾})(_f) (_x)

(n+1)!

_{a x̅} ∈ [_x0, _xm], _x̅ ≠ _xk ∀ k

G(_m) = _β(_m) - P_n(_x)

_F(_x)

_G(_m) = _β(_m) - P_m(_x) - S_fF(_m)

G''(_m) = 0 in almeno n+2 punti:

G⁽ⁿ⁺¹⁾(_m), G⁽ⁿ⁾⁽²⁾(_x) = 0

R_m/_x

13) Dire quando è possibile fattorizzare una matrice quadrata col metodo LU.Descrivere il metodo di eliminazione di Gauss con pivot parziale.Una matrice quadrata _A è fattorizzabile nel prodotto LU se A è invertibilee se i suoi minori principali sono tutti diversi da 0._Auta fattorizzazione, che rappresenta il metodo di eliminazione di Gauss,è uno metodo instabile (perciò appena accenno al metodo di eliminazione di Gauss conpivot parziale (modulo più stabile)). Questo metodo scambia le righe della matricein modo che tutti i sottomultiplicatori (elementi della matrice L) siano in modulominori o uguali a 1.La fattorizzazione corrisponde a P^TA=LU, in cui L e U sono le stesse delteorema LU e P è la matrice di permutazione:P^TP=I → ortogonaleP_ijs=0,1 → c'è esattamente un 1 in ogni riga e colonna di P.

14) Enunciare e dimostrare il Teorema di Gershgorin per la localizzazionedegli autovalori.Teorema di Gershgorin per la localizzazione degli autovalori:Se _A∈M_n(R), λ = autovalore di A, _λ-Aii ≤ (Σ_k=1 ^m a_ik) _k≠iλ ∈ ∪ R_i R_i={zЄC : |z-a_ii|≤ ρ_i}Ogni autovalore sta nei cerchi del piano complesso di centro l'elementodiagonale di A e di raggio ρ_i.

DIM: Au=λu → a_i1m₁+...+a_inm_n= λm_i→ a_nmm₁ + ... + a_nmm_n = λm_n

(λ-a_ii)m_i = Σ _j≠i a_ijm_j= Σ ⁿ a_ijm_j 

m = indice per cui |m_m| = max |m_i| = ||m||_∞1≤i≤m

|λ-a_mm| |m_m| = Σⁿ_j=1,j≠m a_mjm_j

|λ-a_nm| ≤ Σ ^j≠m |a_nm| m_j / m_m ≥ Σ ^j≠m |a_mj| [₁] - |λ-a_nm| ≤ Σ ^j≠m |a_m,| ------------------ [^centro] [^raggio]

20)

Si consideri il seguente metodo iterativo: x_k+1 = x_k - α f(x_k) per risolvere l'equazione f(x) = 0.

1. Dire per quali valori del parametro α ∈ ℝ il metodo converge.
2. Dimostrare che il metodo ha ordine di convergenza p=1 nel caso generale.
3. Determinare un valore di α per cui il metodo ha, invece, ordine p=2.

x_k+1 = x_k - αf(x_k) è il metodo del punto fisso con g(x) = x - αf(x) ⇒ g(x) = 1-αf(x)

a) il metodo converge se |g'(ξ)| < 1 ⇒ |1 - α f'(ξ)| ≤ 1 ⇒ 0 < α f'(ξ) ≤ 2 ⇒ α < ²/_f'(ξ)

b) e_k = x_k - ξ

ξ + e_k+1 = ξ + e_k - α f(ξ + e_k)

e_k+1 = e_k - α[f(ξ) + e_k f'(ξ) + ^ɛ_k2₂ f''(ξ) + o(ɛ_k³)]

e_k+1 = e_k(1 - α f'(ξ)) - α ^ɛ_k2₂ y (ξ) - αo(ɛ_k)

^e_k+1/_ek = 1 - α f'(ξ)

lim ^|e_k+1|/_|ek| = |1-α f'(ξ)|      / ^{P=1 M=1-α f'(ξ)}

c) se α = ¹/_f'(ξ) si ha

e_k+1 = e_k - α [f(ξ) + e_k f'(ξ) + ^ɛ_k2₂ f''(ξ) + o(ɛ_k³)] = e_k - ¹/_f'(ξ) e_k f'(ξ) - ¹/₂ e_k² f''(ξ) + ^o(ɛ_k3)/_f'(ξ)

lim ^|e_k+1|/_|ek|² = |^f''(ξ)/_f'(ξ)| che coincide con M del metodo di Newton-Raphson.   → p = 2.