2.1 Algoritmul de bisecție
Algoritmul de bisecție este o metodă simplă de găsire a rădăcinilor unor funcții unidimensionale. Scopul este de a găsi o rădăcină \(x_0\in\) astfel încât \(f(x_0)=0\). Algoritmul începe cu un interval mare, despre care se știe că conține \(x_0\), și apoi reduce succesiv dimensiunea intervalului până când se pune între paranteze rădăcina. Fundamentul teoretic al algoritmului este teorema valorii intermediare, care afirmă că, dacă o funcție continuă \(f\) ia valorile \(f(a)\) și \(f(b)\) la punctele finale ale intervalului \(\), atunci \(f\) trebuie să ia toate valorile cuprinse între \(f(a)\) și \(f(b)\) undeva în interval. Deci, dacă \(f(a) < \gamma < f(b)\), atunci există un \(c\in\) astfel încât \(f(c)=\gamma\).
Utilizând aceste informații, putem prezenta algoritmul de bisecție. Mai întâi trebuie să verificăm că \(\text{sign}(f(a)) \ne \text{sign}(f(b))\). În caz contrar, intervalul nu conține rădăcina și ar putea fi necesar să fie lărgit. Atunci putem continua:
-
Lasă \(c = \frac{a + b}{2}\).
-
Dacă \(f(c) = 0\), opriți-vă și returnați \(c\).
-
Dacă \(\text{semn}(f(a))\ne\text{semn}(f(c))\), atunci se setează \(b\fară stângă c\). În caz contrar, dacă \(\text{sign}(f(b))\ne\text{sign}(f(c))\), atunci setați \(a\leftarrow c\).
-
Se trece la început și se repetă până la convergență (vezi mai jos).
După \(n\) iterații, dimensiunea intervalului care cuprinde rădăcina va fi \(2^{-n}(b-a)\).
Argitmul de bisecție este util, simplu din punct de vedere conceptual și ușor de implementat. În special, nu aveți nevoie de nicio informație specială despre funcția \(f\), cu excepția capacității de a o evalua în diferite puncte din interval. Dezavantajele sale sunt că este util doar într-o singură dimensiune și convergența sa este liniară, care este cea mai lentă rată de convergență pentru algoritmii pe care îi vom discuta (mai multe despre aceasta mai târziu).
Argitmul bisecției poate întâmpina probleme în situațiile în care funcția \(f\) nu se comportă bine. Situația ideală pentru algoritmul de bisecție arată cam așa.
Configurație ideală pentru algoritmul de bisecție.
Aici, \(f(a)\) și \(f(b)\) sunt de semne opuse și rădăcina se află clar între \(a\) și \(b\).
În scenariul de mai jos, algoritmul nu va porni pentru că \(f(a)>0\) și \(f(b)>0\).
Derivata lui \(f\) la rădăcină este \(0\).
În acest scenariu următor, există două rădăcini între \(a\) și \(b\), pe lângă faptul că avem \(f(a)>0\) și \(f(b)>0\). Ar trebui să se reducă lungimea intervalului de pornire pentru a găsi oricare dintre rădăcini.
Două rădăcini în interiorul intervalului.
În scenariul de mai jos, algoritmul va porni pentru că \(f(a)\) și \(f(b)\) sunt de semn opus, dar nu există o rădăcină.
Intervalul conține o asimptotă, dar nu există rădăcină.
Convergența algoritmului de bisecție poate fi determinată fie având \(|b-a|<\varepsilon\) pentru un anumit \(\varepsilon\) mic, fie având \(|f(b)-f(a)|<\varepsilon\). Criteriul pe care îl veți utiliza va depinde de aplicația specifică și de tipurile de toleranțe necesare.
2.1.1 Exemplu: Cuantile
Dată o funcție de repartiție cumulativă \(F(x)\) și un număr \(p\în (0, 1)\), un cuantile al \(F\) este un număr \(x\) astfel încât \(F(x) = p\). Algoritmul de bisecție poate fi utilizat pentru a găsi un cuantile \(x\) pentru un anumit \(p\) prin definirea funcției \(g(x) = F(x) – p\) și rezolvarea pentru valoarea lui \(x\) care obține \(g(x) = 0\).
O altă modalitate de a spune acest lucru este că inversăm CDF pentru a calcula \(x = F^{-1}(p)\). Deci algoritmul de bisecție poate fi folosit pentru a inversa funcții în aceste situații.
.