طريقة هورنر

This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: See Talk:Horner's method#This Article is about Two Different Algorithms. Please help improve this article if you can. (November 2018) (Learn how and when to remove this message)

في الرياضيات وعلوم الكمبيوتر ، طريقة هورنر (أو مخطط هورنر ) هي خوارزمية لتقييم كثيرات الحدود . وعلى الرغم من تسميتها باسم ويليام جورج هورنر ، إلا أن هذه الطريقة أقدم بكثير، حيث نسبها هورنر نفسه إلى جوزيف لويس لاجرانج ، ويمكن إرجاعها إلى مئات السنين إلى علماء الرياضيات الصينيين والفرس. ^[1] بعد إدخال أجهزة الكمبيوتر، أصبحت هذه الخوارزمية أساسية للحوسبة بكفاءة مع كثيرات الحدود.

تعتمد الخوارزمية على قاعدة هورنر ، حيث يتم كتابة كثير الحدود في شكل متداخل : $${\displaystyle {\begin{aligned}&a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\={}&a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}.\end{aligned}}}$$

يسمح هذا بتقييم كثير حدود من الدرجة n باستخدام الضرب والجمع فقط . وهذا هو الحل الأمثل، حيث توجد كثيرات حدود من الدرجة n لا يمكن تقييمها باستخدام عدد أقل من العمليات الحسابية. ^[2]${\displaystyle n}$${\displaystyle n}$

وبدلا من ذلك، طريقة هورنر وتشير طريقة هورنر-روفيني أيضًا إلى طريقة لتقريب جذور كثيرات الحدود، وصفها هورنر في عام 1819. وهي عبارة عن شكل مختلف منطريقة نيوتن-رافسونالتي أصبحت أكثر كفاءة للحساب اليدوي من خلال تطبيق قاعدة هورنر. كانت تستخدم على نطاق واسع حتى دخلت أجهزة الكمبيوتر في الاستخدام العام حوالي عام 1970.

نظرًا لأن الحدود كثيرة حيث تكون معاملات ثابتة، فإن المشكلة هي تقييم الحدود كثيرة عند قيمة محددة لـ$${\displaystyle p(x)=\sum _{i=0}^{n}a_{i}x^{i}=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n},}$$${\displaystyle a_{0},\ldots ,a_{n}}$${\displaystyle x_{0}}$${\displaystyle x.}$

ولتحقيق هذه الغاية، يتم تعريف تسلسل جديد من الثوابت بشكل متكرر على النحو التالي:

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

( 1 )

ثم تكون قيمة . ${\displaystyle b_{0}}$${\displaystyle p(x_{0})}$

لمعرفة سبب نجاح هذا، يمكن كتابة الحدود المتعددة في النموذج $${\displaystyle p(x)=a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}\ .}$$

وبالتالي، من خلال استبدالها بشكل متكرر في التعبير، ${\displaystyle b_{i}}$$${\displaystyle {\begin{aligned}p(x_{0})&=a_{0}+x_{0}{\Big (}a_{1}+x_{0}{\big (}a_{2}+\cdots +x_{0}(a_{n-1}+b_{n}x_{0})\cdots {\big )}{\Big )}\\&=a_{0}+x_{0}{\Big (}a_{1}+x_{0}{\big (}a_{2}+\cdots +x_{0}b_{n-1}{\big )}{\Big )}\\&~~\vdots \\&=a_{0}+x_{0}b_{1}\\&=b_{0}.\end{aligned}}}$$

والآن يمكن إثبات أن؛

$${\displaystyle p(x)=\left(b_{1}+b_{2}x+b_{3}x^{2}+b_{4}x^{3}+\cdots +b_{n-1}x^{n-2}+b_{n}x^{n-1}\right)\left(x-x_{0}\right)+b_{0}}$$

( 2 )

