Wady aproksymacji Newtona-Raphsona z przybliżoną pochodną numeryczną

17

Załóżmy, że mam jakąś funkcję f i chcę znaleźć x taką, żef ff(x)0 . Mogę użyć metody Newtona-Raphsona. Wymaga to jednak znajomości funkcji pochodnej f(x) . 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.ff

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 )ff(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ą?

Mark Dominus
źródło
5
Metoda sieczna jest doskonałą alternatywą, gdy obliczanie pochodnej jest kosztowne. Trzy kroki secans są na ogół w przybliżeniu równoważne dwóm krokom Newtona, a kroki są tańsze.
1
Za każdym razem, gdy obliczasz pochodną liczbowo według skończonej różnicy (jak sugerujesz), każdy szum w funkcji jest wzmacniany, więc musisz ostrożnie wybierać epsilon. Jedną z możliwości jest to, że kiedy zbliżysz się do rozwiązania, przełącz się na binarną metodę podziału, która z pewnością zbiegnie się, dopóki f jest lokalnie monotoniczny.
Mike Dunlavey,
2
Jak wspomniał André, dwupunktowe pochodne numeryczne, jak sugerujesz, są równoważne zrestartowanej metodzie Secant . Dla szybszej konwergencji sugerowałbym jednak tak zwany algorytm Illinois , który jest bliskim krewnym metody Secant i użyje tylko jednego punktu na krok, w przeciwieństwie do dwóch w twoim przypadku, i nie utknie jak Metoda fałszywej pozycji.
Pedro
Jaki jest wymiar ? Im wyższy wymiar, tym bardziej wartościowa staje się pochodna. Wolny od jakobianów Newton-Kryłow jest opcją, która nie wymaga wyraźnych pochodnych (chociaż wstępne kondycjonowanie jest ważne w przypadku źle uwarunkowanych systemów). x
Jed Brown

Odpowiedzi:

12

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:RnRn

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

Df(x)ei=limε0f(x+εei)f(x)ε

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,,nDfnDfDf

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ε

Df(x)eif(x+εei)f(x)ε,

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)

Geoff Oxberry
źródło