Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share
4  
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

2 Answers 2

up vote 6 down vote accepted

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:

enter image description here

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

enter image description here

share
    
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!

share
    
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

This site is currently not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .