Formalne przedstawienie problemu

Metoda połowienia podziału (inaczej bisekcji) pozwala znaleźć miejsce zerowe funkcji w przedziale. Opiera się ona na twierdzeniu Bolzano-Cauchy’ego:

Jeżeli funkcja ciągła f(x) ma na końcach przedziału domkniętego wartości różnych znaków, to wewnątrz tego przedziału, istnieje co najmniej jeden pierwiastek równania f(x)=0

Dane wejściowe:

• wzór funkcji f(x) ciągłej w przedziale domkniętym [a,b]

• a,b - krańce przedziału domkniętego (funkcja przyjmuje różne znaki na krańcach przedziału)

Oczekiwany wynik:

• Pierwiastek równania f(x)=0 w przedziale domkniętym [a,b]

Rozwiązanie:

• Wyznaczamy punkt x=(a+b)/2 czyli środek przedziału a,b

• Sprawdzamy, czy jest on pierwiastkiem równania, czyli sprawdzamy czy f(x)=0. Jeżeli tak jest algorytm kończy działanie, a punkt x jest szukanym miejscem zerowym.

• W przeciwnym razie, dopóki nie osiągniemy żądanej dokładności, czyli dopóki szerokość przedziału jest większa od obranej dokładności e

• Ponownie wyznaczamy środek przedziału x, dzielący przedział [a, b] na dwa mniejsze przedziały: [a, x] i [x,b]

• Spośród wymienionych dwóch, wybierany jest przedział w którym funkcja osiąga różne znaki na krańcach, czyli

  • Jeżeli f(x)*f(a) < 0 to b = x

  • Jeżeli f(x)*f(b) < 0 to a = x

• Po osiągnięciu żądanej dokładności algorytm kończy działanie, a szukany pierwiastek równania wynosi (a+b)/2

Pseudokod