FORUM DE DISCUSSION SUR LE LANGAGE PANORAMIC

Développement d'applications avec le langage Panoramic
 
AccueilAccueil  FAQFAQ  RechercherRechercher  S'enregistrerS'enregistrer  MembresMembres  GroupesGroupes  Connexion  
Derniers sujets
» Pourquoi le compilateur stagne
par papydall Hier à 23:23

» Immortaliser les photos de famille
par jjn4 Hier à 18:29

» Concours de Morpions
par jjn4 Hier à 18:11

» Compilateur FBPano
par jean_debord Hier à 10:12

» Tout est tranquille
par Jean Claude Ven 22 Sep 2017 - 21:41

» Texte en gif animé
par JL35 Ven 22 Sep 2017 - 13:29

» BasicEditor
par Yannick Mer 20 Sep 2017 - 17:17

» Simuler l’appui d'une touche ou combinaison de touches.
par pascal10000 Lun 18 Sep 2017 - 19:30

» Utilisation de HVIEWER pour afficher des images
par papydall Lun 18 Sep 2017 - 17:43

» Panoramic et les gifs animés.
par papydall Lun 18 Sep 2017 - 16:32

» recover source
par pascal10000 Dim 17 Sep 2017 - 14:21

» Recent dans vos menu
par Jean Claude Sam 16 Sep 2017 - 11:41

» Comment centrer un texte 3D.
par pascal10000 Ven 15 Sep 2017 - 20:20

» Carte interface 16 entrées et 16 sorties
par Jicehel Ven 15 Sep 2017 - 16:30

» Version instantanée V 0.9.28i9 possédant l'objet SYNEDIT
par pascal10000 Ven 15 Sep 2017 - 16:20

Navigation
 Portail
 Index
 Membres
 Profil
 FAQ
 Rechercher
Rechercher
 
 

Résultats par :
 
Rechercher Recherche avancée
Septembre 2017
LunMarMerJeuVenSamDim
    123
45678910
11121314151617
18192021222324
252627282930 
CalendrierCalendrier

Partagez | 
 

  Evaluer un polynôme en un point par la méthode de Horner

Voir le sujet précédent Voir le sujet suivant Aller en bas 
AuteurMessage
papydall

avatar

Nombre de messages : 5533
Age : 67
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

MessageSujet: Evaluer un polynôme en un point par la méthode de Horner   Dim 11 Déc 2016 - 4:41

Code:

rem ============================================================================
rem          Evaluer un polynôme en un point par la méthode de Horner
rem ============================================================================
rem Exemple : Soit le polynôme de degré 5 suivant
rem        P(x) = 3*X^5 + 4*X^4 -12*X^3 + 35*X^2 - 14*X + 17
rem On désire évaluer ce polynôme pour X0 = 3
rem La solution triviale consiste à évaluer la puissance de chaque monôme,
rem multiplier le résultat par le coefficient et faire la somme des monômes obtenus.
rem Mais le calcul des puissances reste coûteux, il existe une méthode qui permet
rem de se passer de ces calculs.
rem Methode de Horner:
rem ==================
rem En effet, prenons le polynôme 3*x^2 + 2*x + 1
rem Avec une factorisation astucieuse, on peut écrire ((3*x + 2)*x + 1) qui ne
rem comporte que des additions et des produits, l élévation à la puissance devient
rem la conséquence du calcul.
rem
rem Pour un polynôme plus fourni : 5*x^5 + 7*x^3 + 8*x^2 on obtient
rem                                ((((5*x)*x + 7)*x + 8)*x)*x
rem Il suffit de calculer au départ avec les coefficients nuls puis de simplifier.
rem
rem Modélisons un polynôme comme un tableau démarrant à l indice 0, le coefficient
rem de degré i étant inscrit dans la cellule i du tableau
rem (les indices sont alignés sur les degrés, c-à-d de droite à gauche).
rem
rem La SUB PolyEval(x) est élégante, concise et rapide :
rem rien que des multiplication et addition
rem ============================================================================
dim DegreMax : DegreMax = 10 : ' Degré maximum du polynôme à modifier si besoin est
dim Coef(DegreMax)          : ' Les coefficients du polynôme
dim Degre                    : ' Degré d'un polynôme <= à DegreMax
dim resultat                : ' Valeur calculée du polynôme
dim i                        : ' Variable compteur
rem ============================================================================
' Exemple 1 : 3x² + 2x + 1
for i = 0 to DegreMax : Coef(i) = 0 : next i : ' Mettre tous les coefficient à zéro
Degre = 2 : ' Degré du polynôme de l'exemple
Coef(0) = 1 : Coef(1) = 2 : Coef(2) = 3  : ' les indices sont alignés sur les degrés
                                          ' donc de droite à gauche