يشكل هذا التعبير تطبيقًا عمليًا لهورنر، لأنه يوفر طريقة سريعة جدًا لتحديد نتيجة؛ حيث يكون (الذي يساوي ) هو الباقي من القسمة، كما هو موضح في الأمثلة أدناه. إذا كان جذرًا لـ ، إذن (بمعنى أن الباقي هو )، مما يعني أنه يمكنك التحليل إلى عوامل مثل . $${\displaystyle p(x)/(x-x_{0})}$$${\displaystyle b_{0}}$${\displaystyle p(x_{0})}$${\displaystyle x_{0}}$${\displaystyle p(x)}$${\displaystyle b_{0}=0}$${\displaystyle 0}$${\displaystyle p(x)}$${\displaystyle x-x_{0}}$

لإيجاد القيم المتتالية، ابدأ بتحديد ، الذي يساوي ببساطة . ثم اعمل بشكل متكرر باستخدام الصيغة: حتى تصل إلى . ${\displaystyle b}$${\displaystyle b_{n}}$${\displaystyle a_{n}}$$${\displaystyle b_{n-1}=a_{n-1}+b_{n}x_{0}}$$${\displaystyle b_{0}}$

تقييم ل . ${\displaystyle f(x)=2x^{3}-6x^{2}+2x-1}$${\displaystyle x=3}$

نحن نستخدم القسمة الاصطناعية على النحو التالي:

 x 0 │    x 3     x 2     x 1     x 0
 3 │ 2 −6 2 −1
   │ 6 0 6
   └──────────────────────
       2 0 2 5

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

ولكن وفقًا لنظرية الباقي المتعدد الحدود ، فإننا نعلم أن الباقي هو . وبالتالي، . ${\displaystyle f(3)}$${\displaystyle f(3)=5}$

في هذا المثال، إذا تمكنا من رؤية أن ، الإدخالات في الصف الثالث. لذا، فإن القسمة التركيبية (التي اخترعها روفيني ونشرها بالفعل قبل 10 سنوات من نشر هورنر) أسهل في الاستخدام؛ ويمكن إثبات أنها تعادل طريقة هورنر. ${\displaystyle a_{3}=2,a_{2}=-6,a_{1}=2,a_{0}=-1}$${\displaystyle b_{3}=2,b_{2}=0,b_{1}=2,b_{0}=5}$

كنتيجة لنظرية الباقي في كثير الحدود، فإن الإدخالات في الصف الثالث هي معاملات كثير الحدود من الدرجة الثانية، حاصل قسمة على . الباقي هو${\displaystyle f(x)}$${\displaystyle 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)}$

  0.5 │ 4 −6 0 3 −5
      │ 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}}.}$$

يتطلب التقييم باستخدام الشكل أحادي الحد لكثيرة حدود من الدرجة جمعًا وضربًا على الأكثر ، إذا تم حساب القوى من خلال الضرب المتكرر وتقييم كل أحادي حد على حدة. يمكن تقليل التكلفة إلى الجمع والضرب من خلال تقييم القوى من خلال التكرار. ${\displaystyle n}$${\displaystyle n}$${\displaystyle (n^{2}+n)/2}$${\displaystyle n}$${\displaystyle 2n-1}$${\displaystyle x}$

إذا تم تمثيل البيانات الرقمية من حيث الأرقام (أو البتات)، فإن الخوارزمية الساذجة تستلزم أيضًا تخزين ما يقرب من أضعاف عدد بتات : يكون للحدودية المقدرة مقدار تقريبي ، ويجب أيضًا تخزين نفسها. على النقيض من ذلك، تتطلب طريقة هورنر عمليات الجمع والضرب فقط ، ومتطلبات التخزين الخاصة بها هي فقط أضعاف عدد بتات . بدلاً من ذلك، يمكن حساب طريقة هورنر باستخدام الضرب المندمج - الجمع . يمكن أيضًا توسيع طريقة هورنر لتقييم المشتقات الأولى للحدودية باستخدام عمليات الجمع والضرب. ^[3]${\displaystyle 2n}$${\displaystyle x}$${\displaystyle x^{n}}$${\displaystyle x^{n}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle x}$${\displaystyle n}$ ${\displaystyle k}$${\displaystyle kn}$

