आईटीपी विधि

संख्यात्मक विश्लेषण में, आईटीपी विधि, अंतर्वेशन रुंडित और परियोजना के लिए संक्षिप्त, पहला मूल -खोज एल्गोरिदम है जो द्विभाजन विधि के इष्टतम सबसे खराब प्रदर्शन को बनाए रखते हुए सेकेंट विधि के सुपरलीनियर अभिसरण को प्राप्त करता है।। यह किसी भी निरंतर वितरण के अंतर्गत द्विभाजन विधि की तुलना में गारंटीकृत औसत प्रदर्शन वाली पहली विधि भी है।व्यवहार में यह पारंपरिक अंतर्वेशन और हाइब्रिड आधारित रणनीतियों ( ब्रेंट की विधि, रिडर्स विधि, इलिनोइस) से अधिक अच्छा प्रदर्शन करता है, क्योंकि यह न केवल अच्छे व्यवहार वाले कार्यों पर सुपर-रैखिक रूप से अभिसरण करता है बल्कि खराब व्यवहार वाले कार्यों के अंतर्गत तेजी से प्रदर्शन की गारंटी भी देता है। अंतर्वेशन विफल हो जाते हैं.

आईटीपी विधि मानक ब्रैकेटिंग रणनीतियों की समान संरचना का पालन करती है जो मूल के स्थान के लिए ऊपरी और निचली सीमाओं पर नज़र रखती है; लेकिन यह उस क्षेत्र पर भी नज़र रखता है जहां सबसे खराब स्थिति वाले प्रदर्शन को ऊपरी सीमा में रखा जाता है। ब्रैकेटिंग रणनीति के रूप में, प्रत्येक पुनरावृत्ति में आईटीपी एक बिंदु पर फलन के मान पर सवाल उठाता है और दो बिंदुओं के बीच के अंतराल के हिस्से को छोड़ देता है जहां फलन मान समान चिह्न साझा करता है। पूछे गए बिंदु की गणना तीन चरणों के साथ की जाती है: यह रेगुला फाल्सी अनुमान को खोजने के लिए प्रक्षेपित करता है, फिर यह अनुमान को उत्तेजित /छोटा कर देता है (इसी तरह) रेगुला फाल्सी के समान § रेगुला फाल्सी में सुधार) और फिर विक्षुब्ध अनुमान को द्विभाजन मध्यबिंदु के पड़ोस में एक अंतराल पर प्रक्षेपित करता है। न्यूनतम अधिकतम इष्टतमता की गारंटी के लिए प्रत्येक पुनरावृत्ति में द्विभाजन बिंदु के आसपास के पड़ोस की गणना की जाती है (प्रमेय 2.1) । विधि तीन अतिप्राचल पर निर्भर करती है $\kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)$ और $n_{0}\in [0,\infty )$ जहाँ $\phi$ स्वर्णिम अनुपात है ${\tfrac {1}{2}}(1+{\sqrt {5}})$: पहले दो खंडन के आकार को नियंत्रित करते हैं और तीसरा एक सुस्त चर है जो प्रक्षेपण चरण के लिए अंतराल के आकार को नियंत्रित करता है।

मूल खोजने की समस्या

एक सतत कार्य $f$ दिया गया $[a,b]$ को $\mathbb {R}$ से परिभाषित ऐसा है कि $f(a)f(b)\leq 0$, जहां एक सवाल की कीमत पर किसी भी दिए गए$x$ पर कोई भी $f(x)$ के मान तक पहुंच सकता है। और, एक पूर्व-निर्दिष्ट लक्ष्य परिशुद्धता $\epsilon >0$ दी गई है , एक मूल खोज एल्गोरिदम को यथासंभव कम से कम प्रश्नों के साथ निम्नलिखित समस्या को हल करने के लिए डिज़ाइन किया गया है:

समस्या परिभाषा: ${\hat {x}}$ को खोजें ऐसा है कि $|{\hat {x}}-x^{*}|\leq \epsilon$, जहाँ $x^{*}$ $f(x^{*})=0$ को संतुष्ट करता है

यह समस्या संख्यात्मक विश्लेषण, कंप्यूटर विज्ञान और अभियांत्रिकी में बहुत सामान्य है; और, मूल खोज एल्गोरिदम इसे हल करने के लिए मानक दृष्टिकोण हैं। प्रायः, मूल-खोज प्रक्रिया को बड़े संदर्भ में अधिक जटिल मूल एल्गोरिदम द्वारा बुलाया जाता है, और इस कारण से मूल समस्याओं को कुशलतापूर्वक हल करना अत्यधिक महत्वपूर्ण है क्योंकि जब बड़े संदर्भ को ध्यान में रखा जाता है तो एक अकुशल दृष्टिकोण उच्च कम्प्यूटेशनल लागत पर आ सकता है।आईटीपी विधि एक साथ अंतर्वेशन गारंटी के साथ-साथ द्विभाजन विधि की मिनमैक्स इष्टतम गारंटी का उपयोग करके ऐसा करने का प्रयास करती है जो अधिकतम $n_{1/2}\equiv \lceil \log _{2}((b_{0}-a_{0})/2\epsilon )\rceil$में समाप्त होती है एक अंतराल$[a_{0},b_{0}]$ पर आरंभ होने पर पुनरावृत्तियाँ।

विधि

दिया गया $\kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)$, $n_{1/2}\equiv \lceil \log _{2}((b_{0}-a_{0})/2\epsilon )\rceil$ और $n_{0}\in [0,\infty )$ जहाँ $\phi$ स्वर्णिम अनुपात है ${\tfrac {1}{2}}(1+{\sqrt {5}})$, प्रत्येक पुनरावृत्ति में $j=0,1,2\dots$ आईटीपी विधि बिंदु $x_{\text{ITP}}$की गणना निम्नलिखित तीन चरण में करती है:

File:ITPstep1.png

आईटीपी पद्धति का चरण 1.

आईटीपी पद्धति का चरण 2.

आईटीपी पद्धति का चरण 3.

File:ITPall steps.png

तीनों चरण मिलकर ITP विधि बनाते हैं। मोटी नीली रेखा विधि के प्रक्षेपित-काटे-प्रक्षेप का प्रतिनिधित्व करती है।

[अंतर्वेशनचरण] द्विभाजन और रेगुला फाल्सी बिंदुओं की गणना करें: $x_{1/2}\equiv {\frac {a+b}{2}}$ और