Metodi Numerici con Elementi di Programmazione (sunto)

Numeri

• Errore incerte (scelta modelli)
• Troncatura (approssimaz del metodo numerico)
• Procedimento (natura algoritmo) - stabilità
• Arrotondamento (approssimaz del numero; macchina fissa)

Cancellazione numerica

Aumento di incertezza del calcolo quando ... ... numeri molto piccoli rispetto ... ... calcolando.

f_m(x) = x (1 + ε_x) f_m(y) = y (1 + ε_y)

f(x) - f(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 ∼ f(ε_x)

Il più lineare p ... dell'algoritmo

Numeri errore

• Incerte (scelta modelli)
• Troncamento (approssimaz. del metodo numerico)
• Procedura (natura algoritmo) → Stabilità
• Aritmetico (approssimaz. del numero: macchina fin.)

Cancellazione numerica

Fenomeno di instabilità del calcolo quando si sottraggono numeri molto vicini rispetto alla precisione con cui si sta lavorando f(x): x(1+_∊) f(y): y(1+_∊)

f(x)-f(y) = x(1+_∊x) - y(1+_∊y)= x-y + x_∊x - y_∊y= (x-y) /1 + _∊x-_∊y/x-y

Stabilità algoritmo

Il più lineare E_m = f(_∊i)

Errore e condizionamento del problema

Errore

Condizionamento del problema

ε = X- X_e ≈ ΔX

f(X+ y) = f(X)+ yⁿ- y^jf^(j)(X)+ (Δx)ⁿ... - f^(x)˃ f^(j)(X)+ (Δx)^j...˃ ∫₀^xf^(j)...- ∫_X^xf⁽ⁱ⁾x... Δx...˃ errore relativo dell’output

Δy = d fx^(x)Δx_X

Numero di cond 2^ε(C^-1)

Teorema Bohm-Jascini

Teorema Bohm-Jascini: ogni algoritmo può essere scritto utilizzando solo 3 strutture di proposizione:

• Sequenze (lettura, scrittura, assegnazione)
• Iterazione (ciclo ripetizione, for ... esecutato controllato while)
• Iterazione

Metodi per radici

Bisezione

Bisezione

X_k = a_k + b_k−∫_c

X_k+1 < c˃ f(X_k+1) <> c

Newton-Raphson delle tangenti

Newton-Raphson delle tangenti

X_k= X_k+1−∫^{f(X_k)∕f′(X_k−1)}

Metodo babilonese

Metodo babilonese

X_k = X_e −∕

Teorema applicabilità Newton

Teorema applicabilità Newton: H_p f ∈ C[_a,b]f_(a)f_(b)funica radice in f

Th) ∃ξ _l ∈ I: ...'sssssss converges Vξ° ∈ Corollario:

e_k+1 = ξ^k+1 - X^* = ...= e_k (e_k + ...=>= lim e_k+1 = ...(today) se e_k° (x) ...X...t... metodi converges se ...efficenza computaz.

Metodo raggiunto: X_k = .......

Condizione: ....

Secanti con estremo: X_k = ...

Metodo punto unito

Metodo punto unito: X₀：...

Cost di canto e_m ≅ Σ ...

Condizione necessaria:...I..e punto di unito...condiz. sufficiente

Hp) ϕ ∈ C¹(Γ), Γ = [α, β], ϕ(Γ) ⊆ I, |ϕ′(x)| ≤ K < 1

Th) X_m = ϕ(X_m−1) converge a ξ punto unito di ϕ in I∀X₀ ∈ I, X₀ = I

ip.1: se sono verificate le ipotesi è possibile cercare un altr. intervallo I₁: ξ ∈ I₁ ⊆ I e vale l'ip.1

ϕ può anche avere un unico invariante

|ϕ(x₁)−ϕ(x₂)| ≤ K |x₁ − x₂|, x_i ∈ (0, 1)

Condiz. sufficiente

Hp) ϕ ∈ C(Γ), Γ: ϕ(I) ⊆ I; I = ϕ(I; I = [x₀], |ϕ(x)| ≤ K < 1

Th) ∃! ∈ I: ∀∑ X_m ϕ(X_m) converge a k ε β e_m = ϕʹ(ξ) ^{1,3 × X − X_m) − ϕ(e_m}) e_m

In mod. κ per conv.

|ϕ(x)| > 0 → converge monotona φ0 → ∫X (x_ex₀) x₀ dϕ(x_ex₀)

|ϕ(X)| < 0→ converge alternata (oppure alternativamente per definiz.)

Teorema converge ordine ρ

Teorema converge ordine ρ

Hp) ϕ ∈ C¹(Γ), Γ:ϕ(I)−Γ, ϕ(I) = I (m)ϕ(I) = [x₀] Th) X_m ϕ(X_m) = conver. a ξ con ordine ρ e fattore di conv. |ϕʹ(ξ)|^{p−1 p!}.

Errore a priori: |e_m| ≤ |e_mI| ≤ K|e_m|^ε−m|e_m| K^{m1−K| −}|K| log |_{e(^1−K−β)}|

Errore a post: |e_{Xm−1Xm−Xm−1}| < K