طريقة هورنر هي الطريقة المثلى، بمعنى أن أي خوارزمية لتقييم كثيرة حدود تعسفية يجب أن تستخدم على الأقل عددًا من العمليات. أثبت ألكسندر أوستروفسكي في عام 1954 أن عدد الإضافات المطلوبة ضئيل. ^{[4] أثبت} فيكتور بان في عام 1966 أن عدد الضرب ضئيل. ^[5] ومع ذلك، عندما تكون مصفوفة، فإن طريقة هورنر ليست مثالية . ${\displaystyle x}$

يفترض هذا أن الحدودية يتم تقييمها في شكل أحادي الحدود ولا يُسمح بأي شرط مسبق للتمثيل، وهو أمر منطقي إذا تم تقييم الحدودية مرة واحدة فقط. ومع ذلك، إذا تم السماح بالشرط المسبق وكان من المقرر تقييم الحدودية عدة مرات، فمن الممكن استخدام خوارزميات أسرع . وهي تنطوي على تحويل لتمثيل الحدودية. بشكل عام، يمكن تقييم الحدودية من الدرجة باستخدام ⌊ n /2 ⌋ +2 فقط من عمليات الضرب والجمع. ^[6]${\displaystyle n}$${\displaystyle n}$

من عيوب قاعدة هورنر أن جميع العمليات تعتمد على بعضها البعض بشكل تسلسلي ، لذا فمن غير الممكن الاستفادة من التوازي على مستوى التعليمات في أجهزة الكمبيوتر الحديثة. في معظم التطبيقات حيث تكون كفاءة تقييم كثيرات الحدود مهمة، يتم تقييم العديد من كثيرات الحدود ذات الدرجة المنخفضة في وقت واحد (لكل بكسل أو مضلع في رسومات الكمبيوتر، أو لكل مربع شبكة في محاكاة رقمية)، لذلك ليس من الضروري إيجاد التوازي داخل تقييم كثير حدود واحد.

ومع ذلك، إذا كان الشخص يقوم بتقييم كثير حدود واحد من مرتبة عالية جدًا، فقد يكون من المفيد تقسيمه على النحو التالي: $${\displaystyle {\begin{aligned}p(x)&=\sum _{i=0}^{n}a_{i}x^{i}\\[1ex]&=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\[1ex]&=\left(a_{0}+a_{2}x^{2}+a_{4}x^{4}+\cdots \right)+\left(a_{1}x+a_{3}x^{3}+a_{5}x^{5}+\cdots \right)\\[1ex]&=\left(a_{0}+a_{2}x^{2}+a_{4}x^{4}+\cdots \right)+x\left(a_{1}+a_{3}x^{2}+a_{5}x^{4}+\cdots \right)\\[1ex]&=\sum _{i=0}^{\lfloor n/2\rfloor }a_{2i}x^{2i}+x\sum _{i=0}^{\lfloor n/2\rfloor }a_{2i+1}x^{2i}\\[1ex]&=p_{0}(x^{2})+xp_{1}(x^{2}).\end{aligned}}}$$

بشكل عام، يمكن تقسيم المجموع إلى k جزء: حيث يمكن تقييم المجموع الداخلي باستخدام حالات موازية منفصلة لطريقة هورنر. يتطلب هذا عمليات أكثر قليلاً من طريقة هورنر الأساسية، لكنه يسمح بتنفيذ SIMD بطريقة k لمعظمها. تقوم المترجمات الحديثة عمومًا بتقييم الحدوديات بهذه الطريقة عندما يكون ذلك مفيدًا، على الرغم من أن هذا يتطلب تمكين الرياضيات الارتباطية (غير الآمنة) لحسابات الفاصلة العائمة ^{[ بحاجة لمصدر ]} . $${\displaystyle p(x)=\sum _{i=0}^{n}a_{i}x^{i}=\sum _{j=0}^{k-1}x^{j}\sum _{i=0}^{\lfloor n/k\rfloor }a_{ki+j}x^{ki}=\sum _{j=0}^{k-1}x^{j}p_{j}(x^{k})}$$

