आईटीपी विधि

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

आईटीपी विधि मानक ब्रैकेटिंग रणनीतियों की समान संरचना का पालन करती है जो मूल के स्थान के लिए ऊपरी और निचली सीमाओं पर नज़र रखती है; लेकिन यह उस क्षेत्र पर भी नज़र रखता है जहां सबसे खराब स्थिति वाले प्रदर्शन को ऊपरी सीमा में रखा जाता है। ब्रैकेटिंग रणनीति के रूप में, प्रत्येक पुनरावृत्ति में आईटीपी एक बिंदु पर फलन के मान पर सवाल उठाता है और दो बिंदुओं के बीच के अंतराल के हिस्से को छोड़ देता है जहां फलन मान समान चिह्न साझा करता है। पूछे गए बिंदु की गणना तीन चरणों के साथ की जाती है: यह रेगुला फाल्सी अनुमान को खोजने के लिए प्रक्षेपित करता है, फिर यह अनुमान को उत्तेजित /छोटा कर देता है (इसी तरह) रेगुला फाल्सी के समान § रेगुला फाल्सी में सुधार) और फिर विक्षुब्ध अनुमान को द्विभाजन मध्यबिंदु के पड़ोस में एक अंतराल पर प्रक्षेपित करता है। न्यूनतम अधिकतम इष्टतमता की गारंटी के लिए प्रत्येक पुनरावृत्ति में द्विभाजन बिंदु के आसपास के पड़ोस की गणना की जाती है (प्रमेय 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}}$की गणना निम्नलिखित तीन चरण में करती है:

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

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

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

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

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

1. [छंटाई चरण] अनुमानक को केंद्र की ओर घुमाएं: $x_{t}\equiv x_{f}+\sigma \delta$ जहाँ $\sigma \equiv {\text{sign}}(x_{1/2}-x_{f})$ और $\delta \equiv \min\{\kappa _{1}|b-a|^{\kappa _{2}},|x_{1/2}-x_{f}|\}$ ;
2. [प्रक्षेपण चरण] अनुमानक को न्यूनतम अंतराल : $x_{\text{ITP}}\equiv x_{1/2}-\sigma \rho _{k}$ पर प्रोजेक्ट करें जहाँ $\rho _{k}\equiv \min \left\{\epsilon 2^{n_{1/2}+n_{0}-j}-{\frac {b-a}{2}},|x_{t}-x_{1/2}|\right\}$.

इस बिंदु पर फलन के मान $f(x_{\text{ITP}})$ की पूछताछ की जाती है, और फिर प्रत्येक छोर पर विपरीत चिह्न के फलन मानों के साथ उप-अंतराल रखकर मूल को ब्रैकेट करने के लिए अंतराल को कम किया जाता है।

एल्गोरिथ्म

निम्नलिखित एल्गोरिदम (छद्म कोड में लिखा गया)मानता है की $y_{a}$ और $y_{b}$का प्रारंभिक मान दिया गया है और $y_{a}<0<y_{b}$ जहाँ $y_{a}\equiv f(a)$ और $y_{b}\equiv f(b)$; को संतुष्ट करता है और, यह एक अनुमान ${\hat {x}}$ को लौटाता है जो $|{\hat {x}}-x^{*}|\leq \epsilon$ को अधिक से अधिक $n_{1/2}+n_{0}$ कार्य मूल्यांकन में संतुष्ट करता है।

इनपुट: $a,b,\epsilon ,\kappa _{1},\kappa _{2},n_{0},f$पूर्वप्रसंस्करण:$n_{1/2}=\lceil \log _{2}{\tfrac {b-a}{2\epsilon }}\rceil$,$n_{\max }=n_{1/2}+n_{0}$, और$j=0$;
    जबकि ( $b-a>2\epsilon$)
  
        पैरामीटर्स की गणना:$x_{1/2}={\tfrac {a+b}{2}}$,$r=\epsilon 2^{n_{\max }-j}-(b-a)/2$,$\delta =\kappa _{1}(b-a)^{\kappa _{2}}$;
        प्रक्षेप:$x_{f}={\tfrac {y_{b}a-y_{a}b}{y_{b}-y_{a}}}$;
        काट-छाँट:$\sigma ={\text{sign}}(x_{1/2}-x_{f})$;
            यदि$\delta \leq |x_{1/2}-x_{f}|$तब$x_{t}=x_{f}+\sigma \delta$,
            अन्य$x_{t}=x_{1/2}$;
        प्रक्षेपण: 
            यदि$|x_{t}-x_{1/2}|\leq r$तब$x_{\text{ITP}}=x_{t}$,
            अन्य$x_{\text{ITP}}=x_{1/2}-\sigma r$;
        अद्यतन अंतराल:$y_{\text{ITP}}=f(x_{\text{ITP}})$;
            यदि$y_{\text{ITP}}>0$तब$b=x_{ITP}$और$y_{b}=y_{\text{ITP}}$,
            Elseif$y_{\text{ITP}}<0$तब$a=x_{\text{ITP}}$और$y_{a}=y_{\text{ITP}}$,
            अन्य$a=x_{\text{ITP}}$और$b=x_{\text{ITP}}$;$j=j+1$;
