Metodo di bisezione

Da Wikipedia

I metodi per calcolare in modo approssimato le radici di un’equazione (valori dell’incognita che soddisfano l’equazione) si articolano in due fasi:

nella prima fase si separano le radici, ovvero si determinano gli intervalli della retta reale che contengono una sola radice dell’equazione;

nella seconda fase si calcola un valore approssimato della radice dell’equazione applicando uno dei metodi disponibili.

Quando si sono separate le radici, ad esempio, si è trovato che la radice $alpha$ è compresa nell’intervallo $[a,b]$ abbiamo due valori approssimati, uno per difetto $a$ ed uno per eccesso $b$ della radice.

Si tratta di restringere l’intervallo in modo da ottenere valori più approssimati, secondo una approssimazione fissata. I procedimenti sono iterativi.

In analisi matematica il teorema di Bolzano, detto anche teorema degli zeri per le funzioni continue, assicura l’esistenza di almeno una radice delle funzioni continue reali che assumano segni opposti ai due estremi di un intervallo.

Nel caso ci si trovi in presenza di una funzione strettamente monotona, il teorema dice che lo zero è unico; se non si fa tale ipotesi gli zeri possono essere più di uno.

Nelle ipotesi

f(x) continua in [a, b]
Un unico zero in [a, b]
La funzione cambia segno negli estremi: $f(a) < 0 < f(b)$

Il metodo di bisezione funziona perché a ogni passo

dimezza l’intervallo
sceglie se aggiornare $a_i$ oppure $b_i$ in modo da mantenere le condizioni iniziali

Il metodo funziona anche se

il cambio di segno è al contrario: $f(a) > 0 > f(b)$
ci sono più zeri nell’intervallo

Esempio

Data l’equazione $\displaystyle \frac{1}{3}x^3 - \frac{5}{3}x^2 + 2 x = 0$ calcolare una delle radici con il metodo di bisezione.
L’equazione può essere studiata facilmente e le radici sono 0, 2, 3.

Separazione delle radici (fai finta di averlo fatto per tentativi…)

x₁= -0,5, f(x₁) = –1.5…
x₂= 0,5, f(x₂) = +0,625…
x₃= 2,5, f(x₃) = –0,208…
x₄ = 4,0, f(x₄) = +2,667…

Avendo individuato 3 intervalli dove la funzione cambia segno abbiamo separato le 3 radici dell’equazione.
Concentriamo l’attenzione su uno dei 3 intervalli: [2,5, 4,0]

Passo		x			y
	`a`	`m`	`b`	`f(a)`	`f(m)`	`f(b)`
1	`2,500000`	`3,250000`	`4,000000`	`-0,208333`	`+0,338542`	`+2,666667`
2	`2,500000`	`2,875000`	`3,250000`	`-0,208333`	`-0,104818`	`+0,338542`
3	`2,875000`	`3,062500`	`3,250000`	`-0,104818`	`+0,067790`	`+0,338542`
4	`2,875000`	`2,968750`	`3,062500`	`-0,104818`	`-0,029958`	`+0,067790`
5	`2,968750`	`3,015625`	`3,062500`	`-0,029958`	`+0,015952`	`+0,067790`
6	`2,968750`	`2,992188`	`3,015625`	`-0,029958`	`-0,007731`	`+0,015952`

Dopo pochi passi

y = -0,007731, molto vicina a 0
x = 2,992188, molto vicina a 3.

Il criterio per fermare l’iterazione si basa però su un altro ragionamento: se si ferma l’iterazione a un certo passo l’errore che si commette è minore di (b-m), oppure (m-a), la dimensione del prossimo intervallo delle x

Passo		x		Errore minore di		y
	`a`	`m`	`b`	m-a b-m	`f(a)`	`f(m)`	`f(b)`
1	`2,500000`	`3,250000`	`4,000000`	`0,750000`	`-0,208333`	`+0,338542`	`+2,666667`
2	`2,500000`	`2,875000`	`3,250000`	`0,375000`	`-0,208333`	`-0,104818`	`+0,338542`
3	`2,875000`	`3,062500`	`3,250000`	`0,187500`	`-0,104818`	`+0,067790`	`+0,338542`
4	`2,875000`	`2,968750`	`3,062500`	`0,093750`	`-0,104818`	`-0,029958`	`+0,067790`
5	`2,968750`	`3,015625`	`3,062500`	`0,046875`	`-0,029958`	`+0,015952`	`+0,067790`
6	`2,968750`	`2,992188`	`3,015625`	`0,023438`	`-0,029958`	`-0,007731`	`+0,015952`

Dopo 6 passi la soluzione approssimata è x = 2,992188.
Se si ferma l’iterazione si commette un errore minore di 0,023438.

Wikipedia: Teorema di Bolzano – Metodo della bisezione – Calcolo di uno zero di una funzione

$\displaystyle a_1 < x_* < b_1$	$\displaystyle f(a_1) < 0 < f(b_1)$
$\displaystyle a_1 \le a_2 \le x_* \le b_2 \le b_1$	$\displaystyle f(a_1) \le f(a_2) \le 0 \le f(b_2) \le f(b_1)$
…	…
$\displaystyle a_1 \dots \le a_n \le x_* \le b_n \le \dots \le b_1$	$\displaystyle f(a_1) \dots \le f(a_n) \le 0 \le f(b_n) \le \dots \le f(b_1)$
…	…