طريقة هورنر هي طريقة سريعة وفعالة في الكود لضرب وقسمة الأعداد الثنائية على متحكم دقيق بدون مضاعف أجهزة . يتم تمثيل أحد الأعداد الثنائية المراد ضربها على هيئة متعددة حدود تافهة، حيث (باستخدام التدوين أعلاه) و و . بعد ذلك، يتم استبعاد x (أو x إلى قوة ما) بشكل متكرر. في نظام الأعداد الثنائية هذا (الأساس 2)، ، لذا يتم استبعاد قوى 2 بشكل متكرر. ${\displaystyle a_{i}=1}$${\displaystyle x=2}$${\displaystyle x=2}$

على سبيل المثال، لإيجاد حاصل ضرب عددين (0.15625) و m : $${\displaystyle {\begin{aligned}(0.15625)m&=(0.00101_{b})m=\left(2^{-3}+2^{-5}\right)m=\left(2^{-3})m+(2^{-5}\right)m\\&=2^{-3}\left(m+\left(2^{-2}\right)m\right)=2^{-3}\left(m+2^{-2}(m)\right).\end{aligned}}}$$

لإيجاد حاصل ضرب عددين ثنائيين d و m :

1. يتم تهيئة السجل الذي يحمل النتيجة الوسيطة إلى d .
2. ابدأ بالبت الأقل أهمية (أقصى اليمين) غير الصفر في م .
   2. احسب (إلى اليسار) عدد مواضع البتات حتى البت التالي الأكثر أهمية غير الصفر. إذا لم يكن هناك بتات أكثر أهمية، فخذ قيمة موضع البت الحالي.
   3. باستخدام هذه القيمة، قم بإجراء عملية تحويل إلى اليسار بهذا العدد من البتات في السجل الذي يحمل النتيجة الوسيطة
3. إذا تم حساب جميع البتات غير الصفرية، فسيحتفظ سجل النتيجة الوسيطة الآن بالنتيجة النهائية. وإلا، أضف d إلى النتيجة الوسيطة، واستمر في الخطوة 2 مع البت الأكثر أهمية التالي في m .

بشكل عام، بالنسبة لعدد ثنائي بقيم بت ( ) يكون المنتج هو في هذه المرحلة من الخوارزمية، يلزم إسقاط المصطلحات ذات المعاملات ذات القيمة الصفرية، بحيث يتم حساب المعاملات الثنائية التي تساوي واحدًا فقط، وبالتالي فإن مشكلة الضرب أو القسمة على الصفر ليست مشكلة، على الرغم من هذا الضمني في المعادلة المعاملية: ${\displaystyle d_{3}d_{2}d_{1}d_{0}}$$${\displaystyle (d_{3}2^{3}+d_{2}2^{2}+d_{1}2^{1}+d_{0}2^{0})m=d_{3}2^{3}m+d_{2}2^{2}m+d_{1}2^{1}m+d_{0}2^{0}m.}$$$${\displaystyle =d_{0}\left(m+2{\frac {d_{1}}{d_{0}}}\left(m+2{\frac {d_{2}}{d_{1}}}\left(m+2{\frac {d_{3}}{d_{2}}}(m)\right)\right)\right).}$$

جميع المقامات تساوي واحدًا (أو يكون المصطلح غائبًا)، لذا فإن هذا يُختزل إلى أو ما يعادله (كما يتسق مع "الطريقة" الموضحة أعلاه) $${\displaystyle =d_{0}(m+2{d_{1}}(m+2{d_{2}}(m+2{d_{3}}(m)))),}$$$${\displaystyle =d_{3}(m+2^{-1}{d_{2}}(m+2^{-1}{d_{1}}(m+{d_{0}}(m)))).}$$

في الرياضيات الثنائية (الأساس 2)، فإن الضرب بقوة 2 هو مجرد عملية إزاحة مسجلة . وبالتالي، يتم حساب الضرب في 2 في الأساس 2 عن طريق إزاحة حسابية . العامل (2 ⁻¹ ) هو إزاحة حسابية لليمين ، و(0) لا ينتج عنه أي عملية (نظرًا لأن 2 ^{0 = 1 هو} عنصر الهوية الضربية )، و(2 ¹ ) ينتج عنه إزاحة حسابية لليسار. يمكن الآن حساب حاصل الضرب بسرعة باستخدام عمليات الإزاحة الحسابية فقط، الجمع والطرح.

