Algorithme pour calculer les termes d'une suite

matilda

Bonjour,

j'essaye d'écrire l'algorithme du problème suivant:

On considère la suite $(x_n)$ définie par:

$$x_0=a, x_{n+1} = \dfrac{1}{2} (x_n + \dfrac{a}{x_n})$$

avec $a$ strictement positif.

Ecrire l'algorithme pour calculer les $N$ premiers termes de la suite $(x_n)$ telle que $|x_{n+1}-x_n| \geq \varepsilon$

Voici ce que j'ai essayé de faire:

- Lire $a$ et $\varepsilon$

- $N=0$ ($N$ ici est le nombre des termes de la suite qui satisfont la condition posée dans l'exercice)

- $x=a$

-$y= \dfrac{1}{2}(x+ \dfrac{a}{x})$

- Si $|y-x| \geq \varepsilon$ alors

                                                 -N=N+1

                                                 -écrire $y$ 

                                                 -poser $x=y$ 

                                                  - puis recalculer un nouveau $y$ et voir à nouveau si ladite condition   est satisfaite

Sinon (si $|y-x| \leq \varepsilon$ : écrire N et arrêter le programme

Ma question est: est-ce que mon algorithme est correcte? Est-ce que si on arrête le programme, l'écriture de $N$ sera possible?

Je vous remercie d'avance pour votre aide.

gerard0

Bonjour.

Si a n'est pas considéré comme faisant partie des termes comptés, ça me semble correct. Sinon, si $|x_1-a| \geq \varepsilon$, il faudra l'afficher et initialiser $N$ à 1.

Tu peux facilement tester ton programme (dans le langage de ton choix), N est souvent très petit.

Cordialement.

NB : L'énoncé du problème n'est pas clair, j'ai suivi ton interprétation (afficher $x_1,x_2,...x_n$ puis $N$)

matilda

Bonjour,

$x_0=a$ fait partie des termes comptés.

C'est pour celà qu'on affiche $x=a$, puis on calcule $y$ (qui est $x_1$) et on fait tout de suite le test. Si ça marche, alors on met $N=N+1$ (c'est à dire $N=1$). Mais si $|a-y| \leq \varepsilon$ alors on aura $N=0$ et aucun terme ne sera affiché.

C'est comme ça que j'ai procédé. Maintenant, je ne comprends pas l'idée d'initialiser $N$ à 1.

Paco_del_Rey

Bonjour matilda.

Que donne ton programme pour \( a = -1 \) ?

Paco.

matilda

Non. $a$ est supérieur à 0. Donc ce cas n'est pas possible

Médiat_Suprème

Si la suite n'est pas convergente, l'algorithme ne s'arrête pas !
Le cas $a = -1$ doit être pris en compte d'une façon ou d'une autre (refuser l'input en est une)

matilda

 @Gerard: Bonjour,

$x_0=a$ fait partie des termes comptés.

C'est pour celà qu'on affiche $x=a$, puis on calcule $y$ (qui est $x_1$) et on fait tout de suite le test. Si ça marche, alors on met $N=N+1$ (c'est à dire $N=1$). Mais si $|a-y| \leq \varepsilon$ alors on aura $N=0$ et aucun terme ne sera affiché.

C'est comme ça que j'ai procédé. Maintenant, je ne comprends pas l'idée d'initialiser $N$ à 1.

Merci d'avance.

Fin de partie

@matilda:  En informatique on a le droit de faire: $x= \dfrac{1}{2}(x+ \dfrac{a}{x})$

qui signifie qu'on prend la valeur de $x$ on calcule $\dfrac{1}{2}(x+ \dfrac{a}{x})$ et on remplace la valeur de $x$ par cette nouvelle valeur. Connais-tu la limite de la suite $x_{n+1}=\dfrac{1}{2}(x_n+ \dfrac{a}{x_n})$? Avec $a>0$, et $x_0=a$

PS:

pour éviter de heurter les mathématiciens, on écrit souvent $x\leftarrow \dfrac{1}{2}(x+ \dfrac{a}{x})$ au lieu de $x= \dfrac{1}{2}(x+ \dfrac{a}{x})$.

lourrran

Je pense que la première étape, c'est de clarifier la question. Dérouler le processus à la main.
Par exemple, si on choisit $a=4$, les premières étapes qu'on peut calculer à la main ou avec un tableur donnent ... ... 
Si on choisit $\varepsilon = 0.1$, on veut que le programme affiche quoi ?
Si on est capable de répondre à cette question, alors, ok, on peut passer à l'étape suivante, écrire un algorithme.
Si on a des doutes sur la réponse pour un couple précis banal comme $(a,\varepsilon = (4,0.1)$ alors il est trop tôt pour parler d'algorithme, il faut d'abord lever le doute.

Et c'est systématique quand on parle d'algorithme. Dans un premier temps, il faut être clair sur le besoin, (le cahier des charges). Ensuite quand la demande est claire, quand on sait faire le calcul avec du papier et un crayon pour quelques cas simples, on peut passer à l'étape suivante.

matilda

@Lourran: Oui je sais ce qu'on cherche.

Si on prend $a=4$ et $\varepsilon =0.1$.

On note $N$ le nombre de termes de la suite qui satisfait la formule donnée.

Au départ, $N=0$.

étape 1: on a le premier terme de la suite qui est $x_0=a=4$.

étape 2: on calcule $x_1= \dfrac{1}{2}(x_0+\dfrac{a}{x_0} =2.$

étape 3: on calcule $|x_1-x_0|$. Ici, on a: $|x_1-x_0|= |2-4|=2$ qui est supérieur à $\varepsilon =0.1$.

Donc, on affiche au conteur $N=1$

Puis on pose $x_1= 2$ et on calcule $x_2= \dfrac{1}{2}(x_1 + \dfrac{a}{x_1})$ et on refait la même procédure.

Donc vous proposer de faire une boucle sur $i$? Que proposez-vous? Svp

lourrran

Si $x_0=4$, alors $x_1$ n'est pas égal à $2$, mais à $2.5$

matilda

Oui pardon. $x_1= 2.5$. $|x_1-x_0|$ est supérieur à $\varepsilon$.

Donc c'est ok.

Mais si on veut afficher le nombre de ces termes de la suite qui vérifient l'inégalité, comment on fait? Svp

Apparemment la proposition que j'ai faite plus haut n'est pas correcte. Comment la corriger?

Merci d'avance.

gerard0

Ok, je vois mieux ce que tu voulais faire, mais comme tu a écrit "écrire y", le a n'est jamais affiché (seulement écrit par l'utilisateur). Dans ce cas, il vaut mieux mettre "écrire x"; car on est sûr que x est dans la liste, on ne sait encore rien sur y.

Sinon, après avoir mieux lu, je reconnais que tu as raison, si on s'arrête à la première étape, c'est bien N=0 qui doit apparaître.

Cordialement.

matilda

Merci beaucoup.

Donc mon algorithme est correct? S'il vous plaît.

gerard0

Heu... Tu as lu ? 

Fin de partie

@matilda: pourquoi ne testes-tu pas ton algorithme réellement? Cela nécessite de connaître un langage  de programmation.

Autrement tu peux le tester sur papier en faisant un tableau avec toutes les variables utilisées et voir comment ces variables changent après l'exécution de chaque instruction et quelles sont leur valeurs à la terminaison du programme.

matilda

C'est compris. L'algorithme qui affiche les $N$ premiers termes de la suite qui satisfont la relation $|x-y| > \varepsilon$ ainsi que leur nombre $N$, est:

-Début

- Lire $a$, $\varepsilon$

-N=0

-x=a

-$y=\dfrac{1}{2}(x+\dfrac{x}{a})$

-Tant que $(|x-y| > \varepsilon)$ faire

                                                            -écrire x

                                                            -N=N+1

                                                            -x=y

                                                           - $y=\dfrac{1}{2}(x+\dfrac{x}{a})$

-Fin Tant que

-écrire N

-Fin

Fin de partie

@matilda: Tu n'as pas besoin de la variable $y$, la variable $x$ peut faire toute seule le boulot.

Edit: Finalement on en a besoin. 

PS:

Ce programme est un peu bizarre, en général on s'intéresse au rang $n$ le plus petit pour lequel on a $\left|U_n-l\right|<\epsilon$ où $l$ est la limite de la suite.

lourrran

@Fdp : tu as raison, on préférerait que le test d'arrêt soit en fonction de la limite, mais ça demande de calculer la limite... Si on est prof d'algorithme, et si on a un public de non-matheux, on ne peut pas faire ce que tu préconises.

@matilda
Dans les grandes lignes, c'est correct.
Mais dans les détails, regardons. L'énoncé parlait de s'arrêter quand un certain truc était $\ge \varepsilon$ ; toi, tu as mis $> \varepsilon$
En pratique, à moins de vraiment mal tomber, $\ge$ ou $>$ vont donner le même résultat. Mais ce n'est pas une raison.

On demandait de s'arrêter quand $|x_{n+1}-x_n|\ge \varepsilon $ ; Je n'ai pas vérifié précisément, mais je pense que tu t'arrêtes quand $|x_n-x_{n-1}|\ge \varepsilon $ ... ou en fait, j'ai l'impression que si c'est bon, c'est par coup de chance.

Médiat_Suprème

N'ayant pas tenu compte de mes 2 remarques, cet algorithme est fautif !