PolyEval(2) : ' Calculer la valeur du polynôme pour x = 2
print resultat
rem ============================================================================
' Exemple 2 : 3x^7 -2x^6 + 3x^3 + 6x² + 10
for i = 0 to DegreMax : Coef(i) = 0 : next i : ' Mettre tous les coefficient à zéro
Degre = 7 : ' Degré du polynôme de l'exemple
Coef(0) = 10 : Coef(2) = 6 : Coef(3) = 3  : Coef(6) = -2 : Coef(7) = 3 : ' les indices sont alignés sur les degrés
                                                                        ' donc de droite à gauche
PolyEval(1) : ' Calculer la valeur du polynôme pour x = 1
print resultat
rem ============================================================================
' Exemple 3 : 3*X^5 + 4*X^4 -12*X^3 + 35*X^2 - 14*X + 17
for i = 0 to DegreMax : Coef(i) = 0 : next i : ' Mettre tous les coefficient à zéro
Degre = 5 : ' Degré du polynôme de l'exemple
Coef(0) = 17 : Coef(1) = -14 : Coef(2) = 35  : Coef(3) = -12 : Coef(4) = 4 : Coef(5) = 3 : ' les indices sont alignés sur les degrés
                                                                                          ' donc de droite à gauche
PolyEval(3) : ' Calculer la valeur du polynôme pour x = 3
print resultat ; "  <---- Methode de Horner"

Eval(3)
print resultat; "  <---- Solution triviale"
end
rem ============================================================================
SUB PolyEval(x)
    resultat = 0
    for i = Degre to 0 step -1
        resultat = resultat * x + coef(i)
    next i
END_SUB
rem ============================================================================
' Solution triviale pour le polynôme de l'exemple 3
' P(x) = 3*X^5 + 4*X^4 -12*X^3 + 35*X^2 - 14*X + 17
SUB Eval(x)
    resultat = 3*power(X,5) + 4*power(X,4) -12*power(X,3) + 35*power(X,2) - 14*X + 17
END_SUB
rem ============================================================================
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/
JL35



Nombre de messages : 5951
Localisation : 77
Date d'inscription : 29/11/2007

MessageSujet: Re: Evaluer un polynôme en un point par la méthode de Horner   Dim 11 Déc 2016 - 23:19

Yvette ? Very Happy
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
papydall

avatar

Nombre de messages : 5533
Age : 67
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

MessageSujet: Re: Evaluer un polynôme en un point par la méthode de Horner   Lun 12 Déc 2016 - 2:25

Non, ce n’est pas Yvette.
Ce sont des mathématiques pures et dures !  tongue

Bon, si tu veux en connaitre un petit peu plus, clique sur ce lien.
Fait en sorte d'avoir à portée de main une boîte de doliprane ou équivalent car c'est dur à avaler ! Laughing
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/
Laurent (Minibug)

avatar

Nombre de messages : 2353
Age : 50
Localisation : Vienne (86)
Date d'inscription : 10/02/2012

MessageSujet: Re: Evaluer un polynôme en un point par la méthode de Horner   Lun 12 Déc 2016 - 9:36

J'ai regardé ton code et ses explication ce matin.

Effectivement, cela semble intéressant. Mais maintenant que l'on a les fonctions de puissance sur nos langage cela a moins d'importance.
Cela dit, la méthode reste très instructive. Merci Papydall !
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
jean_debord

avatar

Nombre de messages : 751
Age : 63
Localisation : Limoges
Date d'inscription : 21/09/2008

MessageSujet: Re: Evaluer un polynôme en un point par la méthode de Horner   Lun 12 Déc 2016 - 11:05

Dans les applications scientifiques, c'est toujours la méthode de Horner que l'on utilise car elle minimise le nombre d'opérations et donc les erreurs d'arrondi.

Il y a une variante qui permet de calculer le polynôme et ses dérivées. Je la mettrai dans FBPano.

Elle s'applique aussi aux nombres complexes, ce qui permet notamment de générer des figures fractales.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://www.unilim.fr/pages_perso/jean.debord/index.htm
papydall

avatar

Nombre de messages : 5533
Age : 67
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

MessageSujet: Re: Evaluer un polynôme en un point par la méthode de Horner   Lun 12 Déc 2016 - 15:10

