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

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 ============================================================================

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 ============================================================================