रैखिक मल्टीस्टेप विधि

From Vigyanwiki

संख्यात्मक साधारण अंतर समीकरण के लिए रैखिक बहुपदीय विधियों का उपयोग किया जाता है। वैचारिक रूप से, एक संख्यात्मक विधि एक प्रारंभिक बिंदु से प्रारम्भ होती है और फिर अगले समाधान बिंदु को खोजने के लिए समय में एक छोटा कदम आगे बढ़ाती है। समाधान निकालने के लिए प्रक्रिया बाद के चरणों के साथ जारी रहती है। एकल-चरण विधियाँ (जैसे यूलर की विधि) वर्तमान मूल्य निर्धारित करने के लिए केवल एक पिछले बिंदु और उसके व्युत्पन्न को संदर्भित करती हैं। रंज-कुट्टा जैसी विधियां उच्च क्रम विधि प्राप्त करने के लिए कुछ मध्यवर्ती कदम (उदाहरण के लिए, आधा कदम) लेती हैं, लेकिन फिर दूसरा कदम उठाने से पहले सभी पिछली जानकारी को त्याग देती हैं। बहुपदीय विधियाँ पिछले चरणों की जानकारी को त्यागने के स्थान पर उसे बनाए रखने और उसका उपयोग करके दक्षता प्राप्त करने का प्रयास करती हैं। नतीजतन, बहुपदीय विधियां कई पिछले बिंदुओं और व्युत्पन्न मूल्यों को संदर्भित करती हैं। रैखिक बहुपदीय विधियों की स्तिथि में, पिछले बिंदुओं और व्युत्पन्न मूल्यों के एक रैखिक संयोजन का उपयोग किया जाता है।

परिभाषाएँ

साधारण अंतर समीकरणों के लिए संख्यात्मक विधियाँ विधि की प्रारंभिक मान समस्या का अनुमानित समाधान करती हैं

परिणाम के मूल्य के लिए अनुमान अलग-अलग समय पर है:


जहाँ समय चरण है (कभी-कभी इसे कहा जाता है) और एक पूर्णांक है।

बहुपदीय विधियाँ अगले मान की गणना करने के लिए पिछले चरणों की जानकारी का उपयोग करती हैं। विशेष रूप से, एक रैखिक बहुपदीय विधि वांछित वर्तमान चरण के लिए के मान की गणना करने के लिए और के रैखिक संयोजन का उपयोग करती है। इस प्रकार, एक रैखिक बहुपदीय विधि रूप की एक विधि है

के साथ है। गुणांक और विधि निर्धारित करें। विधि का अभिकल्पक लागू करने में आसान विधि प्राप्त करने की इच्छा के विरुद्ध सही समाधान के लिए एक अच्छा अनुमान प्राप्त करने की आवश्यकता को संतुलित करते हुए, गुणांक का चयन करता है। विधि को सरल बनाने के लिए प्रायः कई गुणांक शून्य होते हैं।


कोई भी स्पष्ट और अंतर्निहित तरीकों के बीच अंतर कर सकता है। अगर , तो विधि को स्पष्ट कहा जाता है, क्योंकि सूत्र सीधे गणना कर सकता है। अगर तो विधि को अंतर्निहित कहा जाता है, क्योंकि इसका मान के मूल्य पर निर्भर करता है, और समीकरण को हल किया जाना चाहिए। अंतर्निहित सूत्र को हल करने के लिए प्रायः न्यूटन की विधि जैसी पुनरावृत्तीय विधियों का उपयोग किया जाता है।

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

उदाहरण

उदाहरण के लिए समस्या पर विचार करें

सटीक समाधान है।

वन-चरण यूलर

एक सरल संख्यात्मक विधि यूलर की विधि है:

यूलर की विधि को एक चरण के विकृत स्तिथि के लिए एक स्पष्ट बहुपदीय विधि के रूप में देखा जा सकता है।

समस्या पर चरण आकार के साथ लागू की गई यह विधि निम्नलिखित परिणाम देती है:

दो-चरणीय एडम्स-बैशफोर्थ

