Inconvénients de l'approximation de Newton-Raphson avec une dérivée numérique approximative

Supposons que j'ai une fonction $f$ et que je veuille trouver $x$ tel que $f(x)\approx 0$ . Je pourrais utiliser la méthode Newton-Raphson. Mais cela nécessite que je connaisse la fonction dérivée $f'(x)$ . Une expression analytique pour $f$ peut ne pas être disponible. Par exemple, $f$ peut être défini par un morceau de code informatique compliqué qui consulte une base de données de valeurs expérimentales.

Mais même si $f'$ est compliquée, je peux approcher $f'(a)$ pour tout particulier $a$ en choisissant un petit nombre $\epsilon$ et calculting $f'(a) \approx {f(a+\epsilon) - f(a)\over\epsilon}$ .

J'ai entendu dire qu'il y avait des inconvénients distincts à cette approche, mais je ne sais pas ce qu'ils sont. Wikipedia laisse entendre que "L'utilisation de cette approximation entraînerait quelque chose comme la méthode sécante dont la convergence est plus lente que celle de la méthode de Newton."

Quelqu'un peut-il développer ce point et fournir une référence qui traite en particulier des problèmes de cette technique?

reference-request approximation Mark Dominus
la source

La méthode sécante est une excellente alternative lorsque le dérivé est coûteux à calculer. Trois étapes sécantes sont généralement à peu près équivalentes à deux étapes Newton, et les étapes sont moins chères.

Chaque fois que vous calculez une dérivée numériquement par différence finie (comme vous le suggérez), tout bruit dans la fonction est amplifié, vous devez donc choisir soigneusement votre epsilon. Une possibilité est, lorsque vous vous approchez de la solution, de passer à une méthode de subdivision binaire, qui est garantie de converger tant que f est localement monotone.

Mike Dunlavey

Comme mentionné par André, les dérivées numériques à deux points, comme vous le suggérez, équivalent à un redémarrage méthode Secant . Pour une convergence plus rapide, je suggère le soi-disant algorithme de l'Illinois , qui est un proche parent de la méthode Secant et n'utilisera qu'un point par étape, par opposition à deux dans votre cas, et ne restera pas bloqué comme le Méthode des fausses positions.

Pedro

Quelle est la dimension de

? Plus la dimension est élevée, plus un dérivé est précieux. Newton-Krylov sans Jacobien est une option qui n'a pas besoin de dérivés explicites (bien que le préconditionnement soit important pour les systèmes mal conditionnés).

x

$x$

Jed Brown

Par souci de notation, supposons que (c'est-à-dire que c'est une fonction à valeur vectorielle qui prend un vecteur en entrée et génère un vecteur de la même taille). Il y a deux préoccupations: le coût de calcul et la précision numérique. $f: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}$

Calcul de la dérivée (la matrice jacobienne, ou $\mathrm{D}f(x)$ $J(x)$ , ou tout ce que vous préférez) en utilisant des différences finies va nécessiterévaluations de fonctions. Si vous pouviez calculer la dérivée en utilisant l'arithmétique à virgule flottante directement à partir de la définition, vous devriez calculer le quotient de différence $(\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}$

pour chaque , en supposant que vous ne faites aucune sorte de «différenciation finie intelligente» (comme Curtis-Powell-Reid) parce que vous connaissez (ou pouvez détecter) le modèle de rareté de . Si est grand, cela pourrait être beaucoup d'évaluations de fonctions. Si vous avez une expression analytique pour $i = 1, \ldots, n$ $\mathrm{D}f$ $n$ , alors le calculer pourrait être moins cher. Des méthodes de différenciation automatiques (également appelées algorithmes) peuvent également être utilisées dans certains cas pour calculer à environ 3 à 5 fois le coût d'une évaluation de fonction. $\mathrm{D}f$ $\mathrm{D}f$

Il y a aussi des préoccupations numériques. De toute évidence, sur un ordinateur, nous ne pouvons pas prendre la limite d'un scalaire car il va à zéro, donc lorsque nous approchons $\mathrm{D}f$ , nous choisissons vraiment pour être "petit" et calculons $\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}$

où signifie que c'est une approximation, et nous espérons que c'est une très bonne approximation. Le calcul de cette approximation en arithmétique à virgule flottante est difficile car si vous choisissez trop grand, votre approximation pourrait être mauvaise, mais si vous choisissez trop petit, il pourrait y avoir une erreur d'arrondi significative. Ces effets sont traités dans l'article de Wikipedia sur la différenciation numérique en détail superficiel; des références plus détaillées peuvent être trouvées dans l'article. $\approx$ $\varepsilon$ $\varepsilon$

Si l'erreur dans la matrice jacobienne n'est pas trop grande, les itérations de Newton-Raphson convergeront. Pour une analyse théorique détaillée, voir le chapitre 25 de Précision et stabilité des algorithmes numériques de Nick Higham , ou l'article de Françoise Tisseur sur lequel il est basé. $\mathrm{D}f$

Les bibliothèques s'occupent généralement de ces détails algorithmiques pour vous, et généralement, les implémentations de bibliothèque de l'algorithme de Newton-Raphson (ou des variantes de celui-ci) convergeront assez bien, mais de temps en temps, il y aura un problème qui causera des problèmes en raison des inconvénients au dessus. Dans le cas scalaire , j'utiliserais la méthode de Brent , en raison de sa robustesse et de son bon taux de convergence en pratique. $(n = 1)$

Geoff Oxberry
la source

Inconvénients de l'approximation de Newton-Raphson avec une dérivée numérique approximative

Réponses: