226 Suites vectorielles et réelles définies par une relation de récurrence $u_{n + 1} = f (u_{n})$ . Exemples. Applications à la résolution approchée d’équations.

Suites vectorielles et réelles définies par une relation de récurrence $u_{n + 1} = f (u_{n})$ . Exemples. Applications à la résolution approchée d’équations.

analysis

Suites récurrentes

Définition et premières propriétés

[DAN]
p. 145

Définition 1. Soit $E$ un ensemble. On dit qu’une suite $(u_{n})$ d’éléments de $E$ est récurrente d’ordre $h \in N^{*}$ si on peut écrire $\forall n \geq h, u_{n + h} = f (u_{n - 1}, \dots, u_{n - h}) (*)$ où $f : E^{h} \to E$ et les premières valeurs $u_{0}, \dots, u_{h - 1} \in E$ étant donnés.

Exemple 2. On considère la suite numérique $(u_{n})$ définie par $⎩ ⎨ ⎧ u_{0} = 0 u_{1} = - 1 \forall n \in N, u_{n + 2} = 5 u_{n + 1} - 6 u_{n}$ et on a, $\forall n \in N, u_{n} = 2^{n} - 3^{n}$

[GOU20]
p. 206

Exemple 3. On considère les suite numérique $(u_{n})$ et $(v_{n})$ définies par ${u_{0} \geq 0 \forall n \in N, u_{n + 1} = \frac{1 + u _{n}}{2} et \forall n \in N, v_{n} = k = 0 \prod n u_{k}$ Alors, pour $u_{0} = cos (θ)$ , on a $\forall n \in N, v_{n} = k = 1 \prod n cos (\frac{θ}{2 ^{k}}) = \frac{sin ( θ )}{2 ^{n} sin ( \frac{θ}{2 ^{n}} )}$ donc $n \to + \infty lim v_{n} = \frac{sin ( θ )}{θ}$

Application 4 (Formule de Viète). $\frac{2}{π} = \frac{1}{2} \times \frac{1}{2} + \frac{1}{2} \frac{1}{2} \times \dots$

[FGN3]
p. 160

Exemple 5. La suite de fonctions polynômiales $(P_{n})$ définie par récurrence par : $P_{0} : z \mapsto 1, P_{1} : z \mapsto z, et \forall n \geq 1, z P_{n} : z \mapsto P_{n - 1} (z) - P_{n + 1} (z)$ est une suite bornée si et seulement si $z = \pm 1$ .

[I-P]
p. 116

Théorème 6. Soit $(E, d)$ un espace métrique compact. Soit $(u_{n})$ une suite de $E$ telle que $d (u_{n}, u_{n - 1}) ⟶ 0$ . Alors l’ensemble $Γ$ des valeurs d’adhérence de $(u_{n})$ est connexe.

Corollaire 7 (Lemme de la grenouille). Soient $f : [0, 1] \to [0, 1]$ continue et $(x_{n})$ une suite de $[0, 1]$ telle que ${x_{0} \in [0, 1] x_{n + 1} = f (x_{n})$ Alors $(x_{n})$ converge si et seulement si $lim_{n \to + \infty} x_{n + 1} - x_{n} = 0$ .

Récurrences classiques

[GOU20]
p. 201

Soit $K = R$ ou $C$ . On fixe $(u_{n})$ une suite récurrente d’ordre $1$ définie par $u_{n + 1} = f (u_{n})$ où $f : K \to K$ .

Définition 8.

Si $f$ est une translation (ie. $f$ est de la forme $f : x \mapsto x + b$ où $b \in K$ ), alors $(u_{n})$ est une suite arithmétique de raison $b$ .
Si $f$ est linéaire (ie. $f$ est de la forme $f : x \mapsto a x$ où $a \in K$ ), alors $(u_{n})$ est une suite géométrique de raison $a$ .
Si $f$ est affine (ie. $f$ est de la forme $f : x \mapsto a x + b$ où $a, b \in K$ ), alors $(u_{n})$ est une suite arithmético-géométrique.
Si $f$ est homographique (ie. $f$ est de la forme $f : x \mapsto \frac{a x + b}{c x + d}$ où $a$ , $b$ , $c$ , $d \in E$ et $a d - b c \neq = 0$ ), alors $(u_{n})$ vérifie une récurrence homographique.

Proposition 9.

Si $(u_{n})$ est arithmétique de raison $b$ , alors $\forall n \in N$ , $u_{n} = u_{0} + nb$ .
Si $(u_{n})$ est géométrique de raison $a$ , alors $\forall n \in N$ , $u_{n} = a^{n} u_{0}$ .
Si $(u_{n})$ est arithmético-géométrique et si $1 - a \neq = 0$ , en posant $r = (1 - a)^{- 1} b$ , on a $\forall n \in N$ , $u_{n} = a^{n} (u_{0} - r) + r$ .

Proposition 10. Supposons que $(u_{n})$ vérifie une récurrence homographique. On considère l’équation $f (x) = x ⟺ c x^{2} - (a - d) x - b = 0 (E)$ Alors :

Si $(E)$ admet deux racines distinctes $r_{1}$ et $r_{2}$ , on a $\forall n \in N$ , $\frac{u _{n} - r _{1}}{u _{n} - r _{2}} = k^{n} \frac{u _{0} - r _{1}}{u _{0} - r _{2}}$ où $k = \frac{a - r _{1} c}{a - r _{2} c}$ .
Si $(E)$ admet une racine double $r$ , on a $\forall n \in N$ , $\frac{1}{u _{n} - r} = \frac{1}{u _{0} - r} + kn$ où $k = \frac{c}{a - rc}$ .

Remarque 11. Ces formules permettent de décider s’il existe un rang $n$ tel que le dénominateur de $f$ s’annule, auquel cas les termes ultérieurs de la suite ne sont pas définis.

Exemple 12. Pour la relation $u_{n + 1} = \frac{2 u _{n} + 1}{u _{n} + 2}$ , l’équation $(E)$ admet $\pm 1$ pour solutions, donc $\frac{u _{n} + 1}{u _{n} - 1} = 3^{n} \frac{u _{0} + 1}{u _{0} - 1}$ .

Suites récurrentes vectorielles

[GOU21]
p. 153

Proposition 13 (Déterminant circulant). Soient $n \in N^{*}$ et $a_{1}, \dots, a_{n} \in C$ . On pose $ω = e^{\frac{2 iπ}{n}}$ . Alors $a_{0} a_{n - 1} ⋮ a_{1} a_{1} a_{0} ⋮ a_{2} \dots \dots ⋱ \dots a_{n - 1} a_{n - 2} ⋮ a_{0} = j = 0 \prod n - 1 P (ω^{j})$ où $P = \sum_{k = 0}^{n - 1} a_{k} X^{k}$ .

[I-P]
p. 389

suite-de-polygones

Application 14 (Suite de polygones). Soit $P_{0}$ un polygone dont les sommets sont ${z_{0, 1}, \dots, z_{0, n}}$ . On définit la suite de polygones $(P_{k})$ par récurrence en disant que, pour tout $k \in N^{*}$ , les sommets de $P_{k + 1}$ sont les milieux des arêtes de $P_{k}$ .

Alors la suite $(P_{k})$ converge vers l’isobarycentre de $P_{0}$ .

Outils pour étudier les suites récurrentes

Stabilité de l’intervalle et continuité

[AMR11]
p. 38

Soient $I \subseteq R$ un intervalle de $R$ . On fixe $(u_{n})$ une suite récurrente d’ordre $1$ définie par $u_{n + 1} = f (u_{n})$ où $f : I \to R$ .

Théorème 15 (Caractérisation séquentielle de la continuité). En reprenant les notations précédentes, une fonction $g : I \to R$ est continue si et seulement si pour toute suite réelle convergente $(v_{n}) \in I^{N}$ dont on note $ℓ$ la limite, $g (v_{n}) ⟶_{n \to + \infty} ℓ$ .

Corollaire 16. Si une suite récurrente d’ordre $1$ (dont on note $f$ la fonction) converge vers $ℓ$ , alors $f (ℓ) = ℓ$ .

Exemple 17. La suite $(u_{n})$ définie par $u_{0} \in [- \frac{π}{2}, \frac{π}{2}]$ et $\forall n \geq 1, u_{n + 1} = sin (u_{n})$ converge vers $0$ .

[GOU20]
p. 200

Proposition 18.

Si $f$ est croissante, alors $(u_{n})$ est monotone et son sens de monotonie est donnée par le signe de $u_{1} - u_{0}$ .
Si $f$ est décroissante, alors $(u_{2 n})$ et $(u_{2 n + 1})$ sont monotones et leur sens de monotonie est opposé.

Exemple 19. La suite réelle $(u_{n})$ définie par récurrence par : $u_{0} \in [0, 1 [et \forall n \geq 0, u_{n + 1} = \frac{1}{2 - u _{n}}$ est une suite qui converge vers $1$ .

Équation caractéristique

Définition 20. Une suite $(u_{n})$ à valeurs dans $C$ vérifie une récurrence linéaire homogène d’ordre $h$ si $\forall n \in N, u_{n + h} = a_{h - 1} u_{n + h - 1} + \dots + a_{0} u_{0} (*)$ où $a_{1}, \dots, a_{h} \in C$ .

Proposition 21. Si on note $r_{1}, \dots, r_{q}$ les racines du polynôme caractéristique de $(*)$ (de multiplicités respectives $α_{1}, \dots, α_{q}$ ), alors l’ensemble des suites vérifiant $(*)$ est l’ensemble des suites $(u_{n})$ telles que : $u_{n} = P_{1} (n) r_{1}^{n} + \dots + P_{q} (n) r_{q}^{n}$ où $\forall i \in [[1, q]]$ , $P_{i}$ est un polynôme de degré strictement inférieur à $α_{i}$ .

Exemple 22. Soit $(u_{n})$ la suite définie par $\forall n \in N, u_{n} = a u_{n - 1} + b u_{n - 2}$ . Son polynôme caractéristique est $P = X^{2} - a X - b$ .

Si $P$ a deux racines distinctes $r_{1}$ et $r_{2}$ , alors $\forall n \in N, u_{n} = λ r_{1}^{n} + μ r_{2}^{n}$ où $λ$ et $μ$ sont tels que $u_{0} = λ + μ$ et $u_{1} = λ r_{1} + μ r_{2}$ .
Si $P$ a une racine double $r$ , alors $\forall n \in N, u_{n} = (λn + μ) r^{n}$ où $λ$ et $μ$ sont tels que $u_{0} = μ$ et $u_{1} = (λ + μ) r$ .

[AMR11]
p. 47

Exemple 23. Soit $(F_{n})$ la suite de Fibonacci définie par $F_{0} = 0$ , $F_{1} = 1$ et $\forall n \geq 2$ , $F_{n} = F_{n - 1} + F_{n - 2}$ . Alors, $\forall n \in N, F_{n} = \frac{1}{5} ((\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{2})^{n})$

Exemple 24. La suite $(u_{n})$ définie par $u_{0} = 1$ et $u_{n + 2} = u_{n} - u_{n + 1}$ est à termes positifs si et seulement si $u_{1} = \frac{1 - 5}{2}$ .

Développement asymptotique

p. 53

Définition 25. À toute suite numérique $(u_{n})$ on y associe sa suite $(v_{n})$ des moyennes de Cesàro où $\forall n \in N, v_{n} = \frac{1}{n} k = 1 \sum n u_{k}$

Théorème 26. Si $(u_{n})$ converge vers $ℓ \in K$ , alors sa suite des moyennes de Cesàro converge vers $ℓ$ . On dit que $(u_{n})$ converge au sens de Cesàro.

[FGN3]
p. 142

Proposition 27. Soit $f$ une application continue définie au voisinage de $0^{+}$ admettant un développement asymptotique en $0$ de la forme $f (x) = x - a x^{α} + o (x^{α})$ , où $a > 0$ et $α > 1$ . Alors pour $u_{0} > 0$ assez petit, la suite $(u_{n})$ définie par $u_{n + 1} = f (u_{n})$ pour $n \in N$ vérifie $u_{n} \sim \frac{1}{( na ( α - 1 ) ) ^{\frac{1}{α - 1}}}$

Exemple 28. Si $f = sin$ et $(u_{n})$ est définie par $u_{0} \in [0, 2 π]$ et $\forall n \in N, u_{n + 1} = f (u_{n})$ , on a l’équivalent en $+ \infty$ : $u_{n} \sim \frac{3}{n}$

[GOU20]
p. 228

Proposition 29. En reprenant les notations précédentes, on a, pour $u_{0} \in] 0, \frac{π}{2}]$ , $u_{n} = \frac{3}{n} - \frac{3 3}{10} \frac{ln ( n )}{n n} + o (\frac{ln ( n )}{n n})$

[FGN3]
p. 148

Exemple 30. On définit $(u_{n})$ par $u_{0} \in R$ et $\forall n \in N, u_{n + 1} = u_{n} + e^{- u_{n}}$ , on a l’équivalent en $+ \infty$ : $u_{n} = n + \frac{ln ( n )}{2 n} + o (\frac{ln ( n )}{n})$

Applications à la résolution approchée d’équations

Point fixe et itération

[DAN]
p. 146

Théorème 31 (Point fixe de Banach). Soient $(E, d)$ un espace métrique complet et $f : E \to E$ une application contractant (ie. $\exists k \in] 0, 1 [tel que \forall x, y \in E, d (f (x), f (y)) \leq k d (x, y)$ ). Alors, $\exists! x \in E tel que f (x) = x$ De plus la suite des itérés définie par $x_{0} \in E$ et $\forall n \in N, x_{n + 1} = f (x_{n})$ converge vers $x$ .

Théorème 32 (Point fixe dans un compact). Soit $(E, d)$ un espace métrique compact et $f : E \to E$ telle que $\forall x, y \in E, x \neq = y ⟹ d (f (x), f (y)) < d (x, y)$ alors $f$ admet un unique point fixe et pour tout $x_{0} \in E$ , la suite des itérés $x_{n + 1} = f (x_{n})$ converge vers ce point fixe.

[DEM]
p. 95

Application 33. Soient $a, b \in R$ et $f : [a, b] \to R$ dérivable, strictement croissante et telle que $f (a) < 0$ , $f (b) > 0$ et $0 < m \leq f^{'} (x) \leq M$ sur $[a, b]$ . On pose $φ : x \mapsto x - \frac{1}{M} f (x)$ . On considère l’équation : $f (x) = 0 ⟺ φ (x) = x (E)$ Alors :

$(E)$ admet une unique solution $x$ et pour tout point initial $x_{0} \in [a, b]$ , la suite des itérés $(x_{n})$ définie par $\forall n \in N, x_{n + 1} = φ (x_{n})$ converge vers $x$ .
La vitesse de convergence est estimée par la suite géométrique $(1 - \frac{m}{M})$ : il faut que les bornes $m$ et $M$ soient proches.

Remarque 34. Cela marche aussi dans le cas où $f (a) > 0$ , $f (b) < 0$ et $- M \leq f^{'} (x) \leq - m < 0$ (il suffit alors de changer $f$ en $- f$ ).

Définition 35. Soient $I$ un intervalle fermé de $R$ et $φ : I \to I$ une application de classe $C^{1}$ . Soit $a \in I$ un point fixe de $φ$ .

Si $∣ φ^{'} (a) ∣ < 1$ , on dit que $a$ est attractif. Si de plus $φ^{'} (a) = 0$ , $a$ est superattractif.
Si $∣ φ^{'} (a) ∣ > 1$ , on dit que $a$ est répulsif.

Proposition 36. On reprend les notations précédentes et on considère la suite des itérés $(x_{n})$ (avec $x_{0} \in I$ et $\forall n \in N, x_{n + 1} = φ (x_{n})$ ). Alors :

Si $a$ est attractif, $(x_{n})$ converge à une vitesse géométrique : $∣ x_{n} - a ∣ \leq k^{n} ∣ x_{0} - a ∣$
Si $a$ est superattractif et $φ$ est $C^{2}$ telle que $∣ φ^{''} ∣ < M$ sur $I$ , alors la vitesse de convergence est hypergéométrique : $∣ x_{n} - a ∣ \leq \frac{2}{M} 1 0^{- 2^{n}}$
Si $a$ est répulsif, il existe $h > 0$ tel que $φ_{∣ [a - h, a + h]}$ admette une application réciproque $φ^{- 1}$ définie sur $φ ([a - h, a + h])$ et le point $a$ est attractif pour $φ^{- 1}$ .

Exemple 37. Soit $f : x \mapsto x^{3} - 4 x + 1$ . On pose $φ : x \mapsto \frac{1}{4} (x^{3} + 1)$ et on considère $f (x) = 0 ⟺ φ (x) = x (E)$ Alors $(E)$ possède trois solutions réelles $a_{1} < a_{2} < a_{3}$ telles que :

$a_{1} \in] - 2, 5; - 2 [$ .
$a_{2} \in] 0; 0, 5 [$ et $a_{2}$ est attractif.
$a_{3} \in] 1, 5; 2 [$ .

Méthode de Newton

[ROU]
p. 152

methode-de-newton

Théorème 38 (Méthode de Newton). Soit $f : [c, d] \to R$ une fonction de classe $C^{2}$ strictement croissante sur $[c, d]$ . On considère la fonction $φ : [c, d] x \to \mapsto R x - \frac{f ( x )}{f ^{'} ( x )}$ (qui est bien définie car $f^{'} > 0$ ). Alors :

$\exists! a \in [c, d]$ tel que $f (a) = 0$ .
$\exists α > 0$ tel que $I = [a - α, a + α]$ est stable par $φ$ .
La suite $(x_{n})$ des itérés (définie par récurrence par $x_{n + 1} = φ (x_{n})$ pour tout $n \geq 0$ ) converge quadratiquement vers $a$ pour tout $x_{0} \in I$ .

Corollaire 39. En reprenant les hypothèses et notations du théorème précédent, et en supposant de plus $f$ strictement convexe sur $[c, d]$ , le résultat du théorème est vrai sur $I = [a, d]$ . De plus :

$(x_{n})$ est strictement décroissante (ou constante).
$x_{n + 1} - a \sim \frac{f ^{''} ( a )}{2 f ^{'} ( a )} (x_{n} - a)^{2}$ pour $x_{0} > a$ .

Exemple 40.

On fixe $y > 0$ . En itérant la fonction $F : x \mapsto \frac{1}{2} (x + \frac{y}{x})$ pour un nombre de départ compris entre $c$ et $d$ où $0 < c < d$ et $c^{2} < 0 < d^{2}$ , on peut obtenir une approximation du nombre $y$ .
En itérant la fonction $F : x \mapsto \frac{x ^{2} + 1}{2 x - 1}$ pour un nombre de départ supérieur à $2$ , on peut obtenir une approximation du nombre d’or $φ = \frac{1 + 5}{2}$ .

[DEM]
p. 102

Exemple 41. La méthode de Newton appliquée à la fonction $x \mapsto x^{3} - 4 x + 1$ dans le but d’approximer ses zéros donne :

$x_{0}$	$- 2$	$0$	$2$
$x_{1}$	$- 2, 125$	$0, 25$	$1, 875$
$x_{2}$	$- 2, 114975450$	$0, 254098361$	$1, 860978520$
$x_{3}$	$- 2, 114907545$	$0, 254101688$	$1, 860805877$
$x_{4}$	$- 2, 114907541$	$= x_{3}$	$1, 860805853$
$x_{5}$	$= x_{4}$		$= x_{4}$

Généralisation à $R^{m}$

p. 110

Théorème 42 (Méthode de Newton-Raphson). Soit $f : Ω \to R^{m}$ (où $Ω \subset R^{m}$ est un ouvert) de classe $C^{1}$ telle que $f (a) = 0$ . On suppose que $d f_{a}$ est inversible. Alors il existe un voisinage $U$ de $a$ dans $Ω$ tel que $φ : x \mapsto x - (d f_{x})^{- 1} (f (x))$ soit bien définie sur $U$ et la suite des itérés $x_{n + 1} = φ (x_{n})$ converge quadratiquement vers $a$ .

Exemple 43. On considère le système ${x^{2} + x y - 2 y^{2} = 4 x e^{x} + y e^{y} = 0 (S)$ On pose $X_{0} = (- 2 0, 2)$ et $Δ (x, y) = (2 x + y) (y + 1) e^{y} - (x - 4 y) (x + 1) e^{x}$ ainsi que : $φ (x y) = (x y) - \frac{1}{Δ ( x , y )} ((y + 1) e^{y} - (x + 1) e^{x} - x + 4 y 2 x + y) (x^{2} + x y - 2 y^{2} - 4 x e^{x} + y e^{y})$ Alors la suite des itérés $(X_{n}) = (x_{n} y_{n})$ converge vers l’unique solution de $(S)$ et on a :