6
$\begingroup$

This is going to a longish question, so the short version first: Is there a way to sanity-check which solution to the 3-term recurrence relation an application of Miller's algorithm has converged on?

Background: this stems from some work I've been doing to implement hypergeometric functions as part of Boost.Math's special functions. I have $_1F_1$ functional over most of it's domain, if currently inefficient in places (but I know how to fix that). There is one domain that's causing me particular difficulty, and that's $_1F_1(a,-b;z)$. This is mostly fixable using Tricomi's expansions in terms of Bessel functions (A&S 13.3.7 is a somewhat simplified version of these). However, there are values where these expansions fail - either because $J_v(x)$ or $I_v(x)$ over/underflow or because the series is too divergent to be numerically stable. One workaround is to calculate $_1F_1(a,-b;z) / _1F_1(a,-b-1;z)$ and then normalise via one of the Wronksians - the net effect of which is to map $_1F_1(a,-b,z)$ to $_1F_1(1+a+b, 2+b; z)$ which is relatively easy to compute.

The ratio is computed via Millers algorithm: which is to say if $F_n(x)$ tends to 0 for infinite N (and a bunch of other conditions too:) ) then backwards recurrence, starting with 2 arbitrary seed values (0 and 1 by convention) will rapidly converge on the true ratio. However, as formulated by Miller you have to know in advance how many recurrences to evaluate in advance. Shintan and later Gauchi pointed out that the process of applying the recurrences without knowing how many you will need is an identical problem to that of evaluating a continued fraction. So for every function with a 3 term recurrence relation, there is a matching continued fraction which will calculate the minimal solution for the ratio if it exists.

Observations: I've only seen the method formulated for stable backwards recurrences, but it does actually work in the opposite direction too: for example by applying forward recurrences for ratios of $Y_v(x)/Y_{v-1}(x)$ or $K_v(x)/K_{v-1}(x)$. The catch being that these are only locally converging on zero as v->0, and in any case you must not cross the origin during the evaluation.

Now for the actual issue: the direction of stability of recurrence relations in 1F1 is constantly shifting, in the case of $_1F_1(a,-b; z)$ and $b >> z$ then backwards recursion is stable and a traditional Miller-like algorithm works a treat. However, as b decreases in value the function reaches a minima, then begins to alternate in sign and increase in magnitude with forward recursion being stable. As long as you're sufficiently far from the transition region, a Miller-like-algorithm with forward recurrence works well. In both cases convergence is super-fast, typically 10 or so iterations for double precision, so IMO the algorithms are worth pursuing. Finally the direction of stability changes again at the origin - but I'm not so concerned about that as other evaluation methods are available there.

The problem is that there seems to be no way tell where the transition from stable-backwards to stable-forwards recursion will occur (at least not directly from the recurrence relations). Further both the forwards and backwards continued fractions for the ratios always converge rapidly, and always to a result that is consistent with the recurrence relations, even when they used in a domain where they would be unstable for $_1F_1$. So the problem is that the result they converge to is not $_1F_1$ but some other solution when used outside their "safe" domains.

If I had some way to sanity check the result, I could spot pretty quickly whether I had strayed into a problem domain and switch to another method, but at present I don't see any way. In any case I'm hoping someone here will have a brainwave on the issue.

Oh, and yes, I've checked recursion on the $a$ parameter too and it exhibits the same behaviour as recursion on $b$. Don't even mention recursion on both a and b as it's rarely stable in either direction.

Many thanks for reading this far... !

$\endgroup$
  • $\begingroup$ I believe the convergence behaviour in various directions is analysed in Numerical Methods for Special Functions by A. Gil, J. Segura & N. M. Temme (SIAM, 2008), Chapter 4.5.1, Example 4.9, and the anomalous behaviour is also briefly mentioned in Chapter 4.8.2. Not sure if helpful, but it is a great book. $\endgroup$ – student Jan 11 at 16:32
2
$\begingroup$

Apparently I'm not allowed to post comments, but: in case you haven't yet, maybe try having a look at Wimp's book (Computation with Recurrence Relations, Pitman, 1984).

$\endgroup$
  • $\begingroup$ I couldn't find a local copy of that one, but it led to the 2007 paper: TRANSITORY MINIMAL SOLUTIONS OF HYPERGEOMETRIC RECURSIONS AND PSEUDOCONVERGENCE OF ASSOCIATED CONTINUED FRACTIONS by DEANO and SEGURA which covers some of this in gory detail. Much of what I take from their paper is "be careful!" which I'd sort of spotted already :) 'tis a very complex function. $\endgroup$ – John Maddock Jan 11 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.