आईटीपी विधि

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

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

File:ITPstep2.png

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

Error creating thumbnail:

आईटीपी पद्धति का चरण 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}}$

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

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

Iteration	$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

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

विश्लेषण

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

यह भी देखें

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

बाहरी संबंध

• An Improved Bisection Method, by Kudos