Metodo punto unito discreto NN

Metodo punto unito discreto NN |F(X)| → ∀∑ ϕ(X_x−1)_ef(x−1) 15|ϕ(X_i)| ^|ϕ(x_i)| _|

Sulla compatibilità: se |i| ≤ |A|, |A| |A|→ ∫| | | = |→ ρ(A) ≤ |A|^{A| ∀max}

Cond. necessarie

Hp) X^mϕ(X) converge χ, ϕ continua in X

Th) X^e punto unito di e

Cond. suff.

Hp) ϕ è una contrazione |ϕ(X) Ψ(X)| ≤ |ϕ| |κ(X)|

Th) X^(x)(x)→ ϕ(X_Hx>) converge |ϕ/H(X)| ^{β−sup: β min}

Hp) |()| < 1 ∀ ∈ Th) è contrazione in S

Newton sist non lin

Newton sist non lin: ⁽⁺¹⁾ = ⁽⁾ − ⁻¹(⁽⁾) (⁽⁾) det ≠ 0, ∈ ²(Π)

Computazionalm. svantaggioso

⁽⁺¹⁾ = ⁽⁾ −, = ⁽⁺¹⁾ − = ⁽⁺¹⁾ − ⁽⁾

Contion... a posto |⁽⁺¹⁾ − ⁽⁾| = || <

Metodi diretti sistemi lineari

Metodi diretti sistemi lineari: Cramer  det ;    det ;        ⁽⁺¹⁾ = ⁽⁾, = + 1 passo = +1, = colonna  ⁽⁺¹⁾ − ⁽⁾, A = LU →...⁽⁾ = ^(-1),

Sist. indefinito A diag + codog sup.

A = { } AX = B

X_m = b_m / s_m

b_i = s̅_i X̅_i / s_i    ∀i = 1, ..., m-1

C ≤ ε 2ʳʰ⁻¹

Condizionalm. sist. lineari

Condizionalm. sist. (lin.)

A (X + SX) = B + SB

|SX| / |X| < K (A) |SB| / |B|    se De sinonimo def pos => K₂ = λ_max / λ_min

|SX| / |X| ≤ K (A) (|SB| / |B| + |SA| |AH| / |AH| )

Punto unito sist. lin.

Punto unito sist. lin.

F (X̅) = 0 MX = B + NX =>X = M^-1 NX + M^-1 B => C = M^-1 N, Q = M^-1 B

Splitting Jacobi

Splitting Jacobi: D = M , L+U = N => C_jj = D_jj (L +U)- Q_j = D_jj B -

Splitting Gauss-Seidel

Splitting Gauss-Seidel: D + L = M, U = N =>C_GS = -(D + L)^-1 U

Q_GS = (D + L)^-1 B quando applicabile GS è più veloce di J se A è ~ diagonim. => GS e S converge VX⁰ se A è simm. e def pos. => GS converge

|E^(k+1)| = ... |X - X^(k+1) |/|X - X^(k)| = ... 1,10^-m=> X_grand ... P(C)^1/2 ω^m= ...=> K = ... log P(d_i)/...

Splitting sovrarelassato

Splitting sovrarelassato: D/_ω + L = M ⇒ D/_ω = D + U = N↑ se ω = 1 C_SOR = C_GS

Se A è simm. e def pos =>SOR converge se ... ω occxx2

Se A è simm. e def pos e tridiag =>SOR converge ptivrel . cemte ...ω = ω_opt = ... 1/(1 + √(P[_GS])

X^(k+1) = ...ω X^(k) + (1-ω) X^(k)

Equaz.diff.. d Cauchy e ordine N

Equaz.diff.. d Cauchy e ordine N

y⁽ⁿ⁾ = f(x, y_n, y_(n-1) (x), y_(n-2) (x)) ⇒ y₁ y y₂ y y₃ yy_n = f(x, y, y₁, ... y_m)

È limitata in piccoli soluzioni di Cauchy

Hp { f ε C(Q). Q = x0 x1{y... b₁ b₁ b₂ b_k }

Lipschiziano rispetto a yi uniform app e xn,q ⇒ Z ³ 0 y_k = f(x,y^(k)),y(x)) ≤ 1/2 ... V∀

Th) E ..._[x x β/i₂ ... y soluzione di Cauchy

Condizione sufficiente per le lipschiziante

Condizione sufficiente per le lipschiziante

Hp) { ... msop y in Q ) { M {|X^{(k) ...} Th) f e lipschizian rispett a y ⇒

Metodi per equazioni differenziali

Euler esplicito

Euler esplicito: h = ^β⁄_m I = [ ].Χ ( ) y_n+1 = y_n+h∫( ). p=1

Famiglia Runge Kutta

Famiglia Runge Kutta: y(x+h) - y(x) = hΦ(x,y(x),h, β)Σ_α = Σ∫ ₌₁

Heun

Heun (one step esplicito)

q₁ = α_-1 → z = 2 ⇒ p=2

y_n+1 = .y_n+h₂∫(x_n) ∫(x + h _{+ >})

Euler modificato

Euler modificato (one step expl.)

q_-1 → z = 2 ⇒ p=2

y_n+1 = y_n