1^ère partie : démonstration et fonctions APL.

Par Michel J. DUMONTIER

Introduction : Le journal est intitulé les nouvelles d’APL, et pourtant je vais faire resurgir le passé (1960 : presque 40 ans !, APL n’était pas encore né !) en actualisant par APL, donc en APLisant, des propriétés que j’avais découvertes en rédigeant un D.S. de Taupe (sujet de concours d’entrée aux ‘grandes écoles’) que le digne professeur sorti major d’Ulm n’avait pas compris mais qui a fini par comprendre lorsque, sur sa demande, je lui ai expliqué après le cours de maths !

Cette propriété, qui n’avait pas été demandée d’être démontrée, m’avait permis de faire des gros raccourcis dans les démonstrations demandées…ce qui m’avait permis, comme d’habitude, de finir et sortir avant les 4 heures fatidiques !

Anecdote 1: J’ai conservé la démonstration, mais je n’ai pas retrouvé le D.S. que j’avais mis dans un cartable vert format A1 avec tous mes exploits et que j’ai laissé dans un hôtel à Malakoff dans les années 70. Si quelqu’un le retrouve…ou l’a emprunté comme on dit maintenant avec l’évolution des mœurs, on ne sait jamais !

Anecdote 2 : j’avais promis à Gérard Langlet d’écrire ce présent article et de lui envoyer , mais j’ai toujours différé la rédaction, avec l’arrière pensée que, si je le publiais, Gérard écrirait une dizaine d’articles à la suite pour parler de ce sujet comme il l’a fait pour le Quinto…

La suite, ce sera pour le prochain numéro… !

Démonstration :

Condition nécessaire et suffisante pour qu’un polynôme P(x) soit tel que

P(x)­ x^r P(1/x)

(Je reproduis le texte strictement comme je l’ai écrit il y a 40 ans !)

Soit un polynôme P(x)=a_nxⁿ+a_n-hx^n-h+…+a_q+h’x^q+h’+a_qx^q   ordonné suivant les puissances décroissantes de x et où on symbolise les termes de rang h à partir du début et de rang h’ à partir de la fin par a_n-hx^n-h et a_q+h’x^q+h’ et où le terme de plus bas degré a pour degré q.

Formons P’(x)= x^r P(1/x)= a_nx^r-n+a_n-hx^r-n+h+…+a_q+h’x^r-q-h’+a_qx^r-q

Rangeons ce polynôme suivant les puissances décroissantes :

x^r P(1/x)= a_qx^r-q+a_q+h’x^r-q-h’+…+ a_n-hx^r-n+h+ a_nx^r-n

Condition Nécessaire :

identifions les termes de plus haut degré :

a_q=a_n    r-q=n … r=n+q                   }

                                                        }

identifions ceux de plus bas degré :     > c’est la même condition.

                                                        }

a_n=a_q    r-n=q … r=n+q                   }

Rang des termes pour que les degrés soient les mêmes :

n-h=r-q-h’  …  n-h=n+q-q-h’  …  -h=-h’  …  h=h’

Le polynôme devra donc être de la forme :

P(x)=a_nxⁿ+a_n-h1x^n-h1+…+a _n-h1 x^q+h1+a_nx^q

Où les coefficients équidistants des extrêmes sont égaux et où, à chaque terme de coefficient a_n-hi  et de degré n-hi correspond un terme et un seul de même coefficient a_n-hi  et de degré q+hi avec 0<hiˆp et où p est tel que si le nombre de termes est pair et égal à 2N … pˆN-1 et si le nombre de termes est impair et égal à 2N+1 … pˆN dans ce dernier cas, il n’y a qu’un terme pour lequel h=N si celui-ci existe.

Condition suffisante :

Soit un polynôme de la forme :

P(x)=a_nxⁿ+a_n-h1x^n-h1+ a_n-h2x^n-h2+…+ a_n-h2x^q+h2+a_n-h1x ^q+h1+a_nx^q

x^n+q P(1/x)= a_nx^q+a_n-h1x ^q+h1+ a_n-h2x^q+h2+…+ a_n-h2x^n-h2+a_n-h1x^n-h1+a_nxⁿ

donc:

Et c’est ici que cela devient intéressant :

PROPRIÉTÉS IMMÉDIATES :

Soit une fraction g(x) qui est le quotient de 2 tels polynômes tels que

j(x)=x ^n+q j(1/x)  et

f(x)=x ^m+l f(1/x) on a

g(x)= j(x)/ f(x) = x ^n+q / x ^m+l  g(1/x)

En particulier si n+q=m+l  alors

C.Q.F.D.

Implantation en APL.

Comme je le disais plus haut, n’ayant plus la famille de polynômes étudiés en prépa, il va falloir inventer des polynômes adéquats pour commencer.

Voici déjà quelques fonctions utiles de calcul de polynômes.

Valeur d’un polynôme de coefficients C pour la valeur X

Z„C P X

Z„XƒC

Exemple : Valeur du polynôme   x⁵+3x⁴+5x²+11 pour x=2

      1 3 0 5 0 11 P 2

111

(J’espère que les non aplistes qui voient cela pour la 1^ère fois vont apprécier, ou seront abattus, ou seront époustouflés ou … surtout si je leur dis que ce simple symbole antitruc utilisé pour la fonction "base", sert en premier lieu à calculer un nombre en bases multiples ; je sais, beaucoup répondront : on n’a pas appris cela à l’école ! tant pis pour eux, c’est aussi l’évolution des mœurs qui veut cela !)

Fonctions de base de calculs de polynômes :

