طريقة هورنر

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

هذه الطرق مسماة على اسم الرياضياتي البريطاني وليام جورج هورنر، بالرغم من أنهن كن معروفات قبله من پاولو روفيني ، وقبل ستمائة عام، من الرياضياتي الصيني چين جيوشاو وقبل سبعمائة عام من الرياضياتي الفارسي شرف الدين الطوسي.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 وصف الخوارزم

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

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

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

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

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

حينئذ b₀ هي قيمة p(x₀).

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

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

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

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

 أمثلة

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

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

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

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

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

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

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

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

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

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

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

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

 المصادر

 مؤلفات

• William George Horner. A new method of solving numerical equations of all orders, by continuous approximation. In Philosophical Transactions of the Royal Society of London, pp. 308–335, July 1819.
• Spiegel, Murray R. (1956). Schaum's Outline of Theory and Problems of College Algebra. McGraw-Hill Book Company.
• Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Pages 486–488 in section 4.6.4.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Problem 2-3 (pg. 39) and page 823 of section 30.1: Representation of polynomials.
• Kripasagar, Venkat (March 2008). "Efficient Micro Mathematics – Multiplication and Division Techniques for MCUs". Circuit Cellar magazine (212): p. 60. {{cite journal}}: |pages= has extra text (help)CS1 maint: date and year (link)

 وصلات خارجية

• Eric W. Weisstein, Horner's method at MathWorld.
• Module for Horner's Method by John H. Mathews