طريقة هورنر

في الرياضيات وعلوم الحاسوب ، تُعدّ طريقة هورنر (أو مخطط هورنر ) خوارزميةً لحساب كثيرات الحدود . سُمّيت نسبةً إلى ويليام جورج هورنر ، مع أنها أقدم من ذلك بكثير، إذ نسبها هورنر إلى جوزيف لويس لاغرانج ، وقد اكتشفها علماء رياضيات صينيون وفرس قبل ذلك بمئات السنين. ^{[ 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 باستخدام${\displaystyle n}$الضرب و${\displaystyle n}$عمليات الجمع. هذا هو الأمثل، حيث يستحيل تقييم كثيرات الحدود من الدرجة n بعدد أقل من العمليات الحسابية عندما يتم إعطاء كل من x والمعاملات a ₀ ، ... ، a _n كمدخلات. ^{[ 2 ]}

طريقة هورنر وتشير طريقة هورنر-روفيني أيضًا إلى طريقة لتقريب جذور كثيرات الحدود، وصفها هورنر عام 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}}$في التعبير، $$\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 x-x_{0}}$عامل من${\displaystyle p(x)}$.

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

يمكن تعديل طريقة هورنر لحساب الفرق المقسم${\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},}$$ اتبع الخطوات التالية ^{[ 10 ]}$${\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}$.

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

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

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

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

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

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

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

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

• "مخطط هورنر" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]
• تشيو، جين شاو. "طريقة هورنر" (ملف PDF) . turing.une.edu.au (باللغة الصينية). مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 6 يناير 2014. تاريخ الاطلاع: 17 يناير 2026 .
• وايسشتاين، إريك و. (28-09-2018). "طريقة هورنر" . mathworld.wolfram.com . تم الاطلاع عليه بتاريخ 17-01-2026 .المزيد حول تطبيق البحث عن الجذر