यूलर की विधि एक चरणीय विधि है। एक सरल बहुचरणीय विधि दो-चरणीय एडम्स-बैशफोर्थ विधि है


इस विधि के लिए दो मानों और अगले मान की गणना करने की आवश्यकता है, हालाँकि, प्रारंभिक मूल्य समस्या केवल एक मान प्रदान करती है। इस समस्या को हल करने की एक संभावना यूलर की विधि द्वारा गणना किए गए को दूसरे मान के रूप में उपयोग करना है। इस विकल्प के साथ, एडम्स-बैशफोर्थ विधि उत्पन्न होती है (चार अंकों तक पूर्णांकित):

पर सटीक समाधान है, इसलिए दो-चरणीय एडम्स-बैशफोर्थ विधि यूलर की विधि से अधिक सटीक है। यदि चरण का आकार काफी छोटा है तो यह हमेशा स्तिथि होती है।

बहुपदीय विधियों के समूह

रैखिक बहुपदीय विधियों के तीन समूह सामान्यतः उपयोग किए जाते हैं: एडम्स-बैशफोर्थ विधियां, एडम्स-मौल्टन विधियां, और पिछड़े भेदभाव सूत्र (बीडीएफ)।

एडम्स-बैशफोर्थ विधियाँ

एडम्स-बैशफोर्थ विधियाँ स्पष्ट विधियाँ हैं। और गुणांक हैं, जब ऐसे चुना जाता है कि विधियों का क्रम s हो (यह विधियों को विशिष्ट रूप से निर्धारित करता है)।

एडम्स-बैशफोर्थ विधियाँ s = 1, 2, 3, 4, 5 के साथ हैं (हेयरर, नॉरसेट & वानर 1993, §III.1; बुचर 2003, p. 103):

गुणांक निम्नानुसार निर्धारित किया जा सकता है। घात का बहुपद p ज्ञात करने के लिए बहुपद प्रक्षेप का उपयोग करें, यह ऐसा है कि

बहुपद प्रक्षेप उपज के लिए लैग्रेंज बहुपद
बहुपद p स्थानीय रूप से अवकल समीकरण के दाएँ पक्ष का एक अच्छा सन्निकटन इसे हल करना है, इसलिए समीकरण स्थान पर विचार करें। इस समीकरण को बिल्कुल हल किया जा सकता है; समाधान केवल p का अभिन्न अंग है। यह निम्न लेने का सुझाव देता है
एडम्स-बैशफोर्थ विधि तब उत्पन्न होती है जब p के लिए सूत्र प्रतिस्थापित किया जाता है। गुणांक निम्न द्वारा दिए गए हैं
की जगह इसके इंटरपोलेंट पी द्वारा क्रम Hs की त्रुटि उत्पन्न होती है, और यह इस प्रकार है कि एस-चरण एडम्स-बैशफोर्थ विधि में वास्तव में क्रम s (इसरल्स 1996, §2.1) है एडम्स-बैशफोर्थ विधियों को जॉन काउच एडम्स द्वारा फ्रांसिस बैशफोर्थ के कारण केशिका क्रिया प्रतिरूपण के अंतर समीकरण को हल करने के लिए अभिकल्पित किया गया था। बैशफोर्थ (1883) ने उनके सिद्धांत और एडम्स की संख्यात्मक पद्धति (गोल्डस्टाइन 1977) को प्रकाशित किया।

एडम्स-मौलटन विधियाँ

एडम्स-मौलटन विधियाँ एडम्स-बैशफोर्थ विधियों के समान हैं, उनमें और भी हैं। उच्चतम संभव क्रम प्राप्त करने के लिए फिर से b गुणांक को चुना जाता है। हालाँकि, एडम्स-मौल्टन विधियाँ अंतर्निहित विधियाँ हैं। उस प्रतिबंध को हटाकर, एक एस-चरण एडम्स-मौलटन विधि क्रम तक पहुंच सकती है, जबकि एस-चरण एडम्स-बैशफोर्थ विधियों में केवल क्रम एस है।

