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
» Un petit "coucou" à tous les Panoramiciens !
par Yannick Aujourd'hui à 23:06

» mise a jour calculatrice
par joeeee2017 Aujourd'hui à 22:44

» Logiciel de soutien scolaire en langues.
par Pedro Alvarez Aujourd'hui à 16:52

» KGF_dll - nouvelles versions
par Klaus Aujourd'hui à 14:16

» Compilateur FBPano
par Ouf_ca_passe Aujourd'hui à 12:25

» double guillemets "" dans un EDIT
par Marc Hier à 23:43

» Documentation de KGF
par Klaus Lun 20 Nov 2017 - 22:52

» Zoom sur une portion d'écran
par JL35 Lun 20 Nov 2017 - 21:51

» Recherche d'une expression dans un source
par Marc Lun 20 Nov 2017 - 13:08

» Tracer une grille n'importe où sur l'écran
par JL35 Dim 19 Nov 2017 - 22:14

» TourD Version 2
par Klaus Sam 18 Nov 2017 - 23:58

» La métamatière et le peuple
par JL35 Ven 17 Nov 2017 - 21:18

» Capture d'une zone de l'écran total
par JL35 Ven 17 Nov 2017 - 18:41

» qui peut résoudre mon prb
par pascal10000 Jeu 16 Nov 2017 - 17:30

» évènements et objets système : listage automatique
par Jean Claude Jeu 16 Nov 2017 - 11:15

Navigation
 Portail
 Index
 Membres
 Profil
 FAQ
 Rechercher
Rechercher
 
 

Résultats par :
 
Rechercher Recherche avancée
Novembre 2017
LunMarMerJeuVenSamDim
  12345
6789101112
13141516171819
20212223242526
27282930   
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 : 5594
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 : 5992
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 : 5594
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/
Minibug

avatar

Nombre de messages : 2364
Age : 51
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 http://gpp.panoramic.free.fr
jean_debord

avatar

Nombre de messages : 762
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 : 5594
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 : 5594
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: