Metodo della bisezione

Da Wikipedia, l'enciclopedia libera.
Alcuni passi del metodo della bisezione, applicato all'intervallo [a1;b1]. Il punto rosso è la radice della funzione.

In analisi numerica il metodo di bisezione (o algoritmo dicotomico) è il metodo numerico più semplice per trovare le radici di una funzione. La sua efficienza è scarsa e presenta lo svantaggio di richiedere ipotesi particolarmente restrittive. Ha però il notevole pregio di essere stabile in ogni occasione e quindi di garantire sempre la buona riuscita dell'operazione.[1]

Descrizione[modifica | modifica wikitesto]

Data l'equazione definita e continua in un intervallo , tale che , è allora possibile calcolarne un'approssimazione in (vedi teorema degli zeri).

Si procede dividendo l'intervallo in due parti eguali e calcolando il valore della funzione nel punto medio di ascissa Se risulta allora è la radice cercata; altrimenti tra i due intervalli e si sceglie quello ai cui estremi la funzione assume valori di segno opposto. Si ripete per questo intervallo il procedimento di dimezzamento. Così continuando si ottiene una successione di intervalli incapsulati, cioè ognuno incluso nel precedente. Questi intervalli hanno come ampiezze per

I valori sono valori approssimati per difetto della radice, i valori di sono invece i valori della radice approssimati per eccesso. Gli formano una successione crescente limitata ed i formano una successione decrescente limitata. Le due successioni ammettono lo stesso limite che è la radice dell'equazione esaminata.

Come approssimazione della radice si considera il punto medio degli intervalli, cioè per

L'algoritmo viene arrestato quando è abbastanza vicino a e/o quando l'ampiezza dell'intervallo è inferiore ad una certa tolleranza . Dunque come stima di alla fine avremo un certo Si dimostra facilmente che per l'errore commesso vale la seguente relazione:

Un importante corollario è che

quindi la convergenza del metodo è globale.

Se richiediamo otteniamo la seguente condizione per :

Essendo servono in media più di tre bisezioni per migliorare di una cifra significativa l'accuratezza della radice, quindi la convergenza è lenta. Inoltre la riduzione dell'errore a ogni passaggio non è monotona, cioè non è detto che per ogni Non si può definire quindi un vero e proprio ordine di convergenza per questo metodo.

Algoritmo[modifica | modifica wikitesto]

Di seguito si fornisce lo pseudocodice di questo metodo:[2]

N ← 1
While NNMAX # limite alle iterazioni per impedire loop infiniti
  c ← (a + b)/2 # new midpoint
  If f(c) = 0 or (ba)/2 < TOL then # soluzione individuata
    Output(c)
    Stop
  EndIf
  NN + 1 # incremento del contatore
  If sign(f(c)) = sign(f(a)) then ac else bc # nuovo intervallo
EndWhile
Output("Operazione non riuscita.") # massimo numero di iterazioni superato

Esempio[modifica | modifica wikitesto]

È possibile utilizzare il metodo di bisezione per trovare la radice del seguente polinomio:

Innanzitutto bisogna individuare due numeri e tali che e hanno segno discorde. Per la funzione summenzionata, e soddisfano tale criterio, in quanto

e

Essendo la funzione continua, le ipotesi del teorema di Bolzano sono rispettate e deve esservi una radice compresa tra [1, 2].

Essendo gli estremi dell'intervallo che abbiamo considerato e , il punto medio sarà

Il valore della funzione al punto medio sarà . Essendo negativa, viene sostituita con per la prossima iterazione affinché e abbiano segno discorde. Con il continumento di questo processo l'intervallo fra e diverrà drasticamente sempre più piccolo, sino a convergere nella radice ricercata. Si consulti, in tal senso, la tabella successiva:

Iterazione
1 1 2 1.5 −0.125
2 1.5 2 1.75 1.6093750
3 1.5 1.75 1.625 0.6660156
4 1.5 1.625 1.5625 0.2521973
5 1.5 1.5625 1.5312500 0.0591125
6 1.5 1.5312500 1.5156250 −0.0340538
7 1.5156250 1.5312500 1.5234375 0.0122504
8 1.5156250 1.5234375 1.5195313 −0.0109712
9 1.5195313 1.5234375 1.5214844 0.0006222
10 1.5195313 1.5214844 1.5205078 −0.0051789
11 1.5205078 1.5214844 1.5209961 −0.0022794
12 1.5209961 1.5214844 1.5212402 −0.0008289
13 1.5212402 1.5214844 1.5213623 −0.0001034
14 1.5213623 1.5214844 1.5214233 0.0002594
15 1.5213623 1.5214233 1.5213928 0.0000780

Dopo tredici iterazioni è evidente che si verifica una convergenza in 1.521, radice del polinomio.

Note[modifica | modifica wikitesto]

  1. ^ Burden & Faires 1985, p. 35.
  2. ^ Burden & Faires 1985, p. 29.

Bibliografia[modifica | modifica wikitesto]

  • Burden, Richard L.; Faires, J. Douglas (1985), "2.1 The Bisection Algorithm", Numerical Analysis (terza edizione), PWS Publishers, ISBN 0-87150-857-5.

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica