Euh... "O(x²)?"?

Résolu
Yuku Messages postés 215 Statut Membre -  
Sacabouffe Messages postés 9427 Date d'inscription   Statut Membre Dernière intervention   -
Bonjour à tous,

Je suis en train de créer un programme qui calcule la puissance, l'exponentielle, le cosinus et le sinus de deux nombres x et n, à partir de quelques formules.

La formule de l'exponentielle est la suivante :

exp(x) = 1 + (x/1!) + (x^2/2!) + (x^3/3!) + ... + (x^n/n!) + O(x^n)

Tout va bien pour la majorité du calcul, j'ai bien déclaré x et n, et un compteur, etc etc...

Mais qu'est ce que c'est que ce O(x^n)??

Voilà, tout d'abord qu'est-ce-que c'est, et surtout comment le déclarer dans mon programme ?!

Merci d'avance ! :)
Configuration: Windows Vista
Firefox 3.0.3

21 réponses

  • 1
  • 2
  1. Sacabouffe Messages postés 9427 Date d'inscription   Statut Membre Dernière intervention   1 863
     
    Oui aussi.
    Sinon, une autre manière, tu peux calculer en deux fois.
    Si tu veux calculer la somme jusqu'à 4*N+3N est donné.
    sinx= 0;
    for (n=0; n<=N; n++) {
            fact=factorielle(4*n+1);
    	sinx = sinx + (x^(4*n+1))/fact;
    
    }
    for (n=0; n<=N; n++) {
            fact=factorielle(4*n+3);
    	sinx = sinx - (x^(4*n+3))/fact;
    
    }
    3
  2. Sacabouffe Messages postés 9427 Date d'inscription   Statut Membre Dernière intervention   1 863
     
    Salut
    Ben...
    O(x^n), c'est une fonction, cette notation, c'est une des notations de Landau :
    https://fr.wikipedia.org/wiki/Notations_de_Landau

    En fait, on note O(x^n) (ici on devrait préciser pour x→+∞), toute fonction f telle que f(x)/x^n est bornée (ici en l'occurrence quand x→+∞).

    On note o(x^n) (dans le cas qui nous intéresse, pour x→+∞), toute fonction f telle que lim (f(x)/x^n) = 0 (et donc ici, quand x→+∞).

    Ta formule est pas fausse mais on peut la raffiner un peu.
    exp(x) = 1 + (x/1!) + (x^2/2!) + (x^3/3!) + ... + (x^n/n!) + O(x^(n+1))
    Ou
    exp(x) = 1 + (x/1!) + (x^2/2!) + (x^3/3!) + ... + (x^n/n!) + o(x^n)

    Bref, ici donc, ton O(x^(n+1)) ou ton o(x^n), c'est
    (x^(n+1)/(n+1)!) + (x^(n+2)/(n+2)!) + (x^(n+3)/(n+3)!) + ... (jusqu'à +∞)

    Parce qu'en fait, la formule que t'as écrite, c'est juste une écriture moins précise de
    exp(x) = 1 + (x/1!) + (x^2/2!) + (x^3/3!) + ... + (x^n/n!) + ... (jusqu'à +∞)

    Du coup pour ton programme tu t'en occupes pas trop. Tu choisis un n assez grand et tu calcules ta somme jusqu'à n.
    Tu peux améliorer le programme en choisissant le n en fonction de x. En effet, un n qui va te donner des résultats très précis pour un x pas trop grand, va donner des résultats beaucoup moins satisfaisants pour un x plus grand. Du coup, tu peux sommer jusqu'à ce que le premier terme du reste ((x^(n+1)/(n+1)!)) soit inférieur à un petit nombre donné.

    Par contre, si tu vas jusqu'à des n relativement grands, pense à utiliser une exponentiation rapide.
    https://fr.wikipedia.org/wiki/Exponentiation_rapide
    Sinon ça va ramer...

    Et dernière chose, je pense que si t'essaies de calculer l'exponentielle d'un grand nombre de cette manière (Quel sera exactement "grand" ? Ben je sais pas trop...), tu vas rapidement avoir des soucis. En effet, x^n→+∞) (tout au moins pour x > 1) et n!→+∞.
    En théorie (x^n/n!)→+0 mais numériquement, tu vas avoir à évaluer le quotient de deux grands nombres et t'auras des erreurs numériques monstrueuses. Et en plus, passé n=170, le résultat du calcul de n! sera tout simplement +∞.

    Voilà... Amuse-toi bien ! ;-)
    3
  3. toto
     
    Bonsoir

    Sans entrer dans les détails, ça veut simplement dire un terme négligeable. Donc tu n'as pas à t'en soucier.
    Mais pour appliquer ce genre de formule, il faut être capable de calculer le 'n' c'est à dire le nombre de termes à utiliser pour atteindre la précision voulue dans la réponse.
    2
  4. Sacabouffe Messages postés 9427 Date d'inscription   Statut Membre Dernière intervention   1 863
     
    Ben de rien ;-)

    Si tu veux faire un calcul précis, le mieux c'est effectivement des doubles. De toute façon, t'as pas à en stocker une quantité industrielle, juste 3 ou 4, pas de quoi fouetter un chat, tu risques pas d'avoir des soucis d'espace mémoire avec ça :-D
    2
  5. Vous n’avez pas trouvé la réponse que vous recherchez ?

    Posez votre question
  6. Sacabouffe Messages postés 9427 Date d'inscription   Statut Membre Dernière intervention   1 863
     
    Tu fais une boucle où t'incrémentes n de 1, mais dans pour la formule t'utilises 2n+1, et voili voilou...8-)
    2
  7. Sacabouffe Messages postés 9427 Date d'inscription   Statut Membre Dernière intervention   1 863
     
    Si tu veux t'arrêter à 43 par exemple (43=2*21+1)
    sinx= 0;
    for (n=0; n<=21; n++) {
            fact=factorielle(2*n+1);
    	sinx = sinx + ((-1)^n)*(x^(2*n+1))/fact;
    
    }
    factorielle sera ta fonction pour calculer ta factorielle bien évidemment... (^_^)
    2
  8. fiddy Messages postés 441 Date d'inscription   Statut Contributeur Dernière intervention   1 847
     
    -5 7 -9, ça sonne comme un incrément de deux avec changement de signes.
    Donc si c'est négatif tu multiplies par -1 et t'ajoutes 2. Sinon tu multiplies par -1 et tu soustrais 2 ;)
    coeff=coeff>0?-coeff-2:-coeff+2;

    Cdlt
    1
  9. Yuku Messages postés 215 Statut Membre 4
     
    Mais justement, j'incrémente un Compteur qui remplace n et se répète le nombre de fois nécessaires pour faire ce calcul...
    Cela signifie donc que je n'ai pas à me soucier de ce O(x^n)??
    0
  10. Yuku Messages postés 215 Statut Membre 4
     
    Alors merci beaucoup, c'est nettement plus clair !

    Si je veux donc stocker des très grandes variables, qu'est-ce-que je devrais utiliser?

    J'utilise actuellement des double...
    0
  11. Yuku Messages postés 215 Statut Membre 4
     
    Ça marche ! Juste une petite question encore, c'est quoi la différence entre un double et un long double ?
    0
  12. Yuku Messages postés 215 Statut Membre 4
     
    Par contre là je vais avoir besoin d'un petit coup de pouce ><

    Pour l'exponentiel c'était assez facile, la formule était :

    exp(x) = 1 + (x/1!) + (x^2/2!) + (x^3/3!) + ... + (x^n)/n!

    Mais pour le sinus c'est :

    x - x3/3! + x5/5! - x7/7! + ... + (-1)^n ((x^2n+1/(2n+1)!)

    Comment faire pour passer de +3 à -5 puis +7...??

    Je sais comment faire pour incrémenter 1 à chaque fois, mais là... :S
    0
  13. Yuku Messages postés 215 Statut Membre 4
     
    Euh... Perso j'ai pas trop compris là =S
    0
  14. Yuku Messages postés 215 Statut Membre 4
     
    J'ai jamais fait ça, selon les changements de signes donc bon ^^ pas évident...
    0
  15. Yuku Messages postés 215 Statut Membre 4
     
    Ah ouais je vois, ok !

    J'avais sinon pensé à créer une boucle do...while dans laquelle j'insère deux if, le premier calculant n+2 et le deuxième calculant (-n+2), avec à chaque fois pour condition que le compteur < n...
    0
  16. Yuku Messages postés 215 Statut Membre 4
     
    Ouais c'est un peu comme ça que je pensais !

    Mais j'ai du mal avec la boucle for...
    0
  17. Sacabouffe Messages postés 9427 Date d'inscription   Statut Membre Dernière intervention   1 863
     
    OK !
    Enfin voilà... je vais pouvoir t'aider beaucoup plus, ça fait une éternité que j'ai pas touché du C++ :-(
    0
  18. Yuku Messages postés 215 Statut Membre 4
     
    C'est déjà beaucoup ! :)
    0
  19. Sacabouffe Messages postés 9427 Date d'inscription   Statut Membre Dernière intervention   1 863
     
    Si tu le dis... 8-)
    Si t'as un problème plus pointu à résoudre, fais un nouveau sujet, parce que là, je serai vite dépassé. Et dans un sujet qu'a déjà reçu des réponses, je suis pas sûr que quelqu'un de compétent vienne y mettre son nez :-D
    0
  20. Yuku Messages postés 215 Statut Membre 4
     
    Ouais mais pour l'instant tout va bien, en tout cas pour ce programme :)
    0
  • 1
  • 2