व्युत्क्रम द्विघात प्रक्षेप

संख्यात्मक विश्लेषण में, व्युत्क्रम द्विघात प्रक्षेप एक मूल-खोज एल्गोरिथ्म है, जिसका अर्थ है कि यह f(x) = 0 के रूप के समीकरणों को हल करने के लिए एक एल्गोरिथ्म है। विचार यह है कि अनुमानित करने के लिए बहुपद प्रक्षेप का उपयोग किया जाए एफ का व्युत्क्रम फलन। इस एल्गोरिदम का उपयोग शायद ही कभी किया जाता है, लेकिन यह महत्वपूर्ण है क्योंकि यह लोकप्रिय ब्रेंट विधि का हिस्सा है।

विधि

व्युत्क्रम द्विघात प्रक्षेप एल्गोरिथ्म को पुनरावृत्ति संबंध द्वारा परिभाषित किया गया है

$x_{n+1}={\frac {f_{n-1}f_{n}}{(f_{n-2}-f_{n-1})(f_{n-2}-f_{n})}}x_{n-2}+{\frac {f_{n-2}f_{n}}{(f_{n-1}-f_{n-2})(f_{n-1}-f_{n})}}x_{n-1}$

${}+{\frac {f_{n-2}f_{n-1}}{(f_{n}-f_{n-2})(f_{n}-f_{n-1})}}x_{n},$

जहाँ एफ_k = एफ(एक्स_k). जैसा कि पुनरावृत्ति संबंध से देखा जा सकता है, इस विधि के लिए तीन प्रारंभिक मानों, x की आवश्यकता होती है₀, एक्स₁ और एक्स₂.

विधि की व्याख्या

हम तीन पूर्ववर्ती पुनरावृत्तों, x का उपयोग करते हैं_n−2, एक्स_n−1 और एक्स_n, उनके फ़ंक्शन मानों के साथ, एफ_n−2, एफ_n−1 और एफ_n. एफ पैदावार के व्युत्क्रम पर द्विघात प्रक्षेप करने के लिए लैग्रेंज बहुपद को लागू करना

$f^{-1}(y)={\frac {(y-f_{n-1})(y-f_{n})}{(f_{n-2}-f_{n-1})(f_{n-2}-f_{n})}}x_{n-2}+{\frac {(y-f_{n-2})(y-f_{n})}{(f_{n-1}-f_{n-2})(f_{n-1}-f_{n})}}x_{n-1}$

${}+{\frac {(y-f_{n-2})(y-f_{n-1})}{(f_{n}-f_{n-2})(f_{n}-f_{n-1})}}x_{n}.$

हम f के मूल की तलाश कर रहे हैं, इसलिए हम उपरोक्त समीकरण में y = f(x) = 0 प्रतिस्थापित करते हैं और इसका परिणाम उपरोक्त पुनरावर्तन सूत्र में होता है।

व्यवहार

स्पर्शोन्मुख व्यवहार बहुत अच्छा है: आम तौर पर, x पुनरावृत्त होता है_n एक बार जब वे करीब आ जाते हैं तो तेजी से जड़ की ओर एकत्रित हो जाते हैं। हालाँकि, यदि प्रारंभिक मान वास्तविक रूट के करीब नहीं हैं, तो प्रदर्शन अक्सर काफी खराब होता है। उदाहरण के लिए, यदि किसी भी संयोग से दो फ़ंक्शन मान f_n−2, एफ_n−1 और एफ_n संयोग, एल्गोरिथ्म पूरी तरह से विफल रहता है। इस प्रकार, व्युत्क्रम द्विघात प्रक्षेप का उपयोग शायद ही कभी स्टैंड-अलोन एल्गोरिदम के रूप में किया जाता है।

इस अभिसरण का क्रम लगभग 1.84 है जैसा कि सेकेंट विधि विश्लेषण द्वारा सिद्ध किया जा सकता है।

अन्य रूट-खोज विधियों के साथ तुलना

जैसा कि परिचय में बताया गया है, ब्रेंट की विधि में व्युत्क्रम द्विघात प्रक्षेप का उपयोग किया जाता है।

व्युत्क्रम द्विघात प्रक्षेप भी कुछ अन्य मूल-खोज विधियों से निकटता से संबंधित है। द्विघात प्रक्षेप के स्थान पर रैखिक प्रक्षेप का उपयोग करने से छेदक विधि प्राप्त होती है। एफ के व्युत्क्रम के बजाय एफ को इंटरपोल करने से मुलर की विधि मिलती है।

यह भी देखें

• क्रमिक परवलयिक प्रक्षेप एक संबंधित विधि है जो जड़ों के बजाय एक्स्ट्रेमा को खोजने के लिए परवलय का उपयोग करती है।

संदर्भ

• James F. Epperson, An introduction to numerical methods and analysis, pages 182-185, Wiley-Interscience, 2007. ISBN 978-0-470-04963-1