Lentz's algorithm

Last updated January 30, 2023

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

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.^[7] The algorithm suggested that it is possible to terminate the evaluation of continued fractions when $|f_{j}-f_{j-1}|$ is relatively small.^[8]

Algorithm

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

{f}_{0}={b}_{0}

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

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

{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

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

is the $n$ th convergent to $f$ then

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

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

{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}

Lentz's method defines

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

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

so that the $n$ th convergent is

{f}_{n}={C}_{n}{D}_{n}{f}_{n-1}

and uses the recurrence relations

{C}_{0}={\frac {{A}_{0}}{{A}_{-1}}}={b}_{0}

{D}_{0}={\frac {{B}_{-1}}{{B}_{0}}}=0

{f}_{0}={b}_{0}

{C}_{n}={b}_{n}+{\frac {{a}_{n}}{{C}_{n-1}}}

{D}_{n}={\frac {1}{{b}_{n}+{a}_{n}{D}_{n-1}}}

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

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. ^[10]As an example, it was applied to evaluate exponential integral functions. This application was then called modified Lentz algorithm.^[11] 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.^[12]

Related Research Articles

Bessel functions, first defined by the mathematician Daniel Bernoulli and then generalized by Friedrich Bessel, are canonical solutions $y (x)$ of Bessel's differential equation

In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers x, y, the greatest common divisor of x and y is denoted $. For example, the GCD of 8 and 12 is 4, that is, .$

The Gauss–Legendre algorithm is an algorithm to compute the digits of $π$ . It is notable for being rapidly convergent, with only 25 iterations producing 45 million correct digits of $π$ . However, it has some drawbacks and therefore all record-breaking calculations for many years have used other methods, almost always the Chudnovsky algorithm. For details, see Chronology of computation of $π$ .

In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number $x$ to the base $b$ is the exponent to which $b$ must be raised, to produce $x$ . For example, since $1000 = 10 3$ , the logarithm base 10 of $1000$ is $3$ , or $log 10 (1000) = 3$ . The logarithm of $x$ to base $b$ is denoted as $log b (x)$ , or without parentheses, $log b x$ , or even without the explicit base, $log x$ , when no confusion is possible, or when the base does not matter such as in big O notation.

The number $π$ is a mathematical constant that is the ratio of a circle's circumference to its diameter, approximately equal to 3.14159. The number $π$ appears in many formulas across mathematics and physics. It is an irrational number, meaning that it cannot be expressed exactly as a ratio of two integers, although fractions such as $are commonly used to approximate it. Consequently, its decimal representation never ends, nor enters a permanently repeating pattern. It is a transcendental number, meaning that it cannot be a solution of an equation involving only sums, products, powers, and integers. The transcendence of π implies that it is impossible to solve the ancient challenge of squaring the circle with a compass and straightedge. The decimal digits of π appear to be randomly distributed, but no proof of this conjecture has been found.$

In geometry, a solid angle is a measure of the amount of the field of view from some particular point that a given object covers. That is, it is a measure of how large the object appears to an observer looking from that point. The point from which the object is viewed is called the apex of the solid angle, and the object is said to subtend its solid angle at that point.

In mathematics, a recurrence relation is an equation according to which the $th term of a sequence of numbers is equal to some combination of the previous terms. Often, only previous terms of the sequence appear in the equation, for a parameter that is independent of; this number is called the order of the relation. If the values of the first numbers in the sequence have been given, the rest of the sequence can be calculated by repeatedly applying the equation.$

In mathematics, a generalized hypergeometric series is a power series in which the ratio of successive coefficients indexed by n is a rational function of n. The series, if convergent, defines a generalized hypergeometric function, which may then be defined over a wider domain of the argument by analytic continuation. The generalized hypergeometric series is sometimes just called the hypergeometric series, though this term also sometimes just refers to the Gaussian hypergeometric series. Generalized hypergeometric functions include the (Gaussian) hypergeometric function and the confluent hypergeometric function as special cases, which in turn have many particular special functions as special cases, such as elementary functions, Bessel functions, and the classical orthogonal polynomials.

In mathematics, the regula falsi, method of false position, or false position method is a very old method for solving an equation with one unknown; this method, in modified form, is still in use. In simple terms, the method is the trial and error technique of using test ("false") values for the variable and then adjusting the test value according to the outcome. This is sometimes also referred to as "guess and check". Versions of the method predate the advent of algebra and the use of equations.

In complex analysis, a branch of mathematics, a generalized continued fraction is a generalization of regular continued fractions in canonical form, in which the partial numerators and partial denominators can assume arbitrary complex values.

In machine learning, backpropagation is a widely used algorithm for training feedforward artificial neural networks. Generalizations of backpropagation exist for other artificial neural networks (ANNs), and for functions generally. These classes of algorithms are all referred to generically as "backpropagation". In fitting a neural network, backpropagation computes the gradient of the loss function with respect to the weights of the network for a single input–output example, and does so efficiently, unlike a naive direct computation of the gradient with respect to each weight individually. This efficiency makes it feasible to use gradient methods for training multilayer networks, updating weights to minimize loss; gradient descent, or variants such as stochastic gradient descent, are commonly used. The backpropagation algorithm works by computing the gradient of the loss function with respect to each weight by the chain rule, computing the gradient one layer at a time, iterating backward from the last layer to avoid redundant calculations of intermediate terms in the chain rule; this is an example of dynamic programming.

In mathematics, the Hankel transform expresses any given function f(r) as the weighted sum of an infinite number of Bessel functions of the first kind $J ν (kr)$ . The Bessel functions in the sum are all of the same order ν, but differ in a scaling factor k along the r axis. The necessary coefficient $F ν$ of each Bessel function in the sum, as a function of the scaling factor k constitutes the transformed function. The Hankel transform is an integral transform and was first developed by the mathematician Hermann Hankel. It is also known as the Fourier–Bessel transform. Just as the Fourier transform for an infinite interval is related to the Fourier series over a finite interval, so the Hankel transform over an infinite interval is related to the Fourier–Bessel series over a finite interval.

Methods of computing square roots are numerical analysis algorithms for approximating the principal, or non-negative, square root of a real number. Arithmetically, it means given $, a procedure for finding a number which when multiplied by itself, yields; algebraically, it means a procedure for finding the non-negative root of the equation; geometrically, it means given two line segments, a procedure for constructing their geometric mean.$

<span class="mw-page-title-main">Padé approximant</span> Best approximation of a function by a rational function of given order

In mathematics, a Padé approximant is the "best" approximation of a function near a specific point by a rational function of given order. Under this technique, the approximant's power series agrees with the power series of the function it is approximating. The technique was developed around 1890 by Henri Padé, but goes back to Georg Frobenius, who introduced the idea and investigated the features of rational approximations of power series.

Approximations for the mathematical constant pi in the history of mathematics reached an accuracy within 0.04% of the true value before the beginning of the Common Era. In Chinese mathematics, this was improved to approximations correct to what corresponds to about seven decimal digits by the 5th century.

In mathematics, Fourier–Bessel series is a particular kind of generalized Fourier series based on Bessel functions.

In mathematical analysis, the Bessel–Clifford function, named after Friedrich Bessel and William Kingdon Clifford, is an entire function of two complex variables that can be used to provide an alternative development of the theory of Bessel functions. If

<span class="mw-page-title-main">Padé table</span>

In complex analysis, a Padé table is an array, possibly of infinite extent, of the rational Padé approximants

<span class="mw-page-title-main">Geographical distance</span> Distance measured along the surface of the earth

Geographical distance or geodetic distance is the distance measured along the surface of the earth. The formulae in this article calculate distances between points which are defined by geographical coordinates in terms of latitude and longitude. This distance is an element in solving the second (inverse) geodetic problem.

In mathematics, the FEE method, or fast E-function evaluation method, is the method of fast summation of series of a special form. It was constructed in 1990 by Ekaterina Karatsuba and is so-named because it makes fast computations of the Siegel $E$ -functions possible, in particular of $.$

References

1 2 Lentz, W. J. (1973-09-01). "A Method of Computing Spherical Bessel Functions of Complex Argument with Tables". Fort Belvoir, VA. doi:10.21236/ad0767223.{{cite journal}}: Cite journal requires |journal= (help)
↑ Numerical Receipes in C++ page 177-179 ISBN 0 521 75033 4.
1 2 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.
↑ J., Lentz, W. (August 1982). A Simplification of Lentz's Algorithm. Defense Technical Information Center. OCLC 227549426.
↑ 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.
↑ 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.
↑ 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.
↑ 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: 474–480. doi:10.1109/setit.2012.6481959. ISBN 978-1-4673-1658-3. S2CID 15380706.
↑ 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.
↑ 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.
↑ 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.
↑ 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.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:0-1] 1 2 Lentz, W. J. (1973-09-01). "A Method of Computing Spherical Bessel Functions of Complex Argument with Tables". Fort Belvoir, VA. doi:10.21236/ad0767223.{{cite journal}}: Cite journal requires |journal= (help)

[2] Numerical Receipes in C++ page 177-179 ISBN 0 521 75033 4.

[:1-3] 1 2 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] 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.

[8] 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: 474–480. doi:10.1109/setit.2012.6481959. ISBN 978-1-4673-1658-3. S2CID 15380706.

[9] 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.

[10] 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.

[11] 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.

[12] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]