Calcolo degli zeri di una funzione

CALCOLO NUMERICO

PROF.: Alessandro Pugliese

E-MAIL: alessandro.pugliese@uniba.it

RICEVIMENTO: Martedì 15.00-16.00

LINGUAGGIO DI PROGRAMMAZIONE: python (distr. ANACONDA, ide SPYDER)

Capitolo 1: Calcolo degli zeri di una funzione

PROBLEMA. Data f: [a,b]→ℝ (almeno) continua, calcolare un valore α ∈ [a,b] tale che f(α)=0 α tale che f(α)=0 è detto zero della funzione.

ESEMPIO. Supponiamo di voler risolvere:

cos x - x < cos x → cos x - x = 0

in questo caso non abbiamo alcuna procedura finita per poterla risolvere.

RICHIAMO. (Teorema di Bolzano) Sia f: [a,b]→ℝ continua. Se f(a)⋅f(b) < 0, allora ∃ c ∈ (a,b) tale che f(c)=0.

f(a)_.0

y 0

f(b)_.0

Se la funzione verifica le ipotesi del teorema allora ha almeno uno zero. Nelle ipotesi del teorema di Bolzano, lo zero è unico se f è strettamente monotona in [a,b].

I metodi che studieremo sono metodi iterativi. Si parte da un'approssimazione iniziale x₀ e si costruiscono delle approssimazioni successive x₁, x₂, ..., x_n.

Calcolo Numerico

• Prof.: Alessandro Rugi...
• E-MAIL: alessandro.rugi...
• RICEVIMENTO: Martedi’ 15.00-16.00
• LINGUAGGIO DI PROGRAMMAZIONE: python (distr. ANACONDA, ide SPYDER)

Capitolo 1: Calcolo degli zeri di una funzione

Problema: Data f: [a,b] → ℝ (almeno) continua calcolare un valore α∈[a,b] tale che f(α) = 0 α tale che f(α) = 0 e detto zero della funzione.

Esempio: Supponiamo di voler risolvere

in questo caso non abbiamo alcuna procedura finita per poterla risolvere.

Richiamo (Teorema di Bolzano) Sia f: [a,b] → ℝ continua. Se f(a)·f(b) < 0, allora ∃ c ∈ (a,b) tale che f(α) = 0.

Se la funzione verifica le ipotesi del teorema allora ha almeno uno zero.

Nelle ipotesi del teorema di Bolzano lo zero è unico se f è strettamente monotona in [a,b].

Funzione non monotona

2) se f e' derivabile due volte e la derivata seconda f'' ha segno costante in [a;b], cioe' la funzione non cambia mai concavità.

Metodo delle successive bisezioni

Sia f: [a; b] -> R continua e tale che f(a) ⋅ f(b) < 0

Definiamo a⁽⁰⁾ = a, b⁽⁰⁾ = b, x⁽⁰⁾ = (a⁽⁰⁾ + b⁽⁰⁾) / 2

k indica il passo dell'algoritmo

PASSSO GENERICO. Per ogni k ≥ 0

1. se f(c(x^(k+1))) = O, poniamo α = x^(k) e interrompiamo il procedimento,
2. se f(c(b^(k)) c(x^(k)) < 0, poniamo a^(k+1) = x^(k), b^(k+1) = b^(k),
3. se f(c(x^(k))) f(c(x^(k))) < 0 poniamo a^(k+1) = a^(k), b^(k+1) = x^(k)

Infine poniamo x^(k+1) = (a^(k+1) + b^(k+1)) / 2

Si può verificare solo una di queste tre possibilità.

ESEMPIO

Consideriamo una funzione che verifica le ipotesi del Teorema di Bolzano.

La funzione ricade nel caso (3). Dopo il primo passo dell'algoritmo, l'intervallo andrà da x⁽⁰⁾ a b. A questo punto ripeto il procedimento.

Il nuovo intervallo va da x⁽⁰⁾ a x⁽¹⁾.

Dal grafico si nota che la successione di punti si avvicina sempre più ad uno zero d.

Abbiamo due possibilità:

1. Il procedimento si interrompe in un numero finito di passi, fornendo d tale che f(d) = 0.
2. Il procedimento genera una successione {x^(k)}_k≥0 tale che lim_k→+∞ x^(k) = d con f(d) = 0.

Naturalmente, il punto (1) è molto improbabile che accada in senso pratico.

Dal un punto di vista pratico l’algoritmo può produrre intervalli troppo piccoli e la condizione di arresto f(x^(k)) = 0 può non risultare mai verificata esattamente.Il nostro obiettivo è quello di interrompere il procedimento quando x^(k) è sufficientemente vicino ad d.

RICHIAMO (Distanza fra due punti) x,y∈ℝ "distanza di x da y" = |x-y| Fissiamo ε>0 detta tolleranza e cerchiamo k∈ℕ tale che |x^(k+1) - x^(k)| < ε

Proviamo a metterci al passo k dell’algoritmo.

Vogliamo stimare

x^(k+1) - x^(k) = 1/2(b^(k) - a^(k)) < ε

k ≥ 0

dobbiamo imporre questa condizione

Per costruzione ad ogni passo l'ampiezza degli intervalli è dimezzata

Cerchiamo K ∈ N tale che 1/