Περιγραφή του αλγόριθμου

 

Θα προσπαθήσουμε να εξηγήσουμε την δουλειά του Horner στον ομώνυμο αλγόριθμο
Δίνεται το πολυώνυμοp(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n,

Όπου a_0, \ldots, a_nαο,...αn είναι πραγματικοί αριθμοί, για τους οποίους επιθυμούμε να εκτιμήσουμε σε μια τιμή του x. Έστω x_0\,\!.
Για να το πετύχουμε θα ορίσουμε μια καινούρια σειρά σταθερών όπως δείχνουμε παρακάτω:

b_n\,\! :=\,\! a_n\,\!
b_{n-1}\,\! :=\,\! a_{n-1} + b_n x_0\,\!
\vdots
b_0\,\! :=\,\! a_0 + b_1 x_0\,\!

Στην συνέχεια b_0\,\!είναι η τιμή τουp(x_0)\,\!


Για να δούμε πως δουλεύει, ας παρατηρήσουμε ότι το πολυώνυμο μπορεί να γραφεί στην μορφή p(x) = a_0 + x(a_1 + x(a_2 + \cdots x(a_{n-1} + a_n x) \cdots ))

Έτσι επαναλαμβάνοντας συνέχεια αντικαταστάσεις του bi στην παράσταση έχω:

p(x)\,\! =\,\!=\,\! a_0 + x(a_1 + x(a_2 + \cdots x(a_{n-1} + b_n x) \dots ))
=\,\! a_0 + x(a_1 + x(a_2 + \cdots x(b_{n-1}) \dots ))
\vdots
=\,\! a_0 + x(b_1)\,\!
=\,\! b_0\,\!
 
Χρήση

To σχήμα Horner συχνά χρησιμοποιείται στην μετατροπή διαφορετικών αριθμητικών συστημάτων θέσης. Στην περίπτωση αυτή το χ αποτελεί την βάση του αριθμητικού συστήματος και οι συντελεστές αi ψηφία της αναπαράστασης του αριθμού στην βάση-χ .

Κυρίως όμως χρησιμοποιούμε το σχήμα Horner σαν ένα γρήγορο αλγόριθμο για την διαίρεση πολυωνύμου με γραμμικό πολυώνυμο (μέθοδος που ανέπτυξε ο Ruffini).

Παράδειγμα

Έστω το πολυώνυμοf_1(x)=4x^4-6x^3+3x-5\, και το f_2(x)=2x-1\,

Ας διαιρέσουμε το f_1(x)\,με το f_2\,(x)χρησιμοποιώντας το σχήμα Horner
Μπορούμε να χρησιμοποιήσουμε ένα σύνθετο διάγραμμα για να κάνουμε την διαδικασία

 

 

Η απάντηση είναι \frac{f_1(x)}{f_2(x)}=2x^3-2x^2-x+1-\frac{4}{(2x-1)}.

 

Έστω το πολυώνυμο και το
Ας διαιρέσουμε το P(x) με το Q(x) χρησιμοποιώντας το σχήμα Horner

Η απάντηση είναι :