आईटीपी विधि

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

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

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

एक सतत कार्य दिया गया $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.

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

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

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

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

[छंटाई चरण] अनुमानक को केंद्र की ओर घुमाएं: $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}|\}$ ;
[प्रक्षेपण चरण] अनुमानक को न्यूनतम अंतराल पर प्रोजेक्ट करें: $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) ^[3]). यह द्विभाजन विधि की तरह न्यूनतम अधिकतम इष्टतम है जब $n_{0}$ होना चुना गया है $n_{0}=0$ .

औसत प्रदर्शन

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

स्पर्शोन्मुख प्रदर्शन

यदि फ़ंक्शन $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)। ^[3]).

यह भी देखें

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

संदर्भ

↑ Argyros, I. K.; Hernández-Verón, M. A.; Rubio, M. J. (2019). "सेकेंट-जैसी विधियों के अभिसरण पर". Current Trends in Mathematical Analysis and Its Interdisciplinary Applications (in English): 141–183. doi:10.1007/978-3-030-15242-0_5. ISBN 978-3-030-15241-3.
↑ Sikorski, K. (1982-02-01). "द्विभाजन इष्टतम है". Numerische Mathematik (in English). 40 (1): 111–117. doi:10.1007/BF01459080. ISSN 0945-3245. S2CID 119952605.
↑ ^3.0 ^3.1 ^3.2 ^3.3 ^3.4 ^3.5 ^3.6 Oliveira, I. F. D.; Takahashi, R. H. C. (2020-12-06). "मिनमैक्स इष्टतमता को संरक्षित करते हुए द्विभाजन विधि औसत प्रदर्शन का संवर्द्धन". ACM Transactions on Mathematical Software. 47 (1): 5:1–5:24. doi:10.1145/3423597. ISSN 0098-3500.

बाहरी संबंध

An Improved Bisection Method, by Kudos

[4] For a more in-depth discussion of the hyper-parameters, see the documentation for ITP in the kurbo library.

[1] Argyros, I. K.; Hernández-Verón, M. A.; Rubio, M. J. (2019). "सेकेंट-जैसी विधियों के अभिसरण पर". Current Trends in Mathematical Analysis and Its Interdisciplinary Applications (in English): 141–183. doi:10.1007/978-3-030-15242-0_5. ISBN 978-3-030-15241-3.

[2] Sikorski, K. (1982-02-01). "द्विभाजन इष्टतम है". Numerische Mathematik (in English). 40 (1): 111–117. doi:10.1007/BF01459080. ISSN 0945-3245. S2CID 119952605.

[:0-3] 3.0 ^3.1 ^3.2 ^3.3 ^3.4 ^3.5 ^3.6 Oliveira, I. F. D.; Takahashi, R. H. C. (2020-12-06). "मिनमैक्स इष्टतमता को संरक्षित करते हुए द्विभाजन विधि औसत प्रदर्शन का संवर्द्धन". ACM Transactions on Mathematical Software. 47 (1): 5:1–5:24. doi:10.1145/3423597. ISSN 0098-3500.

[1]

[2]

[3]

[lower-alpha 1]

Anonymous

Search

आईटीपी विधि

Namespaces

More

Page actions

Contents

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