Horner-Schema – Wikipedia
Le Schéma de corne (Selon William George Horner) est un processus de transformation pour les polynômes afin de faciliter le calcul des valeurs fonctionnelles. Il peut être utilisé pour simplifier la division polynomiale ainsi que le calcul des points zéro et des dérivations.
À un polynôme
de la part
Ceci provient de n’importe quel anneau de polynomie Schéma de corne défini comme:
- [d’abord]
Arithmétique [ Modifier | Modifier le texte source ]]
Dans le cas des polynomes dans l’orthographe classique, les puissances doivent
,
etc. peut être calculé si la valeur de la fonction à un point
doit être calculé. Dans le polynôme converti selon le schéma Horner, il n’y a pas de puissance, mais seulement la multiplication et l’addition. Le calcul est accéléré car moins de multiplications sont nécessaires: leur nombre est réduit à près de la moitié en utilisant le schéma Horner.
Dans l’orthographe classique sont
Multiplications dans un polynôme à partir du degré
nécessaire:
- Multiplications pour la formation de puissances ; [2]
- plus loin Multiplications pour la multiplication des puissances Avec leurs coefficients.
Dans l’ensemble, vous en avez besoin
Multiplications pour le calcul.
Dans le schéma de cornes, en revanche, vous venez
Multiplications.
Dans les deux cas, le nombre de – calcul moins complexes – ajouts est le même, à savoir
.
Procédure [ Modifier | Modifier le texte source ]]
Grâce à l’exclusion continue des variables de polynomie libre
Le polynôme est représenté comme une boîte de produits et de sommes.
Exemple [ Modifier | Modifier le texte source ]]
L’exemple suivant illustre l’effort informatique inférieur sur le schéma Horner:
Dans la représentation classique (côté gauche), en plus des ajouts, soustractions et multiplications, trois puissances sont formées, qui sont enregistrées par les multiplications en utilisant les schémas Horner (côté droit) et sont donc éliminés. Si les résultats intermédiaires réutilisent, vous enregistrez trois multiplications.
Application [ Modifier | Modifier le texte source ]]
Dans l’analyse, les valeurs du polynôme et de sa dérivation doivent souvent être calculées: que ce soit pour déterminer un point zéro, effectuer une discussion de courbe ou pour esquisser un graphique.
Le formulaire illustré ici est particulièrement adapté au calcul dans la notation polonaise inverse (UPN).
Entre 1975 et 2003, l’impôt sur le revenu dans le FRG a été calculé selon le régime Horner afin d’éviter les erreurs de circulation dans le calcul avec des ordinateurs de poche électronique ou des ordinateurs et donc d’assurer une certitude juridique. [3] [4]
Dérivation [ Modifier | Modifier le texte source ]]
Prenons l’exemple ci-dessus et définissez:
Vous transférez maintenant les coefficients, les produits intermédiaires et les quantités partielles dans une table de trente, avec le
Première ligne les coefficients sont entrés. Les montants partiels entrent dans la troisième ligne. Le premier coefficient de polynôme est repris directement. La quantité partielle précédemment calculée multipliée par
Entraîne ensuite la somme suivante, que vous entrez ensuite dans la deuxième ligne parmi les coefficients suivants.
Vous obtenez donc progressivement le schéma de calcul suivant:
Exemple [ Modifier | Modifier le texte source ]]
Le calcul du polynôme ci-dessus pour
avec l’aide de Schémas de corne Est comme suit:
2 | −4 | −5 | 7 | 11 | |
2 | 4 | 0 | −10 | −6 | |
2 | 0 | −5 | −3 | 5 |
La valeur pour laquelle vous souhaitez calculer le polynôme est généralement écrite dans la ligne médiane devant le schéma, le premier nombre de la ligne supérieure est également écrit dans la ligne inférieure. Puis multiplié ce nombre auquel vous souhaitez calculer le polynôme, le résultat écrit dans la ligne médiane de la deuxième colonne, additionnez les deux valeurs de la deuxième colonne et écrivez le résultat sur la ligne inférieure. Ensuite, le montant de la colonne est répété à partir de la ligne inférieure avec la valeur pour laquelle vous souhaitez calculer le polynôme et le résultat est écrit dans la ligne médiane de la colonne suivante, la colonne ajoute, etc. Le dernier numéro (ici cinq) est le résultat final.
Pour
Cependant, il existe des résultats intermédiaires significativement plus élevés:
2 | −4 | −5 | 7 | 11 | |
5 | dix | 30 | 125 | 660 | |
2 | 6 | 25 | 132 | 671 |
Conversion entre différents systèmes de nombres [ Modifier | Modifier le texte source ]]
Notre représentation familière des nombres dans le système de valeur de travail décimal n’est rien de plus qu’une orthographe raccourcie pour les polynomes spéciaux, à savoir les polynômes avec la base
. Il en va de même pour tous les autres systèmes de valeur professionnelle, par exemple le système binaire. Il y a
. Nous pouvons profiter du schéma Horner pour convertir les nombres de tout autre système de valeur professionnelle en système décimal, et vice versa.
Conversion au système décimal [ Modifier | Modifier le texte source ]]
Exemple: le numéro binaire 110101 doit être converti en système décimal. Quel est le numéro décimal qui en résulte
?
Nous écrivons 110101 binaire Comme polynom:
Ainsi
Selon le schéma Horner:
Nous n’avons pas besoin de calculer cela dans un train, nous pouvons progressivement procéder. Chaque étape consiste en une multiplication avec 2 et un ajout. Pour un aperçu, nous écrivons les étapes les uns avec les autres et notons les résultats provisoires:
Nous avons trouvé la représentation décorative souhaitée.
Le processus est généralisé: un nombre d’un système de valeur professionnelle à la base
est converti en système décimal par
- La valeur du premier chiffre est considérée comme la valeur initiale
- Puis progressivement le résultat de l’étape précédente avec multiplié et le numéro suivant est ajouté
- jusqu’à ce que tous les chiffres soient utilisés.
La façon la plus simple d’écrire à nouveau la facture sous forme tabulaire:
d’abord | d’abord | 0 | d’abord | 0 | d’abord | |
2) | 2 | 6 | douzième | 26 | 52 | |
d’abord | 3 | 6 | 13 | 26 | 53 |
Schéma de corne en cascade [ Modifier | Modifier le texte source ]]
L’inconvénient des schémas Horner à un seul est que des multiplications avec de grands facteurs peuvent être nécessaires (dans l’exemple ci-dessus 2 * 26 = 52). Pour rester dans l’onglet Small Multiplication, utilisez le schéma Horner en cascade ou en plusieurs étapes.
Un seul pour la multiplication est utilisé. Le dix est écrit comme un transfert à la ligne suivante parmi une. Dans le 13 de l’exemple ci-dessus, le 3 est écrit en dessous du 12 et le 1 en dessous de la 3e étape n’est que 3 * 2 + 0 = 6 (au lieu de 13 * 2 + 0 = 26). Ce résultat est également traité; Le TENS est 0. La dernière facture (6 * 2 + 1), en résulte 13. L’un de ce résultat est le dernier nombre du résultat final.
d’abord | d’abord | 0 | d’abord | 0 | d’abord | |
2) | 2 | 6 | douzième | 6 | douzième | |
d’abord | 3 | 6 | 3 | 6 | 3 | |
0 | 0 | d’abord | 0 | d’abord |
Afin de calculer les autres chiffres, le même schéma est à nouveau utilisé sur les dizaines (00101) dans la dernière ligne. Les zéros principaux peuvent être négligés:
d’abord | d’abord | 0 | d’abord | 0 | d’abord | |
2) | 2 | 6 | douzième | 6 | douzième | |
d’abord | 3 | 6 | 3 | 6 | 3 | |
0 | 0 | d’abord | 0 | d’abord | ||
2) | 2 | 4 | ||||
d’abord | 2 | 5 | ||||
0 | 0 |
Puisqu’il n’y a maintenant que des zéros dans la ligne de transmission, la procédure est terminée. Le résultat global (53) est lu dans la dernière colonne d’un en bas en haut.
Orthographe simplifiée [ Modifier | Modifier le texte source ]]
Le schéma de Horner en cascade peut être très simplifié par un peu plus d’arithmétique mentale. Cela accélère considérablement la facture.
Les chiffres du nombre initial sont initialement écrits verticalement. Une ligne verticale est tirée à gauche. Une ligne horizontale sous le dernier chiffre, sous lequel le résultat est à la fin.
Tout d’abord, la qualité maximale (le premier 1) est transférée une ligne à la colonne précédente. Ceci est maintenant à gauche du deuxième numéro (également un 1). Le nombre de gauche est multiplié par la base numérique (ici 2), le nombre de droite ajoute (1 * 2 + 1). D’après le résultat (3), le dix est écrit une colonne plus à gauche, une ligne plus profonde.
La même procédure est effectuée en utilisant celle du résultat (3) et le numéro suivant (0). Le résultat (3 * 2 + 0 = 6) est noté ainsi que le résultat précédent.
Le troisième calcul est 6 * 2 + 1 = 13, puis 3 * 2 + 0 = 6 et enfin 6 * 2 + 1 = 13 à calculer. Comme dans les étapes précédentes, une et des dizaines du résultat sont écrites en diagonale les unes avec les autres.
Le dernier nombre du résultat final (3) est désormais sous la ligne horizontale.
|
|
|
|
|
|
|
Pour calculer les autres chiffres, la colonne principale est désormais traitée avec les dizaines précédemment ignorées ainsi que le nombre initial.
Le premier chiffre valide est transféré une ligne à la colonne précédente. Ce nombre (1) est multiplié par la base (2) et ajouté au produit (2) le numéro suivant (0). Les dizaines et l’un des résultats (02) sont entrés en diagonale comme indiqué ci-dessus.
Le résultat de la dernière facture (2 * 2 + 1 = 05) est également entré. L’un de ce résultat (5) est le prochain numéro du résultat final.
|
|
|
|
|
Puisqu’il n’y a que des zéros dans la crevasse des dizaines, le projet de loi est terminé. Le résultat final (53) peut désormais être lu dans les résultats, cette fois même dans le bon ordre.
Procédure pour la direction inverse [ Modifier | Modifier le texte source ]]
Dans l’inverse, un nombre décimal peut être converti en un certain nombre d’un autre système de nombres. Au lieu d’une multiplication continue avec la base de l’autre système de nombres, une division continue passe par ce nombre. Les chiffres du nombre dans l’autre système numérique résultent de droite à gauche à travers la division demeure.
Dans la notation du tableau, les chiffres du nombre initial sont écrits entre eux et une ligne horizontale est tracée pour le résultat. Cependant, la ligne verticale est tirée ici à droite des chiffres. En tant que mémoire, la base numérique peut être notée en bas à droite.
5 | ||
3 | ||
(2) |
Le premier chiffre, augmenté d’un zéro leader, (05) est partagé par la base numérique (2). Le quotient (2) est écrit dans la colonne précédente. Le reste (1) dans la ligne ci-dessous.
|
|
Ce repos forme un nouveau numéro à double numérique (13) avec le numéro suivant (3). Ce nombre est divisé par la base, le résultat (6 restant 1) est entré dans le schéma en diagonale que ci-dessus.
|
Étant donné que tous les chiffres sont désormais traités, le reste de la dernière facture (1) est le dernier nombre du résultat final.
Les quotients non édités sont traités comme un nouveau numéro décimal (26) auquel la même procédure est appliquée.
|
|
|
|
Le nombre obtenu est un 0. Dans la colonne des quotients non transformés, il y a maintenant un 13.
|
|
|
|
Après cette étape, il y a un 06 dans la colonne Quotient. Le zéro principal est ignoré, le processus commence par le 6.
|
|
Le nombre qui reste à traiter est 3.
|
|
Maintenant, il ne reste plus qu’un 1.
|
|
|
Selon la dernière facture, il y a un 0 dans la colonne Quotient. La procédure est ainsi terminée. Dans la ligne de résultats, le numéro que vous recherchez est dans le bon ordre.
Polynomdivision [ Modifier | Modifier le texte source ]]
Division de polynome avec diviseur linéaire [ Modifier | Modifier le texte source ]]
Dans l’exemple suivant
La division polynomiale avec un diviseur linéaire dans le schéma Horner est d’abord montrée.
La division polynomiale est généralement effectuée sous une forme écrite.
Maintenant, laissez les puissances de
Façon, vous obtenez la présentation suivante:
( | d’abord | −4 | 4 | 3 | −8 | 4 | ) | : | ( d’abord | −2 | ) | = | d’abord | −2 | 0 | 3 | −2 |
– ( | d’abord | −2 | ) | ||||||||||||||
−2 | |||||||||||||||||
– ( | −2 | 4 | ) | ||||||||||||||
0 | |||||||||||||||||
– ( | 0 | 0 | ) | ||||||||||||||
3 | |||||||||||||||||
– ( | 3 | −6 | ) | ||||||||||||||
−2 | |||||||||||||||||
– ( | −2 | 4 | ) | ||||||||||||||
0 |
Si vous compactez maintenant ce schéma sur trois lignes et reprenez le premier coefficient du dividende dans la troisième ligne, vous obtenez:
( | d’abord | −4 | 4 | 3 | −8 | 4 | ) | : | ( d’abord | −2 | ) |
−2 | 4 | 0 | −6 | 4 | ) | ||||||
d’abord | −2 | 0 | 3 | −2 | 0 |
Comme vous pouvez le voir maintenant, les valeurs doubles soulignées de la dernière ligne sont les coefficients du Résultat Polynomial et la dernière valeur derrière elle est la division Rescue (ici zéro).
Si vous multipliez les présats en deuxième ligne, le calcul a lieu en fonction du processus suivant:
Si vous remarquez maintenant la valeur des signes du membre absolu du diviseur du régime, vous obtenez la représentation générale des schémas Horner:
d’abord | −4 | 4 | 3 | −8 | 4 | |
2) | 2 | −4 | 0 | 6 | −4 | |
d’abord | −2 | 0 | 3 | −2 | 0 |
L’exemple ci-dessus peut désormais être résumé dans la formule suivante:
A la tâche de division:
par conséquent
Les coefficients déterminent selon la disposition suivante:
Le schéma Horner est ensuite présenté comme suit:
Division de polynome avec un diviseur du 2e degré [ Modifier | Modifier le texte source ]]
A la tâche de division:
par conséquent
Les coefficients déterminent selon la disposition suivante:
Le schéma Horner généralisé est ensuite présenté comme suit:
Un exemple [ Modifier | Modifier le texte source ]]
Im Horner-Schema:
−6 | 14 | −8 | −2 | 0 | 8 | −6 | |
−1) | 6 | −2 | −2 | 0 | 2 | ||
2) | −12 | 4 | 4 | 0 | −4 | ||
−6 | 2 | 2 | 0 | −2 | 4 | −4 |
Il en résulte:
Linéaire [ Modifier | Modifier le texte source ]]
Dans certains cas, par exemple pour améliorer la convergence dans les processus de Newton, il peut être très utile à la polynomie
dans un polynôme
,
Constant à transformer de sorte qu’avec
est applicable:
Une telle transformation linéaire peut être utilisée en utilisant
au lieu de
et la proliflation ultérieure. Ce calcul peut être beaucoup plus efficace avec le complet Effectuer le schéma Horner.
Regardons le polynôme
de degré
que nous selon les puissances de
veulent se développer:
Pour ce faire, nous divisons le polynôme
au moyen du schéma Horner
. Comme indiqué ci-dessus, nous pouvons à partir du schéma le polynôme
et le reste
Lire pour que ce qui suit s’applique:
Maintenant la division sur le résultat polynôme
réalisé, et nous recevons
ou le reste
:
Après
Divisions que vous obtenez:
- avec
Ça suit:
Avec
est alors la transformation linéaire
D. h. Les restes dans la division continue avec le facteur linéaire
former les coefficients du polynôme transformé
.
Exemple [ Modifier | Modifier le texte source ]]
Si vous voulez z. B. le zéro du polynôme
Calculer, afin que vous puissiez facilement
comme première approximation. Pour plus de calcul, il est maintenant utile
après
Pour développer (voir Newton Procedure / “Methodus Fluxionum et Serierum Infinitarum”). Donc le polynôme est recherché
.
d’abord | 0 | −2 | −5 | |
2) | 2 | 4 | 4 | |
d’abord | 2 | 2 | −1 | |
2) | 2 | 8 | ||
d’abord | 4 | dix | ||
2) | 2 | |||
d’abord | 6 |
Ainsi, le polynôme recherché est
.
Calcul de la dérivation [ Modifier | Modifier le texte source ]]
Une autre propriété des Horner-Schemas est que vous prenez rapidement la première dérivation au point
peut calculer.
Considérons la division
Avec le résultat
que nous pouvons lire du schéma Horner. Tu pouvais aussi voir ça
est.
Il s’applique donc:
La dérivation
peut être calculé avec le quotient de différence. Ça s’applique:
Ça suit:
D. h. Les nombres de la troisième ligne des schémas Horner forment les coefficients pour
. En utilisant à nouveau le schéma Horner, la valeur de la dérivation peut enfin être
être calculé.
Exemple [ Modifier | Modifier le texte source ]]
Regardons le polynôme
Au point x = 2
d’abord | −4 | 4 | 3 | −8 | 4 | |
2) | 2 | −4 | 0 | 6 | −4 | |
d’abord | −2 | 0 | 3 | −2 | 0 | |
2) | 2 | 0 | 0 | 6 | ||
d’abord | 0 | 0 | 3 | 4 |
Vous pouvez maintenant lire dans le schéma:
et
Sonde [ Modifier | Modifier le texte source ]]
Du schéma Horner
5 | −16 | douzième | 6 | −8 | |
2) | dix | −12 | 0 | douzième | |
5 | −6 | 0 | 6 | 4 |
suit
.
Plusieurs dérivations [ Modifier | Modifier le texte source ]]
Les valeurs des autres dérivations peuvent également être vues à partir du schéma Horner. Peut être
- et , avec
Le polynôme que nous pouvons lire dans le schéma complet de Horner (voir ci-dessus),
Zéro [ Modifier | Modifier le texte source ]]
Le schéma Horner peut être utilisé dans divers processus numériques pour déterminer le point zéro des polynomes.
Vous avez z. B. Un zéro “Errat” , comme indiqué ci-dessus, vous pouvez rapidement vérifier si la présomption est bonne.
Afin de raccourcir la «devinettes» du zéro dans certaines tâches simples, vous pouvez utiliser la phrase via Rational Zero. De là, il s’ensuit qu’un point zéro entier est un diviseur de
est. Devrait un facteur avant la puissance maximale de
stand (par exemple 3 à:
), Aussi les diviseurs de
Et mieux pour partager toute la fonction (→
).
Exemple: vous regardez
avec
. Les diviseurs possibles de 6 et donc les candidats à des positions zéro sont de 1, 2, 3, 6 et aussi −1, −2, −3, −6. Avec le schéma Horner, vous pouvez désormais calculer les valeurs fonctionnelles à ces points et donc déterminer les points zéro réels. En tant que points zéro, vous obtenez −1, +1, +6. Une fois que vous avez déterminé un point zéro, vous pouvez également diviser un facteur linéaire avec le schéma Horner, comme expliqué ci-dessus.
Un autre domaine d’application est le processus d’approximation newtonien. Pour le processus de Newton, vous avez besoin à chaque étape d’itération
et
. Comme décrit ci-dessus, ces valeurs peuvent être calculées très rapidement avec le schéma Horner.
William George Horner n’a pas été le premier à découvrir ce processus. Surtout, il le devait à De Morgan que la procédure est devenue connue sous son nom. Paolo Ruffini a déjà publié une procédure correspondante 15 ans avant Horner; Il est donc aussi en Espagne comme Règle de Ruffini désigné. Les premières descriptions connues de la procédure remontent au 11ème siècle (Jia Xian en Chine et As-Samaw’al au Moyen-Orient). [5] Le chinois Zhu Shijie décrit en 1303 dans son livre Siyuan Yujian Une méthode de conversion pour résoudre les équations qu’il Fan FA appelé. Les Arabes ont également utilisé la méthode (As-Samawal, Sharaf al-Din al-Tusi).
- William George Horner: Une nouvelle méthode de résolution d’équations numériques de tous les ordres, par approximation continue. Dans: Transactions philosophiques de la Royal Society of London. 1819, S. 308–335.
- Charles D. Miller, Margaret L. Lial, David I. Tourisque: Fondamentaux de l’algèbre universitaire. 3. Édition révisée. Scott & Foresman / Little & Brown Higher Education, 1990, ISBN 0-673-38638-4, pp. 204-209.
- Gisela Engeln-Fillges, Klaus Niederdrenk, Reinhard Wodicka: Algorithmes Numerik: procédures, exemples, applications. Springer 2005, ISBN 3-540-62669-7, S. 92-100 ( abstrait Dans la recherche de livres Google)
- ↑ Josef Stoer: Mathématiques numériques 1 . 9. Édition. Springer, 2004.
- ↑ Lors du calcul des puissances , K≥2, vous pouvez d’abord calculer le faible puis les puissances les plus élevées. Cela en profite est déjà calculé si est nécessaire. Pour Vous n’avez donc besoin que d’une autre multiplication et non de leur .
- ↑ Calculateur de salaire interactif et d’impôt sur le revenu: Règlement d’arrondi ( Mémento à partir du 21 mai 2014 Archives Internet ) Ministère fédéral des finances: salaire interactive et calculatrice de l’impôt sur le revenu: Règlement d’arrondi
- ↑ Les formules tarifaires de l’impôt sur le revenu depuis 1958 Wolfgang & Johannes Parmentation: les formules tarifaires de l’impôt sur le revenu depuis 1958
- ↑ John J. O’Connor, Edmund F. Robertson: Horner-Schema. Dans: Histoire de MacTUTOR des archives des mathématiques.
Recent Comments