L'algorithme déstabilisé — la suite piégée

L'équation caractéristique associée à la récurrence admet pour racines $r_1=1/3$ et $r_2=4$. La solution générale s'écrit $u_n=\alpha 3^{-n}+\beta 4^n$. Les conditions initiales imposent théoriquement $\alpha =1$ et $\beta =0$. Or, le terme $1/3$ n'est pas représentable de façon exacte en flottant. En machine, la valeur de départ $u_1$ s'écrit $1/3+\delta$ (avec un arrondi $\delta \approx 10^{-17}$). Cela introduit une composante parasite $\beta \approx \delta \ne 0$. Au fil des itérations, le terme exact décroissant $3^{-n}$ tend vers 0, tandis que le terme parasite $\beta 4^n$ est multiplié par 4 à chaque étape. Dès le rang $n\approx 15$, la composante parasite écrase la solution exacte, conduisant à des résultats totalement erronés (ex: $u_{30}\approx -14$ au lieu de $\approx 5\cdot 10^{-15}$).