2.1 Bisection Algorithm
Bisection Algorithm on yksinkertainen menetelmä yksiulotteisten funktioiden juurien löytämiseksi. Tavoitteena on löytää sellainen juuri \(x_0\in\), että \(f(x_0)=0\). Algoritmi lähtee liikkeelle suuresta intervallista, jonka tiedetään sisältävän \(x_0\), ja pienentää sitten intervallia asteittain, kunnes se sulkee juuren. Algoritmin teoreettinen perusta on väliarvoteoria, jonka mukaan jos jatkuva funktio \(f\) ottaa arvot \(f(a)\) ja \(f(b)\) intervallien \(\) päätepisteissä, \(f\):n on otettava kaikki arvot väliltä \(f(a)\) ja \(f(b)\) jossakin päin intervallia. Jos siis \(f(a) < \gamma < f(b)\), niin on olemassa \(c\in\) siten, että \(f(c)=\gamma\).
Näiden tietojen avulla voimme esittää puolitusalgoritmin. Ensin on tarkistettava, että \(\text{sign}(f(a)) \ne \text{sign}(f(b))\). Muussa tapauksessa väli ei sisällä juurta ja sitä on ehkä laajennettava. Silloin voidaan jatkaa:
-
Jos \(c = \frac{a + b}{2}\).
-
Jos \(f(c) = 0\), lopetetaan ja palautetaan \(c\).
-
Jos \(\teksti{merkki}(f(a))\ne\teksti{merkki}(f(c))\), aseta \(b\vasenuoli c\). Else jos \(\text{sign}(f(b))\ne\text{sign}(f(c))\), niin aseta \(a\leftarrow c\).
-
Vaihda alkuun ja toista kunnes konvergenssi on saavutettu (ks. alla).
Iteraatioiden \(n\) jälkeen juurta sulkevan intervallin koko on \(2^{-n}(b-a)\).
Puolistamisalgoritmi on käyttökelpoinen, käsitteellisesti yksinkertainen ja helppo toteuttaa. Et erityisesti tarvitse mitään erityistä tietoa funktiosta \(f\) paitsi kykyä arvioida se eri kohdissa intervallia. Huonoja puolia ovat, että se on käyttökelpoinen vain yhdessä ulottuvuudessa ja sen konvergenssi on lineaarinen, mikä on hitain konvergenssinopeus käsittelemissämme algoritmeissa (tästä lisää myöhemmin).
Puolistamisalgoritmi voi törmätä ongelmiin tilanteissa, joissa funktio \(f\) ei käyttäydy hyvin. Ihanteellinen tilanne bisection-algoritmille näyttää jotakuinkin tältä.
Ideaalinen asetelma bisection-algoritmille.
Tässä \(f(a)\) ja \(f(b)\) ovat vastakkaisia merkkejä, ja juuri on selvästi \(a\) ja \(b\) välissä.
Algoritmi ei käynnisty alla olevassa skenaariossa, koska \(f(a)>0\) ja \(f(b)>0\) ovat \(f(a)>0\).
Juuren \(f\) derivaatta \(f\) on \(0\).
Tässä seuraavassa skenaariossa on kaksi juurta \(a\) ja \(b\) välissä sen lisäksi, että \(f(a)>0\) ja \(f(b)>0\). Aloitusväliä pitäisi lyhentää, jotta jompikumpi juuri löytyisi.
Kaksi juurta välin sisällä.
Algoritmi käynnistyy alla olevassa skenaariossa, koska \(f(a)\) ja \(f(b)\) ovat vastakkaisen merkin omaavia, mutta juurta ei ole.
Intervalli sisältää asymptootin, mutta ei juurta.
Puolistamisalgoritmin konvergenssi voidaan määrittää joko siten, että \(|b-a|<\varepsilon\) on jollakin pienellä \(\varepsilon\)-arvolla, tai siten, että \(\(|f(b)-f(a)|<\varepsilon\)-arvolla. Se, mitä kriteeriä käytetään, riippuu sovelluskohteesta ja siitä, millaisia toleransseja vaaditaan.
2.1.1 Esimerkki: Kumulatiivinen jakaumafunktio \(F(x)\) ja luku \(p\in (0, 1)\), \(F\):n kvanttiili on sellainen luku \(x\), että \(F(x) = p\). Bisection-algoritmia voidaan käyttää kvantiilin \(x\) löytämiseen tietylle \(p\):lle määrittelemällä funktio \(g(x) = F(x) – p\) ja ratkaisemalla \(x\):n arvo, jolla saavutetaan \(g(x) = 0\).
Toinen tapa ilmaista tämä on se, että invertoimme CDF:n laskeaksemme \(x = F^{-1}(p)\). Bisection-algoritmia voidaan siis käyttää funktioiden invertointiin näissä tilanteissa.