طريقة هورنر

لتكن دالة كثيرة الحدود

${\displaystyle p(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n},}$

حيث ${\displaystyle a_{0},\ldots ,a_{n}}$ أعداد حقيقية، يراد بها حساب متعددة الحدود عن قيم معينة x, ولتكن x₀.

لفعل ذلك، نقوم بتعريف تعاقب جديد من الثوابت كما يلي:

${\displaystyle {\begin{aligned}b_{n}&:=a_{n}\\b_{n-1}&:=a_{n-1}+b_{n}x_{0}\\&{}\ \ \vdots \\b_{0}&:=a_{0}+b_{1}x_{0}.\end{aligned}}}$

حينئذ b₀ هي قيمة (p(x_0</sub>.

لمعرفة سبب عمل هذا، لاحظ أن بالإمكان كتابة كثيرة الحدود على الصورة

${\displaystyle p(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots +x(a_{n-1}+a_{n}x)\cdots )).\,}$

وبالتالي، وبالتعويض المتتابع لـ ${\displaystyle b_{i}}$ في التعبير,

${\displaystyle {\begin{aligned}p(x_{0})&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots x_{0}(a_{n-1}+b_{n}x_{0})\cdots ))\\&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots x_{0}(b_{n-1})\dots ))\\&{}\ \ \vdots \\&=a_{0}+x_{0}(b_{1})\\&=b_{0}.\end{aligned}}}$

قيم ${\displaystyle f_{1}(x)=2x^{3}-6x^{2}+2x-1\,}$ لأجل ${\displaystyle x=3\;}$. بإخراج معاملات ${\displaystyle x}$, تتابعيا، يمكن كتابة ${\displaystyle f_{1}}$ بالصورة ${\displaystyle x(x(2x-6)+2)-1\;}$. باستعمال شكل اصطناعي لترتيب هذه الحسابات وتسريع العمليات

${\displaystyle x_{0}}$ |  ${\displaystyle x^{3}}$  ${\displaystyle x^{2}}$   ${\displaystyle x^{1}}$  ${\displaystyle x^{0}}$

3 |  2  -6   2  -1
 |     6   0   6  
 |----------------------
   2   0   2   5

مدخلات الصف الثالث هي مجموع المدخلات في الصفين الأول والثاني. كل مدخل في الصف الثاني يكون نتاج ضرب قيمة x (3 في هذا المثال(بمدخل الصف الثالث مباشرة إلى اليسار. المدخلات في الصف الأول هي معاملات كثيرة الحدود المراد حسابها. الجواب هو 5.

وكنتيجة لنظرية باقي كثيرة الحدود، تكون مدخلات الصف الثالث هي معاملات كثيرة الحدود من الدرجة الثانية التي هي حاصل قسمة f₁/(x-3). الباقي هو 5. هذا يجعل طريقة هورنر مفيدة في قسمة كثيرة الحدود المطولة.

بقسمة ${\displaystyle x^{3}-6x^{2}+11x-6\,}$ على ${\displaystyle x-2}$:

2 |  1  -6  11  -6
 |     2  -8   6  
 |----------------------
   1  -4   3   0

يكون حاصل القسمة ${\displaystyle x^{2}-4x+3}$.

لتكن ${\displaystyle f_{1}(x)=4x^{4}-6x^{3}+3x-5\,}$ و${\displaystyle f_{2}(x)=2x-1\,}$. بقسمة ${\displaystyle f_{1}(x)\,}$ على ${\displaystyle f_{2}\,(x)}$ باستعمال مخطط هورنر.

 2 | 4  -6  0  3  |  -5
---------------------------|------
 1 |    2  -2  -1  |  1
  |            | 
    |----------------------|-------
       2    -2    -1   1   |   -4

الصف الثالث هو مجموع الصفين الأول والثاني، مقسوما على 2. كل مدخل في الصف الثاني هو حاصل ضرب 1 مع مدخل الصف الثالث إلى اليسار. الإجابة تكون:

${\displaystyle {\frac {f_{1}(x)}{f_{2}(x)}}=2x^{3}-2x^{2}-x+1-{\frac {4}{(2x-1)}}.}$

• مبرهنة الجذر النسبي

• إيريك ويستاين، Horner's method، ماثوورلد Mathworld (باللغة الإنكليزية).

• Module for Horner's Method by John H. Mathews

مخطط هورنر - موسوعة المعرفة

• بوابة علم الحاسوب
• بوابة رياضيات
• بوابة خوارزميات