# Analytical convergent sequence and numerical divergent sequence

Is it possible to construct a sequence that converges in theory but when computed numerically with a computer program is diverging.

I feel that today our computer programs doesn't allow such pathological cases so I think I might found such pathological sequence working in simple precision.

Of course I want to avoid the case of overflows.

Finally, what would be an ill-conditioned sequence ? I have some examples about ode, matrix, ... but does there exist an ill-conditioned notion for sequences (defined by a recurrence relation) ?

• You might want to look at Kahan summation, which is a simple summation algorithm which can significantly reduce the effects of numerical errors. See en.wikipedia.org/wiki/Kahan_summation_algorithm
– smh
Jan 11, 2019 at 13:39

Jean-Michel Muller, et. al., "Handbook of Floating-Point Arithmetic 2nd ed.", Birkhäuser 2018, gives the following example due to Muller, specifically constructed to deliver incorrect results with floating-point evaluation:

$${u_{0} = 2,\\ u_{1} = -4,\\ u_{n} = 111 - \frac{1130}{u_{n-1}} + \frac{3000}{u_{n-1}u_{n-2}},\>\>\>\>n \ge 2.}$$

Mathematically, this sequence converges to $$6$$. However, evaluated numerically it appears to approach $$100$$.

Paul Zimmermann, et. al. "Computational Mathematics with SageMath", SIAM 2018, gives the following example due to Marc Deléglise:

$${ u_{0} = \frac{1}{3},\\ u_{n+1} = 4u_{n}-1 }$$

Mathematically, this sequence is stationary, but evaluated in floating-point arithmetic it diverges to $$-\infty$$.

In my opinion, an example could be the calculation of the minimal solution of a three term recurrence relation (TTRR) $$y_{n+1} +a_{n}y_{n}+b_{n}y_{n-1} = 0, \quad n=1,2,3,\ldots$$.

For example, the Bessel $$J_{n}(x)$$ function for a fixed $$x$$ satisfies the TTRR $$y_{n+1}-\frac{2n}{x}y_{n}+y_{n-1} = 0$$ Suppose you know $$y_{0} = J_{0}(1)$$ and $$y_{1} = J_{1}(1)$$ and you wish to calculate $$y_{100} = J_{100}(1)$$ by just applying the TTRR in the forward direction (i.e. increasing $$n$$), you will see that in finite precision arithmetic your solution will be perturbed by the smallest round-off error and instead of a decreasing function, you will notice an increasing function. See the figure below for the relative error between $$J_n(1)$$ calculated using the increasing TTRR and the exact value using state-of-the-art algorithms. Even if you would do this in fixed precision using a very high precision you will always run into trouble for high $$n$$.

Would this be an example of what you are looking for? 