Zadanie zostało opisane tak:
- Mamy funkcję \(f(x)\) ciągłą, monotoniczną i taką, że dla zadanych dwu punktów \(a\) i \(b\) \(f(a)\cdot f(b) < 0\) (funkcja zmienia znak w tym przedziale, a więc ma tam miejsce zerowe).
- Mamy znaleźć jej miejsce zerowe.
- 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.
- Znajdźmy środek przedziału \((a, b)\): \(c=(a+b)/2\).
- Jeżeli funkcja zmienia znak w przedziale \((a,c)\) — odrzucamy przedział \((c,b)\), w przeciwnym razie1 odrzucamy przedział \((a,c)\).
- 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:
|
1 2 3 4 5 6 7 |
int main(int argc, char **argv) { double A, B, C; A = 2.; B = 5.; delta = 0.00001; epsilon = 0.0001; |
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ń.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
pocz: C = ( A + B ) / 2.; if ( fabs( sin(C) ) < delta ) // czy wartość funkcji blisko zera? { printf("C=%.16f\n", C); return 0; } else if ( sin(A) * sin(C) > 0 ) A = C; else B = C; if ( fabs(A - B) > epsilon ) // czy przedział nie jest wystarczająco krótki? goto pocz; printf("!C=%.16f\n", ( A + B ) / 2.); return 0; } |
Właściwie nie ma o czym więcej pisać.
- Teoretycznie możliwe jest, że \(f(c)\) będzie równe zero; warto to uwzględnić, ale szanse są niewielkie.↩