Diapositive 3

Horner Williams George (1786-22.9.1837) - mathématicien anglais. Né à Bristol. Il y étudie et travaille, puis dans les écoles de Bath. Travaux de base sur l'algèbre. En 1819 a publié une méthode de calcul approximatif des racines réelles d'un polynôme, qui s'appelle maintenant la méthode de Ruffini-Horner (cette méthode était connue des Chinois au XIIIe siècle. Le schéma de division d'un polynôme par un binôme x-a est nommé). après Horner.

Diapositive 4

SCHÉMA HORNER

Une méthode de division d'un polynôme du nième degré par un binôme linéaire - a, basée sur le fait que les coefficients du quotient incomplet et le reste sont liés aux coefficients du polynôme divisé et aux formules :

Diapositive 5

Les calculs selon le schéma de Horner sont placés dans le tableau :

Exemple 1. Diviser Le quotient partiel est x3-x2+3x - 13 et le reste est 42=f(-3).

Diapositive 6

Le principal avantage de cette méthode est la compacité de la notation et la possibilité de diviser rapidement un polynôme en un binôme. En fait, le schéma de Horner est une autre forme d'enregistrement de la méthode de regroupement, même si, contrairement à cette dernière, il est totalement non visuel. La réponse (factorisation) s'obtient ici d'elle-même, et nous ne voyons pas le processus pour l'obtenir. Nous ne nous lancerons pas dans une justification rigoureuse du schéma de Horner, mais nous montrerons seulement comment il fonctionne.

Diapositive 7

Exemple 2.

Montrons que le polynôme P(x)=x4-6x3+7x-392 est divisible par x-7, et trouvons le quotient de la division. Solution. En utilisant le schéma de Horner, nous trouvons P(7) : De là, nous obtenons P(7)=0, c'est-à-dire le reste lors de la division d'un polynôme par x-7 est égal à zéro et, par conséquent, le polynôme P(x) est un multiple de (x-7). De plus, les nombres de la deuxième ligne du tableau sont les coefficients du. Quotient de P(x) divisé par (x-7), donc P(x)=(x-7)(x3+x2+7x+56).

Diapositive 8

Factorisez le polynôme x3 – 5x2 – 2x + 16.

Ce polynôme a des coefficients entiers. Si un entier est la racine de ce polynôme, alors c'est un diviseur du nombre 16. Ainsi, si un polynôme donné a des racines entières, alors celles-ci ne peuvent être que les nombres ±1 ; ±2 ; ±4 ; ±8 ; ±16. Par vérification directe nous sommes convaincus que le nombre 2 est la racine de ce polynôme, soit x3 – 5x2 – 2x + 16 = (x – 2)Q(x), où Q(x) est un polynôme du deuxième degré

Diapositive 9

Les nombres résultants 1, −3, −8 sont les coefficients du polynôme, obtenu en divisant le polynôme d'origine par x – 2. Cela signifie que le résultat de la division est : 1 x2 + (–3)x + ( –8) = x2 – 3x – 8. Le degré d'un polynôme résultant de la division est toujours inférieur de 1 au degré de celui d'origine. Donc : x3 – 5x2 – 2x + 16 = (x – 2)(x2 – 3x – 8).

Horner William George () mathématicien anglais. Les principales recherches concernent la théorie des équations algébriques. Développement d'une méthode de résolution approximative d'équations de tout degré. En 1819, il introduisit une méthode importante en algèbre consistant à diviser un polynôme en un binôme (x – a) (schéma de Horner).

Dérivation de formules pour le schéma de Horner Diviser le polynôme f(x) avec le reste par un binôme (x-c) signifie trouver un polynôme q(x) et un nombre r tel que f(x)=(x-c)q(x)+ r Écrivez cette égalité en détail : f 0 x n + f 1 x n-1 + f 2 x n-2 + …+f n-1 x + f n = =(x-c) (q 0 x n-1 + q 1 x n-2 + q 2 x n-3 +…+ q n-2 x + q n-1)+r Égalisons les coefficients aux mêmes puissances : x n : f 0 = q 0 => q 0 = f 0 x n-1 : f 1 = q 1 - c q 0 => q 1 = f 1 + c q 0 x n-2 : f 2 = q 2 - c q 1 => q 2 = f 2 + c q 1 … X 0 : f n = q n - c q n-1 => q n = f n + c q n-1 q 0 = f 0 x n-1 : f 1 = q 1 - c q 0 => q 1 = f 1 + c q 0 x n-2 : f 2 = q 2 - c q 1 => q 2 = f 2 + c q 1 … X 0 : f n = q n - c q n-1 => q n = f n + c q n-1">

