طريقة ITP

في التحليل العددي ، تُعدّ طريقة ITP ( طريقة الاستيفاء والقطع والإسقاط ) أول خوارزمية لإيجاد الجذور تحقق التقارب الفائق الخطي لطريقة القاطع ^{[ 1 ]} مع الحفاظ على الأداء الأمثل ^{[ 2 ]} في أسوأ الحالات لطريقة التنصيف . ^{[ 3 ]} كما أنها أول طريقة تضمن أداءً متوسطًا أفضل من طريقة التنصيف في ظل أي توزيع مستمر. ^{[ 3 ]} عمليًا، تتفوق هذه الطريقة على الاستيفاء التقليدي والاستراتيجيات الهجينة ( طريقة برنت ، ريدرز ، إلينوي )، لأنها لا تتقارب بشكل فائق الخطية على الدوال المنتظمة فحسب، بل تضمن أيضًا أداءً سريعًا على الدوال غير المنتظمة حيث يفشل الاستيفاء. ^{[ 3 ]}

تتبع طريقة ITP نفس بنية استراتيجيات التحديد القياسية التي تتعقب الحدود العليا والسفلى لموقع الجذر؛ ولكنها تتعقب أيضًا المنطقة التي يبقى فيها أداء أسوأ الحالات ضمن حدود عليا. كاستراتيجية تحديد، تستعلم ITP في كل تكرار عن قيمة الدالة عند نقطة واحدة وتتجاهل جزء الفترة بين نقطتين حيث تتشارك قيمة الدالة نفس الإشارة. تُحسب النقطة المستعلم عنها بثلاث خطوات: أولًا، يتم استيفاء التقدير لإيجاد قيمة regula falsi ، ثم يتم تعديل/اقتطاع التقدير (على غرار Regula falsi §  تحسينات في regula falsi )، ثم يتم إسقاط التقدير المعدل على فترة في جوار نقطة منتصف التنصيف. يتم حساب الجوار حول نقطة التنصيف في كل تكرار لضمان الأمثلية الدنيا والقصوى (النظرية 2.1 من ^{[ 3 ]} ). تعتمد الطريقة على ثلاثة معلمات فائقة.${\displaystyle \kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)}$و${\displaystyle n_{0}\in [0,\infty )}$أين${\displaystyle \phi }$هي النسبة الذهبية${\displaystyle {\tfrac {1}{2}}(1+{\sqrt {5}})}$يتحكم المتغيران الأولان في حجم القطع، أما المتغير الثالث فهو متغير ركود يتحكم في حجم الفترة الزمنية لخطوة الإسقاط. ^{[ أ ]}

بالنظر إلى دالة متصلة${\displaystyle f}$مُعرَّف من${\displaystyle [a,b]}$ل${\displaystyle \mathbb {R} }$ بحيث${\displaystyle f(a)f(b)\leq 0}$، حيث يمكن الوصول إلى قيم بتكلفة استعلام واحد${\displaystyle f(x)}$في أي وقت معين${\displaystyle x}$. وبالنظر إلى دقة الهدف المحددة مسبقًا${\displaystyle \epsilon >0}$تم تصميم خوارزمية البحث عن الجذر لحل المشكلة التالية بأقل عدد ممكن من الاستعلامات:

تعريف المسألة: إيجاد${\displaystyle {\hat {x}}}$بحيث ${\displaystyle |{\hat {x}}-x^{*}|\leq \epsilon }$، أين${\displaystyle x^{*}}$يرضي${\displaystyle f(x^{*})=0}$.

تُعدّ هذه المشكلة شائعة جدًا في التحليل العددي وعلوم الحاسوب والهندسة ؛ وتُعتبر خوارزميات إيجاد الجذور هي الأسلوب القياسي لحلها. غالبًا ما يتم استدعاء إجراء إيجاد الجذور بواسطة خوارزميات أصلية أكثر تعقيدًا ضمن سياق أوسع، ولهذا السبب يُعدّ حلّ مشاكل الجذور بكفاءة أمرًا بالغ الأهمية، إذ قد يُكلّف الأسلوب غير الفعال تكلفة حسابية عالية عند أخذ السياق الأوسع في الاعتبار. هذا ما تحاول طريقة ITP تحقيقه من خلال الاستغلال المتزامن لضمانات الاستيفاء وضمانات الأمثلية الدنيا والقصوى لطريقة التنصيف التي تنتهي في أكثر من ${\displaystyle n_{1/2}\equiv \lceil \log _{2}((b_{0}-a_{0})/2\epsilon )\rceil }$التكرارات عند بدء التشغيل على فاصل زمني${\displaystyle [a_{0},b_{0}]}$.

منح${\displaystyle \kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)}$،${\displaystyle n_{1/2}\equiv \lceil \log _{2}((b_{0}-a_{0})/2\epsilon )\rceil }$ و${\displaystyle n_{0}\in [0,\infty )}$ أين${\displaystyle \phi }$هي النسبة الذهبية${\displaystyle {\tfrac {1}{2}}(1+{\sqrt {5}})}$، في كل تكرار${\displaystyle j=0,1,2\dots }$ تقوم طريقة ITP بحساب النقطة${\displaystyle x_{\text{ITP}}}$الخطوات الثلاث التالية:

