Up | Next | Prev | PrevTail | Tail |
Author: Neil Langmead
This package was written when the author was a placement student at ZIB Berlin.
This package arises from the PhD thesis of Dominik Gruntz[Gru96], of the ETH Zürich. He developed a new algorithm to compute limits of "exp-log" functions. Many of the examples he gave were unable to be computed by the present LIMITS package in REDUCE, the simplest example being the following, whose limit is obviously \(0\):
load limits; limit(x^7/e^x,x,infinity); 7 x limit(----,x,infinity) x e
This particular problem arises, because L’Hôpital’s rule for the computation of indefinite forms (such as \(0/0\), or \(\frac {\infty }{\infty }\)) can only be applied in a CAS a finite number of times, and in REDUCE, this number is 3. Appling L’Hôpital’s rule 7 times to the above problem would have yielded the correct answer 0.
The new algorithm solves this particular problem, and enables the computation of many more limit calculations in REDUCE. We first define the domain in which we work, and then give a statement of the main algorithm that is used in this package.
Definition:
Let \(\Re [x]\) be the ring of polynomials in \(x\) with real coefficients, and let \(f\) be an element in this
ring. The field which is obtained from \(\Re [x]\) by closing it under the operations \(f\rightarrow \exp (f)\) and \(f\rightarrow \log |f|\) is called
the \(\mathcal {L}\)-field (or logarithmico-exponential field, or field of exp-log functions for
short).
Hardy proved [Har12] that every \(\mathcal {L}\) function is ultimately continuous, of constant sign,
monotonic, and tends to \(\pm \infty \) or to a finite real constant as \(x\rightarrow +\infty .\)
Here are some examples of exp-log functions, which the package is able to deal with: \begin {align*} f(x) &=e^{x}*\log (\log (x)) \\[2mm] f(x) &=\frac {\log (\log (x+e^{-x}))}{e^{x^{2}}+\log (\log (x))} \\[2mm] f(x) &=\log (x)^{\log (x)} \\[2mm] f(x) &=e^{x*\log (x)} \end {align*}
A complete statement of the algorithm now follows: Let \(f\) be a log-exp function in \(x\), whose limit we wish to compute as \(x\rightarrow x_0.\) The main steps of the algorithm to do this are as follows:
Determine the set \(\Omega \) of the most rapidly varying subexpressions of \(f(x)\). Limits may have to be computed recursively at this stage.
Choose an expression \(\omega \) such that \(\omega >0\), \(\lim _{x \rightarrow \infty } \omega =0 \) and \(\omega \) is in the same comparability class as any element of \(\Omega \). Rewrite the other expressions in \(\Omega \) as \(A(x)\omega ^{c}\), where \(A(x)\) only contains subexpressions in lower comparability classes than \(\Omega \).
Let \(f(\omega )\) be the function obtained from \(f(x)\) by replacing all elements of \(\Omega \) by their representation in terms of \(\omega \). Consider all expressions independent of \(\omega \) as constants and compute the leading term of the power series of f(\(\omega \)) around \(\omega =0^{+}\) as \(c_{0}\omega ^{e_{0}}\).
If the leading exponent \(e_0>0\), then the limit is 0, and we stop. If the leading exponent \(e_0<0\) then the limit is \(\pm \infty \). The sign is defined by the sign of the leading coefficient \(c_0\). If the leading exponent \(e_0=0\) then the limit is the limit of the leading coeficient \(c_0\). If \(c_0\not \in C\), where \(C=\text {Const}(L)\), the set of exp-log constants, we apply the same algorithm recursively on \(c_0\).
The algorithm to compute the most rapidly varying subset (the mrv set) of a function f is given below:
procedure mrv(f)
% f an exp log function in \(x\)
if (not (depend(f,\(x\)))) \(\rightarrow \) return ({})
else if \(f=x \rightarrow \) return({\(x\)})
else if \(f=gh \rightarrow \) return(max(mrv(g),mrv(h)))
else if \(f=g+h \rightarrow \) return(max(mrv(g),mrv(h)))
else if \(f=g^{c}\) and c \(\in C \rightarrow \) return(mrv(g))
else if \(f=\log (g) \rightarrow \) return(mrv(g))
else if \(f=e^{g} \rightarrow \)
if \(\lim _{x \rightarrow \infty } g=\pm \infty \rightarrow \)
return(max({\(e^{g}\)}, mrv(g)))
else \(\rightarrow \) return mrv(g)
end
The function max() computes the maximum of the two sets of expressions. Max() compares two elements of its argument sets and returns the set which is in the higher comparability class or the union of both if they have the same order of variation.
For example, we have \begin {align*} &\text {mrv}(e^{x})=\{e^x\} \\ &\text {mrv}(\log (\log (\log (x+x^2+x^3))))=\{x\} \\ &\text {mrv}(x)=\{x\} \\ &\text {mrv}(e^x+e^{-x}+x^2+x \log (x))= \{e^x,e^{-x} \} \\ &\text {mrv}(e^{e^{-x}})=\{e^{-x} \} \end {align*}
For further details, proofs and explanations of the algorithm, please consult Gruntz’ thesis[Gru96].
Consider the following in REDUCE:
mrv_limit(e^x,x,infinity); infinity mrv_limit(1/log(x),x,infinity); 0 b:=e^x*(e^(1/x-e^-x)-e^(1/x)); -1 - x x + x - e b := e *(e - 1) mrv_limit(b,x,infinity); -1 ex := (log(-log(x)+log(log(x)))-log(log(x))) /(log(log(x)+log(log(log(x)))))*log(x); log(x)*( - log(log(x)) + log(log(log(x)) - log(x))) ex := ----------------------------------------------------- log(log(log(log(x))) + log(x)) mrv_limit(ex,x,infinity); 1 (log(x+e^-x)+log(1/x))/(log(x)*e^x); - x -1 -1 - x e *log(x) *(log(x ) + log(e + x)); mrv_limit(ws,x,infinity); 0 mrv_limit((log(x)*e^-x)/e^(log(x)+e^(x^2)),x,infinity); 0
More examples can be found in the mrvlimit.tst file.
The package provides a means of tracing the mrv_limit function at its main steps, and is intended to help the user if he encounters problems. Messages are displayed informing the user which Taylor expansion is being computed, all recursive calls are listed, and the value returned by the mrv function is given. This information is displayed when a switch trlimit is on.
Note that, due to the recursiveness of the algorithm there is a lot of output when the trlimit switch is on.
Up | Next | Prev | PrevTail | Front |