Lähdekoodi sivulle Regula falsi -menetelmä

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

==Menetelmän kuvaus==

[[Image:False position method.svg|right|thumb|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''<sub>0</sub> ja ''b''<sub>0</sub> siten, että ''f''(''a''<sub>0</sub>) ja ''f''(''b''<sub>0</sub>) ovat erimerkkiset. Menetelmä etenee tuottaen jonon suppenevia välejä [''a''<sub>''k''</sub>, ''b''<sub>''k''</sub>] siten, että väli sisältää sellaisen arvon ''x'', että ''f''(''x'') = 0.

Iteraatiolla numero ''k'' lasketaan lukuarvo
:<math> c_k = \frac{f(b_k)a_k-f(a_k)b_k}{f(b_k)-f(a_k)} </math>. 
''c''<sub>''k''</sub> on pisteiden (''a''<sub>''k''</sub>, f(''a''<sub>''k''</sub>)) ja (''b''<sub>''k''</sub>, f(''b''<sub>''k''</sub>)) kautta kulkevan sekantin nollakohta. Jos f(''a''<sub>''k''</sub>) ja f(''c''<sub>''k''</sub>) ovat samanmerkkiset, valitaan ''a''<sub>''k''+1</sub> = ''c''<sub>''k''</sub> ja ''b''<sub>''k''+1</sub> = ''b''<sub>''k''</sub>, muutoin valitaan ''a''<sub>''k''+1</sub> = ''a''<sub>''k''</sub> ja ''b''<sub>''k''+1</sub> = ''c''<sub>''k''</sub>. Tätä prosessia toistetaan, kunnes juuri on saatu laskettua halutulla tarkkuudella.

Yllä olevaa kaavaa käytetään myös [[sekanttimenetelmä|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''<sub>''k''</sub> ja ''b''<sub>''k''</sub>, voidaan konstruoida pisteiden (''a''<sub>''k''</sub>, ''f''(''a''<sub>''k''</sub>)) ja(''b''<sub>''k''</sub>, ''f''(''b''<sub>''k''</sub>)) 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:

:<math> y - f(b_k) = \frac{f(b_k)-f(a_k)}{b_k-a_k} (x-b_k). </math>

Valitaan nyt arvoksi ''c''<sub>''k''</sub> tämän suoran nollakohta, jolloin ''c''<sub>''k''</sub> on valittu siten, että 

:<math> f(b_k) + \frac{f(b_k)-f(a_k)}{b_k-a_k} (c_k-b_k) = 0. </math>

Tämän yhtälön ratkaisuna saadaan ylempänä oleva yhtälö arvolle ''c''<sub>''k''</sub>.

==Analyysi==

Jos alkuperäiset päätepisteet
''a''<sub>0</sub> ja ''b''<sub>0</sub> on valittu siten, että  ''f''(''a''<sub>0</sub>) ja ''f''(''b''<sub>0</sub>) 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
:<math> f(x) = 2x^3-4x^2+3x </math>
jonka iteroinnin alkuarvoiksi valitaan
[&minus;1,1].  Vasen päätepiste, &minus;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

:<math> 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)}</math>
tai
:<math> 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)}</math>

Tällöin toista päätepisteistä on painotettu siten, että seuraava ''c''<sub>k</sub> 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. [[Fibonacci|Leonardo Pisalainen]] eli Fibonacci mainitsee arabilähteistä oppimansa menetelmän kirjassaan [[Liber Abaci]] vuonna 1202.

== Kirjallisuutta ==
* {{Kirjaviite | Tekijä=Kaleva, Osmo | Nimeke=Numeerinen analyysi | Selite=Opintomoniste 163 | Julkaisija=TTKK | Julkaisupaikka=Tampere | Vuosi=1993 | Tunniste = | Isbn = 951-721-941-5}}

== Aiheesta muualla ==
* J.A. Ford (1995), ''[http://citeseer.ist.psu.edu/67440.html 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)

[[Luokka:Algoritmit]]
[[Luokka:Numeerinen analyysi]]