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
» quel est ce comportement de Panoramic_editor
par Oscaribout Aujourd'hui à 3:02

» bug BORDER_HIDE : bloque la commande full_space
par silverman Aujourd'hui à 1:19

» Découpe dans une image
par JL35 Hier à 22:00

» FNC IsDateValide(d$) pour vérifier la validité d'une date
par papydall Hier à 18:57

» Pour faire plaisir à jjn4.
par Pedro Alvarez Hier à 8:13

» Pour faire plaisir à Marc37.
par Marc Jeu 22 Fév 2018 - 21:46

» Couleur d'une variable qui n'est pas un mot-clé
par bignono Jeu 22 Fév 2018 - 14:03

» Un catalogue de photos de fleurs, avec KBDD, affichage HTML
par Klaus Mer 21 Fév 2018 - 22:44

» KGF_dll - nouvelles versions
par Klaus Mer 21 Fév 2018 - 22:30

» Mah-Jong anglais
par jjn4 Mer 21 Fév 2018 - 14:22

» Partie fractionnaire d'un flottant
par silverman Mer 21 Fév 2018 - 14:19

» bug CREATE_HIDE : corruption de form
par silverman Mer 21 Fév 2018 - 13:32

» Racine carrée d’un nombre par l’algorithme de Héron
par Ouf_ca_passe Mer 21 Fév 2018 - 9:52

» Méthode manuelle d'extraction de la racine carrée
par pascal10000 Mer 21 Fév 2018 - 7:47

» [annulé]ON_MOVE n,l ne fonctionne que sur le form 0
par silverman Mar 20 Fév 2018 - 16:52

Navigation
 Portail
 Index
 Membres
 Profil
 FAQ
 Rechercher
Rechercher
 
 

Résultats par :
 
Rechercher Recherche avancée
Février 2018
LunMarMerJeuVenSamDim
   1234
567891011
12131415161718
19202122232425
262728    
CalendrierCalendrier

Partagez | 
 

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

Aller en bas 
AuteurMessage
papydall

avatar

Nombre de messages : 5746
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 - 2: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 : 6152
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 - 21:19

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

avatar

Nombre de messages : 5746
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 - 0: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 : 2522
Age : 51
Localisation : Vienne (86)
Date d'inscription : 09/02/2012

MessageSujet: Re: Evaluer un polynôme en un point par la méthode de Horner   Lun 12 Déc 2016 - 7: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 : 779
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 - 9: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 : 5746
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 - 13: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 - 16: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 : 5746
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 - 16: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
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: