Lezioni e esercitazioni, Analisi numerica

Analisi Numerica

Metodi e procedure per risolvere problemi in forma numerica

• calcolo scientifico
• calcolo parallelo

Ogni processore risolve una parte per la stessa procedura

La matematica, per ora applicata, ha bisogno di metodi numerici per risolvere i problemi

Metodi per risolvere equazioni non lineari o approssimare funzioni

Burden Faires "Numerical Analysis" Thomson Brooks

Problema Reale → Modello matematico → Problema ben posto

Intendiamo dire che la soluzione è unica allora è ben posto

Modello numerico

Algoritmo → Implementazione su computer → [Output → Analisi Risultati]

Schema risolutivo del modello numerico

Bisogna verificare che i risultati ottenuti siano corretti

Allora i processi potrebbero non essere finiti ma essere iterativi ovvero che continuano dell'input e convergenza alla soluzione

Strumenti elaboratori scientifiche

• linguaggi di programmazione (es. C++)
• excel
• software scientifico (es. Matlab, Maple, Mathematica) ← lo laboratorio di calcolo numerico

Floating Point

Numeri in virgola mobile → Dobbiamo prima studiare

Aritmetica di macchina

ESEMPIO

Crescita della popolazione nel tempo

N(t) La popolazione cresce con velocità proporzionale al suo numero con la costante di proporzionalità

(1) dN(t)/dt = λ N(t) N₀ = N(0)

Si tratta di un'equazione differenziale ordinaria. La soluzione di (1) è N(t) = N₀e^λt

Se introduciamo che vi sia un aumento della popolazione causa immigrazione con velocità/anno costante ν

(2) diventa (2') dN(t)/dt = λ N(t) + ν

La soluzione di (2) ⇒ N(t) = N₀e^λt + ν/λ (e^λt - 1)

(1)

N₀ = 100000 ν = 43500

Alla fine dell'anno sarà 156400. Allora quanto vale la velocità di crescita interna della popolazione?

N₀e^λ·1 + ν/λ (e^λ·1 + 1) = 156400

100000

f(λ) = 0 λ?

Equazione non lineare impossibile risolverla in modo esatto! ⇒ Usiamo passare dal modello matematico al modello numerico!

ARITMETICA di MACCHINA

Viene anche chiamata in virgola mobile (floating point)

x ∈ ℝ x = p·r^q dove r è la base (di solito 10), q è l'esponente, p è detta mantissa

c_-1, c₀, c_n — si dice che la mantissa è normalizzata

Se c₁ ≠ 0

La mantissa di un numero reale x è normalizzata allora

1/r ≤ p ≤ 1

x = 0.3478 · 10^-3 r = 10 q = -3 p = 0.3478 (normalizzata)

X = 0,0325   X* = 0,0324   E_A = |X-X*| = 0,1 × 10^-3 ≤ 1/2 × 10^-3

M=3

• Allora X* ha 3 cifre dopo il primo decimale corrette in base 10
• Le cifre significative sono quelle a sinistra della 1^a cifra unitaria, cioè sono 2,3,2

I numeri non scritti con mantissa normalizzata sono delle significative le cifre uguali della 2^a mantissa

EX   X = 0,032045   Y 4 cifre corrette mentre le cifre significative sono 5

X* = 0,0320000

A Se p* n^mo numerato m macchina ha m decimali: corretti

(p-p*) < = 1/2 × r^-m

|X-X*| < = 1/2 × r^-m

B Se vale E_A   |X-X*| < = 1/2 × r^-m   => X* ha almeno m cifre significative

dimostrazione della (B)

Dalla (A)   |X-X*| < = 1/2 × r^-m × |X|

|p q - p* q| < = 1/2 × r^-m |p q|

|p - p*| < = 1/2 × r^-m |p| < = 1/2 × r^-m

Sono significative m cifre della mantissa normalizzata

EX   X = 0,0028386   r = 10

X* = 0,0028385

E_A = |X-X*| = 0,1 × 10⁶   X* ha m = 6 cifre dopo la virgola corrette

E_R = |(X-X*)/X| = 0,1 × 10^-6

= 0,203860 × 10^-2 => 0,203 - 10^-4

NB L'errore assoluto da informare, X numeri di cifre dopo il punto decimale corrette, & lungo l'errore relativo sul numero di cifre significative (= nel conto delle dimensioni del dato)

y = f(x)

ERRORI x dai esatti, x dai perturbati

1. E_c = f(x_r), f(x) Errore di calcolazione_numerico

DISCRETIZZAZIONE DEL MODELLO

E_t = f_t(x)

Errore di tracciamento

3. E_g = f_t(x) - f_a(x) = E_c + E_t + E_ta

EQUAZIONI NON LINEARI

Vogliamo risolvere un problema della forma f(x) = 0 dove f(x) più essere una funzione non lineare (nel caso ai 1-dimansionale)

• x ∈ Y
• x ∈ X
• [se qual determinato elemento è nato a: f]

f(x) = 0 un'equazione non lineare

1. Equazione algebrica
2. Trascendente

MOLTEPLICITÀ DI UNA RADICE

a radice di f(x) = 0, f(x) = (x-a)^lf_i(x)

moleplicita `

f_(x) = (x-a)^mf_i(x), f_i(a)≠0

1. f_(a) = 0
2. s≤l
2. m-l(a) ≠ 0

metodi numerici per risolvere = successione ai sempre ai, procedo con l'o piu stime iniziali convergento a x_l, x = α

1 separazione delle radici

2 scelta dei metodi

3 studio della convergenza

4 scelta di criteri d'arresto

I. SEPARAZIONE delle RADICI

Si cerca di individuare intervalli in cui ci possa trovare le radici.

II. METODO di BI-SEZIONE

f ∈ C [a,b], f(a)f(b) < 0

• a₁=a, b₁=b, p=a
• i=1
• p_i = ^{a_i + b_i} / ₂
• If |p_i - p_i-1| < ε or |f(p_i)| < ε Then 10 (= end of procedure)
• If f(a_i)f(b_i) > 0 then 6 else go to 8
• a_i+1 = a_i, b_i+1 = p_i
• i=i+1 go to 3
• a_i+1 = p_i, b_i+1 = b_i
• i=i+1 go to 3
• End of procedure => output p_i

=> |b₁-a₁| = ^b-q / _2^i-1 i=1,2,...

q_i stima per difetto di p_i, b_i stima per eccesso di p_i

TEOREMA

Se f ∈ C (a, b) e f(a)f(b) < 0 => la bisezione genera una successione { p_i }_i=1^∞, che approssima uno zero p di f con |p_n - p| ≤ ^b-a / _2ⁱ i > i₀, i >

^{|b_n - a_n|} | ^{|b-a| | b-a₂₄}24, e p ∈ [a_nb_n], ma p_i = ^{b_i + a_i} / ₂ punto medio di

= α + (-1)^p ε_kp

p! ≠ (φ) η_k

ε_k+1 = α - x_k+1 = (-1)^p+1 ε_kp

p!

F^(p)(η_k) η_k ∈ (a_k, x_k)

lim (n⟶∞) η_k = α purché x_k ⟶ α x⟶ α

lim (k⟶∞) |ε_k+1|/|ε_k|^p = lim (k⟶∞) p

F^(p)(η_k) p

!

(F^(p)(α) ≠ 0) = C ≠ 0

TEOREMA

Sia F/ F(x) ∈ C_c(a, b) ∀ x ∈ (a, b) e |F'(x) | ℓ

ε δ t_a x_k+1 = t (x_k) k = 0,1,1 con x₀ dato e t ∈ (0, 1 )

⇒ |ε_n| = |α - x_n| ≤ βⁿ/1-β |x₁ - x₀|

DIM

Do e fisso Io. Assumo m > n

|x_m - x_n| = | x_m + x_m-1 + x_m-2 + ... + x_n+1 - x_k

= [(x_n-x_m-1)+(x_m-x_m-2)+...+ (x_m+1 - x_n) +... ]

≤ | x_m - x_m-1 | + | x_m-1 - x_m-2 | +...+ |x_n+1 - x_n =

= | F(x_m) - F(x_m-2) + ... + F(x_n) - F(x_m-1)

*) |F(x_m) - F(x_m-2) = F' (

ξ_m-2) (x_m- x_m-2) =

≤ F'(

ξ_m-2) |x_m-1 - x_m-2 ≤ | F' ξ_m-1) | F' (x_m-2)

|x_m-x_n| ≤ β^m-1 x₀ + . + β^umn (x_n-1 +) ...

β^um-1(+β^t...- β^m+1...

-

^¨0