Démonstration du fonctionnement du schéma de Horner En utilisant le schéma de Horner, on divise le polynôme f(x) = x 3 - 5x avec le reste par le binôme x-2 On note les coefficients du polynôme d'origine f 0, f 1, f 2, f 3. f0f0 f1f1 f2f2 f3f c 2 Si nous divisons sur (x-c), alors dans la deuxième ligne en partant de la gauche nous écrivons c Préparez des cellules vides pour le reste r et les coefficients du quotient incomplet q 0, q 1 ,q 2 q0q0 q1q1 q2q2 r g 0:=f 0 =1 1 g 1:= c *g 0 + f 1 * + =2 * 1 + (-5)=-3 g 2:= s *g 1 + f 2 =2 * (-3) + 0=-6 * + r:= s *g 2 + f 3 =2 * (-6) + 8= * + -4 Réponse : g(x)=x 2 -3x -6 ; r= -4. f(x)= (x-2)(x 2 -3x-6)-4

Développement d'un polynôme en puissances d'un binôme En utilisant le schéma de Horner, on développe le polynôme f(x)=x 3 +3x 2 -2x+4 en puissances d'un binôme (x+2) f(x)=x 3 +3x 2 -2x+4 =(x +2)(x 2 +x-4) f(x)=x 3 +3x 2 -2x+4= (x+2)((x-1)(x+2) -2) f(x)= x 3 +3x 2 -2x+4= (((1*(x+2)-3)(x+2)-2)(x+2)) f(x) = x 3 +3x 2 -2x+ 4 = (x+2)(x 2 +x-4)+12 = (x+2)((x-1)(x+2)-2)+12 = = (( (1*(x+2 )-3)(x+2)-2)(x+2))+12 = (x+2) 3 -3(x+2) 2 -2(x+2)+ 12

Devoir 1. Divisez f(x)=2x 5 -x 4 -3x 3 +x-3 par x-3 ; 2. À l'aide du schéma de Horner, trouvez les racines entières du polynôme f(x)=x 4 -2x 3 +2x 2 -x-6 (*Remarque : les racines entières d'un polynôme à coefficients entiers doivent être recherchées parmi les diviseurs du terme libre ±1;±2;± 3;±6)

Schéma de Horner - une méthode de division d'un polynôme

$$P_n(x)=\somme\limites_(i=0)^(n)a_(i)x^(n-i)=a_(0)x^(n)+a_(1)x^(n-1 )+a_(2)x^(n-2)+\ldots+a_(n-1)x+a_n$$

sur le binôme $x-a$. Vous devrez travailler avec un tableau dont la première ligne contient les coefficients d'un polynôme donné. Le premier élément de la deuxième ligne sera le nombre $a$, tiré du binôme $x-a$ :

Après avoir divisé un polynôme de nième degré par un binôme $x-a$, on obtient un polynôme dont le degré est inférieur de un à celui d'origine, c'est-à-dire est égal à $n-1$. L’application directe du schéma de Horner est plus facile à démontrer à l’aide d’exemples.

Exemple n°1

Divisez $5x^4+5x^3+x^2-11$ par $x-1$ en utilisant le schéma de Horner.

Faisons un tableau de deux lignes : dans la première ligne nous notons les coefficients du polynôme $5x^4+5x^3+x^2-11$, classés par ordre décroissant des puissances de la variable $x$. Notez que ce polynôme ne contient pas $x$ au premier degré, c'est-à-dire le coefficient de $x$ à la première puissance est 0. Puisque nous divisons par $x-1$, nous écrivons un dans la deuxième ligne :

Commençons par remplir les cellules vides de la deuxième ligne. Dans la deuxième cellule de la deuxième ligne, nous écrivons le nombre $5$, en le déplaçant simplement de la cellule correspondante de la première ligne :

