रिचर्डसन एक्सट्रपलेशन

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

संख्यात्मक विश्लेषण में, रिचर्डसन एक्सट्रपलेशन एक श्रृंखला त्वरण विधि है जिसका उपयोग कुछ मूल्य के अनुमानों के अनुक्रम के अभिसरण की दर में सुधार करने के लिए किया जाता है। $A^{\ast }=\lim _{h\to 0}A(h)$. संक्षेप में, का मूल्य दिया गया है $A(h)$ के कई मानों के लिए $h$, हम अनुमान लगा सकते हैं $A^{\ast }$ अनुमानों का विस्तार करके $h=0$. इसका नाम लुईस फ्राई रिचर्डसन के नाम पर रखा गया है, जिन्होंने 20वीं सदी की शुरुआत में इस तकनीक की शुरुआत की थी। हालाँकि यह विचार क्रिस्टियान ह्यूजेन्स को Pi|π की गणना में पहले से ही ज्ञात था। गैरेट बिरखॉफ़ और जियान-कार्लो रोटा के शब्दों में, व्यावहारिक गणनाओं के लिए इसकी उपयोगिता को शायद ही कम करके आंका जा सकता है। रिचर्डसन एक्सट्रपलेशन के व्यावहारिक अनुप्रयोगों में रोमबर्ग एकीकरण शामिल है, जो ट्रेपेज़ॉइड नियम पर रिचर्डसन एक्सट्रपलेशन को लागू करता है, और सामान्य अंतर समीकरणों को हल करने के लिए बुलिर्श-स्टोअर एल्गोरिदम।

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

संकेतन

होने देना$A_{0}(h)$का एक अनुमान हो$A^{*}$(सटीक मान) जो फॉर्म के अनुमान त्रुटि सूत्र के साथ सकारात्मक चरण आकार एच पर निर्भर करता है

$A^{*}=A_{0}(h)+a_{0}h^{k_{0}}+a_{1}h^{k_{1}}+a_{2}h^{k_{2}}+\cdots$

जहां $a_{i}$ अज्ञात स्थिरांक हैं और $k_{i}$ ऐसे ज्ञात स्थिरांक हैं $h^{k_{i}}>h^{k_{i+1}}$. आगे, $O(h^{k_{i}})$ की काट-छाँट त्रुटि को दर्शाता है $A_{i}(h)$ सन्निकटन ऐसा कि $A^{*}=A_{i}(h)+O(h^{k_{i}}).$ इसी प्रकार, में $A^{*}=A_{i}(h)+O(h^{k_{i}}),$ सन्निकटन $A_{i}(h)$ एक कहा जाता है $O(h^{k_{i}})$ सन्निकटन.

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

$${\begin{aligned}A^{*}&=A_{0}(h)+a_{0}h^{k_{0}}+a_{1}h^{k_{1}}+a_{2}h^{k_{2}}+\cdots \\A^{*}&=A_{0}(h)+a_{0}h^{k_{0}}+O(h^{k_{1}})\\A^{*}&=A_{0}(h)+O(h^{k_{0}})\end{aligned}}$$

उद्देश्य

रिचर्डसन एक्सट्रपलेशन एक ऐसी प्रक्रिया है जो बेहतर अनुमान लगाती है$A^{*}$त्रुटि सूत्र को बदलकर $A^{*}=A_{0}(h)+O(h^{k_{0}})$ को $A^{*}=A_{1}(h)+O(h^{k_{1}}).$ इसलिए, प्रतिस्थापित करके $A_{0}(h)$ साथ $A_{1}(h)$ से ट्रंकेशन त्रुटि कम हो गई है $O(h^{k_{0}})$ को

$O(h^{k_{1}})$ समान चरण आकार के लिए $h$. जिसमें सामान्य पैटर्न होता है $A_{i}(h)$ से अधिक सटीक अनुमान है $A_{j}(h)$ कब $i>j$. इस प्रक्रिया से, हमने बेहतर अनुमान प्राप्त कर लिया है$A^{*}$त्रुटि में सबसे बड़े पद को घटाकर जो था $O(h^{k_{0}})$. बेहतर अनुमान प्राप्त करने के लिए अधिक त्रुटि शब्दों को हटाने के लिए इस प्रक्रिया को दोहराया जा सकता है।

प्रक्रिया

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

$${\begin{aligned}A^{*}&=A_{0}(h)+a_{0}h^{k_{0}}+a_{1}h^{k_{1}}+a_{2}h^{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)\end{aligned}}$$

