في التحليل العددي ، طريقة هورنر ، أو مخطط هورنر ، أو خوارزمية هورنر على اسم ويليام جورج هورنر ، هي خوارزمية فعالة لتقييم كثيرات الحدود ومشتقاتها عند نقطة معينة في شكل أحادية حدود .[1] [2] تصف طريقة هورنر عملية يدوية يمكن بواسطتها تقريب جذور معادلة كثيرة حدود. يمكن النظر لمخطط هورنر أيضا على أنه خوارزمية سريعة لقسمة كثيرة حدود على كثيرة حدود خطية بقاعدة رفيني .
وصف الخوارزمية [ عدل ]
لتكن دالة كثيرة الحدود
p
(
x
)
=
a
0
+
a
1
x
+
a
2
x
2
+
a
3
x
3
+
⋯
+
a
n
x
n
,
{\displaystyle p(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n},}
حيث
a
0
,
…
,
a
n
{\displaystyle a_{0},\ldots ,a_{n}}
أعداد حقيقية، يراد بها حساب متعددة الحدود عن قيم معينة x , ولتكن x 0 .
لفعل ذلك، نقوم بتعريف تعاقب جديد من الثوابت كما يلي:
b
n
:=
a
n
b
n
−
1
:=
a
n
−
1
+
b
n
x
0
⋮
b
0
:=
a
0
+
b
1
x
0
.
{\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 0 هي قيمة (p(x0</sub >.
لمعرفة سبب عمل هذا، لاحظ أن بالإمكان كتابة كثيرة الحدود على الصورة
p
(
x
)
=
a
0
+
x
(
a
1
+
x
(
a
2
+
⋯
+
x
(
a
n
−
1
+
a
n
x
)
⋯
)
)
.
{\displaystyle p(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots +x(a_{n-1}+a_{n}x)\cdots )).\,}
وبالتالي، وبالتعويض المتتابع لـ
b
i
{\displaystyle b_{i}}
في التعبير,
p
(
x
0
)
=
a
0
+
x
0
(
a
1
+
x
0
(
a
2
+
⋯
x
0
(
a
n
−
1
+
b
n
x
0
)
⋯
)
)
=
a
0
+
x
0
(
a
1
+
x
0
(
a
2
+
⋯
x
0
(
b
n
−
1
)
…
)
)
⋮
=
a
0
+
x
0
(
b
1
)
=
b
0
.
{\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}}}
أمثلة [ عدل ]
قيم
f
1
(
x
)
=
2
x
3
−
6
x
2
+
2
x
−
1
{\displaystyle f_{1}(x)=2x^{3}-6x^{2}+2x-1\,}
لأجل
x
=
3
{\displaystyle x=3\;}
. بإخراج معاملات
x
{\displaystyle x}
, تتابعيا، يمكن كتابة
f
1
{\displaystyle f_{1}}
بالصورة
x
(
x
(
2
x
−
6
)
+
2
)
−
1
{\displaystyle x(x(2x-6)+2)-1\;}
. باستعمال شكل اصطناعي لترتيب هذه الحسابات وتسريع العمليات
x
0
{\displaystyle x_{0}}
|
x
3
{\displaystyle x^{3}}
x
2
{\displaystyle x^{2}}
x
1
{\displaystyle x^{1}}
x
0
{\displaystyle x^{0}}
3 | 2 -6 2 -1
| 6 0 6
|----------------------
2 0 2 5
مدخلات الصف الثالث هي مجموع المدخلات في الصفين الأول والثاني. كل مدخل في الصف الثاني يكون نتاج ضرب قيمة x (3 في هذا المثال(بمدخل الصف الثالث مباشرة إلى اليسار. المدخلات في الصف الأول هي معاملات كثيرة الحدود المراد حسابها. الجواب هو 5.
وكنتيجة لنظرية باقي كثيرة الحدود ، تكون مدخلات الصف الثالث هي معاملات كثيرة الحدود من الدرجة الثانية التي هي حاصل قسمة f1 /(x-3). الباقي هو 5. هذا يجعل طريقة هورنر مفيدة في قسمة كثيرة الحدود المطولة .
بقسمة
x
3
−
6
x
2
+
11
x
−
6
{\displaystyle x^{3}-6x^{2}+11x-6\,}
على
x
−
2
{\displaystyle x-2}
:
2 | 1 -6 11 -6
| 2 -8 6
|----------------------
1 -4 3 0
يكون حاصل القسمة
x
2
−
4
x
+
3
{\displaystyle x^{2}-4x+3}
.
لتكن
f
1
(
x
)
=
4
x
4
−
6
x
3
+
3
x
−
5
{\displaystyle f_{1}(x)=4x^{4}-6x^{3}+3x-5\,}
و
f
2
(
x
)
=
2
x
−
1
{\displaystyle f_{2}(x)=2x-1\,}
. بقسمة
f
1
(
x
)
{\displaystyle f_{1}(x)\,}
على
f
2
(
x
)
{\displaystyle f_{2}\,(x)}
باستعمال مخطط هورنر.
2 | 4 -6 0 3 | -5
---------------------------|------
1 | 2 -2 -1 | 1
| |
|----------------------|-------
2 -2 -1 1 | -4
الصف الثالث هو مجموع الصفين الأول والثاني، مقسوما على 2. كل مدخل في الصف الثاني هو حاصل ضرب 1 مع مدخل الصف الثالث إلى اليسار. الإجابة تكون:
f
1
(
x
)
f
2
(
x
)
=
2
x
3
−
2
x
2
−
x
+
1
−
4
(
2
x
−
1
)
.
{\displaystyle {\frac {f_{1}(x)}{f_{2}(x)}}=2x^{3}-2x^{2}-x+1-{\frac {4}{(2x-1)}}.}
انظر أيضاً [ عدل ]
المصادر [ عدل ]
وصلات خارجية [ عدل ]
نسخة مماثلة [ عدل ]
مخطط هورنر - موسوعة المعرفة