Pour les fainéants et ceux qui ont l’esprit vectoriel (et non scalaire comme les non aplistes), voici la fonction PS qui calcule les valeurs d’un polynômes pour plusieurs valeurs de x.

Z„C PS X ;ŒIO

ŒIO„0 ª Z„(X°.*²¼½C)+.×C

Exemple : 

1 3 0 5 0 11 PS 2  4  7

111 1883 24266

PLUS, MOINS, FOIS (produit de polynômes)

Z„X PLUS Y

Z„((-Z)†X)+(-Z„(½,X)—½,Y)†Y

Z„X MOINS Y

Z„X PLUS -Y

Z„X FOIS Y

…(0=NR Y)/3

Z„(Xׯ1†Y) PLUS (X FOIS ¯1‡Y),0 ª …0

Z„0

      1 0 2 0 0 4 PLUS 3 0 2 2

1 0 5 0 2 6

Un gros polynôme MOINS un petit :

1 2 3 4 7 MOINS 2 5 4

1 2 1 ¯1 3

Le contraire :

2 4 6 MOINS 1 4 2 6 3

¯1 ¯4 0 ¯2 3

Rappel du binôme de Newton :

1 2 1 FOIS 1 3 3 1

1 5 10 10 5 1

Passons aux divisions : (cela nous intéresse pour le présent sujet).

Z„X DIVC Y;R9

…((NR X)>NR Y)/3

Z„R9, X DIVC ¯1‡Y MOINS X×R9„(¯1†Y)÷¯1†X ª …0

Z„¼0

Z„X DIVD Y

Z„(²X) DIVC ²Y

(Quand on est fainéant : il faut avoir des idées !)

      1 3 3 1 DIVC 1 5 10 10 5 1

1 2 1

      1 3 3 1 DIVD 1 5 10 10 5 1

1 2 1

Fonctions annexes:

On utilise la fonction (prudente) NR dans DIVC ; la voici :

Z„NR X

Z„+/X=X

Si un polynôme calculé a une succession de coefficients nuls dans les plus hauts degrés, il faut les supprimer, c’est ce que fait la fonction SUP suivante qu’on utilisera dans les restes de divisions.

Z„SUP C

Z„(+/^\0=C)‡C

Examples de divisions avec restes :

      C„1 2 1 ª E„9 7 10 10 5 1

      C DIVC E

1 3 3 1

      Œ„RESTE„E MOINS C FOIS C DIVC E

8 2 0 0 0 0

      (1 2 1 FOIS 1 3 3 1) PLUS 8 2 0 0 0 0

9 7 10 10 5 1

      C DIVD E

9 ¯11 23 ¯25

      Œ„RESTE„E MOINS C FOIS C DIVD E

0 0 0 0 32 26

      SUP RESTE

32 26

      (1 2 1 FOIS 9 ¯11 23 ¯25) PLUS 32 26

9 7 10 10 5 1

Une dernière fonction pour compléter : calcul des coefficients d’un polynôme dont on donne les racines.

Z„CPOLR R;ŒIO;A

ŒIO„0 ª Z„1,²((¼½R)°.=+š~A)+.×(R)×.*A„((½R)½2)‚¼2*½R

CPOLR 2 3 5

1 ¯10 31 ¯30

Vérifions:

(1 ¯2) FOIS (1 ¯3) FOIS 1 ¯5

1 ¯10 31 ¯30

Maintenant, nous sommes prêts à faire un exemple pour faire des essais :

Prenons au hasard, des polynômes symétriques de même degré.

      Œ„E„C,²C„5?10

2 6 7 1 4 4 1 7 6 2

      Œ„C„D,²D„5?10

3 2 0 4 6 6 4 0 2 3

      (C PS 2, ÷2)÷ (E PS 2, ÷2)

0.6993620415 0.6993620415

C.Q.F.Expérimenter !

 Construisons un générateur de polynômes P(x) tels que P(x) ­ x^r P(1/x)

Z„QH POL1SURX AN;P;N;Q;H;A;D;P1

N„¯1†AN ª Q„1†QH ª P„¯1†QH ªA„¯1‡AN ª D„DIFF 0,H„1‡QH ªZ„1†A

…((1+½QH)¬½AN)/FIN1

…((N-P)<(Q+P))/FIN2

BO:Z„Z,((¯1+(1†D))½0)ª A„1‡Aª …(0=½A)/SUIT1ª Z„Z,1†A ª D„1‡D

…(0=½D)/SUIT1 ª…BO

SUIT1:P1„Z ª …((N-P)=Q+P)/SYM

Z„Z,((¯1+N-(Q+2×P))½0)

SYM:Z„Z,²P1 ª Z„Z,(Q½0) ª …0

FIN1:'REVOYEZ HQ ET AN' ª …0

FIN2:'LE PLUS GROS COEFF DE LA 1ERE MOITIE EST TROP GROS'

Ceci va permettre aux curieux et expérimentateurs de tout poil, de s’amuser avec toutes sortes de polynômes en attendant le numéro suivant de la revue AFAPL.

Si quelqu’un fait des trouvailles il peut le faire savoir à la rédaction.

Je ne m’attends pas à quinze articles là-dessus !…

Exemple nous voulons générer le polynôme symétrique qui commence par

3x¹⁵+4x¹²+7x¹⁰ et que ça se débrouille pour trouver le reste !…

alors n=15, a_n=3, h₁=3, h₂=5, q=3, a_n-h1=4, a_n-h2=7

      Œ„C„ 3 3 5 POL1SURX 3 4 7 15

3 0 0 4 0 7 0 7 0 4 0 0 3 0 0 0

      C P 2

123928

      (C P ÷2)×2*(15+3)

123928

Ca marche !

Bon amusement !