Analytical convergent sequence and numerical divergent sequence

Question

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) ?

Answer 1

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$.

Answer 2

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?