Metodo di bisezione

Da Wikiversità, l'apprendimento libero.
Jump to navigation Jump to search
lezione
Metodo di bisezione
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Analisi numerica

Analisi numerica > Metodo di bisezione


Il metodo di bisezione si basa sul teorema di esistenza degli zeri per una funzione continua, il quale garantisce l'esistenza di almeno una radice della funzione su un intervallo se e hanno segno opposto. Se su la funzione è anche monotona, ovvero se , allora lo zero della funzione è unico. Stabilita l'esistenza della soluzione, l'algoritmo definisce la successione come la successione dei punti medi degli intervalli di larghezza decrescente che soddisfano le ipotesi del teorema degli zeri. In pratica, dato un intervallo di partenza con all'interno una radice, si continua a dividere a metà gli intervalli finché l'ultimo è sufficientemente piccolo da assicurarci un buona approssimazione dello zero.

Teorema degli zeri[modifica]

L'enunciato del teorema di esistenza degli zeri per le funzioni continue (o Teorema di Bolzano) dice

Sia una funzione continua tale che

Allora esiste almeno un punto nell'intervallo aperto tale che .

La dimostrazione può essere trovata qui.

Algoritmo di bisezione[modifica]

Data che soddisfi le ipotesi del teorema degli zeri e data una tolleranza

  1. ;
  2. se esci;
  3. se esci;
    altrimenti se ;
    altrimenti ;
  4. torna al passo 1;

Nel primo passo viene definito il nuovo valore della successione: il nuovo punto medio. Nel secondo passo viene effettuato il controllo sulla tolleranza: se l'errore commesso è inferiore alla tolleranza prestabilita accettiamo come radice di . Il terzo passo consiste nel valutare la funzione in : se abbiamo trovato la soluzione; altrimenti, avendo diviso l'intervallo in due, dobbiamo capire da che parte è rimasto lo zero. Per fare ciò utilizziamo le ipotesi del teorema degli zeri, cerchiamo, cioè, il nuovo intervallo tale per cui la funzione agli estremi è di segno oppposto e ridefiniamo quindi l'intervallo, spostando o in . Infine, se non abbiamo ancora trovato una buona approssimazione per la soluzione, torniamo al punto di partenza.

Analisi di convergenza[modifica]

Ad ogni iterazione l'intervallo viene diviso a metà, dove abbiamo indicato con e gli estremi dell'intervallo alla iterazione . Ovviamente . Indichiamo con la lunghezza dell'intervallo . In particolare si ha

Si noti che , e quindi

.

Da questo si ha che , poiché . Quindi si ha

,

che dimostra la convergenza globale del metodo.

La convergenza del metodo di bisezione è molto lenta. Sebbene l'errore, in generale, non diminuisca in maniera monotona, la velocità media di convergenza è 1/2 e quindi, modificando leggermente la definizione di ordine di convergenza, è possibile dire che il metodo di bisezione converge linearmente con fattore di convergenza 1/2. Non crei confusione il fatto che, su alcuni testi o in altre fonti, talvolta, l'errore venga dato dalla relazione . Questo è dovuto al fatto che la successione viene definita per invece che per .

Esempio[modifica]

Si consideri la funzione in . In questo intervallo la funzione ha 3 zeri: , e .

Teoricamente il metodo di bisezione converge in un'iterazione a . Nella pratica, tuttavia, il metodo converge o o a . Infatti, dato che le operazioni vengono fatte in aritmetica finita, e a seconda delle approssimazioni del calcolatore potrà essere positivo o negativo, ma mai nullo. Così l'algoritmo di bisezione in questo caso escluderà automaticamente la radice alla prima iterazione, in quanto l'errore sarà ancora molto grande ().

Supponiamo che l'algoritmo converga a e vediamo quante iterazioni sono richieste affinché l'errore sia minore di . Bisogna quindi richiedere che

,

e quindi, risolvendo la disequazione, che

,

e quindi, poiché è un numero naturale, si ha .

Riferimenti[modifica]

  • Kendall E. Atkinson, chapter 2.1, in An Introduction To Numerical Analysis, 2nd, 1978, 1989.
  • Alfio Quarteroni, Sacco Riccardo e Fausto Saleri, chapter 6.2, in Numerical Mathematics, 2nd edition, 2007.
  • Endre Süli e David F. Mayers, chapter 1.6, in An introduction to numerical analysis, 1st edition, 2003.

Altre risorse sul metodo di bisezione[modifica]

Guarda la pagina altre risorse sulla risoluzione di equazioni non lineari.

Altri progetti