से हमारे सन्निकटन में सुधार करने के लिए $O(h^{k_{0}})$ को $O(h^{k_{1}})$ पहले त्रुटि पद को हटाकर, हम दूसरे समीकरण (2) को इससे गुणा करते हैं$t^{k_{0}}$और हमें देने के लिए पहले समीकरण (1) को घटाएं

$$(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_{1}h^{k_{1}}{\bigg )}+{\bigg (}t^{k_{0}}a_{2}{\bigg (}{\frac {h}{t}}{\bigg )}^{k_{2}}-a_{2}h^{k_{2}}{\bigg )}+O(h^{k_{3}}).$$

यह गुणा-घटाव इसलिए किया गया क्योंकि ${\textstyle {\big [}t^{k_{0}}A_{0}\left({\frac {h}{t}}\right)-A_{0}(h){\big ]}}$ एक $O(h^{k_{1}})$ का सन्निकटन $(t^{k_{0}}-1)A^{*}$. हम अपने मौजूदा फॉर्मूले को हल कर सकते हैं $A^{*}$ दे देना

$$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_{1}h^{k_{1}}{\bigg )}}{t^{k_{0}}-1}}+{\frac {{\bigg (}t^{k_{0}}a_{2}{\bigg (}{\frac {h}{t}}{\bigg )}^{k_{2}}-a_{2}h^{k_{2}}{\bigg )}}{t^{k_{0}}-1}}+O(h^{k_{3}})$$

जिसे इस प्रकार लिखा जा सकता है $A^{*}=A_{1}(h)+O(h^{k_{1}})$ व्यवस्थित करके

$A_{1}(h)={\frac {t^{k_{0}}A_{0}\left({\frac {h}{t}}\right)-A_{0}(h)}{t^{k_{0}}-1}}.$

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

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

$A_{i+1}(h)={\frac {t^{k_{i}}A_{i}\left({\frac {h}{t}}\right)-A_{i}(h)}{t^{k_{i}}-1}}$

कहाँ $k_{i+1}$ संतुष्ट

$A^{*}=A_{i+1}(h)+O(h^{k_{i+1}})$.

गुण

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

इसके अतिरिक्त, अनुमान लगाने के लिए सामान्य सूत्र का उपयोग किया जा सकता है$k_{0}$(ट्रंकेशन त्रुटि का अग्रणी क्रम चरण आकार व्यवहार) जब न तो इसका मूल्य और न ही$A^{*}$एक प्राथमिकता के रूप में जाना जाता है। ऐसी तकनीक अभिसरण की अज्ञात दर को मापने के लिए उपयोगी हो सकती है। का अनुमान दिया गया है$A^{*}$तीन अलग-अलग चरण आकारों से$h$,$h/t$, और$h/s$, सटीक संबंध

$$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}})$$

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

$$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}}$$

जिसका अनुमान लगाने के लिए संख्यात्मक रूप से हल किया जा सकता है$k_{0}$कुछ मनमाने विकल्पों के लिए$h$,$s$, और$t$.

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

मान लीजिए कि हम अनुमान लगाना चाहते हैं $A^{*}$, और हमारे पास एक विधि है $A(h)$ यह एक छोटे पैरामीटर पर निर्भर करता है $h$ इस तरह से कि

$$A(h)=A^{\ast }+Ch^{n}+O(h^{n+1}).$$

आइए एक नए फ़ंक्शन को परिभाषित करें

$$R(h,t):={\frac {t^{n}A(h/t)-A(h)}{t^{n}-1}}$$

कहाँ $h$ और ${\frac {h}{t}}$ दो अलग-अलग चरण आकार हैं।

तब

$$R(h,t)={\frac {t^{n}(A^{*}+C\left({\frac {h}{t}}\right)^{n}+O(h^{n+1}))-(A^{*}+Ch^{n}+O(h^{n+1}))}{t^{n}-1}}=A^{*}+O(h^{n+1}).$$

$R(h,t)$ इसे ए(एच) का रिचर्डसन एक्सट्रपलेशन कहा जाता है, और इसमें उच्च-क्रम त्रुटि अनुमान होता है $O(h^{n+1})$ की तुलना में $A(h)$.

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

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

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

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

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

यह भी देखें

• ऐटकेन की डेल्टा-वर्ग प्रक्रिया
• केंको ताकेबे
• रिचर्डसन पुनरावृत्ति

संदर्भ

• 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).

बाहरी संबंध

• Fundamental Methods of Numerical Extrapolation With Applications, mit.edu
• Richardson-Extrapolation
• Richardson extrapolation on a website of Robert Israel (University of British Columbia)
• Matlab code for generic Richardson extrapolation.
• Julia code for generic Richardson extrapolation.