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

2 Answers 2

7
$\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$
5
  • $\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
    Commented Oct 23, 2016 at 6:06
  • 1
    $\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$ Commented Oct 23, 2016 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
    Commented Oct 23, 2016 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$ Commented Oct 23, 2016 at 8:03
  • $\begingroup$ @Anonymous. Look at my last sentence in the edited answer. $\endgroup$ Commented Oct 23, 2016 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$
1
  • $\begingroup$ Aitken's $\Delta^2$ method works if the base iteration's convergence is linear. You'd need to derive a method similar to Aitken's for quadratic (or higher) convergence. It turns out quite different. $\endgroup$
    – vonbrand
    Commented Apr 7, 2020 at 2:16

You must log in to answer this question.

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