Bisekcja z dokładnością do 0.0001 Kuba: Cześć. Mam wyznaczyć ile iteracji potrzebnych jest do uzyskania zadanej dokładności dla metody bisekcji. Dokładne miejsce zerowe mojej funkcji to 0.38333234 Mój epsilon to 0.0001 Ze wzoru wyznaczam ilość potrzebnych iteracji: ln((b−a)/0.0001) = 12.425 w górę to 13. Dla 13 iteracji wychodzi mi wynik: 0.3833557. Niby okej zaokrąglam wszystko jak leci do 4 miejsca po przecinku i 0.3833=0.3833. Problem jest że dla 12 iteracji wychodzi 0.38328857 co po zaokrągleniu w górę do 4 miejsca również daje 0.3833 Dla 11 iteracji już sie nie zgadza. Gdzie popełniam błąd?
3 cze 13:47
Pytający: https://en.wikipedia.org/wiki/Bisection_method#Iteration_tasks Policz |a − wynik| odpowiednio dla 12 i 13 iteracji.
3 cze 14:15
Pytający: I w podanym przez Ciebie wzorze powinien być logarytm o podstawie 2 (a nie naturalny).
3 cze 14:20
Kuba: Dla 12 iteracji: 0,00004377376231207153 Dla 13 iteracji: 0.00002336490956289516
3 cze 14:24
Pytający: A dobrze liczysz iteracje? Po 1 iteracji Twój wynik to (a+b)/2? Najprościej jakbyś podał a, b i funkcję.
3 cze 14:29
Kuba: Jeszcze jedno proste pytanie które może rozwiąże mój problem. Dokładność do 4 miejsc po przecinku to 0.0001 czy 0.00001
3 cze 14:35
Pytający: Wynik 0.1 otrzymany z dokładnością do 1 miejsca po przecinku oznacza, że dokładny wynik należy do przedziału <0.05, 0.15). Czyli ε ≤ 0.1 / 2 = 0.05 Dla dokładności do 4 miejsc po przecinku ε ≤ 0.0001 / 2 = 0.00005.
3 cze 14:49
Kuba: Dzięki wielkie. Teraz wszystko się zgadza. Miałem błąd w octave dla swojej funkcji Z tym że nie rozumiem za bardzo dlaczego dla 4 miejsc po przecinku daje eps =0.0001/2 i jako warunek stopu b−a<eps. Zdawało mi się zawsze że samo 0.0001 powinno byc hmpf
3 cze 14:57
Pytający: Zależy, czym u Ciebie jest epsilon: • jeśli epsilon to zadana dokładność (przykładowo 0.0001 dla 4 miejsc po przecinku (kropce)), wtedy jako warunek stopu chcesz mieć albo b−a≤eps, albo c−a≤eps/2, • jeśli epsilon oznacza maksymalny dopuszczalny błąd (przykładowo 0.00005 dla dokładności do 4 miejsc po przecinku (kropce)), wtedy jako warunek stopu chcesz mieć c−a≤eps. // c=(a+b)/2 Znaczy po mojemu wciąż coś u Ciebie nie gra...
3 cze 15:33
jc: Jaki masz przedział?
3 cze 15:57
Kuba: To moj epsilon to ten 1 warunek. Czyli b−a<0.0001. Teraz juz wszystko wychodzi bo w swoim wzorze funkcji zamiast ln dalem log2.
3 cze 16:28
jc: Dla 13 iteracji przedział zmniejsza się trochę ponad 8000 razy bo 210=1024. Jeśli na początku masz przedział długość 80, to będziesz miał dokładność 0.01.
3 cze 16:32
Kuba: Na początku mam przedział dł 0.55
3 cze 17:26
jc: 12 to za mało, 13 wystarczy. Do szybkiego oszacowania dobrze wiedzieć, że 210 to nieco ponad 1000.
3 cze 19:55
Kuba: Wyszlo mi 12 z hakiem czyli 13
3 cze 20:07
Kuba: Jednak dalej się nie zgadza po ponownym sprawdzeniu. Funkcja to x+ln(2x), a przedział to a = 0.2 b=0.75. ln((b−a)/0.0001) = 12.425. Wynik dokładny to: 0.3517337112491953 Wynik dla 13 iteracji to: 0.3518005371093751 Wynik dla 14 iteracji to: 0.3517669677734376 Wynik dla 16 iteracji to: 0.3517417907714844 Więc jak widać przy zaokrągleniach dopiero 16 iteracja się zgadza. Już zgłupiałem.
3 cze 21:23
Kuba: Znalazłem jeszcze z wykładu wzór n = log2(2*10k * (b−a) zaokrąglone w górę. Dla niego wychodzi 14 iteracji. Jeżeli patrzeć by tylko na zgodność miejsc po przecinku to w zasadzie się zgadza.
3 cze 21:28
jc: 13 iteracja daje dokładność lepszą niż 1/10000. 0.351733398438 0.35180053710 różnica = 0.00006713867 < 0.0001
3 cze 21:50
Kuba: No to już za bardzo nie wiem teraz czy mam patrzeć na zgodność cyfry po przecinku i zgodnie ze wzorem ze wykładów wziąc 14 iteracje. Czy skorzystać ze wzoru z wikipedii i patrzeć na różnice
3 cze 22:08
jc: Dokładny wynik 0.351733711. Masz przedział długości 0.55. Po po 13 krokach masz przedział o długości 0.55/213 < 0.001 * 0.55/8 < 0.001 * 0.1 = 0.0001.
3 cze 22:16
Kuba: Z wykładów mam taki warunek Eps <= 1/2 * 10−k Z czego eps = wartosc dokladna − wartosc przyblizona Eps dla k = 4 to 0.3517337112491953−0.3517 = 0.00003371124919526736 0.00003<1/2 * 10−4 0.00003<0.00005 Wartość 14 iteracji − Wartość dokladnia ~ 0.0003 Więc 0.0003 < 0.00005 Wartość 13 iteracji − wartosc dokladna ~ 0.00007 0.00007 > 0.00005 Więc się nie zgadza. Czyli 14 iteracja to mimo wszystko ta poprawna?
3 cze 22:18
Pytający: Jeśli jednak chcemy mieć dokładność do 4 miejsc po przecinku, maksymalny dopuszczalny błąd to 0.00005, o czym już wyżej wspomniałem. I wtedy potrzeba co najmniej
 0.75−0.2 
log2(

) iteracji, czyli 14 iteracji.
 0.00005 
https://www.wolframalpha.com/input/?i=(ln(0.75-0.2)-ln(0.00005))%2Fln(2) I faktycznie dopiero po 14 iteracjach mamy pewność, że ów błąd nie przekracza 0.00005 (dopiero wtedy b−a≤0.0001): https://ideone.com/7o3Dz3 Generalnie niewykluczone, że w którejś z wcześniejszych iteracji otrzymasz przybliżenie (aktualny środek przedziału) obarczone mniejszym błędem niż dopuszczalny, ale wtedy jeszcze nie masz pewności, że błąd jest tak mały, jak tego oczekujesz.... do tego zwyczajnie potrzeba x iteracji.
3 cze 22:19
jc: Z jaką dokładnością znasz x, jeśli wiesz, że x∊[3, 4]. Wg mnie z 1, bo największy błąd to 1, wg Ciebie to 2. Dlaczego?
3 cze 22:24
Pytający: Sęk w tym, że algorytm nie zna dokładnej wartości, więc ta wartość ma się nijak do zapewnianej przez ów algorytm dokładności. Maksymalny możliwy błąd zależy jedynie od tego, jak duży przedział pozostał do rozpatrzenia (a to z kolei zależy od aktualnej iteracji).
3 cze 22:24
jc: Chyba rozumiem, o co chodzi, jeśli podasz 3, to wynik wynosi 4, to 2 też by niby pasowało, ale odległość 2 od 4 wynosi 2. No dobrze, mogę zgodzić się na jeszcze jedną iterację choć można by podając przedział, nie byłoby to konieczne.
3 cze 22:27
Pytający: Jc, ale w tym algorytmie wynikiem jest jeden punkt... Nie otrzymujesz w wyniku informacji, że x∊[3, 4], tylko że x≈3.5. W zasadzie na końcu znasz maksymalny dopuszczalny błąd, więc można dorzucić informację o tym błędzie i rezultatem wtedy jest x=3.5 ± 0.5.
3 cze 22:28
jc: Jeszcze inaczej, co podaje algorytm po n−tej iteracji? co po pierwszej? Czy na starcie, czyli przed pierwszą iteracją mamy (a+b)/2 ?
3 cze 22:30
jc: Widzę, że zadałeś to samo pytanie. Ale (a+b)/2 można podać bez żadnych obliczeń.
3 cze 22:31
Kuba: (a+b)/2 = 0.475
3 cze 22:34
Pytający: Ja zaimplementowałem (link parę postów wyżej) tenże przepis (pominąłem sprawdzanie czy |f(c)| jest dostatecznie bliskie zeru): https://en.wikipedia.org/wiki/Bisection_method#Iteration_tasks I według tegoż przepisu obliczenie c=(a+b)/2 to właśnie początek pierwszej iteracji.
3 cze 22:37
jc: ... początek, a koniec? Właściwie ma to znaczenie czysto umowne. Ile nas kosztuje jeszcze jeden krok? Metoda stycznych po 4 krokach daje: 0.351733711249.
3 cze 22:43
Kuba: Pytający jeżeli masz możliwość to zerknąłbyś czy dobrze wszystko zrozumiałem. https://www.fotosik.pl/zdjecie/e3ac031c37d94f93 https://www.fotosik.pl/zdjecie/127c041c8d10d4a7
3 cze 22:45
jc: Zaczynałem od 0.25.
3 cze 22:46
jc: Porównywanie z dokładną wartością nie ma sensu. Gdybyś znał dokładną wartość, to nie musiałbyś liczyć, a jak nie znasz, to nie wiesz ile kroków wykonać. Na dodatek, może się zdarzyć, że dokładna wartość leży w środku przedziału i okaże się, że liczba iteracji wynosi jeden.
3 cze 22:51
Pytający: Wiadomo, że jedna osoba pierwsze obliczenia napisze przed pętlą i nazwie je iteracją zerową, dla innej w ogóle to nie jest iteracja itp. Tak jak mówisz ±1 iteracja nie robi różnicy, no chyba że chodzi o sprawozdanie... które wygląda ok, Kubo. Acz żadnych obliczeń oczywiście nie sprawdzałem, pobieżnie zerknąłem na cyferki − całkiem możliwe, że podobnie zrobi sprawdzający.
3 cze 22:57
Kuba: Dziękuje wam, jakbym miał jakieś pytania do innego podpunktu to już założe nowy temat, bo bisekcja została oficjalnie skonczona
3 cze 23:03