Que técnicas de aproximação existem para a função de super raiz quadrada?

Eu preciso implementar uma aproximação ao inverso de $x^x$ , ou seja, a função quadrada de super raiz (ssrt). Por exemplo, $\mathrm{ssrt}(2) \approx 1.56$ meios que $1.56^{1.56} \approx 2$ . Não estou tão interessado em nenhuma precisão / profundidade de bits em particular quanto em entender quais são minhas opções em contraste com abordagens mais diretas usando séries de potência.

O Wolfram Alpha fornece uma boa solução simbólica em termos da função Lambert W (ou seja, $\ln(x)/W(\ln(x))$ ). Wikipedia dá a mesma fórmula , bem como o equivalente $e^{W(\ln(x))}$ . Dado que há uma quantidade razoável de informações sobre o cálculo de para uma variedade de requisitos. Conheço pelo menos dois livros que detalham detalhadamente a aproximação de ln ( x $W(x)$ [1] [2], tecnicamente isso é tudo o que é necessário para implementar algo$\ln(x)$ [3] [4], então há muito espaço para otimizar a partir dessa direção.

No entanto, tenho duas perguntas:

1. As técnicas de aproximação específicas para esta função foram publicadas em algum lugar?
2. Ele tem outro nome além de "super raiz quadrada" que tornaria a busca por referências um pouco mais fácil?

O Wikipedia / Google encontrou algumas referências dedicadas a funções mais gerais de "tetração" que incluem $\mathrm{ssrt}(x)$ como um caso especial, mas a maioria deles parecem ser mais orientada para explorar / definindo os casos gerais.

-

1. Corless, R .; Gonnet, G .; Hare, D .; Jeffrey, D .; Knuth, Donald (1996), "Sobre a função Lambert W" http://www.apmaths.uwo.ca/~djeffrey/Offprints/W-adv-cm.pdf
2. Biblioteca Digital de Funções Matemáticas . 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. e Monir, A. (2002). Avaliação numérica da função Lambert W e aplicação na geração de ruído gaussiano generalizado com expoente 1/2. Transações IEEE no processamento de sinais 50, 2160-2165. http://www.istia.univ-angers.fr/~chapeau/papers/lambertw.pdf
6. Minero, Paul. Rápido aproximado Lambert W . http://www.machinedlearnings.com/2011/07/fast-approximate-lambert-w.html

-

Atualizar

Depois de fazer mais algumas pesquisas ao longo dos últimos dias, eu ainda não encontrei o tipo de hands-on "estilo Crenshaw" tratamento de s s r t ( x ) que eu estava esperando, mas eu encontrar um novo referência que vale a pena documentar aqui. Na página três em [ 5 ] , há uma seção intitulada "Aproximação rápida", que detalha a aproximação de W ( x ) no contexto da geração de ruído. Como um aparte interessante, a densidade de probabilidade do "ruído gaussiano com expoente 1/2" [no artigo] parece surpreendentemente semelhante ao histograma na resposta de Kellenjb para$[3]$$\mathrm{ssrt}(x)$$[5]$$W(x)$esta pergunta sobre a detecção de recorte de sinal .

Além disso, o link fornecido por rwong nos comentários é um excelente recurso para realmente implementar o W ( x ) , e até vincula ao projeto licenciado por BSD do autor chamado fastapprox , que inclui a implementação descrita.$[6]$$W(x)$

Algumas facadas numéricas no escuro renderam o seguinte para uma abordagem iterativa:

Estamos procurando a solução y = f (x) onde y ^ y = x.

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

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

O valor para é um ponto fixo da equação acima e, empiricamente, parece convergir para alguns valores de x , mas para valores maiores de x ele oscila ou diverge.$y$$x$$x$

Depois, tentei uma abordagem semelhante à raiz quadrada iterativa de Newton:

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

onde y * deve representar uma resposta não-convergente, mas otimista, que mantém a precisão se você adivinhar um valor inicial preciso (na raiz quadrada y ² = x, é y * = x / y).

Parece convergir, mas muito lentamente na extremidade inferior de (próximo de x m i n = ( $x$ )$x_{min} = (\frac{1}{e})^{\frac{1}{e}}$

Também parece que um bom palpite inicial é .$y_0 = \ln(x)+1$

Então imaginei que talvez houvesse uma solução com melhor convergência:

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

Então eu encontrei algo interessante.

$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))$. (Just to clarify, I have no analysis to verify this, but the numbers just popped out of some numerical evaluation I performed.)

Solve for the linear terms in $y$, and you get $y = \dfrac{y_2 + \ln(y) \times y_1}{1 + \ln(y)}$... use $\ln(y_1)$ in place of $\ln(y)$ and you get this iterative approximation:

$$\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*}$$

This appears to work very well, with the initial guess $y = 1+\ln(x)$, and appears to converge within 4 or 5 iterations.

(Someone could probably show that this is equivalent to Newton-Raphson in some way, but I think it's beyond my capability.)