Załóżmy, że mam jakąś funkcję i chcę znaleźć taką, żef f . Mogę użyć metody Newtona-Raphsona. Wymaga to jednak znajomości funkcji pochodnej . Wyrażenie analityczne dla może być niedostępne. Na przykład może być zdefiniowane przez skomplikowany fragment kodu komputerowego, który sprawdza bazę danych wartości eksperymentalnych.
Ale nawet jeśli jest skomplikowane, mogę przybliżać dla dowolnego konkretnego , wybierając małą liczbę i obliczającf ′ ( a ) a ϵ f ′ ( a ) ≈ f ( a + ϵ ) - f ( a ) .
Słyszałem, że takie podejście ma wyraźne wady, ale nie wiem, czym one są. Wikipedia sugeruje, że „użycie tego przybliżenia skutkowałoby czymś w rodzaju metody siecznej, której zbieżność jest wolniejsza niż w przypadku metody Newtona”.
Czy ktoś może rozwinąć tę kwestię i podać odniesienie, które szczególnie omawia problemy związane z tą techniką?
źródło
Odpowiedzi:
Ze względu na notację załóżmy, że (tj. Jest to funkcja o wartości wektorowej, która przyjmuje wektor jako dane wejściowe i wyprowadza wektor tego samego rozmiaru). Istnieją dwie obawy: koszt obliczeniowy i dokładność liczbowa.f:Rn→Rn
Obliczanie pochodnej (macierzy jakobijskiej, J ( x ) lub ( ∇ f ( x ) ) T lub cokolwiek wolisz) przy użyciu różnic skończonych będzie wymagało n oceny funkcji. Jeśli możesz obliczyć pochodną za pomocą arytmetyki zmiennoprzecinkowej bezpośrednio z definicji, musisz obliczyć iloraz różnicyDf(x) J(x) (∇f(x))T n
dla każdego , zakładając, że nie robią żadnego rodzaju „inteligentne skończony różnicowych” (jak Curtis-Powell-Reid) bo wiesz (lub może wykryć) wzór sparsity z D f . Jeśli n jest duże, może to być wiele ocen funkcji. Jeśli masz wyrażenie analityczne D f , a następnie obliczenie to może być tańsze. Automatyczne (znany również jako algorytmiczne) metodami różnicowania może być także stosowana w pewnych przypadkach, aby obliczyć D f o około 3 do 5 razy koszt oceny funkcji.i=1,…,n Df n Df Df
Istnieją również obawy liczbowe. Oczywiście na komputerze, nie możemy podjąć limit skalara, ponieważ dąży do zera, więc kiedy przybliżona , jesteśmy naprawdę zbieranie ε być „małe” i obliczaniaDf ε
gdzie oznacza przybliżenie i mamy nadzieję, że jest to naprawdę dobre przybliżenie. Obliczanie tego przybliżenia w obliczeniach zmiennoprzecinkowych jest trudne, ponieważ jeśli wybierzesz ε za duże, twoje przybliżenie może być złe, ale jeśli wybierzesz ε za małe, może wystąpić znaczny błąd zaokrąglenia. Efekty te są omówione w artykule Wikipedii na temat numerycznego różnicowania w powierzchownych szczegółach; bardziej szczegółowe odniesienia można znaleźć w artykule.≈ ε ε
Jeśli błąd w macierzy Jakubowej nie jest zbyt duży, iteracje Newtona-Raphsona zbiegną się. Szczegółowa analiza teoretyczna znajduje się w rozdziale 25 Dokładności i stabilności algorytmów numerycznych autorstwa Nicka Highama lub w pracy Françoise Tisseur, na której się opiera.Df
Biblioteki na ogół zajmują się tymi szczegółami algorytmicznymi i zwykle implementacje bibliotek algorytmu Newtona-Raphsona (lub jego wariantów) będą ładnie zbiegać się, ale od czasu do czasu pojawia się problem, który powoduje pewne problemy z powodu wad powyżej. W przypadku skalarnym zastosowałbym metodę Brenta , ze względu na jej solidność i dobry wskaźnik konwergencji w praktyce.(n=1)
źródło