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

Załóżmy, że mam jakąś funkcję $f$ i chcę znaleźć $x$ taką, że $f(x)\approx 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. $f$ $f$

Ale nawet jeśli jest skomplikowane, mogę przybliżać dla dowolnego konkretnego , wybierając małą liczbę i obliczając $f'$ $f'(a)$ $a$ $\epsilon$ . $f'(a) \approx {f(a+\epsilon) - f(a)\over\epsilon}$

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ą?

reference-request approximation

— Mark Dominus
źródło

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.

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,

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

$x$

— Jed Brown

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: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}$

Obliczanie pochodnej (macierzy jakobijskiej, lub lub cokolwiek wolisz) przy użyciu różnic skończonych będzie wymagało oceny funkcji. Jeśli możesz obliczyć pochodną za pomocą arytmetyki zmiennoprzecinkowej bezpośrednio z definicji, musisz obliczyć iloraz różnicy $\mathrm{D}f(x)$ $J(x)$ $(\nabla f(x))^{T}$ $n$

\begin{aligned} D f (x) e_{i} = lim_{ε \to 0} \frac{f (x + ε e_{i}) - f (x)}{ε} \end{aligned}

$\begin{align} \mathrm{D}f(x)e_{i} = \lim_{\varepsilon \rightarrow 0} \frac{f(x + \varepsilon e_{i}) - f(x)}{\varepsilon} \end{align}$

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 . Jeśli jest duże, może to być wiele ocen funkcji. Jeśli masz wyrażenie analityczne , 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ć o około 3 do 5 razy koszt oceny funkcji. $i = 1, \ldots, n$ $\mathrm{D}f$ $n$ $\mathrm{D}f$ $\mathrm{D}f$

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 obliczania $\mathrm{D}f$ $\varepsilon$

\begin{aligned} D f (x) e_{i} \approx \frac{f (x + ε e_{i}) - f (x)}{ε}, \end{aligned}

$\begin{align} \mathrm{D}f(x)e_{i} \approx \frac{f(x + \varepsilon e_{i}) - f(x)}{\varepsilon}, \end{align}$

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. $\approx$ $\varepsilon$ $\varepsilon$

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. $\mathrm{D}f$

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