Regula falsi -menetelmä

Regula falsi -menetelmä on numeerisen analyysin algoritmi funktion nollakohdan löytämiseksi. Menetelmässä käytetään käyrän sekantteja uuden, edellistä tarkemman likiarvon löytämiseksi juurelle.

Menetelmän kuvaus

Regula falsi -menetelmän kaksi ensimmäistä iteraatiota. Punainen käyrä on funktio f ja siniset suorat ovat sekantteja.

Regula falsi -menetelmä aloitetaan valitsemalla kaksi pistettä a₀ ja b₀ siten, että f(a₀) ja f(b₀) ovat erimerkkiset. Menetelmä etenee tuottaen jonon suppenevia välejä [a_k, b_k] siten, että väli sisältää sellaisen arvon x, että f(x) = 0.

Iteraatiolla numero k lasketaan lukuarvo

$c_{k}={\frac {f(b_{k})a_{k}-f(a_{k})b_{k}}{f(b_{k})-f(a_{k})}}$.

c_k on pisteiden (a_k, f(a_k)) ja (b_k, f(b_k)) kautta kulkevan sekantin nollakohta. Jos f(a_k) ja f(c_k) ovat samanmerkkiset, valitaan a_k+1 = c_k ja b_k+1 = b_k, muutoin valitaan a_k+1 = a_k ja b_k+1 = c_k. Tätä prosessia toistetaan, kunnes juuri on saatu laskettua halutulla tarkkuudella.

Yllä olevaa kaavaa käytetään myös sekanttimenetelmässä, mutta sekanttimenetelmässä seuraava arvo lasketaan aina kahden viimeksi lasketun pisteen avulla. Regula falsi -menetelmässä taas käytetään viimeksi lasketun pisteen parina edellistä sellaista pistettä, jossa funktion arvo oli erimerkkinen.

Sekantin nollakohdan löytäminen

Kun tunnetaan a_k ja b_k, voidaan konstruoida pisteiden (a_k, f(a_k)) ja(b_k, f(b_k)) kautta kulkeva suora, kuten yllä olevasta kuvasta nähdään. Huomaa, että tämä suora on funktion f sekantti. Sen yhtälö voidaan laskea seuraavasti:

$y-f(b_{k})={\frac {f(b_{k})-f(a_{k})}{b_{k}-a_{k}}}(x-b_{k}).$

Valitaan nyt arvoksi c_k tämän suoran nollakohta, jolloin c_k on valittu siten, että

$f(b_{k})+{\frac {f(b_{k})-f(a_{k})}{b_{k}-a_{k}}}(c_{k}-b_{k})=0.$

Tämän yhtälön ratkaisuna saadaan ylempänä oleva yhtälö arvolle c_k.

Analyysi

Jos alkuperäiset päätepisteet a₀ ja b₀ on valittu siten, että f(a₀) ja f(b₀) ovat erimerkkiset, toinen päätepisteistä suppenee iterointia jatkettaessa kohti funktion f nollakohtaa. Vastaavasti toinen päätepiste pysyy samana kaikille iteraatioille. Seurauksena päätepisteiden välimatka ei suppene kohti nollaa. Tästä taas seuraa, että funktion f(x) lineaarinen approksimaatio ei muutu paremmaksi.

Esimerkkinä tästä ilmiöstä mainittakoon funktio

$f(x)=2x^{3}-4x^{2}+3x$

jonka iteroinnin alkuarvoiksi valitaan [−1,1]. Vasen päätepiste, −1, ei koskaan korvaudu ja näin ollen välin pituus ei koskaan mene ykköstä pienemmäksi (koska funktion nollakohta on nolla). Näin ollen oikea päätepiste lähestyy nollaa.

Jos regula falsi -menetelmä ei tuo ratkaisua juurelle (eli sama päätepiste saadaan kahdesti peräkkäin), voidaan ongelma kiertää muuntamalla menetelmää painokertoimin. Valitaan esimerkiksi

$c_{k}={\frac {{\frac {1}{2}}f(b_{k})a_{k}-f(a_{k})b_{k}}{{\frac {1}{2}}f(b_{k})-f(a_{k})}}$

tai

$c_{k}={\frac {f(b_{k})a_{k}-{\frac {1}{2}}f(a_{k})b_{k}}{f(b_{k})-{\frac {1}{2}}f(a_{k})}}$

Tällöin toista päätepisteistä on painotettu siten, että seuraava c_k saadaan kyseisellä puolella funktiota. Lisäetuna saavutetaan suurempi suppenemisnopeus.

Historia

Vanhimmat dokumentit alkeellisen Regula falsi -menetelmän käytöstä löytyvät intialaisesta matemaattisesta tekstistä Vaishali Ganit noin kolmannelta vuosisadalta ennen ajanlaskun alkua. Vanha kiinalainen teksti The Nine Chapters on the Mathematical Art (九章算術) vuosien 200 eaa. - 100 jaa. mainitsee myös menetelmän. Tässä yhteydessä esimerkit soveltavat menetelmää kuitenkin vain lineaarisiin yhtälöihin, joten ratkaisu saadaan jo ensimmäisellä askeleella. Leonardo Pisalainen eli Fibonacci mainitsee arabilähteistä oppimansa menetelmän kirjassaan Liber Abaci vuonna 1202.

Kirjallisuutta

• Kaleva, Osmo: Numeerinen analyysi. (Opintomoniste 163) Tampere: TTKK, 1993. ISBN 951-721-941-5

Aiheesta muualla

• J.A. Ford (1995), Improved Algorithms of Illinois-type for the Numerical Solution of Nonlinear Equations, Technical Report CSM-257, University of Essex, 1995 (englanniksi)
• Richard L. Burden, J. Douglas Faires (2000), "Numerical Analysis, (7th Ed)", Brooks/Cole. ISBN 0-534-38216-9 (englanniksi)
• L.E. Sigler, Fibonacci's Liber Abaci, Leonardo Pisno's Book of Calculation (2002), Springer-Verlag, New York, ISBN 0-387-40737-5. (englanniksi)