Calcolo degli zeri di una funzione

Calcolo Numerico

• Prof: Alessandro Rugliese
• E-mail: alessandro.rugliese@uniba.it
• Ricevimento: Martedì ore 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]→R (almeno) continua calcolare un valore ∈ [a,b] tale che f(α) = 0α tale che f(α) = 0 e detto zero della funzione.

Esempio: Supponiamo di voler risolverecos x = x ↔ cos x - x = 0In questo caso non abbiamo alcuna procedura finita per poterla risolvere.

Richiamo: (Teorema di Bolzano) Sia f: [a,b]→R continua. Se f(a)•f(b) < 0, allora ∃d∈ (a,b) tale che f(d) = 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]

Il metodo che studieremo sono metodi iterativi. Si parte da un'approssimazione iniziale x₀ e si sostituiscono dell'approssimazioni successive x₁, x₂, ..., xₙ.

Funzione non monotona

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

Metodo della successive bisezione

Sia f: [a,b] → ℝ continua e tale che f(a) · f(b) < 0

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

(k) indica il passo dell'algoritmo

• PASO GENERICO. Per ogni k ≥ 0
• (1) se f(x^(k+1)) = 0 poniamo x^(k+1) * e interrompiamo il procedimento.
• (2) se f(c(x^(k+1))) · f(x^(k)) < 0, poniamo a^(k+1) = x^(k), b^(k+1) = x^(k+1)
• (3) se f(c(x^(k))) · f(x^(k+1)) < 0 poniamo a^(k+1) = x^(k), b^(k+1) = b^(k)
• infine poniamo x^(k+1) = (a^(k+1) + b^(k+1)) / 2

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

L'approssimazione numerica di uno zero c di f si basa in genere sull'uso di metodi iterativi. Si costruisce cioè una successione di valori x_k tali che

lim (k → ∞) x_k = c

- 2 -

ESEMPIO.

Sia α = è (Numero di Nepero)

è ≈ 2,71828 459046

L'ordine di grandezza è maggiore quanto sono all'aumentare le cifre corrette dell'approssimazione di α

Criteri di arresto per il metodo delle successive bisezioni:

1. Errore assoluto

|x^(k) - α^(k)| < Ε

2. Errore relativo

|x^(k) - α^(k)| _{gigante separati} α^(k)| < Ε

3. Residuo

|f(x^(k))| < Ε

4. Errore misto assoluto/relativo

^{|x(k) - α(k)|}/_{|b^(k) β^(k)| + 1} < Ε

L'errore relativo è pericoloso se α ≈ 0 e è molto vicino a 0 Mentre, l’errore assoluto è pericoloso per α molto grandi

Se abbiamo poche informazioni su α conviene usare l’errore misto in quanto:

Errore misto ≈

E_a se α ≈ molto piccolo (E_r è inaffidabile)

E_r se α ≈ molto grande (E_a è inaffidabile)

Nota

Il lento abbattimento dell’errore suggerisce di adottare il metodo di bisezione come una tecnica di avvicinamento alla radice. In pochi passi si ottiene infatti una stima ragionevole di α, a partire dalla quale utilizzando un metodo di ordine più elevato, è possibile convergere rapidamente alla soluzione cercata entro i limiti di accuratezza prestabiliti.

Quindi, k ci dice quante cifre possiamo perdere nella soluzione rispetto a quello che avevamo sui dati.

k è detto numero di condizionamento oppure fattore di amplificazione dell'errore (relativo).

Se k > x (come ordine di grandezza va bene anche 5 o 3) il problema è ben condizionato.

Se k >= x (ordine di grandezza delle decine) il problema è mal condizionato.

In particolare, con k = 10^x quindi possiamo perdere fino a x (9) cifre significative della soluzione (rispetto al numero di cifre significative dei dati).

Per ogni problema dovremo valutare questo k.

RICHIAMO. (polinomio di Taylor) Sia f: [a,b] → R derivabile n+1 volte in (a,b). e sia x₀ ∈ (a,b) allora possiamo scrivere:

f(x) = T_n(x) + R_n(x)         ∀ x ∈ (a,b)

dove T_n(x) = f(x₀) + f'(x₀)(x-x₀) + ... + ^fn(x₀)⁄_n!(x-x₀)ⁿ

R_n(x) = ^fn+1(ξ)⁄_(n+1)! (x-x₀)ⁿ⁺¹         x⁰

ξ e ∈ compreso nell'intervallo di estremi x₀ e x.

T_n(x) è detto polinomio di Taylor centrato in x₀ di grado n

R_n(x) è una funzione detta "resto di Lagrange"

Il polinomio di Taylor è un ottimo strumento per approssimare una funzione con un polinomio.

Nel caso di problemi mal condizionati, l'unica possibilità per ottenere un risultato attendibile dalla sua risoluzione è cercare di ristrutturare il problema in modo analitico.

Avere un problema di condizionamento più favorevole.

Quando ciò non può occorre, tenendo occorre utilizzare dei metodi numerici che siano in grado di preservare le buone proprietà di condizionamento del problema originario.

y = x₂

Il zero non semplice

in questo caso la retta

tangente è

orizzontale

corrisponde all'asse x

ESEMPIO: (Funzione che non ha uno zero semplice)

y = x₂

ƒ_ε(x) = ƒ(x) + ε = x₂ + ε nessuno zero (reale)

ƒ_ε(x) = ƒ(x) - ε = x₂ - ε gli zeri diventano due ±√ε

Errore su ƒ:  ε

Errore su x:  √ε (osservare il grafico)

√ε >> ε>0, se ε è molto piccolo

Errore sui dati

ESEMPIO: ε = 10^-4

√ε ≈ 10^-2

Errore sulla soluzione

Se abbiamo uno zero non semplice cambia la natura degli zeri della

funzione e il problema rimane mal condizionato.