الطريقة سريعة بشكل خاص على المعالجات التي تدعم التحويل والجمع والتراكم بتعليمات واحدة. وبالمقارنة بمكتبة الفاصلة العائمة C، تضحي طريقة هورنر ببعض الدقة، إلا أنها أسرع اسميًا بنحو 13 مرة (أسرع بنحو 16 مرة عند استخدام نموذج " الرقم الموقّع القياسي " (CSD)) وتستخدم 20% فقط من مساحة الكود. ^[7]

يمكن استخدام طريقة هورنر للتحويل بين أنظمة الأعداد الموضعية المختلفة - وفي هذه الحالة يكون x هو أساس نظام الأعداد، وتكون معاملات a _i هي أرقام التمثيل الأساسي x لرقم معين - ويمكن استخدامها أيضًا إذا كانت x عبارة عن مصفوفة ، وفي هذه الحالة تكون الزيادة في الكفاءة الحسابية أكبر. ومع ذلك، في مثل هذه الحالات، هناك طرق أسرع معروفة. ^[8]

باستخدام خوارزمية القسمة الطويلة مع طريقة نيوتن ، من الممكن تقريب الجذور الحقيقية لكثيرة حدود. تعمل الخوارزمية على النحو التالي. إذا كان لكثيرة حدود من الدرجة مع أصفار، فقم بتخمين أولي بحيث . الآن كرر الخطوتين التاليتين: ${\displaystyle p_{n}(x)}$${\displaystyle n}$${\displaystyle z_{n}<z_{n-1}<\cdots <z_{1},}$${\displaystyle x_{0}}$${\displaystyle z_{1}<x_{0}}$

1. باستخدام طريقة نيوتن ، أوجد أكبر صفر باستخدام التخمين .${\displaystyle z_{1}}$${\displaystyle p_{n}(x)}$${\displaystyle x_{0}}$
2. باستخدام طريقة هورنر، قسّم للحصول على . ارجع إلى الخطوة 1 ولكن استخدم الحدودية والتخمين الأولي .${\displaystyle (x-z_{1})}$${\displaystyle p_{n-1}}$${\displaystyle p_{n-1}}$${\displaystyle z_{1}}$

تتكرر هاتان الخطوتان حتى يتم العثور على جميع الأصفار الحقيقية للحدودية. إذا لم تكن الأصفار التقريبية دقيقة بدرجة كافية، فيمكن استخدام القيم التي تم الحصول عليها كتخمينات أولية لطريقة نيوتن ولكن باستخدام الحدودية الكاملة بدلاً من الحدوديات المختصرة. ^[9]

ضع في اعتبارك الحدود المتعددة التي يمكن توسيعها إلى $${\displaystyle p_{6}(x)=(x+8)(x+5)(x+3)(x-2)(x-3)(x-7)}$$$${\displaystyle p_{6}(x)=x^{6}+4x^{5}-72x^{4}-214x^{3}+1127x^{2}+1602x-5040.}$$

من ما سبق نعلم أن أكبر جذر لهذه الحدودية هو 7 وبالتالي نتمكن من تخمين أولي للرقم 8. باستخدام طريقة نيوتن، يتم إيجاد أول صفر من 7 كما هو موضح باللون الأسود في الشكل الموجود على اليمين. بعد ذلك يتم القسمة على للحصول على ما هو مرسوم باللون الأحمر في الشكل الموجود على اليمين. تُستخدم طريقة نيوتن لإيجاد أكبر صفر لهذه الحدودية بتخمين أولي للرقم 7. يوجد أكبر صفر لهذه الحدودية والذي يتوافق مع ثاني أكبر صفر للكثيرة الحدود الأصلية عند 3 ومحاط بدائرة حمراء. تُقسم الآن كثيرة الحدود من الدرجة 5 على للحصول على ما هو موضح باللون الأصفر. يوجد صفر هذه الحدودية عند 2 مرة أخرى باستخدام طريقة نيوتن ومحاط بدائرة صفراء. تُستخدم طريقة هورنر الآن للحصول على ما هو موضح باللون الأخضر ووجد أنه يحتوي على صفر عند −3. يتم تقليص هذه الحدودية إلى ما هو موضح باللون الأزرق ويعطي صفرًا عند −5. يمكن إيجاد الجذر النهائي للحدودية الأصلية إما باستخدام الصفر النهائي كتخمين أولي لطريقة نيوتن، أو عن طريق اختزال وحل المعادلة الخطية . وكما يمكن ملاحظة ذلك، تم إيجاد الجذور المتوقعة لـ −8 و−5 و−3 و2 و3 و7. ${\displaystyle p(x)}$${\displaystyle (x-7)}$$${\displaystyle p_{5}(x)=x^{5}+11x^{4}+5x^{3}-179x^{2}-126x+720}$$${\displaystyle (x-3)}$$${\displaystyle p_{4}(x)=x^{4}+14x^{3}+47x^{2}-38x-240}$$$${\displaystyle p_{3}(x)=x^{3}+16x^{2}+79x+120}$$$${\displaystyle p_{2}(x)=x^{2}+13x+40}$$${\displaystyle p_{2}(x)}$

