Averaging Newton's Method and Halley's Method

1k Views Asked by At

To approximate the Lambert W function, one can use Newton's Method:

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

Or use Halley's Method:

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

Are these two methods identical? / Do they return the same result per iteration?

If not, would averaging the value of these after each iteration make the approximation more accurate?

(This question is related, but tangent to another question of mine that is also about Newton's method and the Lambert W function)

1

There are 1 best solutions below

0
On BEST ANSWER

Under suitable conditions, Halley's method provides cubic convergence, or a tripling of the number of correct digits between $w_j$ and $w_{j+1}$. Newton's method provides only quadratic convergence, or a doubling of the number of correct digits between $w_j$ and $w_{j+1}$.

Since the two methods are frequently interchangeable (meaning that for a given root, the conditions for convergence are met for both methods), one would therefore prefer the use of Halley's method if $f^{\prime\prime}$ exists and is sufficiently easy to compute.

The Wikipedia entry for Halley's method referenced above shows alternative ways of expressing the iteration which demonstrate the relationship with Newton's method and possibly provide improved computational characteristics such as efficiency or accuracy.

Given the different rate of convergence of these two methods, combining them in some fashion does not seem advisable.