Metodo di bisezione

Il metodo di bisezione (o dicotomia) e l algoritmo più robusto per trovare radici di equazioni continue f(x) = 0. Si basa sul teorema di Bolzano: se f e continua su [a,b] e f(a) f(b) < 0, esiste almeno una radice in (a,b). Ad ogni iterazione si dimezza l intervallo, garantendo convergenza.

Idea geometrica

Dato un intervallo [a,b] con f(a) e f(b) di segno opposto, si calcola il punto medio c = (a+b)/2 e si valuta f(c). Si sceglie il sottointervallo [a,c] o [c,b] che mantiene il cambio di segno. Si ripete fino a quando l intervallo e più piccolo della tolleranza desiderata.

Teorema di Bolzano

Se f: [a,b] -> R e continua e f(a) f(b) < 0, allora esiste almeno un c in (a,b) tale che f(c) = 0. Questo teorema (Bernhard Bolzano 1817) e la base del metodo. Ipotesi essenziali: continuità di f e cambio di segno agli estremi. Senza queste ipotesi il metodo non si applica.

Algoritmo

1. Verifica f(a) f(b) < 0. Se no, errore: niente cambio segno.
2. Calcola c = (a + b) / 2.
3. Valuta f(c). Se |f(c)| < tolleranza o |b-a| < tolleranza: STOP, radice = c.
4. Se f(a) f(c) < 0: nuovo intervallo [a, c]. Altrimenti: [c, b].
5. Torna al passo 2.

Convergenza lineare

Ad ogni iterazione l intervallo si dimezza: |I_n| = (b-a) / 2^n. Per ottenere precisione eps servono n >= log_2((b-a)/eps) iterazioni. Esempio: intervallo iniziale [1,2] (larghezza 1), per precisione 1e-10: n = log_2(10^10) ~ 33 iterazioni. Per precisione macchina (1e-16): ~ 53 iterazioni.

Confronto con altri metodi

• Bisezione: ordine 1 (lineare), SEMPRE garantita se f cambia segno.
• Newton: ordine 2 (quadratico), veloce ma può divergere.
• Secante: ordine phi ~ 1.618, veloce ma non sempre converge.
• Regula falsi: ibrida, robusta come bisezione ma più veloce.
• Brent: combina bisezione + interpolazione quadratica inversa, default in scipy.

Vantaggi

• Convergenza GARANTITA per ipotesi di Bolzano.
• Stima a priori del numero di iterazioni: log_2((b-a)/eps).
• Insensibile a derivate, cuspidi, oscillazioni della funzione.
• Implementazione semplicissima.
• Robusto per funzioni black-box dove f' non e disponibile.

Svantaggi

• Convergenza LENTA: 1 cifra binaria per iter (~ 0.30 cifre decimali).
• Necessita un intervallo iniziale con cambio segno: per radici tangenti (f tocca 0 senza cambiare segno) il metodo fallisce.
• Trova UNA radice nell intervallo, non tutte se ne esistono multiple.
• Non sfrutta informazioni locali (derivata, secante).

Esempio: sqrt(2) in [1,2]

f(x) = x^2 - 2. f(1) = -1, f(2) = 2 (cambio segno). Iterazioni:

• iter 1: c = 1.5, f(c) = 0.25 -> [1, 1.5]
• iter 2: c = 1.25, f(c) = -0.4375 -> [1.25, 1.5]
• iter 3: c = 1.375, f(c) = -0.109 -> [1.375, 1.5]
• iter 4: c = 1.4375, f(c) = 0.066 -> [1.375, 1.4375]
• iter 30: c ~ 1.41421356 (10 cifre)
• iter 50: c ~ precisione macchina

Strategia ibrida

Combinare bisezione con metodi superlineari (secante, Newton) e la strategia migliore. Algoritmi come Brent (1973) o Dekker (1969) usano bisezione di sicurezza quando l interpolazione fallisce, garantendo convergenza con velocità superlineare in pratica. Default in scipy.optimize.brentq, MATLAB fzero, R uniroot.

Storia

Il metodo era noto agli antichi (Babilonesi, Erone). Bolzano lo formalizza nel 1817 con il teorema dei valori intermedi. Cauchy lo include in "Cours d Analyse" (1821) come algoritmo standard. La sua semplicità e robustezza lo rende ancora oggi uno dei metodi più usati come fallback in software numerici professionali.

Modalita del calcolatore

Sei funzioni di test: cubica, quadratica, trigonometrica, esponenziale, quintica, sqrt(a) generico. Inserisci [a,b], tolleranza e iter massime. Output: radice, storia di bisezioni, intervallo finale, e iter teoriche secondo log_2((b-a)/eps).

La bisezione oltre le radici: ricerca binaria e ottimizzazione

L'idea di dimezzare ripetutamente un intervallo va ben oltre la ricerca di radici. La ricerca binaria, uno degli algoritmi piu fondamentali dell'informatica, e concettualmente identica: per trovare un elemento in un array ordinato si confronta il valore centrale e si scarta meta dei candidati a ogni passo, esattamente come la bisezione scarta meta dell'intervallo. Entrambe raggiungono la risposta in un numero di passi proporzionale al logaritmo della dimensione del problema.

La stessa strategia si applica a qualunque predicato monotono: la tecnica della "ricerca binaria sulla risposta" risolve problemi di ottimizzazione trovando il valore soglia oltre il quale una condizione diventa vera. Per funzioni unimodali (con un solo massimo o minimo) la variante detta ricerca ternaria divide l'intervallo in tre parti e localizza l'estremo con lo stesso spirito. La bisezione e quindi il prototipo di un'intera famiglia di algoritmi divide-et-impera basati sul dimezzamento.

Robustezza e limiti: quando la bisezione e la scelta giusta

Il grande pregio della bisezione e la garanzia assoluta: se la funzione e continua e cambia segno agli estremi, il metodo converge sempre, senza eccezioni, e fornisce un limite d'errore certo, esattamente (b-a)/2^n dopo n passi. Questa affidabilita la rende preziosa nei contesti in cui il fallimento non e ammissibile, e come componente di sicurezza nei metodi ibridi che la combinano con Newton o la secante per unire garanzia e velocita.

I suoi limiti sono altrettanto netti. La bisezione non puo trovare radici di molteplicita pari, dove la funzione tocca l'asse senza cambiare segno, ne radici complesse, ne piu radici contenute nello stesso intervallo (ne isola solo una). La sua convergenza lineare, che guadagna circa una cifra decimale ogni 3-4 iterazioni, e lenta rispetto ai metodi superlineari. E lo strumento ideale quando la sicurezza conta piu della velocita, o come rete di protezione per metodi piu aggressivi.

Aggiornato a luglio 2026