Bisekcja: Wyznaczanie miejsc zerowych

Wprowadzenie

Wyznaczanie miejsc zerowych funkcji może być pomocne np. przy rozwiązywaniu równań kwadratowych lub innych wielomianów. Jednorazowe uruchomienie metody bisekcji (połowienia przedziałów) może posłużyć do wyznaczenia jednego miejsca zerowego (i tylko jednego) danej funkcji. Zastosowanie tej metody nie gwarantuje jednak wyszukania jakiegokolwiek miejsca zerowego (pomimo tego, że takie występują). Taka sytuacja może mieć miejsce gdy wybierzemy x0 , x1 tak, że dla obu tych punktów wartość funkcji będzie miała ten sam znak.

Dokładność tej funkcji zależy tylko i wyłącznie od ilości wykonanych iteracji - im więcej ich wykonamy (połowień przedziałów) tym dokładniejszy wynik uzyskamy.
Jedną z zalet tej metody jest błąd maksymalny, którym obarczony jest wynik - nigdy nie przekroczy on połowy odległości między badanymi punktami. Na przykład przy badaniu funkcji w przedziale 4-8 przy jednej iteracji maksymalnym błędem będzie 2. Podzielimy bowiem przedział ten na 4-6-8 i przesuniemy jeden z punktów na połowę przedziału, czyli do wartości 6. Jako dodatkową zaletę tej metody można podać, że jest ona zawsze zbieżna.

Wzory

Warunkiem wystarczającym do zaistnienia miejsca zerowego w danym przedziale jest równanie:

1) f(x1) * f(x2) < 0 *gdzie x1 i x2 są granicami przedziałów, w których badamy funkcję)

Wadą tego warunku jest to, że nie jest to warunek konieczny, a zatem nawet w przypadku nie spełnienia tego warunku może okazać się, że w danym przedziale istnieją miejsca zerowe. Wykres działania metody bisekcji dla wzoru: "y = x^2 - 5x -6" oraz danych: a=-3.0 b=3.0 i liczbie iteracji 6: otrzymujemy przedział: (-1.03125, -0.9375)

Kod programu (python w wersji 2.x, najlepiej 2.6):

#!/usr/bin/python
# -*- coding: utf-8 -*-

import math

class Function(object):
 def __init__(self):
  pass
  
 def count(self,x):
  print "Wywolanie z %d" %(x)
  result = math.pow(x,2) + 5*x + 6
  print result
  return result

 def c(self,x):
  return self.count(x)


class Bisection(object):
 def __init__(self,function, a=None, b=None,prec=None):
  self.f = function
  self.a = a
  self.b = b
  self.prec = prec

 def setParameters(self, a, b, prec):
  self.a = a
  self.b = b
  self.prec = prec


 def count(self):
  if((self.a>self.b) or 
     (self.f.c(self.a)*self.f.c(self.b) > 0) or 
     (self.a==None or self.b==None)):
   return
  i = 0
  x1 = float(self.a)
  x2 = float(self.b)
  mediumX = (x1+x2)/2
  print "medium: %d" %(mediumX)
  while(i<self.prec):
   print "hello"
   i += 1
   mediumX = (x1+x2)/2
   print "medium: %d" %(mediumX)
   if(self.f.c(x0)>0):
    if(self.f.c(x1)>0):
     x1=mediumX
    if(self.f.c(x2)>0):
     x2=mediumX
   else:
    if(self.f.c(x1)<0):
     x1=mediumX
    if(self.f.c(x2)<0):
     x2=mediumX
  return (x1,x2,)


function  = Function()
bisection = Bisection(function, 5.0, 7.0, 20100)
print bisection.count()

Schemat blokowy pracy takiego algorytmu przedstawia się następująco:

Artykuł udostępniany na licencji CC-BY-SA-3.0