Quelles techniques d'approximation existent pour la fonction super-racine carrée?

J'ai besoin d'implémenter une approximation de l'inverse de , c'est-à-dire la fonction super-racine carrée (ssrt). Par exemple, signifie que . Je ne suis pas aussi intéressé par une précision / profondeur de bits particulière que par la compréhension de mes options contrairement à des approches plus simples utilisant des séries de puissance.$x^x$$\mathrm{ssrt}(2) \approx 1.56$$1.56^{1.56} \approx 2$

Wolfram Alpha donne une belle solution symbolique en termes de fonction Lambert W (ie ). Wikipedia donne la même formule , ainsi que l'équivalent . Étant donné qu'il existe une quantité raisonnable d'informations sur le calcul de [1] [2], techniquement, c'est tout ce qu'il faut pour implémenter quelque chose pour une variété d'exigences. Je connais au moins deux livres qui détaillent en détail l'approximation de \ ln (x) [3] [4], donc il y a même beaucoup de place pour optimiser dans cette direction.$\ln(x)/W(\ln(x))$$e^{W(\ln(x))}$$W(x)$$\ln(x)$

Cependant, j'ai deux questions:

1. Des techniques d'approximation spécifiques à cette fonction ont-elles été publiées quelque part?
2. Est-ce qu'il porte un autre nom que "super-racine carrée" qui faciliterait un peu la recherche de références?

Wikipedia / Google a trouvé quelques références dédiées à des fonctions plus générales de "tétration" qui incluent $\mathrm{ssrt}(x)$ comme cas spécial, mais la plupart d'entre elles semblent plus adaptées à l'exploration / définition des cas généraux.

-

1. Corless, R .; Gonnet, G .; Hare, D .; Jeffrey, D .; Knuth, Donald (1996), «Sur la fonction Lambert W» http://www.apmaths.uwo.ca/~djeffrey/Offprints/W-adv-cm.pdf
2. Bibliothèque numérique des fonctions mathématiques . http://dlmf.nist.gov/4.13
3. Crenshaw, Jack W. (2000), Math Toolkit for Real-Time Programming.
4. Hart, John F. (1978), Computer Approximations.
5. Chapeau-Blondeau, F. et Monir, A. (2002). Évaluation numérique de la fonction Lambert W et application à la génération de bruit gaussien généralisé avec exposant 1/2. Transactions IEEE sur le traitement du signal 50, 2160-2165. http://www.istia.univ-angers.fr/~chapeau/papers/lambertw.pdf
6. Minero, Paul. Approximatif rapide Lambert W . http://www.machinedlearnings.com/2011/07/fast-approximate-lambert-w.html

-

Mise à jour

Après avoir fait plus de recherches au cours des derniers jours, je n'ai toujours pas trouvé le genre de traitement "style Crenshaw" de que j'espérais, mais j'ai trouvé un nouvelle référence à documenter ici. À la page trois de , il y a une section intitulée "Fast Approximation" qui va dans les moindres détails sur l'approximation de dans le contexte de la génération de bruit. En passant, la densité de probabilité du «bruit gaussien avec exposant 1/2» [dans l'article] ressemble de façon frappante à l'histogramme de la réponse de Kellenjb à cette question sur la détection de l'écrêtage du signal .$[3]$$\mathrm{ssrt}(x)$$[5]$$W(x)$

De plus, le lien donné par rwong dans les commentaires est une excellente ressource pour implémenter , et il est même lié au projet sous licence BSD de l'auteur appelé fastapprox , qui inclut l'implémentation décrite.$[6]$$W(x)$

Quelques coups de couteau numériques dans le noir ont donné les résultats suivants pour une approche itérative:

Nous recherchons la solution y = f (x) où y ^ y = x.

$$y \ln y = \ln x$$

$$y = g(x,y) = e^{\frac{\ln x}{y}}$$

$y$$x$$x$

J'ai ensuite essayé une approche similaire à la racine carrée itérative de Newton:

$$y = \frac{y_{previous} + y_{*}}{2} = \frac{y + e^{\frac{\ln x}{y}}}{2}$$

où y * est censé représenter une réponse non convergente mais optimiste qui maintient la précision si vous devinez une valeur initiale précise (en racine carrée y ² = x, c'est y * = x / y).

$x$$x_{min} = (\frac{1}{e})^{\frac{1}{e}}$

$y_0 = \ln(x)+1$

J'ai donc pensé qu'il y avait peut-être une meilleure solution de convergence:

$y = (1-a) \times y + a \times g(x,y)$$a$$x$

Ensuite, j'ai trouvé quelque chose d'intéressant.

$y$$y^y = x$$y_2 = g(x,y+ \epsilon) = e^{\frac{\ln(x)}{y+\epsilon}}$$y_2-y$$\epsilon \times (-\ln(y))$$y_1 = y + \epsilon$$\epsilon$$y_2 = g(x,y_1)$$(y_2 - y) \approx \epsilon \times (-\ln(y)) = (y_1 - y) \times (-\ln(y))$

$y$$y = \dfrac{y_2 + \ln(y) \times y_1}{1 + \ln(y)}$$\ln(y_1)$$\ln(y)$

$$\begin{align*} y[n+1] &= \frac{g(x,y[n]) + \ln(y[n])\times y[n]}{1+\ln(y[n])}\\ &= \frac{e^{\frac{\ln(x)}{y[n]}} + \ln(y[n])\times y[n]}{1+\ln(y[n])} \end{align*}$$

$y = 1+\ln(x)$

(Quelqu'un pourrait probablement montrer que cela équivaut à Newton-Raphson d'une certaine manière, mais je pense que cela dépasse mes capacités.)