1. [خطوة الاستيفاء] حساب نقاط التنصيف ونقاط الانحراف الكاذب: ${\displaystyle x_{1/2}\equiv {\frac {a+b}{2}}}$ و ${\displaystyle x_{f}\equiv {\frac {bf(a)-af(b)}{f(a)-f(b)}}}$ ؛
2. [خطوة الاقتطاع] قم بتغيير قيمة المُقدِّر باتجاه المركز: ${\displaystyle x_{t}\equiv x_{f}+\sigma \delta }$ أين ${\displaystyle \sigma \equiv {\text{sign}}(x_{1/2}-x_{f})}$و${\displaystyle \delta \equiv \min\{\kappa _{1}|ba|^{\kappa _{2}},|x_{1/2}-x_{f}|\}}$ ؛
3. [خطوة الإسقاط] إسقاط المُقدِّر على فاصل minmax:${\displaystyle x_{\text{ITP}}\equiv x_{1/2}-\sigma \rho _{k}}$أين${\displaystyle \rho _{k}\equiv \min \left\{\epsilon 2^{n_{1/2}+n_{0}-j}-{\frac {ba}{2}},|x_{t}-x_{1/2}|\right\}}$.

قيمة الدالة${\displaystyle f(x_{\text{ITP}})}$يتم الاستفسار عن هذه النقطة، ثم يتم تقليل الفترة الزمنية لتشمل الجذر عن طريق الاحتفاظ بالفترة الفرعية بقيم دالة ذات إشارة معاكسة على كل طرف.

مدخل:${\displaystyle a,b,\epsilon ,\kappa _{1},\kappa _{2},n_{0},f}$المعالجة المسبقة:${\displaystyle n_{1/2}=\lceil \log _{2}{\tfrac {b-a}{2\epsilon }}\rceil }$،${\displaystyle n_{\max }=n_{1/2}+n_{0}}$، و ${\displaystyle j=0}$؛ بينما (${\displaystyle b-a>2\epsilon }$)حساب المعلمات:${\displaystyle x_{1/2}={\tfrac {a+b}{2}}}$،${\displaystyle r=\epsilon 2^{n_{\max }-j}-(b-a)/2}$،${\displaystyle \delta =\kappa _{1}(b-a)^{\kappa _{2}}}$الاستيفاء :${\displaystyle x_{f}={\tfrac {y_{b}a-y_{a}b}{y_{b}-y_{a}}}}$الاقتطاع :${\displaystyle \sigma ={\text{sign}}(x_{1/2}-x_{f})}$؛ لو${\displaystyle \delta \leq |x_{1/2}-x_{f}|}$ثم${\displaystyle x_{t}=x_{f}+\sigma \delta }$، آخر${\displaystyle x_{t}=x_{1/2}}$الإسقاط : إذا${\displaystyle |x_{t}-x_{1/2}|\leq r}$ثم${\displaystyle x_{\text{ITP}}=x_{t}}$، آخر${\displaystyle x_{\text{ITP}}=x_{1/2}-\sigma r}$فترة التحديث:${\displaystyle y_{\text{ITP}}=f(x_{\text{ITP}})}$؛ لو${\displaystyle y_{\text{ITP}}>0}$ثم${\displaystyle b=x_{ITP}}$و${\displaystyle y_{b}=y_{\text{ITP}}}$، إلسيف${\displaystyle y_{\text{ITP}}<0}$ثم${\displaystyle a=x_{\text{ITP}}}$و${\displaystyle y_{a}=y_{\text{ITP}}}$، آخر${\displaystyle a=x_{\text{ITP}}}$و${\displaystyle b=x_{\text{ITP}}}$؛ ${\displaystyle j=j+1}$الناتج :${\displaystyle {\hat {x}}={\tfrac {a+b}{2}}}$

لنفترض أن طريقة ITP تُستخدم لإيجاد جذر لكثير الحدود${\displaystyle f(x)=x^{3}-x-2\,.}$استخدام${\displaystyle \epsilon =0.0005,\kappa _{1}=0.1,\kappa _{2}=2}$و${\displaystyle n_{0}=1}$وجدنا أن:

التكرار	${\displaystyle a_{n}}$	${\displaystyle b_{n}}$	${\displaystyle c_{n}}$	${\displaystyle f(c_{n})}$
1	1	2	1.43333333333333	-0.488629629629630
2	1.43333333333333	2	1.52713145056966	0.0343383329048983
3	1.43333333333333	1.52713145056966	1.52009281150978	-0.00764147709265051
4	1.52009281150978	1.52713145056966	1.52137899116052	-4.25363464540141e-06
5	1.52137899116052	1.52713145056966	1.52138301273268	1.96497878177659e-05
6	1.52137899116052	1.52138301273268	← تم ​​استيفاء معايير التوقف

يمكن مقارنة هذا المثال بطريقة التنصيف (  مثال: إيجاد جذر متعددة الحدود ). تتطلب طريقة ITP أقل من نصف عدد التكرارات التي تتطلبها طريقة التنصيف للحصول على تقدير أدق للجذر دون المساس بضمانات minmax. قد تحقق طرق أخرى سرعة تقارب مماثلة (مثل Ridders وBrent وغيرها) ولكن دون ضمانات minmax التي توفرها طريقة ITP.

تتمثل الميزة الرئيسية لطريقة ITP في أنها تضمن عدم الحاجة إلى عدد تكرارات أكثر من طريقة التنصيف عندما${\displaystyle n_{0}=0}$وبالتالي، يُضمن أن يكون أداؤها المتوسط ​​أفضل من طريقة التنصيف حتى في حالة فشل الاستيفاء. علاوة على ذلك، إذا لم يفشل الاستيفاء (الدوال السلسة)، فإنه يُضمن أن تتمتع برتبة تقارب عالية مثل الطرق القائمة على الاستيفاء.

• حزمة itp ^{[ 4 ]} المساهمة في R .

• طريقة التنصيف
• طريقة ميدرز
• Regula falsi
• طريقة برنت

• طريقة التنصيف المحسّنة ، من تأليف كودوس