Metodi Numerici con Elementi di Programmazione (sunto)

Numeri

Errore

incerte (scelta modelli)

• troncatura (approssimaz del metodo numerico) procedimentos (natura algoritmo) - stabilità
• arrotondamento (approssimaz del numero; macchina fissa)

Cancellazione numerica

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

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) → Stabilita

aritmetico (approssimaz. del numero: macchina fin.)

Cancellazione Numerica:

Fenomeno di instabilita 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

Stabilita Algoritmo:

il piu lineare

E_m = f(_∊i)

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

Ogni algoritmo può essere scritto utilizzando solo 3 strutture di proposizione:

sequenze (lettura, scrittura, assegnazione),

iterazione (ciclo ripetizione, for ...

esecutato controllato while), iterazione

Bisecione

X_k = a_k + b_k−

∫_c

X_k+1 < c

˃ f(X_k+1) <> c

Newton-Raphson delle Tangenti

X_k= X_k+1−

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

Metodo Bablonese

X_k = X_e −∕

Teorema Applicabilita Newton:

H_p f ∈ C[_a,b]f_(a)f_(b)f

unica 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.

Metedo raggiunto:

X_k = ...

....

Condizione: ....

Secani con estremo:

X_k = ...

Metodo punto insieme:

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 ρ

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

|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. necessare

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:

⁽⁺¹⁾ = ⁽⁾ − ⁻¹(⁽⁾) (⁽⁾) det ≠ 0 , ∈ ²(Π)

computazionalm. svantaggioso

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

= ⁽⁺¹⁾ − ⁽⁾

contion... a posto |⁽⁺¹⁾ − ^{()| = || <}

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. (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.

F (X̅) = 0 MX = B + NX =>

X = M^-1 NX + M^-1 B => C = M^-1 N, Q = M^-1 B

Splitting Jacobi:

D = M , L+U = N => C_jj = D_jj (L +U)

- Q_j = D_jj B -

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:

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

y⁽ⁿ⁾ = f(x, y_n, y_(n-1) (x), y_(n-2) (x)) ⇒

• y₁ y
• y₂ y
• y₃ y

y_n = f(x, y, y₁, ... y_m)

È limitata in picoli soluzioni di Cauchy

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

lipschiziano rispeto 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

Hp) { ... msop y in Q ) { M {|X^{(k) ...}

Th) f e lipschizian rispet a y ⇒

Euler Esplicito:

h = ^β⁄_m I = [ ].Χ ( )

y_n+1 = y_n+h∫( ). p=1

Famiglia Runge Kutta:

y(x+h) - y(x) = hΦ(x,y(x),h, β)

Σ_α = Σ∫ ₌₁

Heun (one step esplicito)

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

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

Euler Modificato (one step expl.)

q_-1 → z = 2 ⇒ p=2

y_n+1 = y_n