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

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 11 — La représentation des nombres

Énoncé

Soit la suite définie par $u_{0} = 1$ , $u_{1} = 1/3$ et $u_{n + 1} = \frac{13}{3} u_{n} - \frac{4}{3} u_{n - 1}$ . Expliquer pourquoi le calcul numérique en flottants diverge totalement de la solution mathématique théorique $u_{n} = 3^{- n}$ .

Corrigé

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} = α 3^{- n} + β 4^{n}$ . Les conditions initiales imposent théoriquement $α = 1$ et $β = 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 + δ$ (avec un arrondi $δ \approx 1 0^{- 17}$ ). Cela introduit une composante parasite $β \approx δ \neq = 0$ . Au fil des itérations, le terme exact décroissant $3^{- n}$ tend vers 0, tandis que le terme parasite $β 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 1 0^{- 15}$ ).

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.