Minibug a écrit:
Effectivement, cela semble intéressant. Mais maintenant que l'on a les fonctions de puissance sur nos langage cela a moins d'importance.

Tu as compris la méthode à moitié !
Le but de la méthode est d’améliorer le temps du traitement en minimisant le nombre d’opérations à effectuer et surtout à ne pas  utiliser l’élévation à la puissance qui est une fonction nécessitant beaucoup de temps machine.
Soit un polynôme P(x) de degré n
P(X) = anXn + an-1Xn-1 + an-2Xn-2 + … + a1X+ a0
Soit un nombre X0, le calcul de P(x0) nécessite de calculer chacune des puissances de X0, multiplier celle-ci par son coefficient ak puis faire la somme de ce que l’on a trouvé.
Si on calcule X0 en multipliant successivement X0 par lui-même, le nombre nécessaire de produits est alors de
n + (n - 1) + … + 2 + 1 = n(n+1)/2, quantité qui croît comme le carré du degré du polynôme.
La méthode de Horner consiste à améliorer  ce résultat en effectuant le calcul comme suit :
P(x0) = ((… ((anx0 + an-1)x0 + an-2)x0 + … ) x0 + a1)x0 + a0.
Le nombre de produits est alors réduit à n, de sorte que le temps de calcul d'une fonction polynomiale en un point a est seulement proportionnel au degré du polynôme.
C’est un bien bon exploit !

De plus la méthode de Horner peut être utilisée (en plus de ce qu’a écrit Jean_debord) dans la conversion de base de numération, dans le calcul du quotient d’un polynôme par X-x0, dans le calcul de la valeur approchée d’une racine, dans le calcul des dérivées successives de P en x0 etc.


Jean_debord a écrit:
Il y a une variante qui permet de calculer le polynôme et ses dérivées. Je la mettrai dans FBPano.

Bonne idée !
Merci Jean.


Dernière édition par papydall le Lun 12 Déc 2016 - 18:29, édité 2 fois
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/
papydall

avatar

Nombre de messages : 5533
Age : 67
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

MessageSujet: Re: Evaluer un polynôme en un point par la méthode de Horner   Lun 12 Déc 2016 - 18:23

Code:

