Content deleted Content added
Hamish Gary (talk | contribs) mNo edit summary |
m →Algorithm: fix "big K" notation |
||
| (55 intermediate revisions by 19 users not shown) | |||
Line 1:
In mathematics, '''Lentz's
The version usually employed now is due to Thompson and Barnett.<ref name="Thompson-and-Barnett" />
== History ==
The idea was introduced in 1973 by William J. Lentz<ref name=":0" /> and was simplified by him in 1982.<ref>{{Cite book|last=J.|first=Lentz, W.|url=http://worldcat.org/oclc/227549426|title=A Simplification of Lentz's Algorithm.|date=August 1982|publisher=Defense Technical Information Center|oclc=227549426}}</ref> 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.<ref name="Lentz 668–671">{{Cite journal|last=Lentz|first=William J.|date=1976-03-01|title=Generating Bessel functions in Mie scattering calculations using continued fractions|url=http://dx.doi.org/10.1364/ao.15.000668|journal=Applied Optics|volume=15|issue=3|pages=668–671|doi=10.1364/ao.15.000668|pmid=20165036 |bibcode=1976ApOpt..15..668L |issn=0003-6935|url-access=subscription}}</ref> Simpler Improvements to overcome unwanted zero terms include an altered recurrence relation<ref>{{Cite journal|last1=Jaaskelainen|first1=T.|last2=Ruuskanen|first2=J.|date=1981-10-01|title=Note on Lentz's algorithm|url=http://dx.doi.org/10.1364/ao.20.003289|journal=Applied Optics|volume=20|issue=19|pages=3289–3290|doi=10.1364/ao.20.003289|pmid=20333144 |bibcode=1981ApOpt..20.3289J |issn=0003-6935|url-access=subscription}}</ref> 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.<ref name="Thompson-and-Barnett">{{Cite journal|last1=Thompson|first1=I.J.|last2=Barnett|first2=A.R.|date=1986|title=Coulomb and Bessel functions of complex arguments and order|url=http://dx.doi.org/10.1016/0021-9991(86)90046-x|journal=Journal of Computational Physics|volume=64|issue=2|pages=490–509|doi=10.1016/0021-9991(86)90046-x|bibcode=1986JCoPh..64..490T |issn=0021-9991|url-access=subscription}}</ref>
This theory was initially
== Algorithm ==
Lentz's algorithm is based on the [[Wallis-Euler relations]]. If
:<math>{f}_{0} = {b}_{0}</math>
:<math>{f}_{1} = {b}_{0} + \frac{{a}_{1}}{{b}_{1}}</math>
:<math>{f}_{2} = {b}_{0} + \frac{{a}_{1}}{{b}_{1} + \frac{{a}_{2}}{{b}_{2}}}</math>
:<math>{f}_{3} = {b}_{0} + \frac{{a}_{1}}{{b}_{1} + \frac{{a}_{2}}{{b}_{2} + \frac{{a}_{3}}{{b}_{3}}}}</math>
etc., or using the [[Generalized continued fraction#Notation|big-K notation]], if
:<math>{f}_{n} = {b}_{0} + \underset{j = 1}\overset{n}\operatorname{K}\frac{{a}_{j}}{{b}_{j}}</math>
is the <math>n</math>th convergent to <math>f</math> then
:<math>{f}_{n} = \frac{{A}_{n}}{{B}_{n}}</math>
where <math>{A}_{n}</math> and <math>{B}_{n}</math> are given by the Wallis-Euler recurrence relations
:<math>
\begin{align}
{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{align}
</math>
Lentz's method defines
:<math>{C}_{n} = \frac{{A}_{n}}{{A}_{n - 1}}</math>
:<math>{D}_{n} = \frac{{B}_{n - 1}}{{B}_{n}}</math>
so that the <math>n</math>th convergent is <math>{f}_{n} = {C}_{n} {D}_{n} {f}_{n - 1}</math> with <math>{f}_{0} = \frac{{A}_{0}}{{B}_{0}} = {b}_{0}</math> and uses the recurrence relations
:<math>
\begin{align}
{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{align}
</math>
When the product <math>{C}_{n} {D}_{n}</math> approaches unity with increasing <math>n</math>, it is hoped that <math>{f}_{n}</math> has converged to <math>f</math>.<ref name="Numerical-Recipes">{{Cite book |last1=Press |first1=W.H. |title=Numerical Recipes: The Art of Scientific Computing |last2=Teukolsky |first2=S.A. |last3=Vetterling |first3=W.T. |last4=Flannery |first4=B. P. |publisher=Cambridge University Press |year=2007 |edition=3rd |pages=207–208}}</ref>
Lentz's algorithm has the advantage of side-stepping an inconvenience of the Wallis-Euler relations, namely that the numerators <math>A_n</math> and denominators <math>B_n</math> are prone to grow or diminish very rapidly with increasing <math>n</math>. In direct numerical application of the Wallis-Euler relations, this means that <math>A_{n-1}</math>, <math>A_{n-2}</math>, <math>B_{n-1}</math>, <math>B_{n-2}</math> must be periodically checked and rescaled to avoid floating-point overflow or underflow.<ref name="Numerical-Recipes" />
== Thompson and Barnett modification ==
In Lentz's original algorithm, it can happen that <math>{C}_{n} = 0</math>, resulting in division by zero at the next step. The problem can be remedied simply by setting <math>{C}_{n} = \varepsilon</math> for some sufficiently small <math>\varepsilon</math>. This gives <math>{C}_{n + 1} = {b}_{n + 1} + \frac{{a}_{n + 1}}{\varepsilon} = \frac{{a}_{n + 1}}{\varepsilon}</math> to within floating-point precision, and the product <math>{C}_{n} {C}_{n + 1} = {a}_{n + 1}</math> irrespective of the precise value of ε. Accordingly, the value of <math>{f}_{0} = {C}_{0} = {b}_{0}</math> is also set to <math>\varepsilon</math> in the case of <math>{b}_{0} = 0</math>.
Similarly, if the denominator in <math>{D}_{n} = \frac{1}{{b}_{n} + {a}_{n} {D}_{n - 1}}</math> is zero, then setting <math>{D}_{n} = \frac{1}{\varepsilon}</math> for small enough <math>\varepsilon</math> gives <math>{D}_{n} {D}_{n + 1} = \frac{1}{{a}_{n + 1}}</math> irrespective of the value of <math>\varepsilon</math>.<ref name="Thompson-and-Barnett" /><ref name="Numerical-Recipes" />
▲== Initial Working ==
▲This theory was initially implemented in Lentz's another research when he calculated ratios of Bessel function necessary for [[Mie scattering]]. He demonstrated that the algorithm uses a technique involving the evaluation continued fractions that starts from the beginning and not at the tail. In addition, that continued fraction representations for both ratios of Bessel functions and spherical Bessel functions of consecutive order can be presented with the Lentz algorithm<ref>{{Cite journal|last=Lentz|first=William J.|date=1976-03-01|title=Generating Bessel functions in Mie scattering calculations using continued fractions|url=http://dx.doi.org/10.1364/ao.15.000668|journal=Applied Optics|volume=15|issue=3|pages=668|doi=10.1364/ao.15.000668|issn=0003-6935}}</ref>. The algorithm suggested that it is possible to terminate the evaluation of continued fractions when <math>|f_j-f_(j-1) |</math> is relatively small<ref>{{Cite journal|last=Masmoudi|first=Atef|last2=Bouhlel|first2=Med Salim|last3=Puech|first3=William|date=2012-03|title=Image encryption using chaotic standard map and engle continued fractions map|url=http://dx.doi.org/10.1109/setit.2012.6481959|journal=2012 6th International Conference on Sciences of Electronics, Technologies of Information and Telecommunications (SETIT)|publisher=IEEE|doi=10.1109/setit.2012.6481959}}</ref>.
== Applications ==
Lentz's algorithm was used widely in the late
==References==
{{reflist}}
| |||