طريقة التنصيف

لتحديد متى يجب إيقاف التكرار، من الضروري مراعاة شروط الإيقاف المختلفة المحتملة فيما يتعلق بالتسامح (${\displaystyle \epsilon }$). حدد بيردن وفيرز (2016) شروط التوقف الثلاثة: ^{[ 7 ]}

• التسامح المطلق:${\displaystyle |p_{N}-p_{N-1}|<\epsilon }$
• التسامح النسبي:${\displaystyle \left|{\frac {p_{N}-p_{N-1}}{p_{N}}}\right|<\epsilon ,}$||${\displaystyle p_{N}\neq 0}$
• ${\displaystyle |f(p_{N})|<\epsilon .}$

${\displaystyle |f(p_{N})|<\epsilon }$لا يعطي نتيجة دقيقة في حدود${\displaystyle \epsilon }$إلا إذا${\displaystyle |f'(p_{N})|\geq 1}$أما الاحتمالان الآخران فيمثلان مفهومين مختلفين: الفرق المطلق${\displaystyle |c-a|\leq 5\times 10^{-t}}$يقول إن c و a متساويان بالنسبة لـ${\displaystyle t}$المنازل العشرية، بينما الفرق النسبي${\displaystyle \left|{\frac {c-a}{c}}\right|\leq 5\times 10^{-t}}$يقول إن c و a متساويان بالنسبة لـ${\displaystyle t}$الأرقام المعنوية . ^{[ 8 ]} إذا لم يكن معروفًا شيء عن قيمة الجذر، فإن التسامح النسبي هو أفضل شرط للتوقف. ^{[ 9 ]}

المدخلات لهذه الطريقة هي دالة متصلة${\displaystyle f}$وفترة زمنية${\displaystyle [a,b]}$، بحيث تكون قيم الدالة${\displaystyle f(a)}$و${\displaystyle f(b)}$ تكون الإشارات متعاكسة (يوجد على الأقل تقاطع واحد مع الصفر ضمن الفترة). تقوم كل تكرارة بالخطوات التالية:

1. احسب${\displaystyle c}$، نقطة منتصف الفترة،${\displaystyle c={\frac {a+b}{2}}}$؛
2. احسب قيمة الدالة عند نقطة المنتصف،${\displaystyle f(c)}$؛
3. لو${\displaystyle f(c)=0}$، أعد c؛
4. إذا كان التقارب مُرضيًا (أي،${\displaystyle \left|c-a\right|\leq 5\times 10^{-t}|c|}$)، يعود${\displaystyle c}$؛
5. افحص علامة${\displaystyle f(c)}$واستبدل إما${\displaystyle a}$أو${\displaystyle b}$مع${\displaystyle c}$بحيث يكون هناك تقاطع مع الصفر ضمن الفترة الجديدة.

لنفترض أن طريقة التنصيف تُستخدم لإيجاد جذر لكثير الحدود

${\displaystyle f(x)=x^{3}-x-2\,.}$

أولاً، رقمان${\displaystyle a}$و${\displaystyle b}$يجب إيجادها بحيث${\displaystyle f(a)}$و${\displaystyle f(b)}$لها إشارات متعاكسة. بالنسبة للدالة المذكورة أعلاه،${\displaystyle a=1}$و${\displaystyle b=2}$استيفاء هذا المعيار، كما

${\displaystyle f(1)=(1)^{3}-(1)-2=-2}$

و

${\displaystyle f(2)=(2)^{3}-(2)-2=+4\,.}$

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

التكرار	${\displaystyle a_{n}}$	${\displaystyle b_{n}}$	${\displaystyle c_{n}}$	${\displaystyle f(c_{n})}$
1	1	2	1.5	-0.125
2	1.5	2	1.75	1.6093750
3	1.5	1.75	1.625	0.6660156
4	1.5	1.625	1.5625	0.2521973
5	1.5	1.5625	1.5312500	0.0591125
6	1.5	1.5312500	1.5156250	-0.0340538
7	1.5156250	1.5312500	1.5234375	0.0122504
8	1.5156250	1.5234375	1.5195313	-0.0109712
9	1.5195313	1.5234375	1.5214844	0.0006222
10	1.5195313	1.5214844	1.5205078	-0.0051789
11	1.5205078	1.5214844	1.5209961	-0.0022794
12	1.5209961	1.5214844	1.5212402	-0.0008289
13	1.5212402	1.5214844	1.5213623	-0.0001034
14	1.5213623	1.5214844	1.5214233	0.0002594
15	1.5213623	1.5214233	1.5213928	0.0000780

بعد 13 تكرارًا، يتضح أن هناك تقاربًا إلى حوالي 1.521: وهو جذر لكثير الحدود.

تعتمد بعض هذه الطرق على حساب الدرجة الطوبولوجية . ^{[ 12 ]}

تعتمد طريقة التنصيف المميز على إشارات الدالة فقط عند نقاط مختلفة. لتكن f دالة من R ^d إلى R ^d ، حيث d عدد صحيح ≥ 2. المجسم المميز ^{[ 13 ]} (ويُسمى أيضًا المضلع المقبول ) ^{[ 14 ]} للدالة f هو مجسم في R ^d ، له 2d ^رأسًا ، بحيث يكون لكل رأس v تركيبة إشارات f ( v ) فريدة. على سبيل المثال، عندما d = 2، يكون المجسم المميز للدالة f شكلًا رباعيًا برؤوس (مثلاً) A وB وC وD، بحيث:

• Sign f (A) = ( − , − ), أي أن f ₁ (A)<0, f ₂ (A)<0.
• Sign f (B) = ( − ,+), أي أن f ₁ (B)<0، f ₂ (B)>0.
• Sign f (C) = (+, − ), أي أن f ₁ (C)>0، f ₂ (C)<0.
• Sign f (D) = (+,+), أي أن f ₁ (D)>0، f ₂ (D)>0.

الحافة الصحيحة للمضلع المميز هي حافة بين رأسين، بحيث يختلف متجه الإشارة بينهما بإشارة واحدة فقط. في المثال أعلاه، الحواف الصحيحة للرباعي المميز هي AB وAC وBD وCD. أما القطر فهو زوج من الرؤوس، بحيث يختلف متجه الإشارة بينهما بجميع الإشارات d . في المثال أعلاه، القطران هما AD وBC.

في كل تكرار، تختار الخوارزمية حافة مناسبة من متعدد السطوح (مثلاً، A - B)، وتحسب إشارات f عند نقطة منتصفها (مثلاً، M). ثم تتابع على النحو التالي:

• إذا كانت Sign f (M) = Sign(A)، فسيتم استبدال A بـ M، وسنحصل على متعدد السطوح المميز الأصغر.
• إذا كانت Sign f (M) = Sign(B)، فسيتم استبدال B بـ M، وسنحصل على متعدد السطوح المميز الأصغر.
• وإلا، سنختار حافة مناسبة جديدة ونحاول مرة أخرى.

لنفترض أن قطر (= طول أطول ضلع حقيقي) متعدد السطوح الأصلي المميز هو D. إذن، على الأقل${\displaystyle \log _{2}(D/\varepsilon )}$يلزم تقسيم الحواف إلى نصفين بحيث يكون قطر المضلع المتبقي على الأكثر${\displaystyle \varepsilon }$[ ^{14 ] : 11، المبرهنة 4.7}