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

في الرياضيات ، تُعدّ خوارزمية نيفيل خوارزميةً تُستخدم لاستيفاء كثيرات الحدود، وقد اشتقّها عالم الرياضيات إريك هارولد نيفيل عام 1934. بمعلومية n + 1 نقطة، يوجد كثير حدود وحيد من الدرجة ≤ n يمرّ بهذه النقاط. تقوم خوارزمية نيفيل بتقييم هذا كثير الحدود.

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

بفرض وجود مجموعة من n + 1 نقطة بيانات ( xᵢ _, yᵢ ) حيث لا توجد نقطتان xᵢ متطابقتان، فإن متعددة الحدود الاستيفائية هي متعددة الحدود _{p من} الدرجة n على الأكثر والتي تتمتع بالخاصية التالية :

p ( xi ₎ = yi لجميع قيم i من 0 إلى _n .

هذه المعادلة متعددة الحدود موجودة وفريدة من نوعها. تقوم خوارزمية نيفيل بتقييم المعادلة متعددة الحدود عند نقطة ما x .

لنفترض أن _pᵢ, ⱼ _{يمثل متعدد} الحدود من الدرجة j − i الذي يمر بالنقاط ( xⱼ _, yⱼ ₎ حيث k = i , i + 1, ..., j . ويحقق pᵢ , _{ⱼ العلاقة} التكرارية _{التالية}

${\displaystyle p_{i,i}(x)=y_{i},\,}$	${\displaystyle 0\leq i\leq n,\,}$
${\displaystyle p_{i,j}(x)={\frac {(x-x_{i})p_{i+1,j}(x)-(x-x_{j})p_{i,j-1}(x)}{x_{j}-x_{i}}},\,}$	${\displaystyle 0\leq i<j\leq n.\,}$

يمكن لهذه العلاقة التكرارية حساب p _{0, n} ( x )، وهي القيمة المطلوبة. هذه هي خوارزمية نيفيل.

على سبيل المثال، بالنسبة لـ n = 4، يمكن للمرء استخدام التكرار لملء الجدول المثلثي أدناه من اليسار إلى اليمين.

${\displaystyle p_{0,0}(x)=y_{0}\,}$
	${\displaystyle p_{0,1}(x)\,}$
${\displaystyle p_{1,1}(x)=y_{1}\,}$		${\displaystyle p_{0,2}(x)\,}$
	${\displaystyle p_{1,2}(x)\,}$		${\displaystyle p_{0,3}(x)\,}$
${\displaystyle p_{2,2}(x)=y_{2}\,}$		${\displaystyle p_{1,3}(x)\,}$		${\displaystyle p_{0,4}(x)\,}$
	${\displaystyle p_{2,3}(x)\,}$		${\displaystyle p_{1,4}(x)\,}$
${\displaystyle p_{3,3}(x)=y_{3}\,}$		${\displaystyle p_{2,4}(x)\,}$
	${\displaystyle p_{3,4}(x)\,}$
${\displaystyle p_{4,4}(x)=y_{4}\,}$

ينتج عن هذه العملية p _0,4 ( x )، قيمة متعددة الحدود التي تمر عبر نقاط البيانات n + 1 ( x _i , y _i ) عند النقطة x .

تحتاج هذه الخوارزمية إلى O ( n ² ) عملية حسابية للفاصلة العائمة لاستكمال نقطة واحدة، و O ( n ³ ) عملية حسابية للفاصلة العائمة لاستكمال متعدد الحدود من الدرجة n.

يمكن الحصول على مشتقة متعددة الحدود بنفس الطريقة، أي:

${\displaystyle p'_{i,i}(x)=0,\,}$	${\displaystyle 0\leq i\leq n,\,}$
${\displaystyle p'_{i,j}(x)={\frac {(x-x_{i})p'_{i+1,j}(x)+p_{i+1,j}(x)-(x-x_{j})p'_{i,j-1}(x)-p_{i,j-1}(x)}{x_{j}-x_{i}}},\,}$	${\displaystyle 0\leq i<j\leq n.\,}$

في الصيغ أعلاه، إذا أخذنا درجة كثيرات الحدود الاستيفائية المتتالية d = j − i وغيرنا الترميز إلى p _{d , i} ,

${\displaystyle p_{0,i}(x)=y_{i},}$	${\displaystyle d=0}$
${\displaystyle p_{d,i}(x)={\frac {(x-x_{i})p_{d-1,i+1}(x)-(x-x_{i+d})p_{d-1,i}(x)}{x_{i+d}-x_{i}}},}$	${\displaystyle 1\leq d\leq n,0\leq i\leq nd}$

القيمة النهائية p _{n ,0} (في هذه الصيغة) هي القيمة المطلوبة التي تم استكمالها.

بما أن عدد العناصر المحسوبة، أي نطاق i، يتناقص مع كل قيمة d متتالية ، يمكن استخدام مصفوفة خطية لتحسين كفاءة الذاكرة، حيث يتم استبدال p _i وتجاهل d . (على سبيل المثال:)

يمكن حساب المشتقة (باستخدام قاعدة الضرب ) بنفس الطريقة كما يلي:

${\displaystyle p'_{0,i}(x)=0,}$	${\displaystyle d=0}$
${\displaystyle p'_{d,i}(x)={\frac {(x-x_{i})p'_{d-1,i+1}(x)+p_{d-1,i+1}(x)-(x-x_{i+d})p'_{d-1,i}(x)-p_{d-1,i}(x)}{x_{i+d}-x_{i}}},}$	${\displaystyle 1\leq d\leq n,0\leq i\leq nd}$

كما في السابق، فإن p ′ _{n ,0} (في هذه الصيغة) هو المشتق.

بما أن هذا يعتمد على القيم المحسوبة المتتالية لـ p لكل d ، فإنه يمكن حسابه ضمن نفس الحلقة. إذا تم استخدام مصفوفات خطية لـ p و p′ لتحسين الكفاءة، فيجب حساب قيم p ′ قبل استبدال قيم p .

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

• بريس، ويليام؛ شاول تيوكولسكي؛ ويليام فيترلينغ؛ برايان فلانيري (1992). "§3.1 الاستيفاء والاستقراء متعدد الحدود (مشفر)" (ملف PDF) . وصفات عددية بلغة C. فن الحوسبة العلمية (  الطبعة الثانية). مطبعة جامعة كامبريدج. ISBN 978-0-521-43108-8.{{cite book}}: CS1 maint: url-status ( link ) (link is bad)
• JN Lyness and CB Moler، أنظمة فان دير موند والتمايز العددي، Numerische Mathematik 8 (1966) 458-464 ( دوى:10.1007/BF02166671 )
• نيفيل، إي إتش: الاستيفاء التكراري. مجلة الجمعية الرياضية الهندية 20، 87-120 (1934)

• وايسشتاين، إريك دبليو. "خوارزمية نيفيل" . عالم الرياضيات .