Sovellus: Sekanttimenetelmä

264 days ago by Lauri_Ruotsalainen

Sovellus: Sekanttimenetelmä

Lauri Ruotsalainen, 2011 (perustuu sovellukseen "Root Finding Using Bisection" by William Stein)

Sekanttimenetelmä perustuu lineaarisen interpolointiin. Menetelmässä tarkasteltavan välin puolittamisen sijaan piirretään viiva pisteiden (a,f(a)) ja (b,f(b)) kautta. Välin uudeksi päätepisteeksi valitaan suoran ja x-akselin leikkauskohta c. Leikkauspiste voidaan esittää välin päätepisteiden ja funktion arvojen avulla seuraavasti:

c=b-\frac{b-a}{f(b)-f(a)}\cdot f(b).

Toinen päätepiste voidaan valita siten, että uuden välin päätepisteet ovat erimerkkisiä, kuten puolitusmenetelmässä tehtiin. Toinen vaihtoehto, jota seuraavaksi esitettävä algoritmi käyttää, on ajatella välien päätepisteiden muodostavan jonon: kolme jonon ensimmäistä jäsentä ovat a, b ja c, jonka jälkeen seuraava piste d lasketaan välillä, jonka päätepisteet ovat kaksi edellistä pistettä b ja c. Näin jatketaan, kunnes nollakohta on saatu lasketuksi halutulla tarkkuudella.

Sekanttimenetelmä ei välttämättä löydä nollakohtaa tai sen tuottama ratkaisu voi olla alkuperäisen tarkasteluvälin ulkopuolella. Ikuisen silmukan välttämiseksi algoritmille annetaan syötteenä enimmäismäärä kierroksia (maxn), joiden jälkeen algoritmin suoritus viimeistään pysähtyy ja ohjelma palauttaa viimeksi lasketun pisteen. Jos käyttäjä valitsee parametrin maxn arvoksi nollan, ohjelma suorittaa algoritmia loputtomasti tai kunnes nollakohta löydetään halutulla tarkkuudella. Laskenta keskeytyy myös silloin, jos funktion arvot päätepisteissä ovat yhtä suuret, eli f(b)-f(a)=0. Ohjelma antaa virheilmoituksen nollalla jaettaessa.

Algoritmin toimintaa havainnollistetaan ohjelmassa piirtämällä interpolaatiosuoraa kuvaava jana jokaisen kierroksen jälkeen pisteiden (a,f(a)) ja (b,f(b)) välille. Kuvaajasta havaitaan, miten seuraavan välin päätepiste valitaan suoran ja x-akselin leikkauspisteen perusteella. Jos välin päätepisteet ovat samanmerkkisiä, janaa jatketaan suoran ja x-akselin leikkauspisteeseen asti.

Kuva:


 
def sekanttimenetelma(f, a, b, maxn, h): f(x) = f intervallit = [(a,b)] kierros = 1 while True: c = b-(b-a)*f(b)/(f(b)-f(a)) if abs(f(c)) < h or kierros == maxn: break a, b = b, c intervallit.append((a,b)) kierros += 1 return c, intervallit @interact def _(f = x^2 - 2, a = 0.0, b = 4.0, d = slider(1, 16, 1, 3), maxn = slider(0, 15, 1, 10, label="Kierroksia max")): f(x) = f h = 10^(-d) c, intervallit = sekanttimenetelma(f, float(a), float(b), maxn, h) html("$\\text{Tarkkuus h =} 10^{-d}=10^{-%s}=%s$"%(d, float(h))) html("$\\text{c = }%s$"%c) html("$\\text{f(c) = }%s"%f(c)) html("$\\text{Iteratioita = }%s"%len(intervallit)) # Piirretään algoritmin toimintaa kuvaava grafiikka. P = plot(f, a, b, color='red') k = (P.ymax() - P.ymin())/ (1.5*len(intervallit)) L = sum(line([(c,k*i), (d,k*i)]) for i, (c,d) in enumerate(intervallit) ) L += sum(line([(c,k*i-k/4), (c,k*i+k/4)]) for i, (c,d) in enumerate(intervallit) ) L += sum(line([(d,k*i-k/4), (d,k*i+k/4)]) for i, (c,d) in enumerate(intervallit) ) S = sum(line([(c, f(c)), (d, f(d)), (d-(d-c)*f(d)/(f(d)-f(c)), 0)], color="green") for (c, d) in intervallit) show(P + L + S, xmin=a, xmax=b) 
       

Click to the left again to hide and once more to show the dynamic interactive window