s = 0, 1, 2, 3, 4 के साथ एडम्स-मौलटन विधियाँ (हेयरर, नॉरसेट & वानर 1993, §III.1; क्वार्टरोनी, सैको & सालेरी 2000) सूचीबद्ध हैं, जहां पहले दो तरीके क्रमशः बैकवर्ड यूलर विधि और ट्रेपेज़ॉइडल नियम (अंतर समीकरण) हैं:

एडम्स-मौलटन पद्धति की व्युत्पत्ति एडम्स-बैशफोर्थ पद्धति के समान है; हालाँकि, प्रक्षेप बहुपद न केवल ऊपर दिए गए बिंदुओं t का उपयोग करता है, बल्कि का भी उपयोग करता है। गुणांक निम्न द्वारा दिए गए हैं

एडम्स-बैशफोर्थ विधियों की तरह, एडम्स-मौल्टन विधियाँ पूरी तरह से जॉन काउच एडम्स के कारण हैं। वन रे मौलटन का नाम इन विधियों के साथ जुड़ गया क्योंकि उन्हें एहसास हुआ कि इन्हें एडम्स-बैशफोर्थ विधियों के साथ मिलकर भविष्यवक्ता-सुधारक विधि जोड़ी के रूप में इस्तेमाल किया जा सकता है। (मौलटन 1926); मिलन (1926) का भी यही विचार था। एडम्स ने अंतर्निहित समीकरण को हल करने के लिए न्यूटन की विधि (हेयरर, नॉरसेट & वानर 1993, §III.1) का उपयोग किया।

पिछड़ा विभेदन सूत्र (पीडीएफ)

बीडीएफ विधियां अंतर्निहित विधियां हैं और अन्य गुणांक इस प्रकार चुने गए कि विधि क्रम s (अधिकतम संभव) प्राप्त कर ले। इन विधियों का प्रयोग विशेष रूप से कठोर समीकरणों के समाधान के लिए किया जाता है।

विश्लेषण

रैखिक बहुपदीय विधियों के विश्लेषण में केंद्रीय अवधारणाएं, और वास्तव में अंतर समीकरणों के लिए किसी भी संख्यात्मक विधि, संख्यात्मक साधारण अंतर समीकरण अभिसरण, क्रम और स्थिरता हैं।

संगति और क्रम

पहला सवाल यह है कि क्या विधि सुसंगत है: अंतर समीकरण है

अंतर समीकरण का एक अच्छा सन्निकटन है ? अधिक सटीक रूप से, एक बहुपदीय विधि सुसंगत होती है यदि स्थानीय खंडन त्रुटि चरण आकार h की तुलना में तीव्रता से शून्य हो जाती है क्योंकि h शून्य पर चला जाता है, जहां स्थानीय खंडन त्रुटि को परिणाम के बीच अंतर के रूप में परिभाषित किया जाता है, यह मानते हुए कि पिछले सभी मान सटीक हैं, और समय पर समीकरण का सटीक समाधान हैं। टेलर श्रृंखला का उपयोग करते हुए एक गणना से पता चलता है कि एक रैखिक बहुपदीय विधि सुसंगत है यदि और केवल यदि
ऊपर उल्लिखित सभी विधियाँ (हेयरर, नॉरसेट & वानर 1993, §III.2) सुसंगत हैं।


यदि विधि सुसंगत है, तो अगला प्रश्न यह है कि संख्यात्मक विधि को परिभाषित करने वाला अंतर समीकरण कितनी अच्छी तरह अंतर समीकरण का अनुमान लगाता है। यदि स्थानीय त्रुटि क्रम की है तो बहुपदीय विधि को क्रम पी कहा जाता है जैसे ही h शून्य पर जाता है। यह विधियों के गुणांकों पर निम्नलिखित परिस्थिति के बराबर है:

एस-चरण एडम्स-बैशफोर्थ विधि में क्रम एस है, जबकि एस-चरण एडम्स-मौल्टन विधि में क्रम (हेयरर, नॉरसेट & वानर 1993, §III.2) है। ये स्थितियां प्रायः विशिष्ट बहुपदों का उपयोग करके तैयार की जाती हैं
इन बहुपदों के संदर्भ में, क्रम p रखने की विधि के लिए उपरोक्त परिस्थिति बन जाती है
विशेष रूप से, विधि सुसंगत है यदि इसमें कम से कम एक क्रम है, जो कि स्तिथि और है।

