2
$\begingroup$

For approximating the Lambert W function, the Wikipedia page lists Newton's method and Halley's method.

Newton's method (the Newton–Raphson method) converges quadratically (number of correct digits doubles per iteration). For approximating the Lambert W function, it is defined as:

$$w_{j+1}=w_j-\frac{w_je^{w_j}-z}{e^{w_j}+w_je^{w_j}}$$

Halley's method converges cubically (number of correct digits triples per iteration). For approximating the Lambert W function, it is defined as:

$$w_{j+1}=-\frac{w_je^{w_j}-z}{e^{w_j}(w_j+1)-\frac{(w_j+2)(w_je^{w_j}-z)}{2w_j+2}}$$

Do other methods exist that converge faster than these? If so, what are they?

I have thus far been unable to find any that are used to approximate the Lambert W function.

$\endgroup$
4
$\begingroup$

If you look for higher order formulae, you could consider Householder method which is or order $4$.

If you want to go further, have a look at this paper; using it, you can easily build an iteration which would be of the order you wish.

The equation to solve is $$f(w)=w e^w-z=0\implies f^{(n)}=e^w(w+n)$$ which makes the expression quite simple for the iterates.

For illustration purposes, let us consider $z=123456789$ and, being lazy, use $w_0=\log(123456789)\approx 18.6314$. The following table reports the first iterate $w_1$ as a function of the order $k$ of the method $$\left( \begin{array}{ccc} k & w_1 & \text{method} \\ 2 & 17.73327936 & \text{Newton} \\ 3 & 17.30942321 & \text{Halley}\\ 4 & 17.04239937 & \text{Householder}\\ 5 & 16.85306931 & \text{no name}\\ 6 & 16.70984559 & \text{no name}\\ 7 & 16.59697020 & \text{no name}\\ 8 & 16.50546219 & \text{no name}\\ 9 & 16.42972594 & \text{no name} \end{array} \right)$$ while the exact solution is $15.86715078$; it is quite slow because the starting value $w_0$ is not good enough.

Using a better approximation, as shown here, that is to say $$W(z)\approx L_1-L_2+\frac{L_2}{L_1} \qquad \qquad L_1=\log(z)\qquad L_2=\log(L_1)$$ for the chosen example $(w_0\approx 15.8635)$, the same methods will give $$\left( \begin{array}{ccc} k & w_1 & \text{method} \\ 2 & 15.867157703589425302 & \text{Newton}\\ 3 & 15.867150764845732185 & \text{Halley}\\ 4 & 15.867150782609469895 & \text{Householder}\\ 5 & 15.867150782558279240 & \text{no name}\\ 6 & 15.867150782558436641 & \text{no name}\\ 7 & 15.867150782558436137 & \text{no name}\\ 8 & 15.867150782558436139 & \text{no name}\\ 9 & 15.867150782558436139 & \text{no name} \end{array} \right)$$ while the exact solution is $15.867150782558436139$.

Any way, my personal opinion is that, for $z>0$, it is simpler to find the zero of $$g(w)=\log(w)+w-\log(z)$$ and apply any method to it since the derivatives $g^{(n)}$ are very simple and the $a_i$ are just very simple.

To compare the behavior of the two functions, I show below Newton iterations for the previous value of $z$ still starting with the poorest estimate $$\left( \begin{array}{ccc} n & \text{using f(w)} & \text{using g(w)} \\ 1 & 17.7332793612487 & 15.8555416036877 \\ 2 & 16.9177099266940 & 15.8671505305371 \\ 3 & 16.2832371769982 & 15.8671507825584 \\ 4 & 15.9466743519793 & \\ 5 & 15.8704075861194 & \\ 6 & 15.8671563938690 & \\ 7 & 15.8671507825751 & \\ 8 & 15.8671507825584 & \end{array} \right)$$

$\endgroup$
  • $\begingroup$ This idea of constructing iterative methods is entirely new to me. Could you provide the exact formulae you used for septic, octic, and nonic convergence so I can better understand what you're doing? $\endgroup$ – esote Oct 23 '16 at 6:06
  • $\begingroup$ @Anonymous. No, I refuse to do that (nothing will fit in a page) !! Even for Householder, the formula becomes quite complex. All details are in the second link. In fact, if you want a personal point of view, I should stay with Halley but improving the starting guess as shown in the third link. But, if you have to code it, it is rather simple to implement the method computing first the $a_i$ as given in the second link. $\endgroup$ – Claude Leibovici Oct 23 '16 at 6:24
  • $\begingroup$ Thanks! The second link you provided (I didn't notice on my first read of your answer) helps me tremendously. I already have Halley's method implemented in code, and I will look into the possibility of using the Householder method. I may have to stick with Halley if it ends up as complex as you say. $\endgroup$ – esote Oct 23 '16 at 7:49
  • $\begingroup$ @Anonymous. There is no problem with any of the methods. The formula for Householder is not so bad (neither the higher order formula). As said, for coding, just program the $a_i$ of the second link (this is simple) and finalize. This means that, in the same piece of code, you could have al the methods in an almost generic way. By the way, this is what I have done. Cheers. $\endgroup$ – Claude Leibovici Oct 23 '16 at 8:03
  • $\begingroup$ @Anonymous. Look at my last sentence in the edited answer. $\endgroup$ – Claude Leibovici Oct 23 '16 at 8:10
0
$\begingroup$

If you are afraid of going into complexer formulas than Halley, try using the latter and speed it up by Aitken's delta squared method. This is based on personal experience. Simple and often helpful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.