Jakie techniki aproksymacji istnieją dla funkcji pierwiastka kwadratowego?

Muszę zaimplementować aproksymację do odwrotności $x^x$ , tj. Kwadratowej funkcji super-root (ssrt). Na przykład $\mathrm{ssrt}(2) \approx 1.56$ oznacza, że $1.56^{1.56} \approx 2$ . Nie interesuje mnie żadna konkretna dokładność / głębia bitowa, ponieważ rozumiem, jakie są moje opcje w przeciwieństwie do prostszych podejść wykorzystujących serie mocy.

Wolfram Alpha daje ładne symboliczne rozwiązanie w kategoriach funkcji W Lamberta (tj. $\ln(x)/W(\ln(x))$ ). Wikipedia podaje tę samą formułę , a także równoważny $e^{W(\ln(x))}$ . Biorąc pod uwagę, że istnieje uzasadniona ilość informacji na temat obliczania $W(x)$ [1] [2], technicznie rzecz biorąc, wszystko jest potrzebne, aby coś zaimplementowaćdla różnych wymagań. Znam co najmniej dwie książki, które szczegółowo opisują przybliżenie [3] [4], więc jest nawet dużo miejsca na optymalizację z tego kierunku. $\ln(x)$

Mam jednak dwa pytania:

Czy gdzieś opublikowano techniki przybliżania specyficzne dla tej funkcji?
Czy występuje pod inną nazwą oprócz „pierwiastka kwadratowego”, który nieco ułatwiłby wyszukiwanie referencji?

Wikipedia / Google ujawniło kilka odnośników poświęconych bardziej ogólnym funkcjom „tetracji”, które obejmują jako szczególny przypadek, ale większość z nich wydaje się bardziej nastawiona na badanie / definiowanie ogólnych przypadków. $\mathrm{ssrt}(x)$

Corless, R .; Gonnet, G .; Zając, D .; Jeffrey, D .; Knuth, Donald (1996), „On the Lambert W function” http://www.apmaths.uwo.ca/~djeffrey/Offprints/W-adv-cm.pdf
Cyfrowa biblioteka funkcji matematycznych . http://dlmf.nist.gov/4.13
Crenshaw, Jack W. (2000), Math Toolkit for Real-Time Programming.
Hart, John F. (1978), Computer Approximations.
Chapeau-Blondeau, F. i Monir, A. (2002). Numeryczna ocena funkcji Lamberta W i zastosowania do generowania uogólnionego szumu Gaussa z wykładnikiem 1/2. Transakcje IEEE dotyczące przetwarzania sygnałów 50, 2160-2165. http://www.istia.univ-angers.fr/~chapeau/papers/lambertw.pdf
Minero, Paul. Szybkie Przybliżony Lambert W . http://www.machinedlearnings.com/2011/07/fast-approximate-lambert-w.html

Aktualizacja

Po wykonaniu niektórych więcej badań w ciągu ostatnich kilku dni, wciąż nie znalazłem rodzaj hands-on „Crenshaw stylu” Leczenie miałem nadzieję, ale nie znaleźliśmy nowy referencje warte udokumentowania tutaj. Na stronie trzeciej w znajduje się sekcja zatytułowana „Szybka aproksymacja”, która szczegółowo opisuje przybliżenie w kontekście generowania szumu. Co ciekawe, gęstość prawdopodobieństwa „szumu Gaussa z wykładnikiem 1/2” [w pracy] wygląda uderzająco podobnie do histogramu w odpowiedzi Kellenjba na $[3]$ $\mathrm{ssrt}(x)$ $[5]$ $W(x)$ to pytanie o wykrywanie obcinania sygnału .

Ponadto link podany przez rwong w komentarzach jest świetnym źródłem do faktycznej implementacji , a nawet prowadzi do projektu autora na licencji BSD o nazwie fastapprox , który obejmuje opisaną implementację. $[6]$ $W(x)$

approximation Datageist
źródło

machinedlearnings.com/2011/07/fast-approximate-lambert-w.html

rwong

Zapytałem o to na Meta, ponieważ pole komentarzy nie jest przeznaczone do długich dyskusji. Proszę zasugerować, jak powinniśmy poradzić sobie z tymi pytaniami tutaj: Czy pytania dotyczące analizy numerycznej są tematyczne?

@datageist - Początkowy wniosek z meta pytania brzmiał: jeśli chcesz użyć tej analizy numerycznej do przetwarzania danych DSP, to jest na temat. Jeśli nie, to nie. Jak to się ma do DSP?

Kevin Vermeer

@Kevin Pojawił się w kontekście opracowywania efektu dźwiękowego.

Datageist

Ilekroć muszę napisać procedurę dla funkcji Lamberta, zwykle używam przybliżeń podanych w tym artykule, a następnie szlifuję za pomocą Newtona-Raphsona, Halleya lub jakiejkolwiek innej metody iteracyjnej. Możesz dostosować to podejście do odwracania

...

x^{x}

$x^x$

Niektóre numeryczne dźgnięcia w ciemności dały następujące do iteracyjnego podejścia:

Szukamy rozwiązania y = f (x) gdzie y ^ y = x.

y \ln y = \ln x

$y \ln y = \ln x$

y = sol (x, y) = {mi}^{\frac{\ln x}{y}}

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

Wartość jest stałym punktem powyższego równania i wydaje się, że empirycznie wydaje się zbieżna dla niektórych wartości , ale dla większych wartości oscyluje lub rozbiega się. $y$ $x$ $x$

Następnie wypróbowałem podejście podobne do iteracyjnego pierwiastka kwadratowego Newtona:

y = \frac{y_{p r e v i o u s} + y_{*}}{2} = \frac{y + e^{\frac{\ln x}{y}}}{2}

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

gdzie y * ma reprezentować nieprzekraczającą, ale optymistyczną odpowiedź, która zachowuje dokładność, jeśli zgadniesz dokładną wartość początkową (w pierwiastku kwadratowym y ² = x, to y * = x / y).

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

$y_0 = \ln(x)+1$

Pomyślałem więc, że może jest lepsze rozwiązanie:

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

Potem znalazłem coś interesującego.

$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{aligned} y [n + 1] & = \frac{sol (x, y [n]) + \ln (y [n]) \times y [n]}{1 + \ln (y [n])} \\ = \frac{{mi}^{\frac{\ln (x)}{y [n]}} + \ln (y [n]) \times y [n]}{1 + \ln (y [n])} \end{aligned}

$\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)$

(Ktoś prawdopodobnie mógłby wykazać, że jest to w jakiś sposób równoważne Newtonowi-Raphsonowi, ale myślę, że jest to poza moimi możliwościami.)

Jason S.
źródło

Jakie techniki aproksymacji istnieją dla funkcji pierwiastka kwadratowego?

Odpowiedzi: