Sovellus: Puolitusmenetelmä

91 days ago by Lauri_Ruotsalainen

Lauri Ruotsalainen, 2011
Sage-ohjelmisto matematiikan opetuksessa
 

 

Puolitusmenetelmä

Puolitusmenetelmä perustuu Bolzanon lauseeseen: jos suljetulla välillä jatkuvan funktion arvot välin päätepisteissä ovat erimerkkiset, funktiolla on tällä välillä (ainakin yksi) nollakohta. Puolitusmenetelmässä nollakohdan sijaintia tarkennetaan valitsemalla uuden välin yhdeksi päätepisteeksi aina tarkasteluvälin keskipiste. Toinen päätepiste valitaan siten, että funktion arvot välin päätepisteissä ovat jälleen erimerkkiset. Näin jatketaan, kunnes nollakohta on määritetty halutulla tarkkuudella.

Alla olevassa ohjelmassa puolitusmenetelmä on toteutettu Sagen avulla. Ennen algoritmin käyttöä tulee etsiä väli, jonka päätepisteissä funktiolla on erimerkkiset arvot. Sopiva väli voidaan löytää funktion kuvaajasta. Metodi \textsl{puolitusmenetelma} saa syötteenään funktion f ja välin päätepisteet a ja b. Muuttuja h merkitsee tarkkuutta, jolla nollakohta määrätään. Tarkkuus annetaan muodossa h=10^{-d}, missä d on käyttäjän valittavissa säätimellä. Algoritmin suoritus pysähtyy, kun funktion arvo on pienempi kuin annettu tarkkuus, eli f(c)<h, missä c on haarukoitu nollakohdan estimaatti. Metodi palauttaa pisteen c sekä listan algoritmin suorituksen aikana tutkituista väleistä.

Ohjelma esittää tarkastellut välit piirrettynä samaan kuvaan kuvaajan kanssa. Lisäksi ohjelma tulostaa ratkaistun nollakohdan c, funktion arvon tässä pisteessä sekä iterointikierrosten lukumäärän.

Kuva:
# Sovellus: Puolitusmenetelmä # Lauri Ruotsalainen, 2011 (perustuu sovellukseen "Root Finding Using Bisection" by William Stein) def puolitusmenetelma(f, a, b, h): f(x) = f intervallit = [(a, b)] while True: c = (a + b)/2.0 fa = f(a); fb = f(b); fc = f(c) if abs(fc) < h: break if fa*fc < 0: a, b = a, c elif fc*fb < 0: a, b = c, b else: # Nostaa virheen, jos päätepisteet ovat saman merkkisiä. raise ValueError, "Päätepisteiden tulee olla erimerkkisiä." intervallit.append((a, b)) return c, intervallit @interact def _(f = cos(x) - x, a = 0.0, b = 1.0, d = slider(1, 16, 1, 3) ): f(x) = f h = 10^(-d) # Kokeilee puolitusmenetelmän suorittamista. try: c, intervallit = puolitusmenetelma(f, float(a), float(b), float(h)) # Jos menetelmän suoritus epäonnistuu ValueError:n takia, tulostaa virheilmoituksen ja kuvaajan uuden välin määrittämiseksi. except ValueError: print "Päätepisteiden tulee olla erimerkkisiä." show(plot(f, a, b, color="red"), xmin=a, xmax=b) else: html("$\\text{Tarkkuus = }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) ) show(P + L, xmin=a, xmax=b) 
       

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