Suites convergentes

[pierrotdu18]

Bonjour!

Pour un projet de programmation d'une calculatrice "home-made", j'aurais besoin de quelques suites particulières... Je n'ai le droit qu'à l'addition, la soustraction, la multiplication et la division

J'aimerais des suites (si c'est possible) qui convergent vers :
- Racine n-ième d'un nombre (la suite aura donc un 'argument')
- Cosinus d'un nombre (idem)
- Sinus d'un nombre (idem)
- Ln d'un nombre (idem)
- Exponentielle d'un nombre (idem)

- e (juste un cas particulier de la précédente)
- pi

J'espère que toutes les suites existent! Et que si possible, elle convergent le plus rapidement possible pour ne pas ralentir

Merci!

[Adriweb]

Pas compris le problème, utilise un développement limité, taylor, toussa ?

Exemples : http://fr.wikipedia.org/wiki/D%C3%A9vel ... Formulaire


Edit : ah, ouai, t'es en première... normal que tu n'aies pas eu ce réflexe ^^

[pierrotdu18]

Ah ah ^^
En effet, je ne pense pas que ce soit vraiment grave de ne pas avoir eu ce réflexe

Par contre, c'est mon prof qui m'a dit de faire ça, et il veut des suites, c'est pour ça que j'ai vraiment restreint la chose ^^

EDIT : Nan, franchement laisse tomber les notations petit o, les séries de Taylor, c'est juste carrément pas au programme de première, et ni de terminale je crois... Je connais quelqu'un qui voit ça en MPSI

[Lepzulnag]

Ton prof te demande de trouver la valeur approchée d'une fonction. Généralement pour chaque fonction courante la calculette possède un algorithme unique et optimisé, mais il existe aussi des algo qui permettent d'approcher la valeur d'une fonction quelconque.

Un algorithme c'est comme une suite infinie, chaque itération représente une nouvelle valeur de la suite. Le principe est le suivant :
Soit f ta fonction (racine, exp, ln, ...), et f(n) la valeur que tu cherches à approcher via ta suite.
Trouver f(n) revient à chercher le zéro d'une fonction g telle que g(f(n)) = 0.
Par exemple si f(n) = sqrt(n), alors g sera égal à g(x) = x^2 - n. On aura bien g(f(n)) = 0. Il ne reste plus qu'à trouver le zéro de cette fonction g. Pour cela différentes méthodes existent.

L'algorithme le plus simple est celui de la dichotomie. Tu trouves un intervalle [a,b] qui contient le zéro de ta fonction g (c'est-à-dire n), tel que :
- sur [a,n] g soit positive et sur [n,b] g soit négative
ou
- sur [a,n] g soit négative et sur [n,b] g soit positive.
Trouver cet intervalle est la plus grosse difficulté, et cela nécessite une étude de fonction de g. Mais ensuite on lance l'algorithme, et on est certain de trouver une solution.
(Xi) sera ta série. On prend x0 = le milieu de l'intervalle. On garde en mémoire la distance entre x0 et les bornes de l'intervalle.
Si g(x0) est du même signe que g(a), alors la solution se trouve entre X0 et b. On définit donc :
a = x0
x1 = (a+b)/2, le nouveau centre du nouvel intervalle.
Sinon, la solution se trouve entre a et x0 et on itère de la sorte :
b = x0
x1 = (a+b)/2
Et on recommence le processus...
La suite (Xi) tendra logiquement vers n, qui est le nombre que tu cherches.


Une méthode bien plus performante que celle de la dichotomie est la méthode de Newton : http://fr.wikipedia.org/wiki/M%C3%A9thode_de_Newton
Elle n'est pas si compliquée, mais sûrement pas au programme de lycée et demande la connaissance de la dérivée.

[Lepzulnag]

En fait je viens de me rendre compte que la méthode que je viens de te donner ne marche que si tu peux calculer explicitement g, c'est-à-dire dans le cas des racines n-ièmes uniquement
Après il est peut-être possible de s'en sortir avec une ou deux autres fonctions, mais rien n'est moins sûr.

