Metodo della bisezione

metodo numerico più semplice per trovare le radici di una 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]

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

Descrizione modifica

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 uguali 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

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

È 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  .

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 la continuazione 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 come radice del polinomio.

Note modifica

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

Bibliografia modifica

  • 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

Altri progetti modifica

Collegamenti esterni modifica

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