Halveringsmetoden

Halveringsmetoden er ein enkel iterativ metode for å finna eit nullpunkt til ein funksjon, dvs. finna ei løysing på likninga f(x) = 0. For å bruka metoden må vi kjenna to punkt a og b som er slik at f(a) og f(b) har ulikt fortegn, og  funksjonen må vera kontinuerlig mellom på intervallet [a,b]. Vi startar med å finna midtpunktet m mellom a og b. Hvis  f(m) og f(a) har ulikt fortegn, så leitar vi vidare i intervallet [a,m]. Hvis ikkje fortset vi med intervallet [m,b]. Slik kan vi fortsetja heilt til vi er fornøyd med svaret.

Eksempel

Vi skal finna eit nullpunkt til funksjonen under og startar med verdiane a = 6 og b = 12. Vi finn då midtpunktet m = 9.

Vi ser av figuren at både f(6) og f(9) er negative. Derfor må vi leita vidare i intervallet [9,12]. Vi set no a = 9 og b = 12 og finn eit nytt midtpunkt mellom disse, m = 10.5

Denne gongen ser vi at f(9) er negativ, mens f(10.5) er positiv. Det vil sei at vi kan fortsetja å leita i intervallet [9,10.5]. Vi set altså a = 9 og b = 10.5 og finn det neste midtpunktet, m = 9.75 På denne måten kan vi fortsetja heilt til vi har komt så nær nullpunktet x = 10 som vi vil. Du kan prøva ut metoden her. Sjå også Python-eksempel.

Metoden vil alltid finna ei løysing som er nær nok. Hvis vi startar med heldige verdiar av (feks a = 8 og b = 12), så vil vi finna nullpunktet med ein gong. Men som regel konvergerer metoden seint.

Algoritme

Ein algoritme i pseudokode kan då sjå slik ut. Merk at vi testar om produktet mellom f(a) og f(b) er negativt. Det kan skje hvis f(a) er negativ og f(m) er positiv, ellers hvis f(a) er positiv og f(m) er negativ. Med andre ord: f(a) og f(m) har ulikt fortegn.

    Gitt funksjonen f, a og b.
        gjenta til a,b er nær nok nullpunktet
        	m ← (a + b)/2
			hvis f(m) = 0
				stopp
        	ellers hvis f(a)f(m) < 0
        		b ← m
        	ellers
        		a ← m
    

LENKER

Bisection method (Wikipedia)