طريقة هورنر

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

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

وصف الخوارزمية

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

p(x)=a0+a1x+a2x2+a3x3++anxn,

حيث a0,,an أعداد حقيقية، يراد بها حساب متعددة الحدود عن قيم معينة x, ولتكن x0.

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

bn:=anbn1:=an1+bnx0b0:=a0+b1x0.

حينئذ b0 هي قيمة (p(x0</sub>.

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

p(x)=a0+x(a1+x(a2++x(an1+anx))).

وبالتالي، وبالتعويض المتتابع لـ bi في التعبير,

p(x0)=a0+x0(a1+x0(a2+x0(an1+bnx0)))=a0+x0(a1+x0(a2+x0(bn1)))=a0+x0(b1)=b0.

أمثلة

قيم f1(x)=2x36x2+2x1 لأجل x=3. بإخراج معاملات x, تتابعيا، يمكن كتابة f1 بالصورة x(x(2x6)+2)1. باستعمال شكل اصطناعي لترتيب هذه الحسابات وتسريع العمليات

x0 |  x3  x2   x1  x0
3 |  2  -6   2  -1
 |     6   0   6  
 |----------------------
   2   0   2   5

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

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

بقسمة x36x2+11x6 على x2:

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

يكون حاصل القسمة x24x+3.

لتكن f1(x)=4x46x3+3x5 وf2(x)=2x1. بقسمة f1(x) على f2(x) باستعمال مخطط هورنر.

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

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

f1(x)f2(x)=2x32x2x+14(2x1).

انظر أيضاً

المصادر

  1. ^ "معلومات عن طريقة هورنر على موقع britannica.com". britannica.com. مؤرشف من الأصل في 2016-07-22.
  2. ^ "معلومات عن طريقة هورنر على موقع mathworld.wolfram.com". mathworld.wolfram.com. مؤرشف من الأصل في 2018-09-28.

مؤلفات

وصلات خارجية

نسخة مماثلة

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