4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – smh Jan 11 at 13:39
10
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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?

enter image description here

$\endgroup$
  • $\begingroup$ yes that's a good example ! thanks $\endgroup$ – Smilia Jan 11 at 22:02

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.