How to solve $x \log^2x - c=0$?

Question

I'm optimizing parameters to an algorithm to minimize its run time. Substituting some variables to clean up the presentation, I basically need to solve $x \log^2x - c=0$, but I forget how to solve an equation of this form. How can I do this?

Answer 1

One can use Lambert's $W$-function to solve this. But keep in mind that for $0<c\leq 4 e^{-2}$ the solution is not unique:

For completeness, the possible solutions are: $$ \begin{align} &x=\exp\left[2W_0\left(\pm\frac{\sqrt{c}}{2}\right)\right],\ \exp\left[2W_{-1}\left(\frac{\sqrt{c}}{2}\right)\right] & 0<c\leq 4 e^{-2}\\ &x=\exp\left[2W_0\left(\frac{\sqrt{c}}{2}\right)\right] & 4 e^{-2}<c\\ \end{align} $$ Where $W_0$ and $W_{-1}$ are the two branches of the $W$ function, as described in the wikipedia link. I don't know what software you use, but there's no need to resort to numerical root finding - the $W$-function is implemented in mathematica, matlab, and C++.

---

EDIT

Since you asked about the assymptotics, I'll add that for large $c$ we have $$x(c)=\exp\left[2W_0\left(\frac{\sqrt{c}}{2}\right)\right]=\mathcal{O}\left(\frac{c}{\log^2 c}\right)\ .$$ Actually the following limit holds exatcly: $$ \lim_{c\to\infty}\frac{x(c)}{c/\log^2 c}=\lim_{c\to\infty}\frac{\exp\left[2W_0\left(\frac{\sqrt{c}}{2}\right)\right]}{c/\log^2 c}=1 $$ I got this result by playing with mathematica, and I didn't bother proving it.

Note, though, that it takes a very large $c$ to achieve this limit. I give here the plot of this ratio as a function of $c$:

Answer 2

I'm not sure if you can do this analytically, but you could do it pretty quickly numerically and that seems like it should be good enough. Just write $x \log^2 x - c = 0$ as $$ x = \exp\left( (c/x)^{1/2} \right ) $$ and then numerically find a fixed point. This will work if c is positive and if your initial guess is positive, otherwise you might run into problems.

A quick calculation show the following values for 20 iterations with a starting value of $x=10$ and $c=1$:

{10, 1.37194, 2.34844, 1.92042, 2.05774, 2.00795, 2.02527, 2.01916,
2.02131, 2.02055, 2.02082, 2.02072, 2.02076, 2.02074, 2.02075,
2.02075, 2.02075, 2.02075, 2.02075, 2.02075, 2.02075}.

However, this method can be quite unstable for certain choices of c.

Like you mentioned, you could probably try to approximate with a Taylor expansion. Newton's method uses a second order taylor series to find roots. But, I suppose you'd like some way to find the appropriate x more directly or more automatically. To approximate with a Taylor series you would have to choose a point to expand around. If you chose to expand around x=b to the second order, then you would get the approximation $$ x \log ^2(x)-c \approx \left(b \log ^2(b)-c\right)+(x-b) \left(\log ^2(b)+2 \log (b)\right)+\frac{(x-b)^2 (\log (b)+1)}{b}+O\left((x-b)^3\right)$$. You could then solve for x, given c: $$x = \frac{2 b-b \log ^2(b) \pm\sqrt{b} \sqrt{4 c \log (b)+b \log ^4(b)+4 c}}{2 (\log (b)+1)}$$

A Taylor expansion of a higher degree would make this solving step pretty complicated and you'd have to deal with more roots.

I feel like the problem here, though, is that you wouldn't know where to expand around. And to expand around one particular point and use that for all values of c would be problematic because the approximation can get pretty bad the farther you get from the expansion point. I'm not really sure what to do. Good luck, though!