Lentz's algorithm

In mathematics, Lentz's algorithm is an algorithm to evaluate continued fractions, and was originally devised to compute tables of spherical Bessel functions. ^{[1] [2]}

The version usually employed now is due to Thompson and Barnett. ^[3]

History

The idea was introduced in 1973 by William J. Lentz ^[1] and was simplified by him in 1982. ^[4] Lentz suggested that calculating ratios of spherical Bessel functions of complex arguments can be difficult. He developed a new continued fraction technique for calculating the ratios of spherical Bessel functions of consecutive order. This method was an improvement compared to other methods because it started from the beginning of the continued fraction rather than the tail, had a built-in check for convergence, and was numerically stable. The original algorithm uses algebra to bypass a zero in either the numerator or denominator. ^[5] Simpler Improvements to overcome unwanted zero terms include an altered recurrence relation ^[6] suggested by Jaaskelainen and Ruuskanen in 1981 or a simple shift of the denominator by a very small number as suggested by Thompson and Barnett in 1986. ^[3]

Initial work

This theory was initially motivated by Lentz's need for accurate calculation of ratios of spherical Bessel function necessary for Mie scattering. He created a new continued fraction algorithm that starts from the beginning of the continued fraction and not at the tail-end. This eliminates guessing how many terms of the continued fraction are needed for convergence. In addition, continued fraction representations for both ratios of Bessel functions and spherical Bessel functions of consecutive order themselves can be computed with Lentz's algorithm. ^[5] The algorithm suggested that it is possible to terminate the evaluation of continued fractions when ${\displaystyle |f_{j}-f_{j-1}|}$ is relatively small. ^[7]

Algorithm

Lentz's algorithm is based on the Wallis-Euler relations. If

${\displaystyle {f}_{0}={b}_{0}}$

${\displaystyle {f}_{1}={b}_{0}+{\frac {{a}_{1}}{{b}_{1}}}}$

${\displaystyle {f}_{2}={b}_{0}+{\frac {{a}_{1}}{{b}_{1}+{\frac {{a}_{2}}{{b}_{2}}}}}}$

${\displaystyle {f}_{3}={b}_{0}+{\frac {{a}_{1}}{{b}_{1}+{\frac {{a}_{2}}{{b}_{2}+{\frac {{a}_{3}}{{b}_{3}}}}}}}}$

etc., or using the big-K notation, if

${\displaystyle {f}_{n}={b}_{0}+{\underset {j=1}{\overset {n}{\operatorname {K} }}}{\frac {{a}_{j}}{{b}_{j}+}}}$

is the ${\displaystyle n}$th convergent to ${\displaystyle f}$ then

${\displaystyle {f}_{n}={\frac {{A}_{n}}{{B}_{n}}}}$

where ${\displaystyle {A}_{n}}$ and ${\displaystyle {B}_{n}}$ are given by the Wallis-Euler recurrence relations

${\displaystyle {\begin{aligned}{A}_{-1}&=1&{B}_{-1}&=0\\{A}_{0}&={b}_{0}&{B}_{0}&=1\\{A}_{n}&={b}_{n}{A}_{n-1}+{a}_{n}{A}_{n-2}&{B}_{n}&={b}_{n}{B}_{n-1}+{a}_{n}{B}_{n-2}\end{aligned}}}$

Lentz's method defines

${\displaystyle {C}_{n}={\frac {{A}_{n}}{{A}_{n-1}}}}$

${\displaystyle {D}_{n}={\frac {{B}_{n-1}}{{B}_{n}}}}$

so that the ${\displaystyle n}$th convergent is ${\displaystyle {f}_{n}={C}_{n}{D}_{n}{f}_{n-1}}$ with ${\displaystyle {f}_{0}={\frac {{A}_{0}}{{B}_{0}}}={b}_{0}}$ and uses the recurrence relations

${\displaystyle {\begin{aligned}{C}_{0}&={\frac {{A}_{0}}{{A}_{-1}}}={b}_{0}&{D}_{0}&={\frac {{B}_{-1}}{{B}_{0}}}=0\\{C}_{n}&={b}_{n}+{\frac {{a}_{n}}{{C}_{n-1}}}&{D}_{n}&={\frac {1}{{b}_{n}+{a}_{n}{D}_{n-1}}}\end{aligned}}}$

When the product ${\displaystyle {C}_{n}{D}_{n}}$ approaches unity with increasing ${\displaystyle n}$, it is hoped that ${\displaystyle {f}_{n}}$ has converged to ${\displaystyle f}$. ^[8]

Lentz's algorithm has the advantage of side-stepping an inconvenience of the Wallis-Euler relations, namely that the numerators ${\displaystyle A_{n}}$ and denominators ${\displaystyle B_{n}}$ are prone to grow or diminish very rapidly with increasing ${\displaystyle n}$. In direct numerical application of the Wallis-Euler relations, this means that ${\displaystyle A_{n-1}}$, ${\displaystyle A_{n-2}}$, ${\displaystyle B_{n-1}}$, ${\displaystyle B_{n-2}}$ must be periodically checked and rescaled to avoid floating-point overflow or underflow. ^[8]

Thompson and Barnett modification

In Lentz's original algorithm, it can happen that ${\displaystyle {C}_{n}=0}$, resulting in division by zero at the next step. The problem can be remedied simply by setting ${\displaystyle {C}_{n}=\varepsilon }$ for some sufficiently small ${\displaystyle \varepsilon }$. This gives ${\displaystyle {C}_{n+1}={b}_{n+1}+{\frac {{a}_{n+1}}{\varepsilon }}={\frac {{a}_{n+1}}{\varepsilon }}}$ to within floating-point precision, and the product ${\displaystyle {C}_{n}{C}_{n+1}={a}_{n+1}}$ irrespective of the precise value of ε. Accordingly, the value of ${\displaystyle {f}_{0}={C}_{0}={b}_{0}}$ is also set to ${\displaystyle \varepsilon }$ in the case of ${\displaystyle {b}_{0}=0}$.

Similarly, if the denominator in ${\displaystyle {D}_{n}={\frac {1}{{b}_{n}+{a}_{n}{D}_{n-1}}}}$ is zero, then setting ${\displaystyle {D}_{n}={\frac {1}{\varepsilon }}}$ for small enough ${\displaystyle \varepsilon }$ gives ${\displaystyle {D}_{n}{D}_{n+1}={\frac {1}{{a}_{n+1}}}}$ irrespective of the value of ${\displaystyle \varepsilon }$. ^{[3] [8]}

Applications

Lentz's algorithm was used widely in the late twentieth century. It was suggested that it doesn't have any rigorous analysis of error propagation. However, a few empirical tests suggest that it's at least as good as the other methods. ^[9] As an example, it was applied to evaluate exponential integral functions. This application was then called modified Lentz algorithm. ^[10] It's also stated that the Lentz algorithm is not applicable for every calculation, and convergence can be quite rapid for some continued fractions and vice versa for others. ^[11]

References

1. Lentz, W. J. (September 1973). A Method of Computing Spherical Bessel Functions of Complex Argument with Tables (PDF) (Research and Development Technical Report ECOM-5509). White Sands Missile Range, New Mexico: Atmospheric Sciences Laboratory, US Army Electronics Command.
2. Numerical Recipes in C++. pp. 177–179. ISBN   0 521 75033 4.
3. Thompson, I.J.; Barnett, A.R. (1986). "Coulomb and Bessel functions of complex arguments and order". Journal of Computational Physics. 64 (2): 490–509. Bibcode:1986JCoPh..64..490T. doi:10.1016/0021-9991(86)90046-x. ISSN   0021-9991.
4. J., Lentz, W. (August 1982). A Simplification of Lentz's Algorithm. Defense Technical Information Center. OCLC   227549426.
5. Lentz, William J. (1976-03-01). "Generating Bessel functions in Mie scattering calculations using continued fractions". Applied Optics. 15 (3): 668–671. Bibcode:1976ApOpt..15..668L. doi:10.1364/ao.15.000668. ISSN   0003-6935. PMID   20165036.
6. Jaaskelainen, T.; Ruuskanen, J. (1981-10-01). "Note on Lentz's algorithm". Applied Optics. 20 (19): 3289–3290. Bibcode:1981ApOpt..20.3289J. doi:10.1364/ao.20.003289. ISSN   0003-6935. PMID   20333144.
7. Masmoudi, Atef; Bouhlel, Med Salim; Puech, William (March 2012). "Image encryption using chaotic standard map and engle continued fractions map". 2012 6th International Conference on Sciences of Electronics, Technologies of Information and Telecommunications (SETIT). IEEE. pp. 474–480. doi:10.1109/setit.2012.6481959. ISBN   978-1-4673-1658-3. S2CID   15380706.
8. Press, W.H.; Teukolsky, S.A.; Vetterling, W.T.; Flannery, B. P. (2007). Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press. pp. 207–208.
9. Press, W.H.; Teukolsky, S.A.; Vetterling, W.T.; Flannery, B. P. (1992). Numerical Recipes in Fortran, The Art of Scientific Computing (2nd ed.). Cambridge University Press. p. 165.
10. Press, William H.; Teukolsky, Saul A. (1988). "Evaluating Continued Fractions and Computing Exponential Integrals". Computers in Physics. 2 (5): 88. Bibcode:1988ComPh...2...88P. doi: 10.1063/1.4822777 . ISSN   0894-1866.
11. Wand, Matt P.; Ormerod, John T. (2012-09-18). "Continued fraction enhancement of Bayesian computing". Stat. 1 (1): 31–41. doi:10.1002/sta4.4. ISSN   2049-1573. PMID   22533111. S2CID   119636237.