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

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?

-
There isn't a solution that can be written in terms of elementary functions. This is because you have an $x$ both inside and out of a transcendental function. – Jim Feb 20 '13 at 6:18
You can solve numerically using, e.g., Newton's Method, q.v. – Gerry Myerson Feb 20 '13 at 6:20
Can I approximate it as a function of c? Maybe as a series orsomething? – Joe Feb 20 '13 at 6:59
If you care just about the results, you can use Wolfram|Alpha. – Andrea Corbellini Feb 20 '13 at 10:26

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$:

-
I'm doing asymptomatic analysis. c can be assumed very large. After skimming the Wikipedia article, it's still not clear how x will be bounded asymptotically. – Joe Feb 20 '13 at 18:39
What do you mean? I gave an explicit expression for $x$ as a funcion of $c$. – yohBS Feb 20 '13 at 19:55
I mean I don't have intuition for how $W(z)$ grows compared to $z$. Specifically, $W(z) = O(f(z))$ for what elementary function $f$? Is there one? – Joe Feb 20 '13 at 20:56
+1 though, since now I at least know what $W_0$ is referring to. – Joe Feb 20 '13 at 20:59
@joe see my updated answer. – yohBS Feb 20 '13 at 22:24

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!

-
Convergence of the fixed point iteration $x := f(x)$ is usually easy to work out from the first derivative of $f$. In particular if we can limit ourselves to an interval where $|f'(x)| \lt 1$, then the fixed point iteration converges by "contraction". – hardmath Feb 20 '13 at 12:45