rem ============================================================================
rem            Division polynomiale par X - X0
rem ============================================================================
' Soit P un polynôme de la variable x à coefficients réels ou complexes.
' P(x) est de la forme :
' P(x) = a(n).X^n + a(n-1).X^(n-1) + ... + a(2).X² + a(1).X + a(0)
' L'entier naturel n est le degré du polynôme.
' On appelle racine ou zéro du polynôme P, un nombre réel ou complexe xo tel
' que P(xo) = 0.
rem ============================================================================
rem Théorème 1:
rem ============================================================================
' xo est racine de P si et seulement si P est divisible par x - xo.
' Autrement dit, si le degré du polynôme P est n, alors il existe un polynöme Q
' tel que, quel que soit x, P(x) = (x-x0) * Q(x) avec degré de Q = degré de p - 1
rem Théorème 2:
rem ============================================================================
' P admet x0 comme racine multiple de multiplicité k si et seulement si
' P(xo) = 0 et xo est un zéro d'ordre k - 1 pour le polynôme dérivé de P.
' On peut aussi énoncer:
rem Théorème 3:
rem ============================================================================
' P admet xo comme racine multiple de multiplicité k si et seulement si
' P(xo) = 0 et les dérivées successives de P jusqu'à l'ordre k - 1 s'annulent en xo.
rem ============================================================================
rem Étude d un algorithme en Panoramic pour la division d un polynôme par x - xo
rem Soit P un polynôme d une variable réelle x.
rem Si P(xo) = 0, on a P(x) = (x - xo ) * Q(x) avec degré de Q = degré de P - 1.
rem Si P(xo) est non nul, puisque x - xo est de degré 1, le reste de la division
rem est une constante r et l on a :
rem P(x) = (x - xo ) * Q(x) + r, par suite r = P(xo).
rem Notons maintenant P un polynôme de degré n, noté symboliquement
rem (a(n), a(n-1),..., a2, a1, ao), c-à-d vérifiant pour tout x réel :
rem P(x) = a(n)x^n + a(n-1)x^n-1 + ... + a2x^2 + a1x + ao.
rem Dans la division euclidienne de P par x - xo, le quotient Q est de degré n - 1
rem et si nous écrivons :
rem Q = (0, q(n-1),..., q2, q1, qo), on a : q(n-1) = a(n)
rem A lissue de la k-ème étape de la division, on a :
rem P(x) = (x - xo) * Q(n-1)*(x) + R(k)
rem où Q(n-1) désigne le quotient partiel et R(k) le reste dont le degré est au
rem plus n - k.
rem Au plus, car des monômes peuvent s éliminer par combinaison linéaire, et
rem correspondent aux cas où l on rencontre un coefficient q(k) nul, ce qui
rem n altère en rien l algorithme.
rem Le produit de q(n-1) * x(n-1) par x - xo doit être retiré à l expression P(x).
rem Symboliquement, nous effectuons :
rem (a(n), a(n-1),..., a2, a1, ao) - (a(n), - xo*a(n) , a(n-2) , ..., a1, ao)
rem et nous recommençons notre division en travaillant sur
rem (a(n-1) + xo*a(n), a(n-2), ..., a1,ao) : c-à-d que q(n-2) = a(n-1) + xo*a(n)
rem est le second coefficient de notre quotient, ce dernier terme jouant le rôle
rem du a(n) de départ.
rem On voit là l algorithme d une récurrence descendante pour le calcul des
rem coefficients du quotient : a(p) <--- a(p) + xo*a(p+1) ,  q(p-1) <--- a(p)
rem Partant de p = n - 1, on calcule les q(p) de proche en proche en décrémentant
rem p tant que p > 0 et en mettant dans la variable a(p) la valeur a(p) + xo*a(p+1).
rem Si l on pousse le calcul jusqu à p = 0, on aura qo = r, reste de la division
rem euclidienne de P par Q.
rem ============================================================================
' Pour tester ce programme vous devrez entrer le degré n du polynôme,
' puis xo puis les coefficients a(i) suivant les puissances décroissantes.
rem Exemple 1 :
rem =============
rem P(x) = 2x^3 - 7x + 1 , divisé par x + 1
rem Entrez le degré du polynôme < --- 3
rem entrez x0 <--- -1
rem entrez les coefficients < --- 2 puis 0 puis -7 puis 1
rem le programme donne la solution : 2 -2 -5 r = 6
rem c-à-d p(x) / (x-1) = 2x² - 2x - 5 + 6/(x+1)
rem Exemple 2 :
rem ===========
rem P(x) = x^4 - 3x^3 + 2x^2 - 8x + 6 , divisé par x-3
rem Entrez le degré du polynôme < --- 4
rem entrez x0 <--- 3
rem entrez les coefficients < --- 1 puis -3 puis 2 puis -8 puis 6
rem le programme donne la solution : 1 0 2 -2 r = 0
rem c-à-d que la valeur 3 est un zéro de P et que P(x) = (x-3) * (x^3 + 2x -2)
rem ============================================================================
rem &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
rem ============================================================================

Division_Polynomiale()

end
rem ============================================================================
SUB Division_Polynomiale()
    dim_local n,i,r$,x0,p,k
    repeat
       repeat
          r$ = message_input$("Enrez le dégré du polynôme", "n = ","")
       until numeric(r$) > 0
       n = val(r$)
    until n > 0
    if variable("d") = 0
       dim d : d = n
       dim a(d)
    end_if
    p = n-1
    for i = 0 to d : a(i) = 0 : next i : ' RAZ des coefficients a(i)
    repeat
       r$ = message_input$("Entrez x0","x0 = ","")
    until numeric(r$) > 0
    x0 = val(r$)
    for i = n to 0 step -1
        repeat
           r$ = message_input$("Entrez les coefficients","a"+str$(i),"")
        until numeric(r$) > 0
        a(i) = val(r$)
    next i
    print "Coefficients de Q par degré décroissants à partir de " + str$(p)
    print "q" + str$(p) + " = " + str$(a(n))
    while p >= 0
        a(p) = a(p) + x0*a(p+1)
        k = p-1
        if p > 0
           print "q" + str$(k) + " = " + str$(a(p))
        else
           print "r = " + str$(a(0))
        end_if
        p = p - 1
    end_while
    free d : free a : ' liberer ces variables
END_SUB
rem ============================================================================
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/
Contenu sponsorisé




MessageSujet: Re: Evaluer un polynôme en un point par la méthode de Horner   

Revenir en haut Aller en bas
 
Evaluer un polynôme en un point par la méthode de Horner
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» ZUMO 220 : Rond-point à l'envers
» meilleur moyen pour revenir au point de départ
» point gps ?
» Je reviens toujours au point de départ
» point de depart

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
FORUM DE DISCUSSION SUR LE LANGAGE PANORAMIC :: PANORAMIC :: Vos sources, vos utilitaires à partager-
Sauter vers: