आईटीपी विधि: Difference between revisions

Latest revision as of 11:21, 7 August 2023

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

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

[छंटाई चरण] अनुमानक को केंद्र की ओर घुमाएं: $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}}$

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

मान लीजिए कि बहुपद $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) ^[2])। यह द्विभाजन विधि की तरह न्यूनतम अधिकतम इष्टतम है जब $n_{0}$ , $n_{0}=0$ होना चुना गया है।

औसत प्रदर्शन

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

यह भी देखें

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

संदर्भ

↑ 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.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.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

[3] 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.

[:0-2] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.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]

[lower-alpha 1]

@@ Line 1: / Line 1: @@
-{{Short description|Root-finding algorithm}}
+{{Short description|Root-finding algorithm}}[[संख्यात्मक विश्लेषण]] में, आईटीपी विधि, ''अंतर्वेशन रुंडित और परियोजना'' के लिए संक्षिप्त, पहला [[Index.php?title=मूल-खोज एल्गोरिदम|मूल -खोज एल्गोरिदम]] है <ref>{{Cite journal|last1=Argyros|first1=I. K.|last2=Hernández-Verón|first2=M. A.|last3=Rubio|first3=M. J.|date=2019|title=सेकेंट-जैसी विधियों के अभिसरण पर|url=http://springer.nl.go.kr/chapter/10.1007/978-3-030-15242-0_5|journal=Current Trends in Mathematical Analysis and Its Interdisciplinary Applications|language=en|pages=141–183|doi=10.1007/978-3-030-15242-0_5|isbn=978-3-030-15241-3}}</ref> जो [[द्विभाजन विधि]] के इष्टतम सबसे खराब प्रदर्शन को बनाए रखते हुए सेकेंट विधि के सुपरलीनियर अभिसरण को प्राप्त करता है।।<ref name=":0">{{Cite journal|last1=Oliveira|first1=I. F. D.|last2=Takahashi|first2=R. H. C.|date=2020-12-06|title=मिनमैक्स इष्टतमता को संरक्षित करते हुए द्विभाजन विधि औसत प्रदर्शन का संवर्द्धन|url=https://doi.org/10.1145/3423597|journal=ACM Transactions on Mathematical Software|volume=47|issue=1|pages=5:1–5:24|doi=10.1145/3423597|issn=0098-3500}}</ref> यह किसी भी निरंतर वितरण के अंतर्गत द्विभाजन विधि की तुलना में गारंटीकृत औसत प्रदर्शन वाली पहली विधि भी है।<ref name=":0" />व्यवहार में यह पारंपरिक अंतर्वेशन और हाइब्रिड आधारित रणनीतियों ( ब्रेंट की विधि, रिडर्स विधि, [[Index.php?title=इलिनोइस|इलिनोइस]]) से अधिक अच्छा प्रदर्शन करता है, क्योंकि यह न केवल अच्छे व्यवहार वाले कार्यों पर सुपर-रैखिक रूप से अभिसरण करता है बल्कि खराब व्यवहार वाले कार्यों के अंतर्गत तेजी से प्रदर्शन की गारंटी भी देता है। अंतर्वेशन विफल हो जाते हैं.<ref name=":0" />
-{{more citations needed|date=January 2021}}
-[[संख्यात्मक विश्लेषण]] में, आईटीपी विधि, ''इंटरपोलेट ट्रंकेट एंड प्रोजेक्ट'' के लिए संक्षिप्त, पहला [[जड़-खोज एल्गोरिदम]] है | रूट-फाइंडिंग एल्गोरिदम जो सेकेंट विधि के सुपरलीनियर अभिसरण को प्राप्त करता है<ref>{{Cite journal|last1=Argyros|first1=I. K.|last2=Hernández-Verón|first2=M. A.|last3=Rubio|first3=M. J.|date=2019|title=सेकेंट-जैसी विधियों के अभिसरण पर|url=http://springer.nl.go.kr/chapter/10.1007/978-3-030-15242-0_5|journal=Current Trends in Mathematical Analysis and Its Interdisciplinary Applications|language=en|pages=141–183|doi=10.1007/978-3-030-15242-0_5|isbn=978-3-030-15241-3}}</ref> इष्टतम को बरकरार रखते हुए<ref>{{Cite journal|last=Sikorski|first=K.|date=1982-02-01|title=द्विभाजन इष्टतम है|url=https://doi.org/10.1007/BF01459080|journal=Numerische Mathematik|language=en|volume=40|issue=1|pages=111–117|doi=10.1007/BF01459080|s2cid=119952605|issn=0945-3245}}</ref> सबसे अच्छा, सबसे खराब और औसत मामला|[[द्विभाजन विधि]] का सबसे खराब प्रदर्शन।<ref name=":0">{{Cite journal|last1=Oliveira|first1=I. F. D.|last2=Takahashi|first2=R. H. C.|date=2020-12-06|title=मिनमैक्स इष्टतमता को संरक्षित करते हुए द्विभाजन विधि औसत प्रदर्शन का संवर्द्धन|url=https://doi.org/10.1145/3423597|journal=ACM Transactions on Mathematical Software|volume=47|issue=1|pages=5:1–5:24|doi=10.1145/3423597|issn=0098-3500}}</ref> यह किसी भी निरंतर वितरण के तहत द्विभाजन विधि की तुलना में गारंटीकृत औसत प्रदर्शन वाली पहली विधि भी है।<ref name=":0" />व्यवहार में यह पारंपरिक इंटरपोलेशन और हाइब्रिड आधारित रणनीतियों (ब्रेंट की विधि | ब्रेंट की विधि, रिडर्स विधि, [[नियम नकली]]) से बेहतर प्रदर्शन करता है, क्योंकि यह न केवल अच्छे व्यवहार वाले कार्यों पर सुपर-रैखिक रूप से अभिसरण करता है बल्कि खराब व्यवहार वाले कार्यों के तहत तेजी से प्रदर्शन की गारंटी भी देता है। प्रक्षेप विफल हो जाते हैं.<ref name=":0" />
+आईटीपी विधि मानक ब्रैकेटिंग रणनीतियों की समान संरचना का पालन करती है जो मूल के स्थान के लिए ऊपरी और निचली सीमाओं पर नज़र रखती है; लेकिन यह उस क्षेत्र पर भी नज़र रखता है जहां सबसे खराब स्थिति वाले प्रदर्शन को ऊपरी सीमा में रखा जाता है। ब्रैकेटिंग रणनीति के रूप में, प्रत्येक पुनरावृत्ति में आईटीपी एक बिंदु पर फलन के मान पर सवाल उठाता है और दो बिंदुओं के बीच के अंतराल के हिस्से को छोड़ देता है जहां फलन मान समान चिह्न साझा करता है। पूछे गए बिंदु की गणना तीन चरणों के साथ की जाती है: यह रेगुला फाल्सी अनुमान को खोजने के लिए प्रक्षेपित करता है, फिर यह अनुमान को उत्तेजित /छोटा कर देता है (इसी तरह)  {{section link|रेगुला फाल्सी के समान | रेगुला फाल्सी में सुधार}}) और फिर विक्षुब्ध अनुमान को द्विभाजन मध्यबिंदु के पड़ोस में एक अंतराल पर प्रक्षेपित करता है। न्यूनतम अधिकतम इष्टतमता की गारंटी के लिए प्रत्येक पुनरावृत्ति में द्विभाजन बिंदु के आसपास के पड़ोस की गणना की जाती है (प्रमेय 2.1) <ref name=":0" />। विधि तीन अतिप्राचल पर निर्भर करती है <math>\kappa_1\in (0,\infty), \kappa_2 \in \left[1,1+\phi\right) </math> और <math>n_0\in[0,\infty) </math> जहाँ <math>\phi </math> स्वर्णिम अनुपात है <math>\tfrac{1}{2}(1+\sqrt{5}) </math>: पहले दो खंडन के आकार को नियंत्रित करते हैं और तीसरा एक सुस्त चर है जो प्रक्षेपण चरण के लिए अंतराल के आकार को नियंत्रित करता है।{{efn|1=For a more in-depth discussion of the hyper-parameters, see the documentation for [https://docs.rs/kurbo/0.8.1/kurbo/common/fn.solve_itp.html ITP in the kurbo library].}}
+{| class="wikitable"
-आईटीपी विधि मानक ब्रैकेटिंग रणनीतियों की समान संरचना का पालन करती है जो रूट के स्थान के लिए ऊपरी और निचली सीमाओं का ट्रैक रखती है; लेकिन यह उस क्षेत्र पर भी नज़र रखता है जहां सबसे खराब स्थिति वाले प्रदर्शन को ऊपरी सीमा में रखा जाता है। ब्रैकेटिंग रणनीति के रूप में, प्रत्येक पुनरावृत्ति में आईटीपी एक बिंदु पर फ़ंक्शन के मान पर सवाल उठाता है और दो बिंदुओं के बीच के अंतराल के हिस्से को छोड़ देता है जहां फ़ंक्शन मान समान चिह्न साझा करता है। पूछे गए बिंदु की गणना तीन चरणों के साथ की जाती है: यह रेगुला फाल्सी अनुमान को खोजने के लिए प्रक्षेपित करता है, फिर यह अनुमान को परेशान/छोटा कर देता है (इसी तरह)  {{section link|Regula falsi|Improvements in ''regula falsi''}}) और फिर विक्षुब्ध अनुमान को द्विभाजन मध्यबिंदु के पड़ोस में एक अंतराल पर प्रक्षेपित करता है। न्यूनतम अधिकतम इष्टतमता की गारंटी के लिए प्रत्येक पुनरावृत्ति में द्विभाजन बिंदु के आसपास के पड़ोस की गणना की जाती है (प्रमेय 2.1) <ref name=":0" />). विधि तीन हाइपर-पैरामीटर पर निर्भर करती है <math>\kappa_1\in (0,\infty), \kappa_2 \in \left[1,1+\phi\right) </math> और <math>n_0\in[0,\infty) </math> कहाँ <math>\phi </math> स्वर्णिम अनुपात है <math>\tfrac{1}{2}(1+\sqrt{5}) </math>: पहले दो ट्रंकेशन के आकार को नियंत्रित करते हैं और तीसरा एक सुस्त चर है जो प्रक्षेपण चरण के लिए अंतराल के आकार को नियंत्रित करता है।{{efn|1=For a more in-depth discussion of the hyper-parameters, see the documentation for [https://docs.rs/kurbo/0.8.1/kurbo/common/fn.solve_itp.html ITP in the kurbo library].}}
+|
+|
+|}
 == मूल खोजने की समस्या ==
-एक सतत कार्य दिया गया <math>f</math> से परिभाषित <math>[a,b]</math> को <math>\mathbb{R}</math> ऐसा है कि <math>f(a)f(b)\leq 0</math>, जहां एक क्वेरी की कीमत पर कोई भी इसके मूल्यों तक पहुंच सकता है <math>f(x)</math> किसी भी दिए पर <math>x</math>. और, एक पूर्व-निर्दिष्ट लक्ष्य परिशुद्धता दी गई है <math>\epsilon>0</math>, एक रूट-फाइंडिंग एल्गोरिदम को यथासंभव कम से कम प्रश्नों के साथ निम्नलिखित समस्या को हल करने के लिए डिज़ाइन किया गया है:<blockquote>
+एक सतत कार्य <math>f</math> दिया गया <math>[a,b]</math> को <math>\mathbb{R}</math> से परिभाषित  ऐसा है कि <math>f(a)f(b)\leq 0</math>, जहां एक सवाल की कीमत पर किसी भी दिए गए<math>x</math> पर कोई भी <math>f(x)</math> के मान तक पहुंच सकता है। और, एक पूर्व-निर्दिष्ट लक्ष्य परिशुद्धता <math>\epsilon>0</math> दी गई है , एक मूल खोज एल्गोरिदम को यथासंभव कम से कम प्रश्नों के साथ निम्नलिखित समस्या को हल करने के लिए डिज़ाइन किया गया है:<blockquote>
-समस्या परिभाषा: खोजें <math>\hat{x}</math> ऐसा है कि  <math>|\hat{x}-x^*|\leq \epsilon</math>, कहाँ <math>x^*</math> संतुष्ट <math>f(x^*) = 0</math>.</blockquote>
+समस्या परिभाषा: <math>\hat{x}</math> को खोजें ऐसा है कि  <math>|\hat{x}-x^*|\leq \epsilon</math>, जहाँ <math>x^*</math> <math>f(x^*) = 0</math> को संतुष्ट करता है</blockquote>
-यह समस्या संख्यात्मक विश्लेषण, [[कंप्यूटर विज्ञान]] और [[ अभियांत्रिकी ]] में बहुत आम है; और, रूट-फाइंडिंग एल्गोरिदम इसे हल करने के लिए मानक दृष्टिकोण हैं। अक्सर, रूट-खोज प्रक्रिया को बड़े संदर्भ में अधिक जटिल मूल एल्गोरिदम द्वारा बुलाया जाता है, और इस कारण से रूट समस्याओं को कुशलतापूर्वक हल करना अत्यधिक महत्वपूर्ण है क्योंकि जब बड़े संदर्भ को ध्यान में रखा जाता है तो एक अकुशल दृष्टिकोण उच्च कम्प्यूटेशनल लागत पर आ सकता है। खाता। आईटीपी विधि एक साथ इंटरपोलेशन गारंटी के साथ-साथ द्विभाजन विधि की मिनमैक्स इष्टतम गारंटी का उपयोग करके ऐसा करने का प्रयास करती है जो अधिकतम में समाप्त होती है  <math>n_{1/2}\equiv\lceil\log_2((b_0-a_0)/2\epsilon)\rceil </math> एक अंतराल पर आरंभ होने पर पुनरावृत्तियाँ <math>[a_0,b_0] </math>.
+यह समस्या संख्यात्मक विश्लेषण, [[कंप्यूटर विज्ञान]] और [[ अभियांत्रिकी ]] में बहुत सामान्य है; और, मूल खोज एल्गोरिदम इसे हल करने के लिए मानक दृष्टिकोण हैं। प्रायः, मूल-खोज प्रक्रिया को बड़े संदर्भ में अधिक जटिल मूल एल्गोरिदम द्वारा बुलाया जाता है, और इस कारण से मूल समस्याओं को कुशलतापूर्वक हल करना अत्यधिक महत्वपूर्ण है क्योंकि जब बड़े संदर्भ को ध्यान में रखा जाता है तो एक अकुशल दृष्टिकोण उच्च कम्प्यूटेशनल लागत पर आ सकता है।आईटीपी विधि एक साथ अंतर्वेशन गारंटी के साथ-साथ द्विभाजन विधि की मिनमैक्स इष्टतम गारंटी का उपयोग करके ऐसा करने का प्रयास करती है जो अधिकतम <math>n_{1/2}\equiv\lceil\log_2((b_0-a_0)/2\epsilon)\rceil </math>में समाप्त होती है एक अंतराल<math>[a_0,b_0] </math> पर आरंभ होने पर पुनरावृत्तियाँ।
 == विधि ==
-दिया गया <math>\kappa_1\in (0,\infty), \kappa_2 \in \left[1,1+\phi\right) </math>, <math>n_{1/2} \equiv \lceil\log_2((b_0-a_0)/2\epsilon)\rceil </math> और <math>n_0\in[0,\infty) </math> कहाँ <math>\phi </math> स्वर्णिम अनुपात है <math>\tfrac{1}{2}(1+\sqrt{5}) </math>, प्रत्येक पुनरावृत्ति में <math>j = 0,1,2\dots </math> आईटीपी विधि बिंदु की गणना करती है <math>x_{\text{ITP}} </math> निम्नलिखित तीन चरण:
+दिया गया <math>\kappa_1\in (0,\infty), \kappa_2 \in \left[1,1+\phi\right) </math>, <math>n_{1/2} \equiv \lceil\log_2((b_0-a_0)/2\epsilon)\rceil </math> और <math>n_0\in[0,\infty) </math> जहाँ <math>\phi </math> स्वर्णिम अनुपात है <math>\tfrac{1}{2}(1+\sqrt{5}) </math>, प्रत्येक पुनरावृत्ति में <math>j = 0,1,2\dots </math> आईटीपी विधि बिंदु <math>x_{\text{ITP}} </math>की गणना निम्नलिखित तीन चरण में करती है:
 [[File:ITPstep1.png|thumb|आईटीपी पद्धति का चरण 1.]]
 [[File:ITPstep2.png|thumb|आईटीपी पद्धति का चरण 2.]]
 [[File:ITPstep3.png|thumb|आईटीपी पद्धति का चरण 3.]]
-[[File:ITPall steps.png|thumb|तीनों चरण मिलकर ITP विधि बनाते हैं। मोटी नीली रेखा विधि के प्रक्षेपित-काटे-प्रक्षेप का प्रतिनिधित्व करती है।]]# [इंटरपोलेशन चरण] द्विभाजन और रेगुला फाल्सी बिंदुओं की गणना करें:   <math>x_{1/2} \equiv \frac{a+b}{2} </math> और   <math>x_f \equiv \frac{bf(a)-af(b)}{f(a)-f(b)} </math> ;
+[[File:ITPall steps.png|thumb|तीनों चरण मिलकर ITP विधि बनाते हैं। मोटी नीली रेखा विधि के प्रक्षेपित-काटे-प्रक्षेप का प्रतिनिधित्व करती है।]][अंतर्वेशनचरण] द्विभाजन और रेगुला फाल्सी बिंदुओं की गणना करें:   <math>x_{1/2} \equiv \frac{a+b}{2} </math> और   <math>x_f \equiv \frac{bf(a)-af(b)}{f(a)-f(b)} </math> ;
-# [छंटाई चरण] अनुमानक को केंद्र की ओर घुमाएं:  <math>x_t \equiv x_f+\sigma \delta </math> कहाँ  <math>\sigma \equiv \text{sign}(x_{1/2}-x_f) </math> और <math>\delta \equiv \min\{\kappa_1|b-a|^{\kappa_2},|x_{1/2}-x_f|\} </math> ;
+# [छंटाई चरण] अनुमानक को केंद्र की ओर घुमाएं:  <math>x_t \equiv x_f+\sigma \delta </math> जहाँ <math>\sigma \equiv \text{sign}(x_{1/2}-x_f) </math> और <math>\delta \equiv \min\{\kappa_1|b-a|^{\kappa_2},|x_{1/2}-x_f|\} </math> ;
-# [प्रक्षेपण चरण] अनुमानक को न्यूनतम अंतराल पर प्रोजेक्ट करें: <math>x_{\text{ITP}} \equiv x_{1/2} -\sigma \rho_k  </math> कहाँ <math>\rho_k \equiv \min\left\{\epsilon 2^{n_{1/2}+n_0-j} - \frac{b-a}{2},|x_t-x_{1/2}|\right\} </math>.
+# [प्रक्षेपण चरण] अनुमानक को न्यूनतम अंतराल : <math>x_{\text{ITP}} \equiv x_{1/2} -\sigma \rho_k  </math> पर प्रोजेक्ट करें जहाँ <math>\rho_k \equiv \min\left\{\epsilon 2^{n_{1/2}+n_0-j} - \frac{b-a}{2},|x_t-x_{1/2}|\right\} </math>.
-फ़ंक्शन का मान <math>f(x_{\text{ITP}}) </math> इस बिंदु पर पूछताछ की जाती है, और फिर प्रत्येक छोर पर विपरीत चिह्न के फ़ंक्शन मानों के साथ उप-अंतराल रखकर मूल को ब्रैकेट करने के लिए अंतराल को कम किया जाता है।
+इस बिंदु पर फलन के मान  <math>f(x_{\text{ITP}}) </math> की पूछताछ की जाती है, और फिर प्रत्येक छोर पर विपरीत चिह्न के फलन मानों के साथ उप-अंतराल रखकर मूल को ब्रैकेट करने के लिए अंतराल को कम किया जाता है।
 === एल्गोरिथ्म ===
-निम्नलिखित एल्गोरिदम (छद्म कोड में लिखा गया) प्रारंभिक मान मानता है <math>y_a </math> और <math>y_b </math> दिया जाता है और संतुष्ट किया जाता है <math>y_a<0 <y_b </math> कहाँ <math>y_a\equiv f(a) </math> और <math>y_b\equiv f(b) </math>; और, यह एक अनुमान लौटाता है <math>\hat{x} </math> जो संतुष्ट करता है <math>|\hat{x} - x^*|\leq \epsilon </math> अधिक से अधिक में <math>n_{1/2}+n_0 </math> कार्य मूल्यांकन.
+निम्नलिखित एल्गोरिदम (छद्म कोड में लिखा गया)मानता है की  <math>y_a </math> और <math>y_b </math>का प्रारंभिक मान दिया गया है और  <math>y_a<0 <y_b </math> जहाँ <math>y_a\equiv f(a) </math> और <math>y_b\equiv f(b) </math>; को संतुष्ट करता है और, यह एक अनुमान <math>\hat{x} </math> को लौटाता है  जो  <math>|\hat{x} - x^*|\leq \epsilon </math> को अधिक से अधिक  <math>n_{1/2}+n_0 </math> कार्य मूल्यांकन में संतुष्ट करता है।
   इनपुट: <math>a, b, \epsilon, \kappa_1, \kappa_2, n_0, f </math>पूर्वप्रसंस्करण:<math>n_{1/2} = \lceil \log_2\tfrac{b-a}{2\epsilon}\rceil </math>,<math>n_{\max} = n_{1/2}+n_0 </math>, और<math>j = 0 </math>;
       जबकि ( <math>b-a>2\epsilon </math>)
@@ Line 33: / Line 34: @@
           प्रक्षेप:<math>x_f = \tfrac{y_ba-y_a b}{y_b-y_a} </math>;
           काट-छाँट:<math>\sigma = \text{sign}(x_{1/2}-x_f) </math>;
-              अगर<math>\delta\leq|x_{1/2}-x_f| </math>तब<math>x_t = x_f+\sigma \delta </math>,
+              यदि<math>\delta\leq|x_{1/2}-x_f| </math>तब<math>x_t = x_f+\sigma \delta </math>,
               अन्य<math>x_t = x_{1/2} </math>;
           प्रक्षेपण:
-              अगर<math>|x_t-x_{1/2}|\leq r </math>तब<math>x_{\text{ITP}} = x_t </math>,
+              यदि<math>|x_t-x_{1/2}|\leq r </math>तब<math>x_{\text{ITP}} = x_t </math>,
               अन्य<math>x_{\text{ITP}} = x_{1/2}-\sigma r </math>;
           अद्यतन अंतराल:<math>y_{\text{ITP}} = f(x_{\text{ITP}}) </math>;
-              अगर<math>y_{\text{ITP}}>0 </math>तब<math>b = x_{ITP} </math>और<math>y_b = y_{\text{ITP}} </math>,
+              यदि<math>y_{\text{ITP}}>0 </math>तब<math>b = x_{ITP} </math>और<math>y_b = y_{\text{ITP}} </math>,
               Elseif<math>y_{\text{ITP}}<0 </math>तब<math>a = x_{\text{ITP}} </math>और<math>y_a = y_{\text{ITP}} </math>,
               अन्य<math>a = x_{\text{ITP}} </math>और<math>b = x_{\text{ITP}} </math>;<math>j = j+1 </math>;
@@ Line 45: / Line 46: @@
 == उदाहरण: एक बहुपद का मूल ज्ञात करना ==
-मान लीजिए कि बहुपद का मूल ज्ञात करने के लिए ITP विधि का उपयोग किया जाता है <math> f(x) = x^3 - x - 2 \,.</math> का उपयोग करते हुए <math> \epsilon = 0.0005, \kappa_1 = 0.1, \kappa_2 = 2</math> और <math> n_0 = 1</math> हम पाते हैं कि:
+मान लीजिए कि बहुपद<math> f(x) = x^3 - x - 2 \,.</math>का मूल ज्ञात करने के लिए ITP विधि का उपयोग किया जाता है। <math> \epsilon = 0.0005, \kappa_1 = 0.1, \kappa_2 = 2</math> और <math> n_0 = 1</math> का उपयोग करते हुए हम पाते हैं कि:
 {| class="wikitable"
-!Iteration
+!पुनरावर्तन
 !<math>a_n</math>
 !<math>b_n</math>
@@ Line 88: / Line 89: @@
 | colspan="2" |&larr; Stopping Criteria Satisfied
 |}
-इस उदाहरण से तुलना की जा सकती है {{section link|Bisection method|Example: Finding the root of a polynomial}}. न्यूनतम अधिकतम गारंटी पर बिना किसी लागत के रूट का अधिक सटीक अनुमान प्राप्त करने के लिए आईटीपी विधि को द्विभाजन की तुलना में आधे से भी कम पुनरावृत्तियों की आवश्यकता होती है। अन्य विधियाँ भी अभिसरण की समान गति प्राप्त कर सकती हैं (जैसे कि रिडर्स, ब्रेंट इत्यादि) लेकिन आईटीपी विधि द्वारा दी गई न्यूनतम अधिकतम गारंटी के बिना।
+इस उदाहरण की तुलना {{section link|द्विभाजन विधि|उदाहरण: एक बहुपद का मूल ज्ञात करना}} से जा सकती है।न्यूनतम अधिकतम गारंटी पर बिना किसी लागत के मूल का अधिक सटीक अनुमान प्राप्त करने के लिए आईटीपी विधि को द्विभाजन की तुलना में आधे से भी कम पुनरावृत्तियों की आवश्यकता होती है। अन्य विधियाँ भी अभिसरण की समान गति प्राप्त कर सकती हैं (जैसे कि रिडर्स, ब्रेंट इत्यादि) लेकिन आईटीपी विधि द्वारा दी गई न्यूनतम अधिकतम गारंटी के बिना।
 == विश्लेषण ==
-आईटीपी विधि का मुख्य लाभ यह है कि इसमें द्विभाजन विधि की तुलना में अधिक पुनरावृत्तियों की आवश्यकता नहीं होने की गारंटी है <math> n_0 = 0</math>. और इसलिए इंटरपोलेशन विफल होने पर भी इसका औसत प्रदर्शन द्विभाजन विधि से बेहतर होने की गारंटी है। इसके अलावा, यदि इंटरपोलेशन विफल नहीं होते हैं (सुचारू कार्य), तो इंटरपोलेशन आधारित तरीकों के रूप में अभिसरण के उच्च क्रम का आनंद लेने की गारंटी है।
+आईटीपी विधि का मुख्य लाभ यह है कि इसमें द्विभाजन विधि की तुलना में अधिक पुनरावृत्तियों की आवश्यकता नहीं होने की गारंटी है <math> n_0 = 0</math>। और इसलिए अंतर्वेशन विफल होने पर भी इसका औसत प्रदर्शन द्विभाजन विधि से अधिक अच्छा होने की गारंटी है। इसके अतिरिक्त, यदि अंतर्वेशन विफल नहीं होते हैं (सुचारू कार्य), तो अंतर्वेशन आधारित तरीकों के रूप में अभिसरण के उच्च क्रम का आनंद लेने की गारंटी है।
 === सबसे खराब स्थिति प्रदर्शन ===
-क्योंकि आईटीपी विधि अनुमानक को न्यूनतम अधिकतम अंतराल पर प्रोजेक्ट करती है <math> n_0</math> सुस्त, इसकी अधिक से अधिक आवश्यकता होगी <math> n_{1/2}+n_0</math> पुनरावृत्तियाँ (प्रमेय 2.1) <ref name=":0" />). यह द्विभाजन विधि की तरह न्यूनतम अधिकतम इष्टतम है जब <math> n_0</math> होना चुना गया है <math> n_0 = 0</math>.
+क्योंकि आईटीपी विधि अनुमानक को न्यूनतम अधिकतम अंतराल पर प्रोजेक्ट करती है <math> n_0</math> ढील के साथ, इसकी अधिक से अधिक <math> n_{1/2}+n_0</math> पुनरावृत्तियो की आवश्यकता होगी (प्रमेय 2.1) <ref name=":0" />)। यह द्विभाजन विधि की तरह न्यूनतम अधिकतम इष्टतम है जब <math> n_0</math> ,<math> n_0 = 0</math>होना चुना गया है।
 === औसत प्रदर्शन ===
-क्योंकि इससे ज्यादा नहीं लगता <math> n_{1/2}+n_0</math> पुनरावृत्तियों में, किसी भी वितरण के लिए पुनरावृत्तियों की औसत संख्या हमेशा द्विभाजन विधि की तुलना में कम होगी <math> n_0 = 0</math> (परिणाम 2.2) <ref name=":0" />).
+क्योंकि  <math> n_{1/2}+n_0</math> इससे ज्यादा पुनरावृत्तिया नहीं लेती , किसी भी वितरण के लिए पुनरावृत्तियों की औसत संख्या हमेशा द्विभाजन विधि की तुलना में कम होगी जब <math> n_0 = 0</math> होगा (परिणाम 2.2) <ref name=":0" />).
-=== स्पर्शोन्मुख प्रदर्शन ===
+=== उपगामी प्रदर्शन ===
-यदि फ़ंक्शन <math> f(x)</math> दो बार भिन्न और मूल है <math> x^*</math> सरल है, तो आईटीपी विधि द्वारा उत्पादित अंतराल अभिसरण के क्रम के साथ 0 में परिवर्तित हो जाते हैं <math> \sqrt{\kappa_2}</math> अगर <math> n_0 \neq 0</math> या अगर <math> n_0 = 0</math> और <math> (b-a)/\epsilon</math> पद के साथ 2 की घात नहीं है <math> \tfrac{\epsilon 2^{n_{1/2}}}{b-a}</math> शून्य के बहुत करीब नहीं (प्रमेय 2.3)। <ref name=":0" />).
+यदि फलन<math> f(x)</math> दो बार भिन्न और मूल है <math> x^*</math> सरल है, तो आईटीपी विधि द्वारा उत्पादित अंतराल अभिसरण के क्रम <math> \sqrt{\kappa_2}</math> के साथ 0 में परिवर्तित हो जाते हैं  यदि <math> n_0 \neq 0</math> या यदि <math> n_0 = 0</math> और <math> (b-a)/\epsilon</math> ,<math> \tfrac{\epsilon 2^{n_{1/2}}}{b-a}</math>पद के साथ 2 की घात नहीं है  शून्य के बहुत करीब नहीं है(प्रमेय 2.3)। <ref name=":0" />).
 == यह भी देखें ==
@@ Line 114: / Line 115: @@
 == संदर्भ ==
-<!--- See http://en.wikipedia.org/wiki/Wikipedia:Footnotes on how to create references using<ref></ref> tags, these references will then appear here automatically -->
 {{Reflist}}
@@ Line 121: / Line 122: @@
 * [https://link.growkudos.com/1iwxps83474 An Improved Bisection Method], by [https://info.growkudos.com/ Kudos]
-[[Category: जड़-खोज एल्गोरिदम]]
-[[Category: Machine Translated Page]]
+[[Category:CS1 English-language sources (en)]]
 [[Category:Created On 14/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:जड़-खोज एल्गोरिदम]]

Anonymous

Search

आईटीपी विधि: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 11:21, 7 August 2023

Contents

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