Calcolo di zeri con il metodo di bisezione

Dal  Teorema di Weierstrass (se f: [a, b]->R è continua su [a, b], essa è dotata di massimo e di minimo) si può dedurre il Lemma "Una funzione continua su un intervallo non può passare da valori negativi a valori positivi senza annullarsi almeno in un punto" (si dimostra per assurdo considerando la funzione 1/f(x)).
Questo lemma viene impiegato costruttivamente considerando intervalli via via più piccoli (ognuno lungo la metà del precedente) e fermandosi o alla determinazione dello zero o al raggiungimento della precisione richiesta.

Ad esempio nella figura si considerano gli intervalli [a0, b0],  [a1=a0, b1], [a2, b2=b1], [a3, b3=b2=b1] e fermandosi in quanto b3-a3 ha raggiunto la precisione richiesta.
Quindi il valor medio c tra a3 e b3 approssima lo zero esatto per meno della metà della precisione.

E' possibile fare delle prove qui di seguito:

Automatizzando la ricerca si può costruire un programma con il seguente input ed output:

Il programma è innanzitutto una implementazione di un algoritmo in uno specifico linguaggio di programmazione.

Algoritmo

L'algoritmo di bisezione che segue è realizzato tramite un ciclo controllato dopo l'esecuzione dei calcoli ("ripeti") anziché prima ("mentre") e si ferma dopo un numero prefissato di iterazioni (da: Barozzi, G.,C., Corso di Analisi matematica, Cap. 6, Zanichelli,1989); altre informazioni in Pascal, Derive, Teoria .

0.	A <- a, B <- b, KMAX <- kmax
1.	K <- 0
2.	ripetere
|		M <- (A + B)/2
|		K <- K +1
|		se f(M) =/= 0, allora
|			se f(A)*f(M) < 0,
|			allora B <- M
|			altrimenti: A <- M
|_	fino a quando f(M) = 0, oppure K = KMAX

3.	stampare M, f(M), K
4.	fine

Programma Javascript (realizzato con while)

Qui sotto si vede il modo in cui l'algoritmo è stato implementato utilizzando Javascript. Si è preferito controllare il ciclo prima della sua esecuzione: ciò rende necessaria qualche ripetizione ma qualcuno lo preferisce perché permette di non effettuare le istruzioni del ciclo se la soluzione è già trovata (è una questione di stile).

Le variabili di ingresso sono scritte in un modulo dati in celle di input a, b, e. Anche la funzione è scritta in una cella di ingresso (dati.f) e verrà ricalcolata (eval) di volta in volta.

Ricordiamo che in Javascript - come in diversi linguaggi basati su oggetti - alla cella di ingresso è associato una valore (value) ma anche un nome ecc. Quindi se della cella a si vuole il valore si dovrà scrivere dati.a.value .

<SCRIPT language=JavaScript> function f(x){return eval(dati.f.value)}; function calcola(){ //Variabili locali// var an,bn,c,err; //Inizializzazione delle variabili// an=new Number(dati.a.value); bn=new Number(dati.b.value); c=new Number((bn+an)/2); err= new Number(dati.e.value); msg=new String(""); /*bisezione il ciclo continua quando lo zero non è trovato e quando lo zero non è identificato con sufficiente precisione*/ while ((f(c) != 0) && ((bn-an) > err)) {msg=msg+an+" < "+c+" < "+bn+"\n"; // in msg accumulo l'output if ((f(c)*f(an))<0) {bn=c} else {an=c}; c=(bn+an)/2;}; //operazioni di scrittura msg=msg+an+" < "+c+" < "+bn+"\n"; // in msg accumulo l'output msg="Valore stimato: "+c+"\n\n"+msg; dati.report.value=msg; // visualizzo l'output }; </SCRIPT>

Per ottenere una copia gratuita di Borland Turbo pascal 5.5 si veda: Borland Museum Il seguente programma è tratto dal sito del Prof. S. Berardi in un testo RTF (cercare : "bisezione").

Program bisezione; var iniziale, finale, precisione:real; {Scrivere tale procedimento sotto forma di funzione Zero(a,b,epsilon).} {inserendo f(x) come sottofunzione di Zero. Scegliere f(x)=x2 + x -1, a=0, b=1} {e trovare uno "zero" di f in [a,b].} function Zeri (a, b, epsilon : Real) : Real; {| Precond..: a<b, epsilon>0, f continua su [a,b], segno f(a) =/= segno f(b) |} function f (x : Real) : Real; begin f := x * x + x - 1; end; var m : Real; begin m := (a + b) / 2; {| segno f(a) =/= segno f(b) |} while (b - a) >= epsilon do begin if f(a) * f(m) <= 0 then {| segno f(a) =/= segno f(m) |} b := m else {| segno f(m) =/= segno f(b) |} a := m; m := (a + b) / 2; end; {| (b-a) < epsilon, segno f(a) =/= segno f(b) |} zeri := m; {| Postc. : distanza tra valore di ritorno e uno "zero" di f < (b-a) < epsilon |} end; begin writeln('funzione x^2 + x - 1'); writeln('scrivi gli estremi iniziale e finale e la precisione richiesta separati da spazi'); readln(iniziale,finale,precisione); writeln(Zeri(iniziale,finale,precisione)); readln end.