# Accelerating convergence of a generalized continued fraction

I wish to compute

$$\frac{1}{1 + \frac{1^3}{1 + \frac{2^3}{1 + \frac{3^3}{1+\cdots} } } }$$ to high accuracy. To start, I tried computing $$\frac{1}{1 + \frac{1^2}{1 + \frac{2^2}{1 + \frac{3^2}{1+\cdots} } } }$$ whose limit ($$\ln(2)$$) was known to Euler. Using the modified Lentz's method, I found that increasing the number of partial numerators used in the calculation by an order of gave me roughly one additional decimal digits, so (for example) computing this to an accuracy of 100 digits is completely intractable.

Is there a method to accelerate the convergence of these slowly convergent continued fractions?

• Compensated addition might help. – Richard Jul 9 '20 at 12:35
• I would start with the techniques listed in the DLMF (dlmf.nist.gov/3.9), especially the ones implemented in mpmath.org/doc/current/calculus/sums_limits.html, but there isn't a guarantee that any of them will work. – Kirill Jul 9 '20 at 13:35
• @Richard: I'm using MPFR; but I think your suggestion would indeed be helpful at lower precisions. – user14717 Jul 9 '20 at 16:49
• Lentz-Thompson-Barnett converts the CF into a product, so @Richard's suggestion is not immediately applicable. Using Steed's method might work with that proposal, but be careful. – J. M. Jul 10 '20 at 4:50

The series that converges to $$\ln(2)$$ appears to be suitable for Cohen-Villegas-Zagier acceleration [PDF]. This is an acceleration technique for alternating series, but continued fractions with positive partial numerators and denominators are equivalent to alternating series.

In particular, if $$S_m$$ is the $$m$$-th continued fraction approximant, then let

$$d_n=\sum_{m=1}^n \frac{n}{n+m}{n+m\choose2m}2^{2m}$$

and if certain conditions are met, the accelerated sequence

$$\tilde{S}_n=\frac{1}{d_n}\sum_{m=1}^n \frac{n}{n+m}{n+m\choose2m}2^{2m} S_m$$

converges geometrically at the rate $$5.828^{-n}$$.

It is possible to compute the acceleration coefficients "on the fly" with $$O(1)$$ storage and sum the accelerated series term by term while computing the continued fraction approximants using Lentz's method. Using $$n=131$$ appears to be sufficient to compute $$\ln(2)$$ to 100 decimal digits.

However, using this technique to compute the other series,

$$\frac{1}{1+}\frac{1^3}{1+}\frac{2^3}{1+}\frac{3^3}{1+}\ldots$$

does not appear to deliver geometric convergence.

In fact, I suspect this series may not converge at all. Plotting successive approximants of this series suggests the even and odd approximants may approach different limits.

According to Theorem 4.7 in the 2016 Continued Fractions course notes by Gautam Gopal Krishnan, a continued fraction $$a_0 + \frac{1}{a_1+}\frac{1}{a_2+}\ldots$$ can be rewritten as a series:

$$a_0 + \sum_{n=1}^\infty \frac{(-1)^{n-1}}{q_n q_{n-1}}$$

where $$q_n$$ is given by Theorem 2.4 in the same notes as

$$\begin{eqnarray*} q_0 & = & 1 \\ q_1 & = & a_1 \\ q_n & = & a_n q_{n-1} + q_{n-2} \end{eqnarray*}$$

Maybe the series has better convergence properties in your case?

Disclaimer: I have not verified the theorem, so you should test it numerically to be sure! If I understand the notation by Krishnan correctly, the continued fratcion and the series are always identical if truncated at the same position $$n$$ (the theorem is stated only for finite continued fractions).

• Isn't this only for simple continued fractions? Mine is a generalized continued fraction. – user14717 Jul 9 '20 at 16:50
• Oh yes. I did not notice that your denominator changes in each step, albeit it is not of the most generalized from. Did you search for a similar formula for non-simple continued fractions? If you find one, please let us know. – cdalitz Jul 9 '20 at 17:30
• @user and cdalitz: one can always perform an equivalence transformation such that your CF's partial numerators or partial denominators are unity; see e.g. Waadeland/Lorentzen, among other standard references. Having done that, you can now easily construct the Euler-Minding series described in this answer (see again Waadeland/Lorentzen), but it is my own experience that the resulting series is often not easily accelerated by usual methods like Shanks/Wynn or Levin. – J. M. Jul 10 '20 at 4:48
• (As an aside, I detest the term "generalized continued fraction", but it is quite unfortunately standard.) – J. M. Jul 10 '20 at 4:52