يمكن تعديل طريقة هورنر لحساب الفرق المقسوم عليه، مع الأخذ في الاعتبار الحدود (كما في السابق)، اتبع ما يلي ^[10]${\displaystyle (p(y)-p(x))/(y-x).}$$${\displaystyle p(x)=\sum _{i=0}^{n}a_{i}x^{i}=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n},}$$ $${\displaystyle {\begin{aligned}b_{n}&=a_{n},&\quad d_{n}&=b_{n},\\b_{n-1}&=a_{n-1}+b_{n}x,&\quad d_{n-1}&=b_{n-1}+d_{n}y,\\&{}\ \ \vdots &\quad &{}\ \ \vdots \\b_{1}&=a_{1}+b_{2}x,&\quad d_{1}&=b_{1}+d_{2}y,\\b_{0}&=a_{0}+b_{1}x.\end{aligned}}}$$

عند الانتهاء، لدينا هذا الحساب للفرق المقسوم يخضع لخطأ تقريب أقل من التقييم و بشكل منفصل، خاصة عندما . الاستبدال في هذه الطريقة يعطي ، المشتق لـ . $${\displaystyle {\begin{aligned}p(x)&=b_{0},\\{\frac {p(y)-p(x)}{y-x}}&=d_{1},\\p(y)&=b_{0}+(y-x)d_{1}.\end{aligned}}}$$${\displaystyle p(x)}$${\displaystyle p(y)}$${\displaystyle x\approx y}$${\displaystyle y=x}$${\displaystyle d_{1}=p'(x)}$${\displaystyle p(x)}$

تمت قراءة ورقة هورنر بعنوان "طريقة جديدة لحل المعادلات العددية من جميع الرتب، عن طريق التقريب المستمر"، ^[12] أمام الجمعية الملكية بلندن، في اجتماعها في 1 يوليو 1819، مع تكملة في عام 1823. ^[12] تم الترحيب بحرارة وتوسع بورقة هورنر في الجزء الثاني من المعاملات الفلسفية للجمعية الملكية بلندن لعام 1819 من قبل أحد المراجعين ^{[ رابط معطل دائم ]} في عدد أبريل 1820 من مجلة The Monthly Review: أو، Literary Journal ؛ وبالمقارنة، تم رفض ورقة فنية كتبها تشارلز باباج بفظاظة في هذه المراجعة. خلص تسلسل المراجعات في The Monthly Review لشهر سبتمبر 1821 إلى أن هولدريد كان أول شخص يكتشف حلاً عمليًا مباشرًا وعامًا للمعادلات العددية. أظهر فولر ^[13] أن الطريقة في ورقة هورنر عام 1819 تختلف عما أصبح يُعرف بعد ذلك باسم "طريقة هورنر" وبالتالي فإن الأولوية لهذه الطريقة يجب أن تذهب إلى هولدر (1820).

على عكس معاصريه الإنجليز، استعان هورنر بالأدب القاري، وخاصة أعمال أربوجاست . ومن المعروف أيضًا أن هورنر قرأ عن كثب كتاب جون بونيكاسل عن الجبر، رغم أنه أهمل عمل باولو روفيني .

على الرغم من أن هورنر يُنسب إليه الفضل في جعل هذه الطريقة في متناول الجميع وعملية، إلا أنها كانت معروفة قبل هورنر بفترة طويلة. وفقًا للترتيب الزمني العكسي، كانت طريقة هورنر معروفة بالفعل:

• باولو روفيني عام 1809 (انظر قاعدة روفيني ) ^{[14] [15]}
• إسحاق نيوتن في عام 1669 ^{[16] [17]}
• عالم الرياضيات الصيني تشو شيجيه في القرن الرابع عشر ^[15]
• عالم الرياضيات الصيني تشين جيو شاو في أطروحته الرياضية المكونة من تسعة أقسام في القرن الثالث عشر
• عالم الرياضيات الفارسي شرف الدين الطوسي في القرن الثاني عشر (أول من استخدم هذه الطريقة في حالة عامة من المعادلة التكعيبية) ^[18]
• عالم الرياضيات الصيني جيا شيان في القرن الحادي عشر ( سلالة سونغ )
• الفصول التسعة في الفن الرياضي ، عمل صيني من عهد أسرة هان (202 ق.م - 220 م) حرره ليو هوي (القرن الثالث الميلادي). ^[19]

يقدم تشين جيو شاو في كتابه Shu Shu Jiu Zhang ( رسالة رياضية في تسعة أقسام ؛ 1247) مجموعة من الأساليب من نوع هورنر لحل المعادلات متعددة الحدود، والتي كانت تستند إلى أعمال سابقة لعالم الرياضيات جيا شيان من أسرة سونغ في القرن الحادي عشر ؛ على سبيل المثال، هناك طريقة مناسبة بشكل خاص لحل المعادلات ثنائية الخماسية، ويعطي تشين مثالاً على ذلك، بما يتماشى مع العادة الصينية آنذاك في دراسات الحالة. كتب يوشيو ميكامي في كتابه تطوير الرياضيات في الصين واليابان (لايبزيج 1913):

"... من يستطيع أن ينكر حقيقة استخدام عملية هورنر الشهيرة في الصين قبل ما يقرب من ستة قرون طويلة من استخدامها في أوروبا... نحن بالطبع لا ننوي بأي حال من الأحوال أن نعزو اختراع هورنر إلى أصل صيني، لكن مرور الوقت يجعل من غير المستحيل تمامًا أن يكون الأوروبيون قد عرفوا الطريقة الصينية بطريقة مباشرة أو غير مباشرة." ^[20]

استنتج أولريش ليبريشت : من الواضح أن هذا الإجراء هو اختراع صيني ... لم تكن الطريقة معروفة في الهند . وقال، ربما تعلم فيبوناتشي ذلك من العرب، الذين ربما استعاروا من الصينيين. ^[21] تمت مناقشة استخراج الجذور التربيعية والتكعيبية على خطوط مماثلة بالفعل من قبل ليو هوي فيما يتعلق بالمشكلتين IV.16 و 22 في Jiu Zhang Suan Shu ، بينما يفترض وانغ شياوتونغ في القرن السابع أن قرائه يمكنهم حل التكعيبية بطريقة تقريبية موصوفة في كتابه Jigu Suanjing .

• خوارزمية كلينشو لتقييم كثيرات الحدود في صيغة تشيبيشيف
• خوارزمية دي بور لتقييم الخطوط المنحنية في شكل B-spline
• خوارزمية De Casteljau لتقييم كثيرات الحدود في شكل بيزييه
• مخطط استرين لتسهيل التوازي في بنيات الكمبيوتر الحديثة
• طريقة ليل لتقريب الجذور بيانياً
• قاعدة روفيني والقسمة التركيبية لقسمة كثير الحدود على ثنائي الحدود من الشكل x − r

• "مخطط هورنر"، موسوعة الرياضيات ، EMS Press ، 2001 [1994]
• تشيو جين شاو، شو شو جيو تشانغ (طبعة كونغ شو جي تشنغ)
• لمزيد من المعلومات حول تطبيق العثور على الجذر، راجع [1] محفوظ في 2018-09-28 على موقع Wayback Machine