Remplissons la cellule suivante selon ce principe : $1\cdot 5+5=10$ :

Remplissons la quatrième cellule de la deuxième ligne de la même manière : $1\cdot 10+1=11$ :

Pour la cinquième cellule on obtient : $1\cdot 11+0=11$ :

Et enfin, pour la dernière, sixième cellule, on a : $1\cdot 11+(-11)=0$ :

Le problème est résolu, il ne reste plus qu'à écrire la réponse :

Comme vous pouvez le constater, les nombres situés sur la deuxième ligne (entre un et zéro) sont les coefficients du polynôme obtenu après avoir divisé $5x^4+5x^3+x^2-11$ par $x-1$. Naturellement, puisque le degré du polynôme d'origine $5x^4+5x^3+x^2-11$ était égal à quatre, le degré du polynôme résultant $5x^3+10x^2+11x+11$ est un moins, c'est à dire. est égal à trois. Le dernier nombre de la deuxième ligne (zéro) signifie le reste lorsque l'on divise le polynôme $5x^4+5x^3+x^2-11$ par $x-1$. Dans notre cas, le reste est nul, c'est-à-dire les polynômes sont également divisibles. Ce résultat peut également être caractérisé comme suit : la valeur du polynôme $5x^4+5x^3+x^2-11$ pour $x=1$ est égale à zéro.

La conclusion peut aussi être formulée sous cette forme : puisque la valeur du polynôme $5x^4+5x^3+x^2-11$ à $x=1$ est égale à zéro, alors l'unité est la racine du polynôme 5 $^4+5x^3+ x^2-11 $.

Exemple n°2

Divisez le polynôme $x^4+3x^3+4x^2-5x-47$ par $x+3$ en utilisant le schéma de Horner.

Précisons immédiatement que l'expression $x+3$ doit être présentée sous la forme $x-(-3)$. Le projet de Horner impliquera exactement -3$. Puisque le degré du polynôme d'origine $x^4+3x^3+4x^2-5x-47$ est égal à quatre, alors par division nous obtenons un polynôme du troisième degré :

Le résultat signifie que

$$x^4+3x^3+4x^2-5x-47=(x+3)(x^3+0\cdot x^2 +4x-17)+4=(x+3)(x^ 3+4x-17)+4$$

Dans cette situation, le reste en divisant $x^4+3x^3+4x^2-5x-47$ par $x+3$ est de 4$. Ou, ce qui revient au même, la valeur du polynôme $x^4+3x^3+4x^2-5x-47$ pour $x=-3$ est égale à $4$. À propos, cela est facile à vérifier en remplaçant directement $x=-3$ dans le polynôme donné :

$$x^4+3x^3+4x^2-5x-47=(-3)^4+3 \cdot (-3)^3-5 \cdot (-3)-47=4.$$

Ceux. Le schéma de Horner peut être utilisé si vous devez trouver la valeur d'un polynôme pour une valeur donnée d'une variable. Si notre objectif est de trouver toutes les racines d’un polynôme, alors le schéma de Horner peut être appliqué plusieurs fois de suite jusqu’à épuiser toutes les racines, comme indiqué dans l’exemple n°3.

Exemple n°3

Trouvez toutes les racines entières du polynôme $x^6+2x^5-21x^4-20x^3+71x^2+114x+45$ en utilisant le schéma de Horner.