Pour le cosinus et le sinus j'avais mis au point un algorithme et pourrai peut-être t'aider, mais il faut que j'en retrouve le principe..

[Excale]

Avec les DL comme proposé par Adriweb*:

(en espérant que ça rentre dans le cadre de la loi en tant que courte citation à titre d'exemple)

*edit: et un peu (voire plus qu'un peu selon la personne) d'extrapolation....

[Bisam]

Plutôt que des séries entières (qui mettent généralement pas mal de temps pour converger), il vaut mieux cibler des suites récurrentes de la forme

$mathjax$u_{n+1}=f(u_n)$mathjax$

avec des points fixes attracteurs, que l'on peut éventuellement améliorer avec diverses méthodes (comme la méthode de Newton, par exemple...)

Tu pourras même faire un seul algorithme qui marche dans tous les cas...

Par exemple, pour la racine n-ème, tu peux prendre la fonction

$mathjax$f:x\mapsto x^n-a$mathjax$

qui s'annule en la racine n-ème de a, puis avec la méthode de Newton, tu fabriques la fonction

$mathjax$g:x\mapsto x-\frac{f(x)}{f'(x)}=\left(1-\frac{1}{n}\right)x+\frac{a}{n x^{n-1}}$mathjax$

et tu définis la suite récurrente

$mathjax$u_{p+1}=g(u_p)$mathjax$

. La suite u va alors converger rapidement vers une valeur où

$mathjax$f$mathjax$

s'annule, c'est-à-dire vers la racine n-ème de a.


Mais, malheureusement, tu ne pourras pas faire les autres cas avec les restrictions imposées (seulement les 4 opérations !)

Pour le coup, les séries entières convergent très rapidement pour l'exponentielle, et en combinant avec des simplifications trigo, cela marche aussi pour les cosinus et sinus.
Tu peux aussi utiliser la suite

$mathjax$(1+\frac{a}{n})^n$mathjax$

qui converge assez rapidement vers

$mathjax$e^{a}$mathjax$

.

Pour le logarithme, c'est plus compliqué car la série entière converge lentement voire pas du tout si on n'est pas dans la bonne plage de valeurs.

[pierrotdu18]

D'accord, merci à tout le monde
Par contre, je suis désolé mais je vais laisser tomber les développements limités, ce n'est pas l'objectif de mon programme, car le but est avant tout de me servir de la convergence de suites simples

Merci Bisam pour la suite qui converge vers

$mathjax$e^a$mathjax$

, je pense qu'elle va me servir Par contre je n'ai pas compris la fin de ton message, pour les fonctions trigonométriques, on peut trouver des séries entières qui convergent vers ces fonctions avec un nombre d'itération peu élevé?
Les calculatrices sur PC utilisent quoi pour approximer les fonctions trigonométriques?

[Excale]

Tu peux à l'aide des DL en déduire une suite qui converge vers... (donc ça reste une histoire de suite^^)

M'enfin, comme indiqué sur mon image, c'est loin d'être le plus efficace. (Newton converge quadratiquement vers la pomme dans le référentiel de cette dernière, c'est beaucoup mieux)

[Bisam]

Pierrot : Les séries entières, c'est une amélioration des développements limités pour avoir une égalité sur tout un intervalle et non seulement une approximation au voisinage d'un point... mais fondamentalement, ce sont les mêmes calculs, donc tu peux laisser tomber.

En revanche, si mon calcul pour l'exponentielle te plaît, tu peux l'utiliser pour calculer des cosinus et des sinus en utilisant des nombres complexes et la formule de Moivre.... plus d'explications si tu le demandes.


PS : En fait, à bien y réfléchir, elle ne converge pas si rapidement que ça cette suite... L'erreur relative est de l'ordre de

$mathjax$-\frac{x^2}{2n}$mathjax$

, et donc il faut aller loin dans les valeurs de n pour avoir une bonne approximation. Mais si on va trop loin, ce sont les erreurs d'arrondis qui augmentent et qui faussent le résultat.