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]
La funzione cambia segno negli estremi dell’intervallo
- $f(a) < 0 < f(b)$
- $f(a) > 0 > f(b)$

il metodo di bisezione funziona perché a ogni passo

calcola il valore centrale dell’ascissa: $\displaystyle m_i = (a_i + b_i)/2$
assegnare il valore di $m_i$ a $a_i$ oppure a $b_i$ in modo da mantenere il cambio di segno della funzione

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

Esempio

Data l’equazione $\displaystyle \frac{1}{3}x^3 - \frac{5}{3}x^2 + 2 x = 0$ calcolare, in modo approssimato, le sue radici.

Un’equazione polinomiale di 3° grado può avere fino a 3 radici reali.
L’equazione può essere studiata facilmente e le radici sono 0, 2, 3.

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

	$x_i$	$f(x_i)$	?
1	`-0,5`	`-1,458333...`
2	`+0,5`	`+0,625000`	`- / +`
3	`+2,5`	`-0,208333...`	`+ / -`
4	`+4,0`	`+2,666666...`	`- / +`

Hai individuato 3 intervalli dove la funzione cambia segno, hai separato le 3 radici dell’equazione.

Concentriamo la nostra attenzione su uno dei 3 intervalli, per esempio [2,5, 4,0]

Passo		`x`			`f(x)`
	`a_i`	`m_i`	`b_i`	`f(a_i)`	`f(m_i)`	`f(b_i)`
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

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

Criteri per fermare l’iterazione

Se f(x) = 0 allora x è la radice dell’equazione.
Se si decide di interrompere l’iterazione al passo i-esimo allora l’errore che si commette è minore di b_i-m_i, oppure m_i-a_i, la dimensione del prossimo intervallo delle x

Passo		`x`		Errore minore di		`f(x)`
	`a_i`	`m_i`	`b_i`	`m_i-a_i b_i-m_i`	`f(a_i)`	`f(m_i)`	`f(b_i)`
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

Python