रिचर्डसन एक्सट्रपलेशन: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Sequence acceleration method in numerical analysis}} File:Richardson extra 2d.gif|thumb|दो आयामों में रिचर्डसन ए...")
 
No edit summary
 
(5 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|Sequence acceleration method in numerical analysis}}
{{Short description|Sequence acceleration method in numerical analysis}}
[[File:Richardson extra 2d.gif|thumb|दो आयामों में रिचर्डसन एक्सट्रपलेशन विधि का एक उदाहरण।]][[संख्यात्मक विश्लेषण]] में, रिचर्डसन एक्सट्रपलेशन एक श्रृंखला त्वरण विधि है जिसका उपयोग कुछ मूल्य के अनुमानों के [[अनुक्रम]] के [[अभिसरण की दर]] में सुधार करने के लिए किया जाता है। <math>A^\ast = \lim_{h\to 0} A(h)</math>. संक्षेप में, का मूल्य दिया गया है <math>A(h)</math> के कई मानों के लिए <math>h</math>, हम अनुमान लगा सकते हैं <math>A^\ast</math> अनुमानों का विस्तार करके <math>h=0</math>. इसका नाम [[लुईस फ्राई रिचर्डसन]] के नाम पर रखा गया है, जिन्होंने 20वीं सदी की शुरुआत में इस तकनीक की शुरुआत की थी।<ref>{{cite journal
[[File:Richardson extra 2d.gif|thumb|दो आयामों में रिचर्डसन एक्सट्रपलेशन विधि का एक उदाहरण।]]
 
 
संख्यात्मक विश्लेषण में, रिचर्डसन एक्सट्रपलेशन एक अनुक्रम त्वरण विधि है जिसका उपयोग कुछ मूल्य <math>A^\ast = \lim_{h\to 0} A(h)</math> के अनुमानों के अनुक्रम के अभिसरण की दर में सुधार करने के लिए किया जाता है। संक्षेप में, <math>h</math> के कई मानों के लिए <math>A(h)</math> का मान दिया गया है, हम अनुमानों को <math>h=0</math> पर एक्सट्रपलेशन करके <math>A^\ast</math>का अनुमान लगा सकते हैं। इसका नाम लुईस फ्राई रिचर्डसन के नाम पर रखा गया है, जिन्होंने 20वीं सदी की प्रारंभ में इस तकनीक की प्रारंभ की थी<ref>{{cite journal
  | last=Richardson | first=L. F. | author-link=Lewis Fry Richardson
  | last=Richardson | first=L. F. | author-link=Lewis Fry Richardson
  | title=The approximate arithmetical solution by finite differences of physical problems including differential equations, with an application to the stresses in a masonry dam
  | title=The approximate arithmetical solution by finite differences of physical problems including differential equations, with an application to the stresses in a masonry dam
Line 17: Line 20:
  | first2=J. A.
  | first2=J. A.
| doi-access=free
| doi-access=free
  }}</ref> हालाँकि यह विचार [[क्रिस्टियान ह्यूजेन्स]] को Pi|π की गणना में पहले से ही ज्ञात था।<ref>{{Citation|last=Brezinski|first=Claude|title=Some pioneers of extrapolation methods|date=2009-11-01|url=https://www.worldscientific.com/doi/10.1142/9789812836267_0001|work=The Birth of Numerical Analysis|pages=1–22|publisher=WORLD SCIENTIFIC|doi=10.1142/9789812836267_0001|isbn=978-981-283-625-0}}</ref> [[ गैरेट बिरखॉफ़ ]] और [[जियान-कार्लो रोटा]] के शब्दों में, व्यावहारिक गणनाओं के लिए इसकी उपयोगिता को शायद ही कम करके आंका जा सकता है।<ref>Page 126 of {{cite book | last=Birkhoff | first=Garrett | author-link=Garrett Birkhoff |author2=Gian-Carlo Rota |author2-link=Gian-Carlo Rota | title=Ordinary differential equations | publisher=John Wiley and sons | year=1978 | edition=3rd | isbn=0-471-07411-X | oclc= 4379402}}</ref> रिचर्डसन एक्सट्रपलेशन के व्यावहारिक अनुप्रयोगों में [[रोमबर्ग एकीकरण]] शामिल है, जो ट्रेपेज़ॉइड नियम पर रिचर्डसन एक्सट्रपलेशन को लागू करता है, और सामान्य अंतर समीकरणों को हल करने के लिए बुलिर्श-स्टोअर एल्गोरिदम।
  }}</ref> चूँकि यह विचार क्रिस्टियान ह्यूजेंस को π की गणना में पहले से ही पता था।<ref>{{Citation|last=Brezinski|first=Claude|title=Some pioneers of extrapolation methods|date=2009-11-01|url=https://www.worldscientific.com/doi/10.1142/9789812836267_0001|work=The Birth of Numerical Analysis|pages=1–22|publisher=WORLD SCIENTIFIC|doi=10.1142/9789812836267_0001|isbn=978-981-283-625-0}}</ref> बिरखॉफ और रोटा के शब्दों में, "व्यावहारिक गणनाओं के लिए इसकी उपयोगिता को संभवतः ही कम करके आंका जा सकता है।"<ref>Page 126 of {{cite book | last=Birkhoff | first=Garrett | author-link=Garrett Birkhoff |author2=Gian-Carlo Rota |author2-link=Gian-Carlo Rota | title=Ordinary differential equations | publisher=John Wiley and sons | year=1978 | edition=3rd | isbn=0-471-07411-X | oclc= 4379402}}</ref>
 
रिचर्डसन एक्सट्रपलेशन के व्यावहारिक अनुप्रयोगों में [[रोमबर्ग एकीकरण]] सम्मिलित है, जो ट्रेपेज़ॉइड नियम पर रिचर्डसन एक्सट्रपलेशन को प्रयुक्त करता है, और सामान्य अंतर समीकरणों को हल करने के लिए बुलिर्श-स्टोअर एल्गोरिदम है।


==सामान्य सूत्र==
==सामान्य सूत्र==


=== संकेतन ===
=== संकेतन ===
होने देना<math>A_0(h)</math>का एक अनुमान हो<math>A^*</math>(सटीक मान) जो फॉर्म के अनुमान त्रुटि सूत्र के साथ सकारात्मक चरण आकार एच पर निर्भर करता है
मान लीजिए कि<math>A_0(h)</math> <math>A^*</math>(स्पष्ट मान) का एक अनुमान है जो प्रपत्र के त्रुटि सूत्र के साथ धनात्मक चरण आकार h पर निर्भर करता है
:<math> A^* = A_0(h)+a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots </math>
:<math> A^* = A_0(h)+a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots </math>
जहां <math>a_i</math> अज्ञात स्थिरांक हैं और <math>k_i</math> ऐसे ज्ञात स्थिरांक हैं <math>h^{k_i}>h^{k_{i+1}}</math>. आगे, <math>O(h^{k_i})</math> की [[काट-छाँट त्रुटि]] को दर्शाता है <math>A_i(h)</math> सन्निकटन ऐसा कि <math>A^*=A_i(h)+O(h^{k_i}).</math> इसी प्रकार, में <math>A^*=A_i(h)+O(h^{k_i}),</math> सन्निकटन <math>A_i(h)</math> एक कहा जाता है <math>O(h^{k_i})</math> सन्निकटन.
जहां <math>a_i</math> अज्ञात स्थिरांक हैं और<math>k_i</math> ज्ञात स्थिरांक हैं जैसे कि <math>h^{k_i}>h^{k_{i+1}}</math> इसके अतिरिक्त <math>O(h^{k_i})</math>,<math>A_i(h)</math> सन्निकटन की काट-छाँट त्रुटि को इस प्रकार दर्शाता है कि <math>A^*=A_i(h)+O(h^{k_i}).</math> इसी प्रकार,<math>A^*=A_i(h)+O(h^{k_i}),</math> में सन्निकटन <math>A_i(h)                                                                                                                                                                                                            
                                                                                                                                                                                                                               
                                                                                                                                                                             
                                                                                                                                                                                                                                     
            </math>} को <math>O(h^{k_i})</math> सन्निकटन कहा जाता है।


ध्यान दें कि [[ बिग ओ अंकन ]] के साथ सरलीकरण करके, निम्नलिखित सूत्र समतुल्य हैं:
ध्यान दें कि [[ बिग ओ अंकन |बिग ओ अंकन]] के साथ सरलीकरण करके, निम्नलिखित सूत्र समतुल्य हैं:


<math display="block"> \begin{align}  
<math display="block"> \begin{align}  
Line 33: Line 42:
A^* &= A_0(h)+O(h^{k_0})  
A^* &= A_0(h)+O(h^{k_0})  
\end{align} </math>
\end{align} </math>
=== उद्देश्य ===
=== उद्देश्य ===
रिचर्डसन एक्सट्रपलेशन एक ऐसी प्रक्रिया है जो बेहतर अनुमान लगाती है<math>A^*</math>त्रुटि सूत्र को बदलकर <math>A^*=A_0(h)+O(h^{k_0})</math> को <math>A^*=A_1(h)+O(h^{k_1}).</math> इसलिए, प्रतिस्थापित करके <math>A_0(h)</math> साथ <math>A_1(h)</math> से ट्रंकेशन त्रुटि कम हो गई है <math>O(h^{k_0}) </math> को
रिचर्डसन एक्सट्रपलेशन एक ऐसी प्रक्रिया है जो त्रुटि सूत्र को <math>A^*=A_0(h)+O(h^{k_0})</math> को <math>A^*=A_1(h)+O(h^{k_1}).</math> में बदलकर <math>A^*</math>का उत्तम अनुमान लगाती है, इसलिए, <math>A_0(h)</math> को <math>A_1(h)</math> से बदलने से ट्रंकेशन त्रुटि<math>O(h^{k_0}) </math> से कम हो गई है <math>O(h^{k_1}) </math> समान चरण आकार <math>O(h^{k_1}) </math> के लिए। सामान्य पैटर्न तब होता है जिसमें <math>A_i(h)</math> , <math>i>j</math> होने पर <math>A_i(h)</math> की तुलना में अधिक स्पष्ट अनुमान होता है। इस प्रक्रिया द्वारा, हमने त्रुटि में सबसे बड़े पद जो कि <math>O(h^{k_0}) </math> था, को घटाकर <math>A^*</math> का उत्तम अनुमान प्राप्त किया है। उत्तम अनुमान प्राप्त करने के लिए अधिक त्रुटि शब्दों को हटाने के लिए इस प्रक्रिया को दोहराया जा सकता है।
<math>O(h^{k_1}) </math> समान चरण आकार के लिए <math>h</math>. जिसमें सामान्य पैटर्न होता है <math>A_i(h)</math> से अधिक सटीक अनुमान है <math>A_j(h)</math> कब <math>i>j</math>. इस प्रक्रिया से, हमने बेहतर अनुमान प्राप्त कर लिया है<math>A^*</math>त्रुटि में सबसे बड़े पद को घटाकर जो था <math>O(h^{k_0}) </math>. बेहतर अनुमान प्राप्त करने के लिए अधिक त्रुटि शब्दों को हटाने के लिए इस प्रक्रिया को दोहराया जा सकता है।


=== प्रक्रिया ===
=== प्रक्रिया ===
चरण आकारों का उपयोग करना<math>h</math>और<math>h / t</math>कुछ स्थिरांक के लिए<math>t</math>, के लिए दो सूत्र<math>A^*</math>हैं:
कुछ स्थिरांक <math>t</math> के लिए चरण आकार <math>h</math> और <math>h / t</math> का उपयोग करते हुए,<math>A^*</math> के लिए दो सूत्र हैं:


<math display="block">\begin{align} A^* &= A_0(h)+ a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + O(h^{k_3}) & (1) \\\\
<math display="block">\begin{align} A^* &= A_0(h)+ a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + O(h^{k_3}) & (1) \\\\
A^* &= A_0\!\left(\frac{h}{t}\right) + a_0\left(\frac{h}{t}\right)^{k_0} + a_1\left(\frac{h}{t}\right)^{k_1} + a_2\left(\frac{h}{t}\right)^{k_2} + O(h^{k_3}) & (2)
A^* &= A_0\!\left(\frac{h}{t}\right) + a_0\left(\frac{h}{t}\right)^{k_0} + a_1\left(\frac{h}{t}\right)^{k_1} + a_2\left(\frac{h}{t}\right)^{k_2} + O(h^{k_3}) & (2)
\end{align}</math>
\end{align}</math>
से हमारे सन्निकटन में सुधार करने के लिए <math>O(h^{k_0})</math> को <math>O(h^{k_1})</math> पहले त्रुटि पद को हटाकर, हम दूसरे समीकरण (2) को इससे गुणा करते हैं<math>t^{k_0}</math>और हमें देने के लिए पहले समीकरण (1) को घटाएं<math display="block"> (t^{k_0}-1)A^* = \bigg[t^{k_0}A_0\left(\frac{h}{t}\right) - A_0(h)\bigg] + \bigg(t^{k_0}a_1\bigg(\frac{h}{t}\bigg)^{k_1}-a_1h^{k_1}\bigg)+ \bigg(t^{k_0}a_2\bigg(\frac{h}{t}\bigg)^{k_2}-a_2h^{k_2}\bigg) + O(h^{k_3}). </math>यह गुणा-घटाव इसलिए किया गया क्योंकि <math display="inline">\big[t^{k_0}A_0\left(\frac{h}{t}\right) - A_0(h)\big]</math> एक <math>O(h^{k_1})</math> का सन्निकटन <math>(t^{k_0}-1)A^*</math>. हम अपने मौजूदा फॉर्मूले को हल कर सकते हैं <math>A^*</math> दे देना<math display="block">A^* = \frac{\bigg[t^{k_0}A_0\left(\frac{h}{t}\right) - A_0(h)\bigg]}{t^{k_0}-1}
पहले त्रुटि पद को हटाकर अपने सन्निकटन को <math>O(h^{k_0})</math> से <math>O(h^{k_1})</math> तक सुधारने के लिए, हम दूसरे समीकरण (2) को <math>t^{k_0}</math> से गुणा करते हैं और पहले समीकरण (1) को घटाकर हमें प्राप्त होता है<math display="block"> (t^{k_0}-1)A^* = \bigg[t^{k_0}A_0\left(\frac{h}{t}\right) - A_0(h)\bigg] + \bigg(t^{k_0}a_1\bigg(\frac{h}{t}\bigg)^{k_1}-a_1h^{k_1}\bigg)+ \bigg(t^{k_0}a_2\bigg(\frac{h}{t}\bigg)^{k_2}-a_2h^{k_2}\bigg) + O(h^{k_3}). </math>यह गुणा और घटाव इसलिए किया गया क्योंकि <math display="inline">\big[t^{k_0}A_0\left(\frac{h}{t}\right) - A_0(h)\big]</math>, <math>O(h^{k_1})</math> का <math>(t^{k_0}-1)A^*</math> सन्निकटन है। हम <math>A^*</math> देने के लिए अपने वर्तमान सूत्र को हल कर सकते हैं<math display="block">A^* = \frac{\bigg[t^{k_0}A_0\left(\frac{h}{t}\right) - A_0(h)\bigg]}{t^{k_0}-1}


+ \frac{\bigg(t^{k_0}a_1\bigg(\frac{h}{t}\bigg)^{k_1}-a_1h^{k_1}\bigg)}{t^{k_0}-1}
+ \frac{\bigg(t^{k_0}a_1\bigg(\frac{h}{t}\bigg)^{k_1}-a_1h^{k_1}\bigg)}{t^{k_0}-1}
Line 51: Line 57:
+\frac{\bigg(t^{k_0}a_2\bigg(\frac{h}{t}\bigg)^{k_2}-a_2h^{k_2}\bigg)}{t^{k_0}-1}
+\frac{\bigg(t^{k_0}a_2\bigg(\frac{h}{t}\bigg)^{k_2}-a_2h^{k_2}\bigg)}{t^{k_0}-1}


+O(h^{k_3}) </math>जिसे इस प्रकार लिखा जा सकता है <math>A^* = A_1(h)+O(h^{k_1})</math> व्यवस्थित करके
+O(h^{k_3}) </math>जिसे सेटिंग करके<math>A^* = A_1(h)+O(h^{k_1})</math>लिखा जा सकता है


:<math>A_1(h) = \frac{t^{k_0}A_0\left(\frac{h}{t}\right) - A_0(h)}{t^{k_0}-1} .</math>
:<math>A_1(h) = \frac{t^{k_0}A_0\left(\frac{h}{t}\right) - A_0(h)}{t^{k_0}-1} .</math>
Line 59: Line 65:
एक सामान्य पुनरावृत्ति संबंध को सन्निकटन के लिए परिभाषित किया जा सकता है
एक सामान्य पुनरावृत्ति संबंध को सन्निकटन के लिए परिभाषित किया जा सकता है
:<math> A_{i+1}(h) = \frac{t^{k_i}A_i\left(\frac{h}{t}\right) - A_i(h)}{t^{k_i}-1} </math>
:<math> A_{i+1}(h) = \frac{t^{k_i}A_i\left(\frac{h}{t}\right) - A_i(h)}{t^{k_i}-1} </math>
कहाँ <math>k_{i+1}</math> संतुष्ट
जहाँ <math>k_{i+1}</math> संतुष्ट
:<math> A^* = A_{i+1}(h) + O(h^{k_{i+1}}) </math>.
:<math> A^* = A_{i+1}(h) + O(h^{k_{i+1}}) </math>.


Line 65: Line 71:
रिचर्डसन एक्सट्रपलेशन को एक रैखिक [[अनुक्रम परिवर्तन]] के रूप में माना जा सकता है।
रिचर्डसन एक्सट्रपलेशन को एक रैखिक [[अनुक्रम परिवर्तन]] के रूप में माना जा सकता है।


इसके अतिरिक्त, अनुमान लगाने के लिए सामान्य सूत्र का उपयोग किया जा सकता है<math>k_0</math>(ट्रंकेशन त्रुटि का अग्रणी क्रम चरण आकार व्यवहार) जब न तो इसका मूल्य और न ही<math>A^*</math>एक प्राथमिकता के रूप में जाना जाता है। ऐसी तकनीक अभिसरण की अज्ञात दर को मापने के लिए उपयोगी हो सकती है। का अनुमान दिया गया है<math>A^*</math>तीन अलग-अलग चरण आकारों से<math>h</math>,<math>h / t</math>, और<math>h / s</math>, सटीक संबंध<math display="block">A^*=\frac{t^{k_0}A_i\left(\frac{h}{t}\right) - A_i(h)}{t^{k_0}-1} + O(h^{k_1}) = \frac{s^{k_0}A_i\left(\frac{h}{s}\right) - A_i(h)}{s^{k_0}-1} + O(h^{k_1})</math>एक अनुमानित संबंध उत्पन्न करता है (कृपया ध्यान दें कि यहां संकेतन थोड़ा भ्रम पैदा कर सकता है, उपरोक्त समीकरण में दिखाई देने वाले दो ओ केवल अग्रणी क्रम चरण आकार के व्यवहार को इंगित करते हैं लेकिन उनके स्पष्ट रूप अलग-अलग हैं और इसलिए दो ओ शब्दों को रद्द करना लगभग मान्य है)<math display="block">A_i\left(\frac{h}{t}\right) + \frac{A_i\left(\frac{h}{t}\right) - A_i(h)}{t^{k_0}-1} \approx A_i\left(\frac{h}{s}\right) +\frac{A_i\left(\frac{h}{s}\right) - A_i(h)}{s^{k_0}-1}</math>जिसका अनुमान लगाने के लिए संख्यात्मक रूप से हल किया जा सकता है<math>k_0</math>कुछ मनमाने विकल्पों के लिए<math>h</math>,<math>s</math>, और<math>t</math>.
इसके अतिरिक्त, सामान्य सूत्र का उपयोग <math>k_0</math> (ट्रंकेशन त्रुटि का अग्रणी क्रम चरण आकार व्यवहार) का अनुमान लगाने के लिए किया जा सकता है, जब न तो इसका मान और न ही <math>A^*</math> को प्राथमिकता से जाना जाता है। ऐसी तकनीक अभिसरण की अज्ञात दर को मापने के लिए उपयोगी हो सकती है। तीन अलग-अलग चरण आकारों <math>h</math>,<math>h / t</math>, से <math>A^*</math> का अनुमान दिया गया है, और स्पष्ट संबंध <math>h / s</math> दिया गया है<math display="block">A^*=\frac{t^{k_0}A_i\left(\frac{h}{t}\right) - A_i(h)}{t^{k_0}-1} + O(h^{k_1}) = \frac{s^{k_0}A_i\left(\frac{h}{s}\right) - A_i(h)}{s^{k_0}-1} + O(h^{k_1})</math>एक अनुमानित संबंध उत्पन्न करता है (कृपया ध्यान दें कि यहां संकेतन थोड़ा अस्पष्ट उत्पन्न कर सकता है, उपरोक्त समीकरण में दिखाई देने वाले दो ओ केवल अग्रणी क्रम चरण आकार के व्यवहार को निरुपित करते हैं किंतु उनके स्पष्ट रूप अलग-अलग हैं और इसलिए दो ओ शब्दों को समाप्त करना लगभग मान्य है)<math display="block">A_i\left(\frac{h}{t}\right) + \frac{A_i\left(\frac{h}{t}\right) - A_i(h)}{t^{k_0}-1} \approx A_i\left(\frac{h}{s}\right) +\frac{A_i\left(\frac{h}{s}\right) - A_i(h)}{s^{k_0}-1}</math>जिसे <math>h</math>,<math>s</math>, और <math>t</math> के कुछ इच्छित विकल्पों के लिए <math>k_0</math> का अनुमान लगाने के लिए संख्यात्मक रूप से हल किया जा सकता है।


==रिचर्डसन एक्सट्रपलेशन का उदाहरण==
==रिचर्डसन एक्सट्रपलेशन का उदाहरण==
मान लीजिए कि हम अनुमान लगाना चाहते हैं <math>A^*</math>, और हमारे पास एक विधि है <math>A(h)</math> यह एक छोटे पैरामीटर पर निर्भर करता है <math>h</math> इस तरह से कि
मान लीजिए कि हम <math>A^*</math> का अनुमान लगाना चाहते हैं, और हमारे पास एक विधि <math>A(h)</math>) है जो एक छोटे पैरामीटर <math>h</math> पर इस तरह निर्भर करती है कि
<math display="block">A(h) = A^\ast + C h^n + O(h^{n+1}).</math>
<math display="block">A(h) = A^\ast + C h^n + O(h^{n+1}).</math>
आइए एक नए फ़ंक्शन को परिभाषित करें<math display="block"> R(h,t) := \frac{ t^n A(h/t) - A(h)}{t^n-1} </math>कहाँ <math>h</math> और <math>\frac{h}{t}</math> दो अलग-अलग चरण आकार हैं।
आइए एक नए फलन को परिभाषित करें<math display="block"> R(h,t) := \frac{ t^n A(h/t) - A(h)}{t^n-1} </math>जहाँ <math>h</math> और <math>\frac{h}{t}</math> दो अलग-अलग चरण आकार हैं।


तब<math display="block"> R(h, t) = \frac{ t^n ( A^* + C \left(\frac{h}{t}\right)^n + O(h^{n+1}) ) - ( A^* + C h^n + O(h^{n+1}) ) }{ t^n - 1} = A^* + O(h^{n+1}). </math><math> R(h,t) </math> इसे ए(एच) का रिचर्डसन [[एक्सट्रपलेशन]] कहा जाता है, और इसमें उच्च-क्रम त्रुटि अनुमान होता है <math> O(h^{n+1}) </math> की तुलना में <math> A(h) </math>.
तब<math display="block"> R(h, t) = \frac{ t^n ( A^* + C \left(\frac{h}{t}\right)^n + O(h^{n+1}) ) - ( A^* + C h^n + O(h^{n+1}) ) }{ t^n - 1} = A^* + O(h^{n+1}). </math><math> R(h,t) </math> को <math> A(h) </math> का रिचर्डसन एक्सट्रपलेशन कहा जाता है, और इसमें <math> A(h) </math> की तुलना में उच्च-क्रम त्रुटि अनुमान <math> O(h^{n+1}) </math> है।


बहुत बार, बहुत छोटे h' के साथ A(h') के बजाय R(h) का उपयोग करके दी गई सटीकता प्राप्त करना बहुत आसान होता है। जहां A(h') सीमित परिशुद्धता (गोल त्रुटियां) और/या आवश्यक [[कम्प्यूटेशनल लागत]] में वृद्धि के कारण समस्याएं पैदा कर सकता है (नीचे उदाहरण देखें)।
बहुत बार, बहुत छोटे h' के साथ A(h') के अतिरिक्त R(h) का उपयोग करके दी गई स्पष्टता प्राप्त करना बहुत आसान होता है। जहां A(h') सीमित परिशुद्धता (गोल त्रुटियों) और/या आवश्यक गणनाओं की बढ़ती संख्या के कारण समस्याएं उत्पत्ति कर सकता है (नीचे उदाहरण देखें)।


==रिचर्डसन एक्सट्रपलेशन के लिए उदाहरण छद्मकोड कोड==
==रिचर्डसन एक्सट्रपलेशन के लिए उदाहरण छद्मकोड कोड==


MATLAB शैली में निम्नलिखित छद्म कोड ODE को हल करने में मदद करने के लिए रिचर्डसन एक्सट्रपलेशन को प्रदर्शित करता है <math>y'(t) = -y^2</math>, <math>y(0) = 1</math> ट्रेपेज़ॉइडल विधि के साथ. इस उदाहरण में हमने चरण का आकार आधा कर दिया है <math>h</math> प्रत्येक पुनरावृत्ति और इसलिए ऊपर की चर्चा में हमारे पास वह होगा <math>t = 2</math>. ट्रैपेज़ॉइडल विधि की त्रुटि को विषम शक्तियों के रूप में व्यक्त किया जा सकता है ताकि कई चरणों में त्रुटि को सम शक्तियों में व्यक्त किया जा सके; यह हमें उत्थान की ओर ले जाता है <math>t</math> दूसरी शक्ति के लिए और की शक्तियाँ लेने के लिए <math>4 = 2^2 = t^2</math> छद्म कोड में. हम का मूल्य ज्ञात करना चाहते हैं <math>y(5)</math>, जिसका सटीक समाधान है <math>\frac{1}{5 + 1} = \frac{1}{6} = 0.1666...</math> चूँकि ODE का सटीक समाधान है <math>y(t) = \frac{1}{1 + t}</math>. यह छद्मकोड मानता है कि एक फ़ंक्शन कहा जाता है <code>Trapezoidal(f, tStart, tEnd, h, y0)</code> मौजूद है जो गणना करने का प्रयास करता है <code>y(tEnd)</code> फ़ंक्शन पर ट्रैपेज़ॉइडल विधि निष्पादित करके <code>f</code>, शुरुआती बिंदु के साथ <code>y0</code> और <code>tStart</code> और चरण का आकार <code>h</code>.
मैटलैब शैली में निम्नलिखित छद्मकोड ट्रैपेज़ॉइडल विधि के साथ ओडीई <math>y'(t) = -y^2</math>, <math>y(0) = 1</math>को हल करने में सहायता करने के लिए रिचर्डसन एक्सट्रपलेशन को प्रदर्शित करता है। इस उदाहरण में हम प्रत्येक पुनरावृत्ति में चरण आकार को आधा कर देते हैं और इसलिए ऊपर की चर्चा में हमारे पास वह <math>t = 2</math> होगा। ट्रैपेज़ॉइडल विधि की त्रुटि को विषम शक्तियों के संदर्भ में व्यक्त किया जा सकता है जिससे कई चरणों में त्रुटि को सम शक्तियों में व्यक्त किया जा सके; यह हमें <math>t</math> को दूसरी घात तक बढ़ाने और छद्मकोड में <math>4 = 2^2 = t^2</math> की घातें लेने की ओर ले जाता है। हम <math>y(5)</math> का मान ज्ञात करना चाहते हैं, जिसका स्पष्ट समाधान<math>\frac{1}{5 + 1} = \frac{1}{6} = 0.1666...</math> है... क्योंकि ODE का स्पष्ट समाधान <math>y(t) = \frac{1}{1 + t}</math> है। यह छद्म कोड मानता है कि <code>Trapezoidal(f, tStart, tEnd, h, y0</code>नामक एक फलन उपस्थित है जो प्रारंभिक बिंदु<code>y0</code>और <code>tStart</code> और चरण आकार एच के साथ फलन <code>f</code>पर ट्रैपेज़ॉयडल विधि निष्पादित करके <code>y(tEnd)</code> की गणना करने का प्रयास करता है।


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


<syntaxhighlight lang="matlab">
<syntaxhighlight lang="matlab">
Line 141: Line 147:
*ऐटकेन की डेल्टा-वर्ग प्रक्रिया
*ऐटकेन की डेल्टा-वर्ग प्रक्रिया
* [[ केंको ताकेबे ]]
* [[ केंको ताकेबे ]]
* [[रिचर्डसन पुनरावृत्ति]]
* [[रिचर्डसन पुनरावृत्ति|रिचर्डसन इटेरशन]]  


==संदर्भ==
==संदर्भ==
Line 155: Line 161:
* [https://www.mathworks.com/matlabcentral/fileexchange/24388-richardson-extrapolation Matlab code] for generic Richardson extrapolation.
* [https://www.mathworks.com/matlabcentral/fileexchange/24388-richardson-extrapolation Matlab code] for generic Richardson extrapolation.
* [https://github.com/JuliaMath/Richardson.jl Julia code] for generic Richardson extrapolation.
* [https://github.com/JuliaMath/Richardson.jl Julia code] for generic Richardson extrapolation.
[[Category: संख्यात्मक विश्लेषण]] [[Category: एक्सट्रपलेशन]] [[Category: उदाहरण MATLAB/ऑक्टेव कोड वाले लेख]]


[[Category: Machine Translated Page]]
[[Category:Created On 23/07/2023]]
[[Category:Created On 23/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:उदाहरण MATLAB/ऑक्टेव कोड वाले लेख]]
[[Category:एक्सट्रपलेशन]]
[[Category:संख्यात्मक विश्लेषण]]

Latest revision as of 16:23, 1 August 2023

दो आयामों में रिचर्डसन एक्सट्रपलेशन विधि का एक उदाहरण।


संख्यात्मक विश्लेषण में, रिचर्डसन एक्सट्रपलेशन एक अनुक्रम त्वरण विधि है जिसका उपयोग कुछ मूल्य के अनुमानों के अनुक्रम के अभिसरण की दर में सुधार करने के लिए किया जाता है। संक्षेप में, के कई मानों के लिए का मान दिया गया है, हम अनुमानों को पर एक्सट्रपलेशन करके का अनुमान लगा सकते हैं। इसका नाम लुईस फ्राई रिचर्डसन के नाम पर रखा गया है, जिन्होंने 20वीं सदी की प्रारंभ में इस तकनीक की प्रारंभ की थी[1][2] चूँकि यह विचार क्रिस्टियान ह्यूजेंस को π की गणना में पहले से ही पता था।[3] बिरखॉफ और रोटा के शब्दों में, "व्यावहारिक गणनाओं के लिए इसकी उपयोगिता को संभवतः ही कम करके आंका जा सकता है।"[4]

रिचर्डसन एक्सट्रपलेशन के व्यावहारिक अनुप्रयोगों में रोमबर्ग एकीकरण सम्मिलित है, जो ट्रेपेज़ॉइड नियम पर रिचर्डसन एक्सट्रपलेशन को प्रयुक्त करता है, और सामान्य अंतर समीकरणों को हल करने के लिए बुलिर्श-स्टोअर एल्गोरिदम है।

सामान्य सूत्र

संकेतन

मान लीजिए कि (स्पष्ट मान) का एक अनुमान है जो प्रपत्र के त्रुटि सूत्र के साथ धनात्मक चरण आकार h पर निर्भर करता है

जहां अज्ञात स्थिरांक हैं और ज्ञात स्थिरांक हैं जैसे कि इसके अतिरिक्त , सन्निकटन की काट-छाँट त्रुटि को इस प्रकार दर्शाता है कि इसी प्रकार, में सन्निकटन } को सन्निकटन कहा जाता है।

ध्यान दें कि बिग ओ अंकन के साथ सरलीकरण करके, निम्नलिखित सूत्र समतुल्य हैं:

उद्देश्य

रिचर्डसन एक्सट्रपलेशन एक ऐसी प्रक्रिया है जो त्रुटि सूत्र को को में बदलकर का उत्तम अनुमान लगाती है, इसलिए, को से बदलने से ट्रंकेशन त्रुटि से कम हो गई है समान चरण आकार के लिए। सामान्य पैटर्न तब होता है जिसमें , होने पर की तुलना में अधिक स्पष्ट अनुमान होता है। इस प्रक्रिया द्वारा, हमने त्रुटि में सबसे बड़े पद जो कि था, को घटाकर का उत्तम अनुमान प्राप्त किया है। उत्तम अनुमान प्राप्त करने के लिए अधिक त्रुटि शब्दों को हटाने के लिए इस प्रक्रिया को दोहराया जा सकता है।

प्रक्रिया

कुछ स्थिरांक के लिए चरण आकार और का उपयोग करते हुए, के लिए दो सूत्र हैं:

पहले त्रुटि पद को हटाकर अपने सन्निकटन को से तक सुधारने के लिए, हम दूसरे समीकरण (2) को से गुणा करते हैं और पहले समीकरण (1) को घटाकर हमें प्राप्त होता है
यह गुणा और घटाव इसलिए किया गया क्योंकि , का सन्निकटन है। हम देने के लिए अपने वर्तमान सूत्र को हल कर सकते हैं
जिसे सेटिंग करकेलिखा जा सकता है


पुनरावृत्ति संबंध

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

जहाँ संतुष्ट

.

गुण

रिचर्डसन एक्सट्रपलेशन को एक रैखिक अनुक्रम परिवर्तन के रूप में माना जा सकता है।

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

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

रिचर्डसन एक्सट्रपलेशन का उदाहरण

मान लीजिए कि हम का अनुमान लगाना चाहते हैं, और हमारे पास एक विधि ) है जो एक छोटे पैरामीटर पर इस तरह निर्भर करती है कि

आइए एक नए फलन को परिभाषित करें
जहाँ और दो अलग-अलग चरण आकार हैं।

तब

को का रिचर्डसन एक्सट्रपलेशन कहा जाता है, और इसमें की तुलना में उच्च-क्रम त्रुटि अनुमान है।

बहुत बार, बहुत छोटे h' के साथ A(h') के अतिरिक्त R(h) का उपयोग करके दी गई स्पष्टता प्राप्त करना बहुत आसान होता है। जहां A(h') सीमित परिशुद्धता (गोल त्रुटियों) और/या आवश्यक गणनाओं की बढ़ती संख्या के कारण समस्याएं उत्पत्ति कर सकता है (नीचे उदाहरण देखें)।

रिचर्डसन एक्सट्रपलेशन के लिए उदाहरण छद्मकोड कोड

मैटलैब शैली में निम्नलिखित छद्मकोड ट्रैपेज़ॉइडल विधि के साथ ओडीई , को हल करने में सहायता करने के लिए रिचर्डसन एक्सट्रपलेशन को प्रदर्शित करता है। इस उदाहरण में हम प्रत्येक पुनरावृत्ति में चरण आकार को आधा कर देते हैं और इसलिए ऊपर की चर्चा में हमारे पास वह होगा। ट्रैपेज़ॉइडल विधि की त्रुटि को विषम शक्तियों के संदर्भ में व्यक्त किया जा सकता है जिससे कई चरणों में त्रुटि को सम शक्तियों में व्यक्त किया जा सके; यह हमें को दूसरी घात तक बढ़ाने और छद्मकोड में की घातें लेने की ओर ले जाता है। हम का मान ज्ञात करना चाहते हैं, जिसका स्पष्ट समाधान है... क्योंकि ODE का स्पष्ट समाधान है। यह छद्म कोड मानता है कि Trapezoidal(f, tStart, tEnd, h, y0नामक एक फलन उपस्थित है जो प्रारंभिक बिंदुy0और tStart और चरण आकार एच के साथ फलन fपर ट्रैपेज़ॉयडल विधि निष्पादित करके y(tEnd) की गणना करने का प्रयास करता है।

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

tStart = 0          % Starting time
tEnd = 5            % Ending time
f = -y^2            % The derivative of y, so y' = f(t, y(t)) = -y^2
                    % The solution to this ODE is y = 1/(1 + t)
y0 = 1              % The initial position (i.e. y0 = y(tStart) = y(0) = 1)
tolerance = 10^-11  % 10 digit accuracy is desired

maxRows = 20                % Don't allow the iteration to continue indefinitely
initialH = tStart - tEnd    % Pick an initial step size
haveWeFoundSolution = false % Were we able to find the solution to within the desired tolerance? not yet.

h = initialH

% Create a 2D matrix of size maxRows by maxRows to hold the Richardson extrapolates
% Note that this will be a lower triangular matrix and that at most two rows are actually
% needed at any time in the computation.
A = zeroMatrix(maxRows, maxRows)

%Compute the top left element of the matrix. The first row of this (lower triangular) matrix has now been filled.
A(1, 1) = Trapezoidal(f, tStart, tEnd, h, y0)

% Each row of the matrix requires one call to Trapezoidal
% This loops starts by filling the second row of the matrix, since the first row was computed above
for i = 1 : maxRows - 1 % Starting at i = 1, iterate at most maxRows - 1 times
    h = h/2             % Halve the previous value of h since this is the start of a new row.
    
    % Starting filling row i+1 from the left by calling the Trapezoidal function with this new smaller step size
    A(i + 1, 1) = Trapezoidal(f, tStart, tEnd, h, y0)
    
    for j = 1 : i     % Go across this current (i+1)-th row until the diagonal is reached
        % To compute A(i + 1, j + 1), which is the next Richardson extrapolate, 
        % use the most recently computed value (i.e. A(i + 1, j)) and the value from the
        % row above it (i.e. A(i, j)).
     
        A(i + 1, j + 1) = ((4^j).*A(i + 1, j) - A(i, j))/(4^j - 1);
    end
    
    % After leaving the above inner loop, the diagonal element of row i + 1 has been computed
    % This diagonal element is the latest Richardson extrapolate to be computed.
    % The difference between this extrapolate and the last extrapolate of row i is a good
    % indication of the error.
    if (absoluteValue(A(i + 1, i + 1) - A(i, i)) < tolerance)  % If the result is within tolerance
        print("y = ", A(i + 1, i + 1))                         % Display the result of the Richardson extrapolation
        haveWeFoundSolution = true
        break                                                  % Done, so leave the loop
    end
end

if (haveWeFoundSolution == false)   % If we were not able to find a solution to within the desired tolerance
    print("Warning: Not able to find solution to within the desired tolerance of ", tolerance);
    print("The last computed extrapolate was ", A(maxRows, maxRows))
end


यह भी देखें

संदर्भ

  1. Richardson, L. F. (1911). "The approximate arithmetical solution by finite differences of physical problems including differential equations, with an application to the stresses in a masonry dam". Philosophical Transactions of the Royal Society A. 210 (459–470): 307–357. doi:10.1098/rsta.1911.0009.
  2. Richardson, L. F.; Gaunt, J. A. (1927). "The deferred approach to the limit". Philosophical Transactions of the Royal Society A. 226 (636–646): 299–349. doi:10.1098/rsta.1927.0008.
  3. Brezinski, Claude (2009-11-01), "Some pioneers of extrapolation methods", The Birth of Numerical Analysis, WORLD SCIENTIFIC, pp. 1–22, doi:10.1142/9789812836267_0001, ISBN 978-981-283-625-0
  4. Page 126 of Birkhoff, Garrett; Gian-Carlo Rota (1978). Ordinary differential equations (3rd ed.). John Wiley and sons. ISBN 0-471-07411-X. OCLC 4379402.
  • Extrapolation Methods. Theory and Practice by C. Brezinski and M. Redivo Zaglia, North-Holland, 1991.
  • Ivan Dimov, Zahari Zlatev, Istvan Farago, Agnes Havasi: Richardson Extrapolation: Practical Aspects and Applications, Walter de Gruyter GmbH & Co KG, ISBN 9783110533002 (2017).


बाहरी संबंध