Polynômes (dont trinômes) . Algorithmes en Langage Pascal pour Atari ST (Pure Pascal, HiSpeed Pascal) et Turbo Pascal

Accueil

Lexique

Unités

ALGORITHMES

Tutoriel

Cette page est en cours de construction...

Dans cette première version de page sur les polynômes, le type Polynome utilise des tableaux "statiques" (donné par le type Array), mais une version ultérieure utilisera les tableaux dynamiques (avec les pointeurs en Pascal). La version statique occupe ici bcp de place (65536 index, même avec un degre très inférieur), alors qu'avec la version "tableau dynamique" cela ne consommera QUE la mémoire nécessaire à chaque polynôme.

Cette page est consacrée aux algorithmes de Polynômes en langage Pascal. Elle est issue en grande partie (la majorité des algorithmes), du cours "Programmation et calcul scientifique" du Conservatoire National des Arts et Métiers", dispensé par Michel Lalos en 1993-1994. J'y ai ajouté des détails comme la démonstraton des dérivées de polynômes, sur les index des types array, etc.

Un polynôme est une formule mathématiques de la forme:
a₀x⁰ + a₁x¹ + a₂x² + .. + a_nxⁿ

Bien entendu, cela inclut les polynômes de degré 1 (résolution d'équation du 1^er degré) et les trinômes de type a.x²+b.x+c. Le degré d'un polynôme est la plus grande puissance de X de ce polynôme.

Pour manipuler les polynômes, on va créer un type d'enregistrement "Polynome" contenant 2 variables:

un entier (j'ai choisi le type word mais ça pourrait être un longint) "degre" indiquant le degré du polynôme (autrement dit, la plus grande puissance)
un tableau de réels correspondant aux coefficients dudit polynôme. Un coefficient peut, évidemment, avoir la valeur 0

Type
    Polynome : Record
        degre : word;
        coef : array [word] of real;
    end;

En langage Pascal, lorsqu'on déclare une variable quelconque, ici un tableau, les valeurs sont initialisées automatiquement à 0.
Toujours en Pascal, contrairement au langage C (limité aux seul types "int"), les index des tableaux peuvent être de différents types : entiers, énumérés, interval, char ou même booléen! De ce fait, la limite d'index est celle du type couvrant le plus large champ de valeurs, c'est à dire LongInt (plus de 2 milliards de valeurs puisque LongInt est un type signé). Dans cette page, je limite le nombre d'index à 65536 en utilisant le type word dans l'index, mais libre à vous de l'adapter. De même, il n'y a pas de tests de conditions limites dans les fonction (avec la procédure RunError).

Les variables peuvent être de type réels (Type real) ou complexes, mais dans ce chapitre, on écrira des algorithmes préférentiellement dans le corps des Réels (pour les coefficients). A vous d'adapter les types de variables pour vos propres besoins.

Trinômes
1. Résolutions de trinômes
Polynômes
1. Calcul d'un polynôme (avec X donné en paramètre)
2. Somme de 2 polynômes
3. Multiplication de 2 polynômes
4. Dérivée d'un polynôme
5. Intégrale d'un polynôme
6. Division euclidienne de 2 polynômes
7. Interpolation polynôme de Lagrange

I. Les trinômes

Chapitre en cours d'étude...

Un trinôme est un polynôme de degré 2. On peut définir les types Complex et trinome_roots :

Type
    Complex : Array ['a'..'b'] of real;
    trinome_roots : record
        nb_roots : byte {1 ou 2 resultats dans le corps des complexes}
        X : array [1..2] of Complex;
    end;

On va définir le type Complex comme :

I.1. Résolutions de trinômes

Il s'agit de la classique résolution de trinômes tels qu'on nous l'enseigne au lycée. On a une variable interne Delta et on renvoie le nombre de valeurs résultantes (1 ou 2) et le résultat sous forme de tableaux à 2 entrées (complexes).

L'appel à cette fonction peut se faire en donnant en paramètres, les 3 coefficients d'un polynôme de degré 3:

result := trinome_solve(Pol1.coef[2],Pol1.coef[1],Pol1.coef[0]);

Puisque a est de degré 2, b de degré 1 et c de degré 0, on positionne les index en ordre décroissant.
result est, ici, de type trinome_roots.

Function trinome_solve (a,b,c : real):trinome_roots;
var
    delta : real;
    solution:trinome_roots;
begin
    delta:=sqr(b)-4*a*c;
    with solution do
    begin
        x[1,'a']:=-b/(2*a);
        x[2,'a']:=x[1,'a'];
        if delta>0 then
        begin
            inc(nb_roots);{nb_roots est initialisé à 0}
            x[1,'a']:=x[1,'a']-sqrt(delta)/(2*a);
            x[2,'a']:=x[2,'a']+sqrt(delta)/(2*a);
        end;
        if delta<0 then
        begin
            inc(nb_roots);
            x[1,'b']:=-sqrt(-delta)/(2*a);
            x[2,'b']:=sqrt(-delta)/(2*a);
        end;
    end;
    trinome_solve:=solution;
end;

En Turbo Pascal/Free Pascal, on ne peut pas appliquer des opérations sur les fonctions elles même. Voilà pourquoi on a utilisé une variable interne Solution.
Pour les nombres complexes, on constate qu'il y a toujours la même constante -b/2a en résultat minimum. L'opération avec delta ne s'ajoute (soit à la partie réelle, soit à la partie imaginaire) que si ce dernier n'est pas nul (en inversant le signe de delta si celui ci est négatif).

II. Polynômes

Les fonctions et procédures de ce chapitre fonctionnent mais une étude est en cours pour l'adapter à des types tableau dynamique compatible aux standards Turbo Pascal

II.1. Calcul d'un polynôme

Cette fonction a en paramètre, un polynôme, une valeur réelle pour le X et renvoie le résultat. Pour donner le résultat, on fait une boucle où, à partir du degré N jusqu'au degré 1, on multiplie par X et on ajoute le coef d'indice inférieur.

Function polynome_sol (Pol : Polynome ; X : real):real;
var
    i : word;
    y : real;
begin
    y := Pol.coef[Pol.degre];
    for i:=pol.degre downto 1 do
        y := y*x+Pol.coef[i-1];
    polynome_sol:=y;
end;

III.2. Somme de 2 polynômes

Cette fonction retourne la somme de 2 polynômes qui peuvent être de degré différents. Les coefficients du résultat est la somme des coefficients de même degrés des 2 polynômes.

Function polynome_sum (Pol1,Pol2 : Polynome):Polynome;
var
    Q : polynome;
    i,n : word;
begin
    if Pol1.degre>Pol2.degre then
    Begin
        Q:=Pol1;
        for i:=0 to Pol2.degre do
            Q.coef[i]:=Q.coef[i]+Pol2.coef[i];
    end
    else
    Begin
        Q:=Pol2;
        for i:=0 to Pol1.degre do
            Q.coef[i]:=Q.coef[i]+Pol1.coef[i];
    end;
    polynome_sum:=q;
end;

II.3. Multiplication de 2 polynômes

Cette fonction multiplie 2 polynômes de degrés deg1 et deg2. Le résultat est un polynôme de degré deg1+deg2 (somme des degrés des 2 polynômes).
La méthode est celle de la distributivité de la multiplication sur l'addition. Exemple :

(a.x²+b.x+c).(d.x+e) = (a.d).x³ + (a.e + b.d).x² + (b.e + c.d).x + c.e

On obtient un ensemble de (n+p) coefficients dont chacun d'eux est donné par la combinaison linéaire des produits 2 à 2 de coefficients dont la somme des degrés donne le degré du coefficient. Pour ainsi dire, on fera 2 boucles (complexité N²) dans lesquels, le coefficient c[i+j] du résultat sera mis à jour par :

c[i+j] = c[i+j]+a[i]*b[j]

On peut donc écrire la fonction :

Function polynome_mul (Pol1,Pol2 : Polynome):Polynome;
var
    Q : polynome;
    i,j : word;
begin
    Q.degre:=Pol1.degre+Pol2.degre;
    for i:=0 to Pol1.degre do
        for j:=0 to Pol2.degré do
            Q.coef[i+j] := Q.coef[i+j] + Pol1.coef[i]*Pol2.coef[j];
    polynome_mul:=q;
end;

II.4. Dérivée de polynôme

La dérivée d'un polynôme est la somme des dérivées des termes de ce polynôme. On va démontrer quelle est la dérivée d'un terme m.xⁿ.

Soit m.(X+dX)ⁿ. D'après le triangle de Pascal : m.(X+dX)ⁿ = m.(Xⁿ + Cⁿ₁.X^n-1.dX + Cⁿ₂.X^n-2.dX² + .. + Cⁿ_n-2.X².dX^n-2 + Cⁿ_n-1.X¹.dX^n-1 + dXⁿ) Cⁿ_k est le Combinatoire de k parmi n A partir de dX² (inclus), les termes sont négligeables On ne garde donc que Xⁿ + Cⁿ₁.X^n-1.dX pour le calcul de la dérivée. A.dX représente la droite tangente à la courbe au point X=X₀. Que vaut le coefficient directeur A (A est alors la dérivée) ? On a m.(X+dX)ⁿ ≈ m.(Xⁿ + Cⁿ₁.X^n-1.dX) m.(X+dX)ⁿ ≈ m.Xⁿ + m.Cⁿ₁.X^n-1.dX Avec Cⁿ₁ = n!/((n-1)!.1!) = n, il vient A.dX = m.n.X^n-1.dX, soit A=m.n.X^n-1 En conclusion d(m.Xⁿ) = m.n.X^n-1, (m étant le coefficient de degré n)

De là, on peut écrire la fonction dérivée de polynôme :

Function polynome_der (Pol : Polynome):Polynome;
var
    Q : polynome;
    i : word;
begin
    Q.degre:=Pol.degre-1;
    for i:=Pol.degre downto 1
        Q.coef[i-1] := i * Pol.coef[i];
    polynome_der:=q;
end;

II.5. Intégrale de polynôme

Il s'agit de la fonction inverse de la dérivée.

Function polynome_int (Pol : Polynome):Polynome;
var
    Q : polynome;
    i : word;
begin
    Q.degre:=Pol.degre+1;
    for i:=Q.degre downto 1
        Q.coef[i] := Pol.coef[i-1]/i;
    polynome_int:=q;
end;

Sommaire Algorithmes