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?

Pytający: https://en.wikipedia.org/wiki/Bisection_method#Iteration_tasks Policz |a − wynik| odpowiednio dla 12 i 13 iteracji.

Pytający: I w podanym przez Ciebie wzorze powinien być logarytm o podstawie 2 (a nie naturalny).

Kuba: Dla 12 iteracji: 0,00004377376231207153 Dla 13 iteracji: 0.00002336490956289516

Pytający: A dobrze liczysz iteracje? Po 1 iteracji Twój wynik to (a+b)/2? Najprościej jakbyś podał a, b i funkcję.

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

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.

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

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...

jc: Jaki masz przedział?

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.

jc: Dla 13 iteracji przedział zmniejsza się trochę ponad 8000 razy bo 2¹0=1024. Jeśli na początku masz przedział długość 80, to będziesz miał dokładność 0.01.

Kuba: Na początku mam przedział dł 0.55

jc: 12 to za mało, 13 wystarczy. Do szybkiego oszacowania dobrze wiedzieć, że 2¹⁰ to nieco ponad 1000.

Kuba: Wyszlo mi 12 z hakiem czyli 13

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.

Kuba: Znalazłem jeszcze z wykładu wzór n = log₂(2*10^k * (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.

jc: 13 iteracja daje dokładność lepszą niż 1/10000. 0.351733398438 0.35180053710 różnica = 0.00006713867 < 0.0001

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

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/2¹3 < 0.001 * 0.55/8 < 0.001 * 0.1 = 0.0001.

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⁻⁴ 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?

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.

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?

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).

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.

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.

jc: Jeszcze inaczej, co podaje algorytm po n−tej iteracji? co po pierwszej? Czy na starcie, czyli przed pierwszą iteracją mamy (a+b)/2 ?

jc: Widzę, że zadałeś to samo pytanie. Ale (a+b)/2 można podać bez żadnych obliczeń.

Kuba: (a+b)/2 = 0.475

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.

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.

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

jc: Zaczynałem od 0.25.

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.

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.

Kuba: Dziękuje wam, jakbym miał jakieś pytania do innego podpunktu to już założe nowy temat, bo bisekcja została oficjalnie skonczona