Algoritmo di bisezione

Il teorema degli zeri non dice dove sta lo zero, solo che esiste. L’algoritmo di bisezione lo trova per approssimazioni successive, dimezzando l’intervallo a ogni passo.

In sintesi — Procedimento

1. Partire da $[a,b]$ con $f(a)\cdot f(b)<0$.
2. Calcolare il punto medio $m = \dfrac{a+b}{2}$ e il segno di $f(m)$.
3. Se $f(a)\cdot f(m) < 0$: lo zero sta in $[a,m]$, pongo $b=m$. Altrimenti sta in $[m,b]$, pongo $a=m$.
4. Ripetere dal passo 2 finché $|b-a|<\varepsilon$ (la precisione desiderata).

A ogni passo l’intervallo si dimezza: dopo $n$ passi l’errore è $\le\dfrac{b-a}{2^n}$.

Esempio — Bisezione applicata a $\ln(x+3)-3x+0{,}1=0$

Sia $f(x) = \ln(x+3)-3x+0{,}1$. Cerchiamo uno zero.

$f(0) = \ln 3 + 0{,}1 \approx 1{,}2 > 0$; $\quad f(1) = \ln 4 - 3 + 0{,}1 \approx -1{,}5 < 0$. Segni opposti: c’è uno zero in $[0,1]$.

Passo	$a$	$b$	$m$	$f(m)$
1	$0$	$1$	$0{,}5$	$f(0{,}5)\approx -0{,}15 < 0$
2	$0$	$0{,}5$	$0{,}25$	$f(0{,}25)\approx 0{,}43 > 0$
3	$0{,}25$	$0{,}5$	$0{,}375$	$f(0{,}375)\approx 0{,}12 > 0$
4	$0{,}375$	$0{,}5$	$0{,}4375$	$f(0{,}4375)\approx -0{,}02 < 0$
5	$0{,}375$	$0{,}4375$	$0{,}406$	$f(0{,}406)\approx 0{,}05 > 0$

Dopo 5 passi lo zero è in $[0{,}406;\ 0{,}4375]$, con errore $<0{,}032$. Valore approssimato: $x\approx 0{,}42$.

La forza della bisezione è la sua robustezza: richiede solo di saper valutare $f$ e riconoscere il suo segno, e converge sempre (purché si parta da un cambio di segno). Il prezzo è la lentezza: guadagna circa una cifra decimale ogni $3{,}3$ iterazioni.

Collegamenti

Argomenti: Continuita
Concetti: Algoritmo di bisezione · Teorema degli zeri
Competenze: Stimare · Usare formule