आउटपुट: ${\hat {x}}={\tfrac {a+b}{2}}$

उदाहरण: एक बहुपद का मूल ज्ञात करना

मान लीजिए कि बहुपद$f(x)=x^{3}-x-2\,.$का मूल ज्ञात करने के लिए ITP विधि का उपयोग किया जाता है। $\epsilon =0.0005,\kappa _{1}=0.1,\kappa _{2}=2$ और $n_{0}=1$ का उपयोग करते हुए हम पाते हैं कि:

पुनरावर्तन	$a_{n}$	$b_{n}$	$c_{n}$	$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	← Stopping Criteria Satisfied

इस उदाहरण की तुलना द्विभाजन विधि § उदाहरण: एक बहुपद का मूल ज्ञात करना से जा सकती है।न्यूनतम अधिकतम गारंटी पर बिना किसी लागत के मूल का अधिक सटीक अनुमान प्राप्त करने के लिए आईटीपी विधि को द्विभाजन की तुलना में आधे से भी कम पुनरावृत्तियों की आवश्यकता होती है। अन्य विधियाँ भी अभिसरण की समान गति प्राप्त कर सकती हैं (जैसे कि रिडर्स, ब्रेंट इत्यादि) लेकिन आईटीपी विधि द्वारा दी गई न्यूनतम अधिकतम गारंटी के बिना।

विश्लेषण

आईटीपी विधि का मुख्य लाभ यह है कि इसमें द्विभाजन विधि की तुलना में अधिक पुनरावृत्तियों की आवश्यकता नहीं होने की गारंटी है $n_{0}=0$। और इसलिए अंतर्वेशन विफल होने पर भी इसका औसत प्रदर्शन द्विभाजन विधि से अधिक अच्छा होने की गारंटी है। इसके अतिरिक्त, यदि अंतर्वेशन विफल नहीं होते हैं (सुचारू कार्य), तो अंतर्वेशन आधारित तरीकों के रूप में अभिसरण के उच्च क्रम का आनंद लेने की गारंटी है।

सबसे खराब स्थिति प्रदर्शन

क्योंकि आईटीपी विधि अनुमानक को न्यूनतम अधिकतम अंतराल पर प्रोजेक्ट करती है $n_{0}$ ढील के साथ, इसकी अधिक से अधिक $n_{1/2}+n_{0}$ पुनरावृत्तियो की आवश्यकता होगी (प्रमेय 2.1) )। यह द्विभाजन विधि की तरह न्यूनतम अधिकतम इष्टतम है जब $n_{0}$ ,$n_{0}=0$होना चुना गया है।

औसत प्रदर्शन

क्योंकि $n_{1/2}+n_{0}$ इससे ज्यादा पुनरावृत्तिया नहीं लेती , किसी भी वितरण के लिए पुनरावृत्तियों की औसत संख्या हमेशा द्विभाजन विधि की तुलना में कम होगी जब $n_{0}=0$ होगा (परिणाम 2.2) ).

उपगामी प्रदर्शन

यदि फलन$f(x)$ दो बार भिन्न और मूल है $x^{*}$ सरल है, तो आईटीपी विधि द्वारा उत्पादित अंतराल अभिसरण के क्रम ${\sqrt {\kappa _{2}}}$ के साथ 0 में परिवर्तित हो जाते हैं यदि $n_{0}\neq 0$ या यदि $n_{0}=0$ और $(b-a)/\epsilon$ ,${\tfrac {\epsilon 2^{n_{1/2}}}{b-a}}$पद के साथ 2 की घात नहीं है शून्य के बहुत करीब नहीं है(प्रमेय 2.3)। ).

यह भी देखें

• द्विभाजन विधि
• रिडर्स विधि
• रेगुला मिथ्या
• ब्रेंट की विधि

बाहरी संबंध

• An Improved Bisection Method, by Kudos