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

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

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

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

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

संकेतन

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

$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_{0}(h)+O(h^{k_{0}})$ को $A^{*}=A_{1}(h)+O(h^{k_{1}}).$ में बदलकर $A^{*}$का उत्तम अनुमान लगाती है, इसलिए, $A_{0}(h)$ को $A_{1}(h)$ से बदलने से ट्रंकेशन त्रुटि$O(h^{k_{0}})$ से कम हो गई है $O(h^{k_{1}})$ समान चरण आकार $O(h^{k_{1}})$ के लिए। सामान्य पैटर्न तब होता है जिसमें $A_{i}(h)$ , $i>j$ होने पर $A_{i}(h)$ की तुलना में अधिक स्पष्ट अनुमान होता है। इस प्रक्रिया द्वारा, हमने त्रुटि में सबसे बड़े पद जो कि $O(h^{k_{0}})$ था, को घटाकर $A^{*}$ का उत्तम अनुमान प्राप्त किया है। उत्तम अनुमान प्राप्त करने के लिए अधिक त्रुटि शब्दों को हटाने के लिए इस प्रक्रिया को दोहराया जा सकता है।

प्रक्रिया

कुछ स्थिरांक $t$ के लिए चरण आकार $h$ और $h/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^{*}$ को प्राथमिकता से जाना जाता है। ऐसी तकनीक अभिसरण की अज्ञात दर को मापने के लिए उपयोगी हो सकती है। तीन अलग-अलग चरण आकारों $h$,$h/t$, से $A^{*}$ का अनुमान दिया गया है, और स्पष्ट संबंध $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}}$$

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

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

मान लीजिए कि हम $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)$ को $A(h)$ का रिचर्डसन एक्सट्रपलेशन कहा जाता है, और इसमें $A(h)$ की तुलना में उच्च-क्रम त्रुटि अनुमान $O(h^{n+1})$ है।

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

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

मैटलैब शैली में निम्नलिखित छद्मकोड ट्रैपेज़ॉइडल विधि के साथ ओडीई $y'(t)=-y^{2}$, $y(0)=1$को हल करने में सहायता करने के लिए रिचर्डसन एक्सट्रपलेशन को प्रदर्शित करता है। इस उदाहरण में हम प्रत्येक पुनरावृत्ति में चरण आकार को आधा कर देते हैं और इसलिए ऊपर की चर्चा में हमारे पास वह $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नामक एक फलन उपस्थित है जो प्रारंभिक बिंदु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

यह भी देखें

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

संदर्भ

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