Metoda połowienia dla bystrzaków

Zadanie zostało opisane tak:

  1. Mamy funkcję \(f(x)\) ciągłą, monotoniczną i taką, że dla zadanych dwu punktów \(a\)\(b\) \(f(a)\cdot f(b) < 0\) (funkcja zmienia znak w tym przedziale, a więc ma tam miejsce zerowe).
  2. Mamy znaleźć jej miejsce zerowe.
  3. Nie potrafimy analitycznie rozwiązać równanie \(f(x)=0\).

Proponuję iteracyjną metodę szukania punktu najbliższego rozwiązaniu tego równania metodą połowienia.

  1. Znajdźmy środek przedziału \((a, b)\): \(c=(a+b)/2\).
  2. Jeżeli funkcja zmienia znak w przedziale \((a,c)\) — odrzucamy przedział \((c,b)\), w przeciwnym razie1 odrzucamy przedział \((a,c)\).
  3. Powyższą procedurę powtarzamy tak długo, aż długość przedziału \((a,b)\) będzie krótsza niż zadana wartość \(\varepsilon\), lub gdy wartość funkcji \(f(c)\) będzie bliska zeru (\(|f(c)|<\delta\)).

Dalsze założenia

Do dalszych obliczeń wybierzemy funkcję, której miejsca zerowego będziemy szukali. Będzie to funkcja \(\sin(x)\). Z formalnego punktu widzenia nie spełnia ona założeń (jest okresowa), ale jeżeli ograniczymy rozważania do przedziału \((2,5)\) wszystko powinno być dobrze. Oprócz tego znamy dokłądną wartość miejsca zerowego: jest nią \(\pi\).

Kompletny program może wyglądać tak:

 

delta to stała definiująca dostateczną „bliskość” \(f(c)\) od zera pozwalająca przerwać obliczenia, a epislon to stałą określająca graniczną długość przedziału poszukiwań.

 

Właściwie nie ma o czym więcej pisać.


  1. Teoretycznie możliwe jest, że \(f(c)\) będzie równe zero; warto to uwzględnić, ale szanse są niewielkie.