Les coefficients du polynôme en question sont des nombres entiers et le coefficient de la puissance la plus élevée de la variable (c'est-à-dire $x^6$) est égal à un. Dans ce cas, les racines entières du polynôme doivent être recherchées parmi les diviseurs du terme libre, c'est-à-dire parmi les diviseurs du nombre 45. Pour un polynôme donné, ces racines peuvent être les nombres $45 ; \; 15 ; \; 9 ; \; 5 ; \; 3 ; \; 1$ et -45$; \; -15 ; \; -9 ; \; -5 ; \; -3 ; \; -1$. Vérifions, par exemple, le nombre $1$ :

Comme vous pouvez le voir, la valeur du polynôme $x^6+2x^5-21x^4-20x^3+71x^2+114x+45$ avec $x=1$ est égale à $192$ (le dernier nombre dans la deuxième ligne), et non $0 $, donc l'unité n'est pas la racine de ce polynôme. Puisque la vérification a échoué, vérifions la valeur $x=-1$. Nous ne créerons pas de nouvelle table pour cela, mais continuerons à utiliser la table. N° 1, en y ajoutant une nouvelle (troisième) ligne. La deuxième ligne, dans laquelle la valeur de $1$ a été cochée, sera surlignée en rouge et ne sera plus utilisée dans les discussions ultérieures.

Vous pouvez bien sûr simplement réécrire le tableau, mais le remplir manuellement prendra beaucoup de temps. De plus, il peut y avoir plusieurs nombres dont la vérification échouera, et il est difficile d'écrire un nouveau tableau à chaque fois. Lors du calcul « sur papier », les lignes rouges peuvent simplement être barrées.

Ainsi, la valeur du polynôme $x^6+2x^5-21x^4-20x^3+71x^2+114x+45$ à $x=-1$ est égale à zéro, c'est-à-dire le nombre $-1$ est la racine de ce polynôme. Après avoir divisé le polynôme $x^6+2x^5-21x^4-20x^3+71x^2+114x+45$ par le binôme $x-(-1)=x+1$ on obtient le polynôme $x ^5+x ^4-22x^3+2x^2+69x+45$, dont les coefficients sont tirés de la troisième ligne du tableau. N°2 (voir exemple n°1). Le résultat des calculs peut également être présenté sous cette forme :

\begin(équation)x^6+2x^5-21x^4-20x^3+71x^2+114x+45=(x+1)(x^5+x^4-22x^3+2x^2 +69x+45)\fin(équation)

Continuons la recherche de racines entières. Nous devons maintenant rechercher les racines du polynôme $x^5+x^4-22x^3+2x^2+69x+45$. Là encore, les racines entières de ce polynôme sont recherchées parmi les diviseurs de son terme libre, les nombres $45$. Essayons de vérifier à nouveau le nombre $-1$. Nous ne créerons pas de nouveau tableau, mais continuerons à utiliser le tableau précédent. N ° 2, c'est-à-dire Ajoutons-y une ligne supplémentaire :

Ainsi, le nombre $-1$ est la racine du polynôme $x^5+x^4-22x^3+2x^2+69x+45$. Ce résultat peut s'écrire ainsi :

\begin(équation)x^5+x^4-22x^3+2x^2+69x+45=(x+1)(x^4-22x^2+24x+45) \end(équation)

Compte tenu de l'égalité (2), l'égalité (1) peut être réécrite sous la forme suivante :

\begin(équation)\begin(aligné) & x^6+2x^5-21x^4-20x^3+71x^2+114x+45=(x+1)(x^5+x^4-22x ^2+2x^2+69x+45)=\\ & =(x+1)(x+1)(x^4-22x^2+24x+45)=(x+1)^2(x^ 4-22x^2+24x+45)\fin(aligné)\fin(équation)

Il faut maintenant chercher les racines du polynôme $x^4-22x^2+24x+45$ - naturellement, parmi les diviseurs de son terme libre (les nombres $45$). Vérifions à nouveau le nombre $-1$ :

Le nombre $-1$ est la racine du polynôme $x^4-22x^2+24x+45$. Ce résultat peut s'écrire ainsi :

\begin(équation)x^4-22x^2+24x+45=(x+1)(x^3-x^2-21x+45) \end(équation)

Compte tenu de l'égalité (4), on réécrit l'égalité (3) sous la forme suivante :

\begin(équation)\begin(aligné) & x^6+2x^5-21x^4-20x^3+71x^2+114x+45=(x+1)^2(x^4-22x^3 +24x+45)= \\ & =(x+1)^2(x+1)(x^3-x^2-21x+45)=(x+1)^3(x^3-x^ 2-21x+45)\fin(aligné)\fin(équation)

Nous recherchons maintenant les racines du polynôme $x^3-x^2-21x+45$. Vérifions à nouveau le nombre $-1$ :

Le contrôle s'est soldé par un échec. Soulignons la sixième ligne en rouge et essayons de vérifier un autre nombre, par exemple le nombre $3$ :

Le reste est nul, donc le nombre $3$ est la racine du polynôme en question. Donc $x^3-x^2-21x+45=(x-3)(x^2+2x-15)$. Maintenant, l'égalité (5) peut être réécrite comme suit.

Calculer la valeur d’un polynôme en un point est l’un des problèmes de programmation classiques les plus simples.
Lors de la réalisation de différents types de calculs, il est souvent nécessaire de déterminer les valeurs des polynômes pour des valeurs données des arguments. Souvent, le calcul approximatif des fonctions se résume au calcul de polynômes approximatifs.
Le lecteur moyen de Habrahabr ne peut pas être qualifié d’inexpérimenté dans l’utilisation de toutes sortes de perversions. Une personne sur deux dira que le polynôme doit être calculé à l'aide de la règle de Horner. Mais il y a toujours un petit « mais », le plan de Horner est-il toujours le plus efficace ?

Schéma Horner

Des exceptions

Y a-t-il autre chose, puisque le système de Horner est le plus économique ?

Dans certains cas, il est conseillé d'utiliser des schémas en deux étapes pour obtenir des valeurs polynomiales. Dans un premier temps, les actions sont effectuées uniquement sur les coefficients du polynôme ; celui-ci est converti sous une forme spéciale. Dans un deuxième temps, la valeur du polynôme lui-même est calculée pour les valeurs données de l'argument. Dans ce cas, il se peut que le nombre d’opérations effectuées à la deuxième étape soit inférieur à celui des calculs utilisant le schéma de Horner.

Encore une fois, notez que de telles méthodes de calcul sont utiles lors du calcul des valeurs d'un polynôme pour un grand nombre de valeurs de x. Le gain est obtenu du fait que la première étape du polynôme n'est effectuée qu'une seule fois. Un exemple est le calcul de fonctions élémentaires, où le polynôme d'approximation est préparé à l'avance.

Dans d'autres discussions, parlant du nombre d'opérations de calcul, je garderai à l'esprit la complexité de la deuxième étape des calculs.

Schéma de J. Todt pour les polynômes de degré 6

Les coefficients sont déterminés par la méthode des coefficients indéterminés basés sur la condition. À partir de la dernière condition, nous composons un système d'équations, assimilant les coefficients de degrés égaux de polynômes.

Je ne présenterai pas ici le système lui-même. Mais il est facilement résolu par la méthode de substitution, auquel cas vous devez résoudre des équations quadratiques. Les coefficients peuvent s'avérer complexes, mais si les coefficients s'avèrent réels, alors les calculs nécessitent trois multiplications et sept additions au lieu de cinq multiplications et six additions selon le schéma de Horner.

Il n’est pas nécessaire de parler de l’universalité de ce schéma, mais le lecteur peut clairement apprécier la réduction du nombre d’opérations par rapport au schéma de Horner.

Schéma Yu.L. Ketkova

Yu.L. Ketkov a donné une représentation générale du polynôme du nième degré pour n>5, qui conduit toujours à des expressions réelles et nécessite [(n+1)/2]+ multiplications et n+1 additions pour calculer le polynôme du nième degré.

Par exemple, avec n=2k, le schéma de Ketkov se réduit à trouver des polynômes :

Tous les coefficients inconnus sont trouvés à partir de l'égalité. Dans les travaux de Ketkov, une méthode est donnée pour résoudre les systèmes résultants, qui donne toujours des coefficients réels.

Schémas de V.Ya. Pana

V.Ya. Pan a travaillé sur des problèmes de calcul optimal de polynômes. Il a notamment proposé plusieurs schémas de calcul de polynômes réels, très proches des estimations d'E. Belaga. Je vais donner quelques schémas de Pan pour des polynômes réels.
1. Schéma de calcul des polynômes du quatrième degré.
Un polynôme est considéré.

Présentons-le sous la forme :

Pour calculer la valeur d'un polynôme, nous utilisons les expressions suivantes :

Ce circuit nécessite une multiplication et une addition dans la deuxième étape.

La particularité de ce schéma est que les coefficients existent toujours pour les coefficients réels du polynôme d'origine.

Chez V.Ya. Pan, il existe d'autres schémas de calcul de polynômes, y compris des schémas complexes.

Conclusion

Cependant, si le nombre de valeurs polynomiales à calculer est important et que les performances sont très importantes, il est alors logique d'envisager l'utilisation de méthodes spéciales pour calculer les polynômes.

Certains lecteurs diront que jouer avec des projets autres que ceux de Horner est difficile, fastidieux et ne vaut pas la peine de s'y intéresser. Cependant, dans la vraie vie, il existe des problèmes dans lesquels vous devez simplement calculer un grand nombre de valeurs de polynômes avec de grandes puissances (par exemple, leur calcul peut prendre des mois), et réduire de moitié le nombre de multiplications donnera un gain significatif. gain de temps, même s'il faut passer quelques jours pour mettre en œuvre un schéma spécifique de calcul de polynômes.

Littérature

1. Ketkov Yu.L. À propos d'une façon de calculer des polynômes sur des machines mathématiques. // Actualités de l'Université, vol. 1., n° 4, 1958.
2. V. Ya. Pan, « Calcul de polynômes utilisant des schémas avec traitement préliminaire des coefficients et un programme de recherche automatique de paramètres », Zh. mathématiques. et les mathématiques. Fiz., 2:1 (1962), 133-140
3. V. Ya. Pan, « Sur les méthodes de calcul des valeurs des polynômes », Uspekhi Mat, 21 : 1(127) (1966), 103-134.
4. V. Ya. Pan, « Sur le calcul des polynômes du cinquième et septième degré avec des coefficients réels », Zh. mathématiques. et les mathématiques. Fiz., 5 : 1 (1965), 116-118
5. Pan V. Ya. Quelques schémas de calcul des valeurs de polynômes avec des coefficients réels. Problèmes de cybernétique. Vol. 5. M. : Nauka, 1961, 17-29.
6. Belaga E. G. Sur le calcul des valeurs d'un polynôme à une variable avec traitement préalable des coefficients. Problèmes de cybernétique. Vol. 5. M. : Fizmatgiz, 1961, 7-15.

Vous pouvez aider et transférer des fonds pour le développement du site

Calculer la valeur d’un polynôme en un point est l’un des problèmes de programmation classiques les plus simples.
Lors de la réalisation de différents types de calculs, il est souvent nécessaire de déterminer les valeurs des polynômes pour des valeurs données des arguments. Souvent, le calcul approximatif des fonctions se résume au calcul de polynômes approximatifs.
Le lecteur moyen de Habrahabr ne peut pas être qualifié d’inexpérimenté dans l’utilisation de toutes sortes de perversions. Une personne sur deux dira que le polynôme doit être calculé à l'aide de la règle de Horner. Mais il y a toujours un petit « mais », le plan de Horner est-il toujours le plus efficace ?


Mon objectif n’est pas de décrire précisément des algorithmes de calcul de polynômes, mais seulement de montrer que dans certains cas il est possible (nécessaire) d’appliquer d’autres schémas que les règles de Horner. Pour ceux qui sont intéressés par le matériel, à la fin de l'article se trouve une liste de références qui peuvent être consultées pour une étude plus détaillée de la question.
De plus, il est parfois dommage que les noms de nos mathématiciens russes restent peu connus. De plus, je suis simplement heureux de parler du travail de nos mathématiciens.

Schéma Horner

Des exceptions

Y a-t-il autre chose, puisque le système de Horner est le plus économique ?

Dans certains cas, il est conseillé d'utiliser des schémas en deux étapes pour obtenir des valeurs polynomiales. Dans un premier temps, les actions sont effectuées uniquement sur les coefficients du polynôme ; celui-ci est converti sous une forme spéciale. Dans un deuxième temps, la valeur du polynôme lui-même est calculée pour les valeurs données de l'argument. Dans ce cas, il se peut que le nombre d’opérations effectuées à la deuxième étape soit inférieur à celui des calculs utilisant le schéma de Horner.

Encore une fois, notez que de telles méthodes de calcul sont utiles lors du calcul des valeurs d'un polynôme pour un grand nombre de valeurs de x. Le gain est obtenu du fait que la première étape du polynôme n'est effectuée qu'une seule fois. Un exemple est le calcul de fonctions élémentaires, où le polynôme d'approximation est préparé à l'avance.

Dans d'autres discussions, parlant du nombre d'opérations de calcul, je garderai à l'esprit la complexité de la deuxième étape des calculs.

Schéma de J. Todt pour les polynômes de degré 6

Les coefficients sont déterminés par la méthode des coefficients indéterminés basés sur la condition. À partir de la dernière condition, nous composons un système d'équations, assimilant les coefficients de degrés égaux de polynômes.

Je ne présenterai pas ici le système lui-même. Mais il est facilement résolu par la méthode de substitution, auquel cas vous devez résoudre des équations quadratiques. Les coefficients peuvent s'avérer complexes, mais si les coefficients s'avèrent réels, alors les calculs nécessitent trois multiplications et sept additions au lieu de cinq multiplications et six additions selon le schéma de Horner.

Il n’est pas nécessaire de parler de l’universalité de ce schéma, mais le lecteur peut clairement apprécier la réduction du nombre d’opérations par rapport au schéma de Horner.

Schéma Yu.L. Ketkova

Yu.L. Ketkov a donné une représentation générale du polynôme du nième degré pour n>5, qui conduit toujours à des expressions réelles et nécessite [(n+1)/2]+ multiplications et n+1 additions pour calculer le polynôme du nième degré.

Par exemple, avec n=2k, le schéma de Ketkov se réduit à trouver des polynômes :

Tous les coefficients inconnus sont trouvés à partir de l'égalité. Dans les travaux de Ketkov, une méthode est donnée pour résoudre les systèmes résultants, qui donne toujours des coefficients réels.

Schémas de V.Ya. Pana

V.Ya. Pan a travaillé sur des problèmes de calcul optimal de polynômes. Il a notamment proposé plusieurs schémas de calcul de polynômes réels, très proches des estimations d'E. Belaga. Je vais donner quelques schémas de Pan pour des polynômes réels.
1. Schéma de calcul des polynômes du quatrième degré.
Un polynôme est considéré.

Présentons-le sous la forme :

Pour calculer la valeur d'un polynôme, nous utilisons les expressions suivantes :

Ce circuit nécessite une multiplication et une addition dans la deuxième étape.

La particularité de ce schéma est que les coefficients existent toujours pour les coefficients réels du polynôme d'origine.

Chez V.Ya. Pan, il existe d'autres schémas de calcul de polynômes, y compris des schémas complexes.

Conclusion

Cependant, si le nombre de valeurs polynomiales à calculer est important et que les performances sont très importantes, il est alors logique d'envisager l'utilisation de méthodes spéciales pour calculer les polynômes.

Certains lecteurs diront que jouer avec des projets autres que ceux de Horner est difficile, fastidieux et ne vaut pas la peine de s'y intéresser. Cependant, dans la vraie vie, il existe des problèmes dans lesquels vous devez simplement calculer un grand nombre de valeurs de polynômes avec de grandes puissances (par exemple, leur calcul peut prendre des mois), et réduire de moitié le nombre de multiplications donnera un gain significatif. gain de temps, même s'il faut passer quelques jours pour mettre en œuvre un schéma spécifique de calcul de polynômes.

Littérature

1. Ketkov Yu.L. À propos d'une façon de calculer des polynômes sur des machines mathématiques. // Actualités de l'Université, vol. 1., n° 4, 1958.
2. V. Ya. Pan, « Calcul de polynômes utilisant des schémas avec traitement préliminaire des coefficients et un programme de recherche automatique de paramètres », Zh. mathématiques. et les mathématiques. Fiz., 2:1 (1962), 133-140
3. V. Ya. Pan, « Sur les méthodes de calcul des valeurs des polynômes », Uspekhi Mat, 21 : 1(127) (1966), 103-134.
4. V. Ya. Pan, « Sur le calcul des polynômes du cinquième et septième degré avec des coefficients réels », Zh. mathématiques. et les mathématiques. Fiz., 5 : 1 (1965), 116-118
5. Pan V. Ya. Quelques schémas de calcul des valeurs de polynômes avec des coefficients réels. Problèmes de cybernétique. Vol. 5. M. : Nauka, 1961, 17-29.
6. Belaga E. G. Sur le calcul des valeurs d'un polynôme à une variable avec traitement préalable des coefficients. Problèmes de cybernétique. Vol. 5. M. : Fizmatgiz, 1961, 7-15.