Metoda dychotomii – Wikipedia

Kolejne etapy metody dychotomii z przedziałem jako punktem wyjścia [[[ A _Pierwszy ; B _Pierwszy ] . Zero funkcji jest na czerwono.

. Metoda dychotomii Lub Metoda bissekcji jest, w matematyce, algorytm poszukiwania zero funkcji, która polega na powtarzaniu udostępniania dwuczęściowego przedziału, a następnie wybieraniu pod-interval, w którym istnieje zero funkcji.

Rozważamy dwie liczby rzeczywiste A I B i prawdziwa funkcja F Kontynuuj w czasie [[[ A W B ] Jak na przykład F ( A ) I F ( B ) być przeciwnymi znakami.
Załóżmy, że chcieliśmy rozwiązać równanie F ( X ) = 0. Zgodnie z twierdzeniem o wartościach pośrednich, F ma co najmniej jedno zero w przedziale [[[ A W B ] . Metoda dychotomii polega na podzieleniu przedziału poprzez obliczenie M = ( A + B ) / 2 . Istnieją teraz dwie możliwości: albo F ( A ) I F ( M ) Są też przeciwnymi znakami F ( M ) I F ( B ) są przeciwnymi znakami.

Algorytm dychotomii jest następnie stosowany do sub-interval, w którym zachodzi zmiana znaku, co oznacza, że ​​algorytm dychotomii jest rekurencyjny.

Błąd bezwzględny metody dychotomii jest co najwyżej

${DisplayStyle {frac {b-a} {2^{n+1}}}}$

Po N Kroki, ponieważ błąd jest zmniejszony o połowę na każdym etapie.

I odwrotnie, jeśli staramy się upewnić, że błąd bezwzględny jest mniejszy niż określona wartość mi , wiemy, jak policzyć liczbę niezbędnych iteracji N Aby zaspokoić tę tolerancję w końcowym wyniku:

Metoda zbiega się liniowo, co jest bardzo powolne w porównaniu z metodą Newtona. Zaletą w porównaniu z tym ostatnim jest jego większe pole zastosowania: wystarczy, że F ( A ) I F ( B ) są przeciwnymi znakami i znakiem F ( M ) przy każdej iteracji.

Pod hipotezą, że znak F ( M ) być determinacją, oto reprezentacja metody pseudo-kodu, gdzie mi jest pożądaną precyzją.

Dopóki ( B - A )> mi  M ← ( A + B ) / 2 I ( F ( A )* F ( M ) ≤ 0) WIĘC  B ← M  W przeciwnym razie  A ← M  Zakończ tak  Zakończyć tak długo, jak  

Główną praktyczną zaletą tej metody jest jej solidność, ponieważ jeśli F jest ciągły, wówczas algorytm jest teoretycznie zbieżny (wielkość przedziału badawczego ma tendencję do zera). Główną wadą w algorytmie jest to, że tylko znak F jest używany, co prowadzi do dość powolnej zbieżności (prawie liniowej zbieżności). Metoda Newtona, która wykorzystuje wartość F a także wartość nachylenia F , jest, gdy zbiega się, znacznie szybciej (zbieżność kwadratowa).

Załóżmy na przykład, że proste zero jest równe 1, że funkcja jest dwukrotnie stale różniła się i że F’ ( X ) = 1 . Załóżmy ponadto, że używamy binarnych pływających przecinków IEEE-754 z 64 bitami, w tym 53 bitami precyzji. Załóżmy, że szukamy błędu bezwzględnego poniżej 10 ^-16 . Jeśli początkowy przedział badawczy ma długość równą 1, wówczas dychotomia wymaga 52 iteracji. Przeciwnie, jeśli punkt początkowy jest powiązany z błędem bezwzględnym mniejszym niż 0,1, wówczas metoda Newtona zbiega się w zaledwie 5 iteracjach.

Ta metoda wielkiej solidności wymaga jednak poznania na każdym etapie znaku F ( M ) . W kilku przypadkach może się zdarzyć, że wartość F ( M ) lub tak blisko 0, że dokładność oprogramowania obliczeniowego nie umożliwia już ustalenia znaku F ( M ) (Błędy zaokrąglania mogą prowadzić do przeciwnego znaku lub 0). Zastosowanie algorytmu może następnie prowadzić do błędnej eliminacji połowy przedziału i zbieżności w kierunku odległej wartości korzenia.

Bardziej ogólnie, określenie znaku F ( M ) Może być niemożliwe, nawet poprzez zwiększenie dokładności obliczenia oprogramowania. Rozważmy na przykład prawdziwy A które można obliczyć za pomocą wartości dziesiętnych lub racjonalnych przybliżonych A _N W ogóle precyzji Pierwszy / N pożądany. Teraz rozważ funkcję F Udoskonalić w odstępach [0, Pierwszy / 3 ] W [[[ Pierwszy / 3 W 2 / 3 ] I [[[ 2 / 3 , Pierwszy] i takie jak F (0) = -1 W F (1) = 1 W F ( Pierwszy / 3 ) = F ( 2 / 3 ) = a . Metoda dychotomii wymaga określenia znaku F ( Pierwszy / 2 ) = a . Jednak nie ma ogólnego algorytmu, który pozwala zdecydować, czy a> 0 W A = 0 Lub A <0 . Rzeczywiście, taki algorytm, jeśli istnieje, konieczność dokonywania skończonej liczby obliczeń, powinien podjąć decyzję w świetle skończonej liczby przybliżonych wartości A _N , co jest niewystarczające do zakończenia.

Ten limit prowadzi teoretyków ^{[[[ Pierwszy ]} konstruktywna analiza w celu zakwalifikowania metody dychotomii Nie konstruktywne i faworyzuj alternatywne stwierdzenie: Wyszukaj wartość X Jak na przykład |. F ( X ) | być mniej niż danym błędem.