Metodi Numerici con Elementi di Programmazione (sunto)

Numeri

Errore: incertezza (scelta modello) troncamento (approssimazione del metodo numerico) procedimento (metodo algoritmo) → stabilità arrotondamento (approssimazione del numero macchina)

Cancellazione numerica:

Fenomeno di instabilità del calcolo quando alla sottrazione numerica interviene rispetto alla precisione con cui si sta lavorando. fl(x) = x(1+ε)   fl(y) = y(1+ε_y)

fl(x-y) = x(1+ε_x) - y(1+ε_y) = x-y + xε_x - yε_y = (x-y) [(1+ xε_x - yε_y)/(x-y)]

Stabilità algoritmo: E_m = fl(ε₁) Il più lineare, passo m dell'algoritmo

Condizionamento del Problema

considerate il problemadell'input indipendente dalla stabilitá dell'algoritmo e i arrotondamenti

ε = X ˜X = ΔX

y = f(x)

y + Δy = f(x + Δx) = f(x) + Δx ⋅ f'(x) + ...

→ Δy = f'(x) ⋅ Δx + ...

• Δy / y ≈ f'(x) / f(x) ⋅ Δx / x
• errore relativo sull'output = Δy / y
• errore relativo al dato iniziale

numero di condizionamenti 2^C(f)

Teorema Boh{..} Jacopini:

Ogni algoritmo pi{..} essere scritto utilizzandosolo le 3 strutture di programmazione di sequenza (lettura, scrittura, assegnazione)interazione a ciclo (ripetizione if{..} else{..}) edinterazione controllata (while{..}) iterazione

Bisezione

x_k = (a_k + b_k) / 2

|f(x_k)| ≤ (b - a) / 2^k

C = 1

azzera 0 posto: |x_k - x_k+1| < ε

|f(x_k+1)| < ε

azzera e primitiva f_k < b - a / 2^k < C

|f_k log(2_e) b - a / ε|

Newton-Raphson delle Tangenti

x_k - x_k+1 = f(x_k) / f'(x_k)

Metodo Babilonese

x_k = x_k+1 - f_k = x_k - 2 / 2 ⋅ L^X_k

Teorema Applicabilità Newton:

{Hp} f ∈ C (a,b). f(a) ⋅ f(b) < 0, f'(x) ≠ 0 ∀x ∈ [a,b]

∃ unica radice in { }

Sist. indotto A diag. e diag. sup.

A = ^{_i, 0} _{, ,} AX = B

X = ^b _s

X_i = ^{b - Σ_,X} _s V: i = 1, ..., m-1

C_e = 2 - 1

Condizionam. Sist. (LIN.)

A(x + Sx) = B + SB

^|Sx| ≤ K(A) ^|SB|

^|x| _{|B| |A|}

K(A) ^|A|

(A + SA)(X + Sx) = B₁ + SB

^|Sx| ≤ K(A) ^{[|SB| + |SA|]}

^|X| _{(1-KA) |A| |B1|}

[|SBV| + |SA|]

^1-KA _{|B| |A|}

Punto Unito Sist. LIN.

F(X) = 0 X^(k+1) = Φ(X^(k))

Φ(x₁,..., x) = Σ^{, =}Cx +

→ |C_Φ(x) =| C

Cond. neces. e suff. per proc. iter. sist. lin.

Hp) F(x) lineare P(C) < 1

Th) Il procedimento iterativo converge

errore a post. |E^(k+1)| ≤ ^f(|C_Φ(x) - C) |X^{(k) - X(k+1)}| +

errore a pri. K ≥ ^log (||(1- f(C_Φ)) |X⁽⁰⁾| - |X⁽¹⁾|)

velocita converg V = -log (P(C))

Splitting generale:

A = M + N, M invertible.

[M + N]X = B → MX = B - NX →

X = -MNX + M^-1B → C = -M^-1N, Q = M^-1B

Splitting Jacobi:

D = M, L + U = N

C = D^-1(L + U)

Q = D^-1B

*

|f_m(x)| ≤ ε Σ_k=1^m|P_k (x)| ≤ ε max{|l(x)|}

Spline lineare

S₁(x) = ¹/_h1 ((x₁ - x)y_i - (x_i - x)y) / x_i - x_i-1

i=1,...,m

Spline cubica

S₃(x) = ¹/_hi ((x_i - x)³) M_i + ((x - x_i)³ )M_i+1)

• h₁h_i-1h₁ = h_iy
• y_i y_i+1
• Spline cubiche naturale
• Δ₀ M₀ = 0

Matr. coeff. triang. sup. diag. dom. def.

Approssimazione minimi quadrati

S_n = Σ_i=0ⁿ x^k, V_k = Σ_i=0^m y_ix^k

[A] = {{S₀ S₁ ... S_n}}

minwe.se M +- interp. e app. min quad coincide

Formule quadratura interpolatorie

I(f) = ∫_a^b/f(x)dx = ∫_a^bπ(x)dx + E_m(x)dx = Σ_m(x)R(X)