स्थिरता और अभिसरण

एक-चरणीय विधि का संख्यात्मक समाधान प्रारंभिक स्थिति पर निर्भर करता है, लेकिन एस-चरण विधि का संख्यात्मक समाधान सभी प्रारम्भिक मानों पर निर्भर करता है। इस प्रकार यह रुचि का विषय है कि क्या प्रारंभिक मूल्यों में गड़बड़ी के संबंध में संख्यात्मक समाधान स्थिर है। एक रैखिक बहुपदीय विधि किसी निश्चित समय अंतराल पर एक निश्चित अंतर समीकरण के लिए शून्य-स्थिर है, यदि आकार ε के प्रारम्भिक मूल्यों में गड़बड़ी के कारण उस समय अंतराल पर संख्यात्मक समाधान K के कुछ मूल्य के लिए Kε से अधिक नहीं बदलता है जो चरण आकार h पर निर्भर नहीं करता है। इसे शून्य-स्थिरता कहा जाता है क्योंकि यह अंतर समीकरण (सुली & मेयर्स 2003, p. 332) की स्थिति की जांच करने के लिए पर्याप्त है।

यदि विशिष्ट बहुपद ρ के मूलों का मापांक 1 से कम या उसके बराबर है और मापांक 1 के मूल गुणनफल 1 के हैं, तो हम कहते हैं कि मूल स्थिति संतुष्ट है। एक रैखिक बहुपदीय विधि शून्य-स्थिर है यदि और केवल तभी जब मूल स्थिति (सुली & मेयर्स 2003, p. 335) संतुष्ट हो।

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

इसके अतिरिक्त, यदि विधि अभिसरण है, तो विधि को दृढ़ता से स्थिर कहा जाता है, मापांक 1 का एकमात्र मूल है। यदि यह अभिसरण है और मापांक 1 की सभी घात दोहराई नहीं जाती हैं, लेकिन ऐसे एक से अधिक मूल हैं, तो इसे अपेक्षाकृत स्थिर कहा जाता है। ध्यान दें कि विधि को अभिसरण करने के लिए 1 को मूल होना चाहिए; इस प्रकार अभिसरण विधियाँ हमेशा इन दोनों में से एक होती हैं।

कठोर समीकरणों पर रैखिक बहुपदीय विधियों के प्रदर्शन का आकलन करने के लिए, रैखिक परीक्षण समीकरण y' = λy पर विचार करें। चरण आकार h के साथ इस अंतर समीकरण पर लागू एक बहुपदीय विधि विशेषता बहुपद के साथ एक रैखिक पुनरावृत्ति संबंध उत्पन्न करती है

इस बहुपद को बहुपदीय विधि का स्थिरता बहुपद कहा जाता है। यदि इसकी सभी घात का मापांक एक से कम है तो बहुपदीय विधि का संख्यात्मक समाधान शून्य में परिवर्तित हो जाएगा और बहुपदीय विधि को hλ के उस मान के लिए बिल्कुल स्थिर कहा जाता है। विधि को ए-स्थिर कहा जाता है यदि यह नकारात्मक वास्तविक भाग वाले सभी hλ के लिए बिल्कुल स्थिर है। पूर्ण स्थिरता का क्षेत्र सभी hλ का समुच्चय है जिसके लिए बहुपदीय विधि बिल्कुल स्थिर है (सुली & मेयर्स 2003, pp. 347 & 348)। अधिक विवरण के लिए, कठोर समीकरण बहुपदीय विधियों पर अनुभाग देखें।

उदाहरण

एडम्स-बैशफोर्थ तीन-चरणीय विधि पर विचार करें

इस प्रकार एक अभिलक्षणिक बहुपद है
जिसकी घात हैं, और उपरोक्त स्तिथियाँ पूरी होती हैं। जैसे मापांक 1 का एकमात्र मूल है, विधि अत्यधिक स्थिर है। अन्य विशेषता बहुपद निम्न है

पहली और दूसरी डहलक्विस्ट बाधाएँ

ये दो परिणाम जर्मुंड डहलक्विस्ट द्वारा सिद्ध किए गए थे और अभिसरण के क्रम के लिए और एक रैखिक बहुपदीय विधि के कठोर समीकरण ए-स्थिरता के लिए एक महत्वपूर्ण सीमा का प्रतिनिधित्व करते हैं। पहला डहलक्विस्ट अवरोध डहलक्विस्ट (1956) और दूसरे में डहलक्विस्ट (1963) सिद्ध हुआ था।

पहला डहलक्विस्ट अवरोध

पहला डहलक्विस्ट अवरोध बताता है कि एक शून्य-स्थिर और रैखिक q-चरण बहुपदीय विधि q + 1 से अधिक अभिसरण का क्रम प्राप्त नहीं कर सकती है यदि q विषम है और यदि q सम है तो q + 2 से अधिक है। यदि विधि भी स्पष्ट है, तो यह q से अधिक क्रम प्राप्त नहीं कर सकती है (हेयरर, नॉरसेट & वानर 1993, Thm III.3.5)

दूसरा डहलक्विस्ट अवरोध

दूसरा डहलक्विस्ट अवरोध बताता है कि कोई भी स्पष्ट रैखिक बहुपदीय विधियां कठोर समीकरण ए-स्थिर नहीं हैं। इसके अतिरिक्त, एक (अंतर्निहित) ए-स्थिर रैखिक बहुपदीय विधि का अधिकतम क्रम 2 है। क्रम 2 के ए-स्थिर रैखिक बहुपदीय तरीकों में, समलंबी नियम में सबसे छोटी त्रुटि स्थिरांक है (डहलक्विस्ट 1963, टीएचएम 2.1 and 2.2).

यह भी देखें

संदर्भ

  • Bashforth, Francis (1883), An Attempt to test the Theories of Capillary Action by comparing the theoretical and measured forms of drops of fluid. With an explanation of the method of integration employed in constructing the tables which give the theoretical forms of such drops, by J. C. Adams, Cambridge{{citation}}: CS1 maint: location missing publisher (link).
  • Butcher, John C. (2003), Numerical Methods for Ordinary Differential Equations, John Wiley, ISBN 978-0-471-96758-3.
  • Dahlquist, Germund (1956), "साधारण अंतर समीकरणों के संख्यात्मक एकीकरण में अभिसरण और स्थिरता", Mathematica Scandinavica, 4: 33–53, doi:10.7146/math.scand.a-10454.
  • Dahlquist, Germund (1963), "A special stability problem for linear multistep methods", BIT, 3: 27–43, doi:10.1007/BF01963532, ISSN 0006-3835, S2CID 120241743.
  • Goldstine, Herman H. (1977), A History of Numerical Analysis from the 16th through the 19th Century, New York: Springer-Verlag, ISBN 978-0-387-90277-7.
  • Hairer, Ernst; Nørsett, Syvert Paul; Wanner, Gerhard (1993), Solving ordinary differential equations I: Nonstiff problems (2nd ed.), Berlin: Springer Verlag, ISBN 978-3-540-56670-0.
  • Hairer, Ernst; Wanner, Gerhard (1996), Solving ordinary differential equations II: Stiff and differential-algebraic problems (2nd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-60452-5.
  • Iserles, Arieh (1996), A First Course in the Numerical Analysis of Differential Equations, Cambridge University Press, ISBN 978-0-521-55655-2.
  • Milne, W. E. (1926), "Numerical integration of ordinary differential equations", American Mathematical Monthly, Mathematical Association of America, 33 (9): 455–460, doi:10.2307/2299609, JSTOR 2299609.
  • Moulton, Forest R. (1926), New methods in exterior ballistics, University of Chicago Press.
  • Quarteroni, Alfio; Sacco, Riccardo; Saleri, Fausto (2000), Matematica Numerica, Springer Verlag, ISBN 978-88-470-0077-3.
  • Süli, Endre; Mayers, David (2003), An Introduction to Numerical Analysis, Cambridge University Press, ISBN 0-521-00794-1.


बाहरी संबंध