लेविंसन रिकर्सन: Difference between revisions

Revision as of 09:01, 28 July 2023

लेविंसन प्रत्यावर्तन या लेविंसन-डर्बिन रिकर्सन, टोएप्लिट्ज़ आव्यूह से जुड़े समीकरण के हल की गणना करने के लिए रैखिक बीजगणित में प्रक्रिया है। एल्गोरिदम $Θ (n 2)$ समय में चलता है, जो गॉस-जॉर्डन उन्मूलन पर एक स्पष्ट सुधार है, जो Θ(n³⁾ में चलता है।

लेविंसन-डर्बिन एल्गोरिदम को सर्वप्रथम 1947 में नॉर्मन लेविंसन द्वारा प्रस्तावित किया गया था, जिसे 1960 में जेम्स डर्बिन द्वारा सुधारा गया और बाद में इसमें सुधार किया गया था, द्वारा सुधारा गया था, और बाद में डब्ल्यू.एफ. ट्रेंच और एस. ज़ोहर द्वारा क्रमशः $4 n 2$ और फिर $3 n 2$ गुणन में सुधार किया गया था।

डेटा को संसाधित करने की अन्य विधियों में शूर अपघटन और चोल्स्की अपघटन सम्मिलित हैं। इनकी तुलना में, लेविंसन रिकर्सन (विशेष रूप से विभाजित लेविंसन रिकर्सन) कम्प्यूटेशनल रूप से तीव्र होता है, परन्तु निकटन त्रुटियों जैसी कम्प्यूटेशनल अशुद्धियों के प्रति अधिक संवेदनशील होता है।

टोएप्लिट्ज़ आव्यूह के लिए बेरिस एल्गोरिदम (सामान्य बेरिस एल्गोरिदम के साथ भ्रमित नहीं होना चाहिए) लेविंसन रिकर्सन जितना तीव्र चलता है, परन्तु यह $O (n 2)$ समष्टि का उपयोग करता है, जबकि लेविंसन रिकर्सन मात्र O(n) समष्टि का उपयोग करता है। यद्यपि, बेरिस एल्गोरिदम संख्यात्मक स्थिरता है,^[1]^[2] जबकि लेविंसन रिकर्सन मात्र दुर्बल रूप से स्थिर है (अर्थात यह ठीक रूप से वातानुकूलित रैखिक प्रणालियों के लिए संख्यात्मक स्थिरता प्रदर्शित करता है)।^[3]

नवीन एल्गोरिदम, जिन्हें लक्षणात्मक रूप से तीव्र या कभी-कभी अतितीव्र टोएप्लिट्ज़ एल्गोरिदम कहा जाता है, विभिन्न p के लिए (जैसे p = 2,^[4]^[5] p = 3 ^[6]) के लिए $Θ(n log p n)$ में हल कर सकते हैं। लेविंसन रिकर्सन कई कारणों से लोकप्रिय बना हुआ है; एक के लिए, तुलना में इसे समझना अपेक्षाकृत सरल है; दूसरे के लिए, यह छोटे n (सामान्यतः n <256) के लिए अतितीव्र एल्गोरिदम से तीव्र हो सकता है।^[7]

व्युत्पत्ति

पृष्ठभूमि

आव्यूह समीकरण रूप

\mathbf {M} \,{\vec {x}}={\vec {y}}

का अनुसरण करते हैं।

लेविंसन-डर्बिन एल्गोरिदम का उपयोग ऐसे किसी भी समीकरण के लिए किया जा सकता है, जब तक कि M गैर-शून्य मुख्य विकर्ण के साथ ज्ञात टोएप्लिट्ज़ आव्यूह है। यह ${\vec {y}}$ एक ज्ञात सदिश समष्टि है, और ${\vec {x}}$ संख्याओं x_i का अज्ञात सदिश है जिसे अभी तक निर्धारित नहीं किया गया है।

इस लेख के लिए, ê_i सदिश है जो पूर्ण रूप से शून्य से बना है, इसके iवें स्थान को छोड़कर, जिसका मान एक है। इसकी लंबाई निकट के संदर्भ से स्पष्ट रूप से निर्धारित होगी। शब्द N उपरोक्त आव्यूह की चौड़ाई को संदर्भित करता है - 'M' N×N आव्यूह है। अंत में, इस आलेख में, सुपरस्क्रिप्ट आगमनात्मक सूचकांक को संदर्भित करते हैं, जबकि सबस्क्रिप्ट सूचकांकों को दर्शाते हैं। उदाहरण के लिए (और परिभाषा), इस आलेख में, आव्यूह 'Tⁿ n×n आव्यूह है जो 'M' से ऊपरी बाएँ n×n कक्ष की प्रतिलिपि बनाता है - अर्थात, Tⁿ_ij = M_ij।

Tⁿ भी टोएप्लिट्ज़ आव्यूह है, जिसका अर्थ है कि इसे

\mathbf {T} ^{n}={\begin{bmatrix}t_{0}&t_{-1}&t_{-2}&\dots &t_{-n+1}\\t_{1}&t_{0}&t_{-1}&\dots &t_{-n+2}\\t_{2}&t_{1}&t_{0}&\dots &t_{-n+3}\\\vdots &\vdots &\vdots &\ddots &\vdots \\t_{n-1}&t_{n-2}&t_{n-3}&\dots &t_{0}\end{bmatrix}}

के रूप में लिखा जा सकता है।

परिचयात्मक चरण

एल्गोरिदम दो चरणों में आगे बढ़ता है। पहले चरण में, सदिश के दो समुच्चय स्थापित किए जाते हैं, जिन्हें अग्र और पश्च सदिश कहा जाता है। अग्र सदिश का उपयोग पश्च सदिश के समुच्चय को प्राप्त करने में सहायता के लिए किया जाता है; तो उन्हें तुरंत त्याग दिया जा सकता है। दूसरे चरण के लिए पश्च सदिश आवश्यक हैं, जहां उनका उपयोग वांछित हल बनाने के लिए किया जाता है।

लेविंसन-डर्बिन रिकर्सन n^वें "अग्र सदिश" को परिभाषित करता है, जिसे ${\vec {f}}^{n}$ कहा जाता है, लंबाई n के सदिश के रूप में जो संतुष्ट करता है:

\mathbf {T} ^{n}{\vec {f}}^{n}={\hat {e}}_{1}.

n^वें पश्च सदिश ${\vec {b}}^{n}$ को इसी प्रकार परिभाषित किया गया है; यह लंबाई n का सदिश है जो संतुष्ट करता है:

\mathbf {T} ^{n}{\vec {b}}^{n}={\hat {e}}_{n}.

एक महत्वपूर्ण सरलीकरण तब हो सकता है जब M सममित आव्यूह है; तो दोनों सदिश bⁿ_i = fⁿ_n_+1−i— से संबंधित हैं - अर्थात, वे एक दूसरे के पंक्ति-व्युत्क्रम हैं। यह उस विशेष स्थिति में कुछ अतिरिक्त गणना शेष रह सकती है।

पश्च सदिश प्राप्त करना

यद्यपि एक आव्यूह सममित न हो, फिर भी n^वें अग्र और पश्च के सदिश को लंबाई n - 1 के सदिश से निम्नानुसार पाया जा सकता है। सर्वप्रथम, अग्र सदिश को प्राप्त करने के लिए शून्य के साथ बढ़ाया जा सकता है:

\mathbf {T} ^{n}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\\\end{bmatrix}}={\begin{bmatrix}\ &\ &\ &t_{-n+1}\\\ &\mathbf {T} ^{n-1}&\ &t_{-n+2}\\\ &\ &\ &\vdots \\t_{n-1}&t_{n-2}&\dots &t_{0}\\\end{bmatrix}}{\begin{bmatrix}\ \\{\vec {f}}^{n-1}\\\ \\0\\\ \\\end{bmatrix}}={\begin{bmatrix}1\\0\\\vdots \\0\\\varepsilon _{f}^{n}\end{bmatrix}}.

Tⁿ⁻¹ से Tⁿ तक जाने में, आव्यूह में जोड़ा गया अतिरिक्त स्तम्भ हल को उद्विग्न नहीं करता है जब शून्य का उपयोग अग्र सदिश को बढ़ाने के लिए किया जाता है। यद्यपि, आव्यूह में जोड़ी गई अतिरिक्त पंक्ति ने हल को बाधित कर दिया है; औऔर इसने एक अवांछित त्रुटि शब्द εf बनाया है जो अंतिम स्थान पर आता है। उपरोक्त समीकरण इसका मान देता है:

\varepsilon _{f}^{n}\ =\ \sum _{i=1}^{n-1}\ M_{ni}\ f_{i}^{n-1}\ =\ \sum _{i=1}^{n-1}\ t_{n-i}\ f_{i}^{n-1}.

यह त्रुटि शीघ्र ही वापस आ जाएगी और नवीन अग्र सदिश से समाप्त कर दी जाएगी; परन्तु सर्वप्रथम, पश्च सदिश को समान (यद्यपि व्युत्क्रमा) विधि से बढ़ाया जाना चाहिए। पश्च सदिश के लिए,

\mathbf {T} ^{n}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\\\end{bmatrix}}={\begin{bmatrix}t_{0}&\dots &t_{-n+2}&t_{-n+1}\\\vdots &\ &\ &\ \\t_{n-2}&\ &\mathbf {T} ^{n-1}&\ \\t_{n-1}&\ &\ &\end{bmatrix}}{\begin{bmatrix}\ \\0\\\ \\{\vec {b}}^{n-1}\\\ \\\end{bmatrix}}={\begin{bmatrix}\varepsilon _{b}^{n}\\0\\\vdots \\0\\1\end{bmatrix}}.

पहले के जैसे, आव्यूह में जोड़ा गया अतिरिक्त स्तम्भ इस नवीन पश्च सदिश को उद्विग्न नहीं करता है; परन्तु अतिरिक्त पंक्ति करती है। यहां हमारे निकट मान के साथ एक और अवांछित त्रुटि ε_b है:

\varepsilon _{b}^{n}\ =\ \sum _{i=2}^{n}\ M_{1i}\ b_{i-1}^{n-1}\ =\ \sum _{i=1}^{n-1}\ t_{-i}\ b_{i}^{n-1}.\

इन दो त्रुटि शब्दों का उपयोग निम्नानुसार वर्णित उच्च-क्रम वाले अग्र और पश्च के सदिश बनाने के लिए किया जा सकता है। आव्यूहों की रैखिकता का उपयोग करते हुए, निम्नलिखित पहचान सभी $(\alpha ,\beta )$ के लिए मान्य है:

\mathbf {T} \left(\alpha {\begin{bmatrix}{\vec {f}}\\\ \\0\\\end{bmatrix}}+\beta {\begin{bmatrix}0\\\ \\{\vec {b}}\end{bmatrix}}\right)=\alpha {\begin{bmatrix}1\\0\\\vdots \\0\\\varepsilon _{f}\\\end{bmatrix}}+\beta {\begin{bmatrix}\varepsilon _{b}\\0\\\vdots \\0\\1\end{bmatrix}}.

यदि α और β को चुना जाता है ताकि दाहिनी ओर से ê₁ or ê_n प्राप्त हो, तो कोष्ठक में स्थित मात्रा क्रमशः n^वें अग्र या पश्च सदिश की परिभाषा को पूर्ण करेगी। उन अल्फा और बीटा को चुनने पर, कोष्ठक में सदिश योग सरल होता है और वांछित परिणाम देता है।

इन गुणांकों को खोजने के लिए, $\alpha _{f}^{n}$ , $\beta _{f}^{n}$ जैसे कि:

{\vec {f}}^{n}=\alpha _{f}^{n}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}+\beta _{f}^{n}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}

और क्रमशः $\alpha _{b}^{n}$ , $\beta _{b}^{n}$ जैसे कि:

{\vec {b}}^{n}=\alpha _{b}^{n}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}+\beta _{b}^{n}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}.

पूर्व दोनों समीकरणों को ${\mathbf {T} }^{n}$ से गुणा करने पर निम्नलिखित समीकरण प्राप्त होता है:

{\begin{bmatrix}1&\varepsilon _{b}^{n}\\0&0\\\vdots &\vdots \\0&0\\\varepsilon _{f}^{n}&1\end{bmatrix}}{\begin{bmatrix}\alpha _{f}^{n}&\alpha _{b}^{n}\\\beta _{f}^{n}&\beta _{b}^{n}\end{bmatrix}}={\begin{bmatrix}1&0\\0&0\\\vdots &\vdots \\0&0\\0&1\end{bmatrix}}.

अब, ऊपर दिए गए दो सदिशों के बीच के सभी शून्यों को अनदेखा कर दिया गया है और ध्वस्त कर दिया गया है, मात्र निम्नलिखित समीकरण शेष है:

{\begin{bmatrix}1&\varepsilon _{b}^{n}\\\varepsilon _{f}^{n}&1\end{bmatrix}}{\begin{bmatrix}\alpha _{f}^{n}&\alpha _{b}^{n}\\\beta _{f}^{n}&\beta _{b}^{n}\end{bmatrix}}={\begin{bmatrix}1&0\\0&1\end{bmatrix}}.

इन्हें हल करने के साथ (क्रैमर 2×2 आव्यूह व्युत्क्रम सूत्र का उपयोग करके), नवीन अग्र और पश्च सदिश हैं:

{\vec {f}}^{n}={1 \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}-{\varepsilon _{f}^{n} \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}

{\vec {b}}^{n}={1 \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}-{\varepsilon _{b}^{n} \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}.

इन सदिश योगों को निष्पादित करने से, पहले वाले सदिशों से अग्र और पश्च का n^वां सदिश प्राप्त होता है। जो कुछ शेष है वह इन सदिशों में से पहले को ढूंढना है, और फिर कुछ त्वरित योग और गुणन से शेष को प्राप्त करना है। पहले अग्र और पश्च वाले सदिश मात्र हैं:

{\vec {f}}^{1}={\vec {b}}^{1}=\left[{1 \over M_{11}}\right]=\left[{1 \over t_{0}}\right].

पश्च सदिश का उपयोग करना

उपरोक्त चरण 'M' के लिए n पश्च सदिश देते हैं। वहां से, अधिक यादृच्छिक समीकरण है:

{\vec {y}}=\mathbf {M} \ {\vec {x}}.

हल उसी पुनरावर्ती विधि से बनाया जा सकता है जैसे पश्च सदिश बनाए गए थे। इसलिए, ${\vec {x}}$ मध्यवर्ती के अनुक्रम में सामान्यीकृत किया जाना चाहिए ${\vec {x}}^{n}$ , ऐसा है कि ${\vec {x}}^{N}={\vec {x}}$ .

हल तब पुनरावर्ती रूप से यह ध्यान देकर बनाया जाता है कि यदि

\mathbf {T} ^{n-1}{\begin{bmatrix}x_{1}^{n-1}\\x_{2}^{n-1}\\\vdots \\x_{n-1}^{n-1}\\\end{bmatrix}}={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n-1}\end{bmatrix}}.

फिर, शून्य के साथ फिर से विस्तार करना, और जहां आवश्यक हो, त्रुटि स्थिरांक को परिभाषित करना:

\mathbf {T} ^{n}{\begin{bmatrix}x_{1}^{n-1}\\x_{2}^{n-1}\\\vdots \\x_{n-1}^{n-1}\\0\end{bmatrix}}={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n-1}\\\varepsilon _{x}^{n-1}\end{bmatrix}}.

फिर हम n का उपयोग कर सकते हैं^{त्रुटि शब्द को खत्म करने और इसे वांछित सूत्र के साथ बदलने के लिए पश्च सदिश निम्नानुसार है:}

\mathbf {T} ^{n}\left({\begin{bmatrix}x_{1}^{n-1}\\x_{2}^{n-1}\\\vdots \\x_{n-1}^{n-1}\\0\\\end{bmatrix}}+(y_{n}-\varepsilon _{x}^{n-1})\ {\vec {b}}^{n}\right)={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n-1}\\y_{n}\end{bmatrix}}.

इस विधि को n = N तक विस्तारित करने से हल प्राप्त होता है ${\vec {x}}$ .

व्यवहार में, ये चरण अक्सर शेष प्रक्रिया के साथ-साथ किए जाते हैं, परन्तु वे सुसंगत इकाई बनाते हैं और उन्हें अपने स्वयं के चरण के रूप में माना जाना चाहिए।

कक्ष लेविंसन एल्गोरिदम

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

यह भी देखें

स्प्लिट लेविंसन रिकर्सन
रैखिक भविष्यवाणी
स्वप्रतिगामी मॉडल

↑ Bojanczyk et al. (1995).
↑ Brent (1999).
↑ Krishna & Wang (1993).
↑ "संग्रहीत प्रति" (PDF). Archived from the original (PDF) on 2012-03-25. Retrieved 2013-04-01.
↑ "संग्रहीत प्रति" (PDF). Archived from the original (PDF) on 2009-11-15. Retrieved 2009-04-28.
↑ "संग्रहीत प्रति" (PDF). saaz.cs.gsu.edu. Archived from the original (PDF) on 18 April 2007. Retrieved 12 January 2022.
↑ "संग्रहीत प्रति" (PDF). Archived from the original (PDF) on 2006-09-05. Retrieved 2006-08-15.

संदर्भ

Defining sources

Levinson, N. (1947). "The Wiener RMS error criterion in filter design and prediction." J. Math. Phys., v. 25, pp. 261–278.
Durbin, J. (1960). "The fitting of time series models." Rev. Inst. Int. Stat., v. 28, pp. 233–243.
Trench, W. F. (1964). "An algorithm for the inversion of finite टोएप्लिट्ज़ matrices." J. Soc. Indust. Appl. Math., v. 12, pp. 515–522.
Musicus, B. R. (1988). "Levinson and Fast Choleski Algorithms for टोएप्लिट्ज़ and Almost टोएप्लिट्ज़ Matrices." RLE TR No. 538, MIT. [1]
Delsarte, P. and Genin, Y. V. (1986). "The split Levinson algorithm." IEEE Transactions on Acoustics, Speech, and Signal Processing, v. ASSP-34(3), pp. 470–478.

Further work

Bojanczyk, A.W.; Brent, R.P.; De Hoog, F.R.; Sweet, D.R. (1995). "On the stability of the Bareiss and related Toeplitz factorization algorithms". SIAM Journal on Matrix Analysis and Applications. 16: 40–57. arXiv:1004.5510. doi:10.1137/S0895479891221563. S2CID 367586.
Brent R.P. (1999), "Stability of fast algorithms for structured linear systems", Fast Reliable Algorithms for Matrices with Structure (editors—T. Kailath, A.H. Sayed), ch.4 (SIAM).
Bunch, J. R. (1985). "Stability of methods for solving टोएप्लिट्ज़ systems of equations." SIAM J. Sci. Stat. Comput., v. 6, pp. 349–364. [2]
Krishna, H.; Wang, Y. (1993). "The Split Levinson Algorithm is weakly stable". SIAM Journal on Numerical Analysis. 30 (5): 1498–1508. doi:10.1137/0730078.

Summaries

Bäckström, T. (2004). "2.2. Levinson–Durbin Recursion." Linear Predictive Modelling of Speech – Constraints and Line Spectrum Pair Decomposition. Doctoral thesis. Report no. 71 / Helsinki University of Technology, Laboratory of Acoustics and Audio Signal Processing. Espoo, Finland. [3]
Claerbout, Jon F. (1976). "Chapter 7 – Waveform Applications of Least-Squares." Fundamentals of Geophysical Data Processing. Palo Alto: Blackwell Scientific Publications. [4]
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 2.8.2. Toeplitz Matrices", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
Golub, G.H., and Loan, C.F. Van (1996). "Section 4.7 : टोएप्लिट्ज़ and related Systems" Matrix Computations, Johns Hopkins University Press

[1] Bojanczyk et al. (1995).

[2] Brent (1999).

[3] Krishna & Wang (1993).

[4] "संग्रहीत प्रति" (PDF). Archived from the original (PDF) on 2012-03-25. Retrieved 2013-04-01.

[5] "संग्रहीत प्रति" (PDF). Archived from the original (PDF) on 2009-11-15. Retrieved 2009-04-28.

[6] "संग्रहीत प्रति" (PDF). saaz.cs.gsu.edu. Archived from the original (PDF) on 18 April 2007. Retrieved 12 January 2022.

[7] "संग्रहीत प्रति" (PDF). Archived from the original (PDF) on 2006-09-05. Retrieved 2006-08-15.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
-लेविंसन [[ प्रत्यावर्तन ]] या लेविंसन-डर्बिन रिकर्सन, [[टोएप्लिट्ज़ मैट्रिक्स]] से जुड़े समीकरण के समाधान की गणना करने के लिए रैखिक बीजगणित में एक प्रक्रिया है। [[कलन विधि]] चलता है {{math|[[Big O notation|Θ]](''n''<sup>2</sup>)}} समय, जो गॉस-जॉर्डन उन्मूलन पर एक मजबूत सुधार है, जो Θ(n) में चलता है<sup>3</sup>).
+लेविंसन [[ प्रत्यावर्तन |प्रत्यावर्तन]] या लेविंसन-डर्बिन रिकर्सन, [[टोएप्लिट्ज़ मैट्रिक्स|टोएप्लिट्ज़ आव्यूह]] से जुड़े समीकरण के हल की गणना करने के लिए रैखिक बीजगणित में प्रक्रिया है। [[कलन विधि|एल्गोरिदम]] {{math|[[Big O notation|Θ]](''n''<sup>2</sup>)}} समय में चलता है, जो गॉस-जॉर्डन उन्मूलन पर एक स्पष्ट सुधार है, जो Θ(n<sup>3)</sup> में चलता है।
-लेविंसन-डर्बिन एल्गोरिथ्म को सबसे पहले 1947 में [[नॉर्मन लेविंसन]] द्वारा प्रस्तावित किया गया था, जिसे 1960 में [[जेम्स डर्बिन]] द्वारा सुधारा गया और बाद में इसमें सुधार किया गया। {{math|4''n''<sup>2</sup>}} और तब {{math|3''n''<sup>2</sup>}} क्रमशः डब्ल्यू.एफ. ट्रेंच और एस. ज़ोहर द्वारा गुणन।
+लेविंसन-डर्बिन एल्गोरिदम को सर्वप्रथम 1947 में [[नॉर्मन लेविंसन]] द्वारा प्रस्तावित किया गया था, जिसे 1960 में [[जेम्स डर्बिन]] द्वारा सुधारा गया और बाद में इसमें सुधार किया गया था, द्वारा सुधारा गया था, और बाद में डब्ल्यू.एफ. ट्रेंच और एस. ज़ोहर द्वारा क्रमशः {{math|4''n''<sup>2</sup>}} और फिर {{math|3''n''<sup>2</sup>}} गुणन में सुधार किया गया था।
-डेटा को संसाधित करने की अन्य विधियों में [[शूर अपघटन]] और चोल्स्की अपघटन शामिल हैं। इनकी तुलना में, लेविंसन रिकर्सन (विशेष रूप से विभाजित लेविंसन रिकर्सन) कम्प्यूटेशनल रूप से तेज़ होता है, लेकिन राउंड-ऑफ त्रुटियों जैसी कम्प्यूटेशनल अशुद्धियों के प्रति अधिक संवेदनशील होता है।
+डेटा को संसाधित करने की अन्य विधियों में [[शूर अपघटन]] और चोल्स्की अपघटन सम्मिलित हैं। इनकी तुलना में, लेविंसन रिकर्सन (विशेष रूप से विभाजित लेविंसन रिकर्सन) कम्प्यूटेशनल रूप से तीव्र होता है, परन्तु निकटन त्रुटियों जैसी कम्प्यूटेशनल अशुद्धियों के प्रति अधिक संवेदनशील होता है।
-टोप्लिट्ज़ मैट्रिक्स के लिए [[बेरिस एल्गोरिथ्म]] (सामान्य बेरिस एल्गोरिदम के साथ भ्रमित नहीं होना चाहिए) लेविंसन रिकर्सन जितना तेज़ चलता है, लेकिन यह इसका उपयोग करता है {{math|''O''(''n''<sup>2</sup>)}} स्पेस, जबकि लेविंसन रिकर्सन केवल O(n) स्पेस का उपयोग करता है। हालाँकि, बेरिस एल्गोरिथ्म [[संख्यात्मक स्थिरता]] है,<ref>Bojanczyk et al. (1995).</ref><ref>Brent (1999).</ref> जबकि लेविंसन रिकर्सन केवल कमजोर रूप से स्थिर है (यानी यह स्थिति संख्या | अच्छी तरह से वातानुकूलित रैखिक प्रणालियों के लिए संख्यात्मक स्थिरता प्रदर्शित करता है)।<ref>Krishna & Wang (1993).</ref>
-नए एल्गोरिदम, जिन्हें एसिम्प्टोटिकली फास्ट या कभी-कभी सुपरफास्ट टोप्लिट्ज़ एल्गोरिदम कहा जाता है, हल कर सकते हैं {{math|Θ(''n'' log<sup>''p''</sup>''n'')}} विभिन्न पी के लिए (जैसे पी = 2,<ref>{{Cite web |url=http://www.maths.anu.edu.au/~brent/pd/rpb143tr.pdf |title=संग्रहीत प्रति|access-date=2013-04-01 |archive-date=2012-03-25 |archive-url=https://web.archive.org/web/20120325215317/http://maths.anu.edu.au/~brent/pd/rpb143tr.pdf |url-status=dead }}</ref><ref>{{cite web |url=http://etd.gsu.edu/theses/available/etd-04182008-174330/unrestricted/kimitei_symon_k_200804.pdf |title=संग्रहीत प्रति|access-date=2009-04-28 |url-status=dead |archive-url=https://web.archive.org/web/20091115041852/http://etd.gsu.edu/theses/available/etd-04182008-174330/unrestricted/kimitei_symon_k_200804.pdf |archive-date=2009-11-15 }}</ref> पी = 3 <ref>{{cite web |url=http://saaz.cs.gsu.edu/papers/sfast.pdf |title=संग्रहीत प्रति|website=saaz.cs.gsu.edu |access-date=12 January 2022 |archive-url=https://web.archive.org/web/20070418074240/http://saaz.cs.gsu.edu/papers/sfast.pdf |archive-date=18 April 2007 |url-status=dead}}</ref>). लेविंसन रिकर्सन कई कारणों से लोकप्रिय बना हुआ है; एक के लिए, तुलना में इसे समझना अपेक्षाकृत आसान है; दूसरे के लिए, यह छोटे n (आमतौर पर n <256) के लिए सुपरफास्ट एल्गोरिदम से तेज़ हो सकता है।<ref>{{Cite web |url=http://www.math.niu.edu/~ammar/papers/amgr88.pdf |title=संग्रहीत प्रति|access-date=2006-08-15 |archive-date=2006-09-05 |archive-url=https://web.archive.org/web/20060905064921/http://www.math.niu.edu/~ammar/papers/amgr88.pdf |url-status=dead }}</ref>
+टोएप्लिट्ज़ आव्यूह के लिए [[बेरिस एल्गोरिथ्म|बेरिस एल्गोरिदम]] (सामान्य बेरिस एल्गोरिदम के साथ भ्रमित नहीं होना चाहिए) लेविंसन रिकर्सन जितना तीव्र चलता है, परन्तु यह {{math|''O''(''n''<sup>2</sup>)}} समष्टि का उपयोग करता है, जबकि लेविंसन रिकर्सन मात्र O(n) समष्टि का उपयोग करता है। यद्यपि, बेरिस एल्गोरिदम [[संख्यात्मक स्थिरता]] है,<ref>Bojanczyk et al. (1995).</ref><ref>Brent (1999).</ref> जबकि लेविंसन रिकर्सन मात्र दुर्बल रूप से स्थिर है (अर्थात यह ठीक रूप से वातानुकूलित रैखिक प्रणालियों के लिए संख्यात्मक स्थिरता प्रदर्शित करता है)।<ref>Krishna & Wang (1993).</ref>
+नवीन एल्गोरिदम, जिन्हें लक्षणात्मक रूप से तीव्र या कभी-कभी अतितीव्र टोएप्लिट्ज़ एल्गोरिदम कहा जाता है, विभिन्न p के लिए (जैसे p = 2,<ref>{{Cite web |url=http://www.maths.anu.edu.au/~brent/pd/rpb143tr.pdf |title=संग्रहीत प्रति|access-date=2013-04-01 |archive-date=2012-03-25 |archive-url=https://web.archive.org/web/20120325215317/http://maths.anu.edu.au/~brent/pd/rpb143tr.pdf |url-status=dead }}</ref><ref>{{cite web |url=http://etd.gsu.edu/theses/available/etd-04182008-174330/unrestricted/kimitei_symon_k_200804.pdf |title=संग्रहीत प्रति|access-date=2009-04-28 |url-status=dead |archive-url=https://web.archive.org/web/20091115041852/http://etd.gsu.edu/theses/available/etd-04182008-174330/unrestricted/kimitei_symon_k_200804.pdf |archive-date=2009-11-15 }}</ref> p = 3 <ref>{{cite web |url=http://saaz.cs.gsu.edu/papers/sfast.pdf |title=संग्रहीत प्रति|website=saaz.cs.gsu.edu |access-date=12 January 2022 |archive-url=https://web.archive.org/web/20070418074240/http://saaz.cs.gsu.edu/papers/sfast.pdf |archive-date=18 April 2007 |url-status=dead}}</ref>) के लिए {{math|Θ(''n'' log<sup>''p''</sup>''n'')}} में हल कर सकते हैं। लेविंसन रिकर्सन कई कारणों से लोकप्रिय बना हुआ है; एक के लिए, तुलना में इसे समझना अपेक्षाकृत सरल है; दूसरे के लिए, यह छोटे n (सामान्यतः n <256) के लिए अतितीव्र एल्गोरिदम से तीव्र हो सकता है।<ref>{{Cite web |url=http://www.math.niu.edu/~ammar/papers/amgr88.pdf |title=संग्रहीत प्रति|access-date=2006-08-15 |archive-date=2006-09-05 |archive-url=https://web.archive.org/web/20060905064921/http://www.math.niu.edu/~ammar/papers/amgr88.pdf |url-status=dead }}</ref>
 == व्युत्पत्ति ==
 === पृष्ठभूमि ===
-मैट्रिक्स समीकरण प्रपत्र का अनुसरण करते हैं
+आव्यूह समीकरण रूप
-: <math>\mathbf M \, \vec x = \vec y.</math>
+: <math>\mathbf M \, \vec x = \vec y</math> का अनुसरण करते हैं।
-लेविंसन-डर्बिन एल्गोरिथ्म का उपयोग ऐसे किसी भी समीकरण के लिए किया जा सकता है, जब तक कि एम एक गैर-शून्य मुख्य विकर्ण के साथ एक ज्ञात टोप्लिट्ज़ मैट्रिक्स है। यहाँ <math>\vec y</math> एक ज्ञात सदिश समष्टि है, और <math>\vec x</math> संख्या x का एक अज्ञात सदिश है<sub>''i''</sub> अभी तक निर्धारित नहीं किया गया है।
+लेविंसन-डर्बिन एल्गोरिदम का उपयोग ऐसे किसी भी समीकरण के लिए किया जा सकता है, जब तक कि '''M''' गैर-शून्य मुख्य विकर्ण के साथ ज्ञात टोएप्लिट्ज़ आव्यूह है। यह <math>\vec y</math> एक ज्ञात सदिश समष्टि है, और <math>\vec x</math> संख्याओं x<sub>''i''</sub> का अज्ञात सदिश है जिसे अभी तक निर्धारित नहीं किया गया है।
-इस लेख के लिए, ê<sub>''i''</sub> एक वेक्टर है जो इसके वें स्थान को छोड़कर पूरी तरह से शून्य से बना है, जिसका मान एक है। इसकी लंबाई आस-पास के संदर्भ से स्पष्ट रूप से निर्धारित होगी। शब्द N उपरोक्त मैट्रिक्स की चौड़ाई को संदर्भित करता है - 'M' एक N×N मैट्रिक्स है। अंत में, इस आलेख में, सुपरस्क्रिप्ट एक आगमनात्मक सूचकांक को संदर्भित करते हैं, जबकि सबस्क्रिप्ट सूचकांकों को दर्शाते हैं। उदाहरण के लिए (और परिभाषा), इस आलेख में, मैट्रिक्स 'टी'<sup>n</sup> एक n×n मैट्रिक्स है जो 'M' से ऊपरी बाएँ n×n ब्लॉक को कॉपी करता है - यानी, T<sup>n</sup><sub>''ij''</sub> = एम<sub>''ij''</sub>.
+इस लेख के लिए, ê<sub>''i''</sub> सदिश है जो पूर्ण रूप से शून्य से बना है, इसके iवें स्थान को छोड़कर, जिसका मान एक है। इसकी लंबाई निकट के संदर्भ से स्पष्ट रूप से निर्धारित होगी। शब्द N उपरोक्त आव्यूह की चौड़ाई को संदर्भित करता है - '''<nowiki/>'M'<nowiki/>''' N×N आव्यूह है। अंत में, इस आलेख में, सुपरस्क्रिप्ट आगमनात्मक सूचकांक को संदर्भित करते हैं, जबकि सबस्क्रिप्ट सूचकांकों को दर्शाते हैं। उदाहरण के लिए (और परिभाषा), इस आलेख में, आव्यूह '<nowiki/>'''T'''<sup>''n''</sup> n×n आव्यूह है जो '''<nowiki/>'M'''' से ऊपरी बाएँ n×n कक्ष की प्रतिलिपि बनाता है - अर्थात, T<sup>n</sup><sub>''ij''</sub> = M<sub>''ij''</sub>।
-टी<sup>n</sup> भी एक Toeplitz मैट्रिक्स है, जिसका अर्थ है कि इसे इस प्रकार लिखा जा सकता है
+'''T'''<sup>''n''</sup> भी टोएप्लिट्ज़ आव्यूह है, जिसका अर्थ है कि इसे
 : <math>\mathbf T^n = \begin{bmatrix}
@@ Line 27: / Line 26: @@
      \vdots & \vdots  & \vdots  & \ddots & \vdots   \\
      t_{n-1}& t_{n-2} & t_{n-3} & \dots  & t_0
-   \end{bmatrix}. </math>
+   \end{bmatrix} </math> के रूप में लिखा जा सकता है।
 === परिचयात्मक चरण ===
-एल्गोरिथम दो चरणों में आगे बढ़ता है। पहले चरण में, वैक्टर के दो सेट स्थापित किए जाते हैं, जिन्हें फॉरवर्ड और बैकवर्ड वेक्टर कहा जाता है। आगे वाले वैक्टर का उपयोग पिछड़े वैक्टर के सेट को प्राप्त करने में मदद के लिए किया जाता है; तो उन्हें तुरंत त्याग दिया जा सकता है। दूसरे चरण के लिए बैकवर्ड वेक्टर आवश्यक हैं, जहां उनका उपयोग वांछित समाधान बनाने के लिए किया जाता है।
+एल्गोरिदम दो चरणों में आगे बढ़ता है। पहले चरण में, सदिश के दो समुच्चय स्थापित किए जाते हैं, जिन्हें अग्र और पश्च सदिश कहा जाता है। अग्र सदिश का उपयोग पश्च सदिश के समुच्चय को प्राप्त करने में सहायता के लिए किया जाता है; तो उन्हें तुरंत त्याग दिया जा सकता है। दूसरे चरण के लिए पश्च सदिश आवश्यक हैं, जहां उनका उपयोग वांछित हल बनाने के लिए किया जाता है।
-लेविंसन-डर्बिन रिकर्सन एन को परिभाषित करता है<sup>वें</sup>आगे वेक्टर, निरूपित <math>\vec f^n</math>, लंबाई n के वेक्टर के रूप में जो संतुष्ट करता है:
+लेविंसन-डर्बिन रिकर्सन n<sup>वें</sup> "अग्र सदिश" को परिभाषित करता है, जिसे <math>\vec f^n</math>कहा जाता है, लंबाई n के सदिश के रूप में जो संतुष्ट करता है:
 :<math>\mathbf T^n \vec f^n = \hat e_1.</math>
-तब<sup>वें</sup>बैकवर्ड वेक्टर <math>\vec b^n</math> समान रूप से परिभाषित किया गया है; यह लंबाई n का सदिश है जो संतुष्ट करता है:
+n<sup>वें</sup> पश्च सदिश <math>\vec b^n</math> को इसी प्रकार परिभाषित किया गया है; यह लंबाई n का सदिश है जो संतुष्ट करता है:
 :<math>\mathbf T^n \vec b^n = \hat e_n.</math>
-एक महत्वपूर्ण सरलीकरण तब हो सकता है जब ''एम'' एक [[सममित मैट्रिक्स]] है; तो दोनों वेक्टर ''बी'' से संबंधित हैं<sup>n</sup><sub>''i''</sub> = एफ<sup>n</sup><sub>''n''+1−''i''</sub>-अर्थात्, वे एक-दूसरे की पंक्ति-उलट हैं। यह उस विशेष मामले में कुछ अतिरिक्त गणना बचा सकता है।
+एक महत्वपूर्ण सरलीकरण तब हो सकता है जब ''M'' [[सममित मैट्रिक्स|सममित आव्यूह]] है; तो दोनों सदिश ''b<sup>n</sup><sub>i</sub>'' = ''f<sup>n</sup><sub>n</sub>''<sub>+1−''i''</sub>— से संबंधित हैं - अर्थात, वे एक दूसरे के पंक्ति-व्युत्क्रम हैं। यह उस विशेष स्थिति में कुछ अतिरिक्त गणना शेष रह सकती है।
-=== पिछड़े सदिश प्राप्त करना ===
+=== पश्च सदिश प्राप्त करना ===
-भले ही मैट्रिक्स सममित न हो, फिर भी n<sup>वें</sup> आगे और पीछे के वेक्टर को लंबाई n - 1 के वैक्टर से निम्नानुसार पाया जा सकता है। सबसे पहले, आगे के वेक्टर को प्राप्त करने के लिए शून्य के साथ बढ़ाया जा सकता है:
+यद्यपि एक आव्यूह सममित न हो, फिर भी n<sup>वें</sup> अग्र और पश्च के सदिश को लंबाई n - 1 के सदिश से निम्नानुसार पाया जा सकता है। सर्वप्रथम, अग्र सदिश को प्राप्त करने के लिए शून्य के साथ बढ़ाया जा सकता है:
 :<math>\mathbf T^n \begin{bmatrix} \vec f^{n-1} \\ 0 \\ \end{bmatrix} =
@@ Line 63: / Line 61: @@
                     \varepsilon_f^n
    \end{bmatrix}. </math>
-''टी'' से जाने में<sup>n−1</sup>' से 'T<sup>n</sup>'', मैट्रिक्स में जोड़ा गया अतिरिक्त ''कॉलम'' समाधान को परेशान नहीं करता है जब शून्य का उपयोग फॉरवर्ड वेक्टर को बढ़ाने के लिए किया जाता है। हालाँकि, मैट्रिक्स में जोड़ी गई अतिरिक्त ''पंक्ति'' ने समाधान को बाधित कर दिया है; और इसने एक अवांछित त्रुटि शब्द ''ε'' बनाया है<sub>''f''</sub> जो अंतिम स्थान पर होता है. उपरोक्त समीकरण इसका मान देता है:
+'''''T<sup>n</sup>''<sup>−1</sup>''' से '''''T<sup>n</sup>''''' तक जाने में, आव्यूह में जोड़ा गया अतिरिक्त स्तम्भ हल को उद्विग्न नहीं करता है जब शून्य का उपयोग अग्र सदिश को बढ़ाने के लिए किया जाता है। यद्यपि, आव्यूह में जोड़ी गई अतिरिक्त पंक्ति ने हल को बाधित कर दिया है; औऔर इसने एक अवांछित त्रुटि शब्द εf बनाया है जो अंतिम स्थान पर आता है। उपरोक्त समीकरण इसका मान देता है:
 : <math> \varepsilon_f^n \ = \  \sum_{i=1}^{n-1} \ M_{ni} \  f_{i}^{n-1} \ = \ \sum_{i=1}^{n-1} \  t_{n-i} \ f_{i}^{n-1}. </math>
-यह त्रुटि शीघ्र ही वापस आ जाएगी और नए फॉरवर्ड वेक्टर से समाप्त कर दी जाएगी; लेकिन सबसे पहले, बैकवर्ड वेक्टर को समान (यद्यपि उलटा) तरीके से बढ़ाया जाना चाहिए। बैकवर्ड वेक्टर के लिए,
+यह त्रुटि शीघ्र ही वापस आ जाएगी और नवीन अग्र सदिश से समाप्त कर दी जाएगी; परन्तु सर्वप्रथम, पश्च सदिश को समान (यद्यपि व्युत्क्रमा) विधि से बढ़ाया जाना चाहिए। पश्च सदिश के लिए,
 :<math> \mathbf T^n \begin{bmatrix} 0 \\ \vec b^{n-1} \\ \end{bmatrix} =
@@ Line 87: / Line 85: @@
    \end{bmatrix}. </math>
-पहले की तरह, मैट्रिक्स में जोड़ा गया अतिरिक्त कॉलम इस नए बैकवर्ड वेक्टर को परेशान नहीं करता है; लेकिन अतिरिक्त पंक्ति करती है. यहां हमारे पास एक और अवांछित त्रुटि है ε<sub>''b''</sub> मूल्य के साथ:
+पहले के जैसे, आव्यूह में जोड़ा गया अतिरिक्त स्तम्भ इस नवीन पश्च सदिश को उद्विग्न नहीं करता है; परन्तु अतिरिक्त पंक्ति करती है। यहां हमारे निकट मान के साथ एक और अवांछित त्रुटि ''ε<sub>b</sub>'' है:
 :<math> \varepsilon_b^n \ = \ \sum_{i=2}^n \  M_{1i} \ b_{i-1}^{n-1} \ = \ \sum_{i=1}^{n-1} \  t_{-i} \ b_i^{n-1}. \ </math>
-इन दो त्रुटि शब्दों का उपयोग निम्नानुसार वर्णित उच्च-क्रम वाले आगे और पीछे के वैक्टर बनाने के लिए किया जा सकता है। आव्यूहों की रैखिकता का उपयोग करते हुए, निम्नलिखित पहचान सभी के लिए मान्य है <math>(\alpha,\beta)</math>:
+इन दो त्रुटि शब्दों का उपयोग निम्नानुसार वर्णित उच्च-क्रम वाले अग्र और पश्च के सदिश बनाने के लिए किया जा सकता है। आव्यूहों की रैखिकता का उपयोग करते हुए, निम्नलिखित पहचान सभी <math>(\alpha,\beta)</math> के लिए मान्य है:
 :<math>\mathbf T \left( \alpha
@@ Line 115: / Line 113: @@
    \end{bmatrix}.</math>
-यदि α और β को चुना जाता है ताकि दाहिनी ओर ê प्राप्त हो<sub>1</sub> या<sub>''n''</sub>, तो कोष्ठक में मौजूद मात्रा n की परिभाषा को पूरा करेगी<sup>वें</sup> क्रमशः आगे या पीछे वेक्टर। उन अल्फा और बीटा को चुनने पर, कोष्ठक में वेक्टर योग सरल होता है और वांछित परिणाम देता है।
+यदि α और β को चुना जाता है ताकि दाहिनी ओर से ''ê''<sub>1</sub> or ''ê<sub>n</sub>'' प्राप्त हो, तो कोष्ठक में स्थित मात्रा क्रमशः n<sup>वें</sup> अग्र या पश्च सदिश की परिभाषा को पूर्ण करेगी। उन अल्फा और बीटा को चुनने पर, कोष्ठक में सदिश योग सरल होता है और वांछित परिणाम देता है।
-इन गुणांकों को खोजने के लिए, <math>\alpha^n_{f}</math>, <math>\beta^n_{f}</math> ऐसे हैं कि:
+इन गुणांकों को खोजने के लिए, <math>\alpha^n_{f}</math>, <math>\beta^n_{f}</math> जैसे कि:
 :<math>
 \vec f^n = \alpha^n_{f} \begin{bmatrix} \vec f^{n-1}\\
@@ Line 126: / Line 124: @@
 \end{bmatrix}
 </math>
-और क्रमशः  <math>\alpha^n_{b}</math>, <math>\beta^n_{b}</math> ऐसे हैं कि:
+और क्रमशः <math>\alpha^n_{b}</math>, <math>\beta^n_{b}</math> जैसे कि:
 :<math>\vec b^n = \alpha^n_{b}
 \begin{bmatrix}
@@ Line 137: / Line 135: @@
 \end{bmatrix}.
 </math>
-पिछले दोनों समीकरणों को इससे गुणा करने पर <math>{\mathbf T}^n</math> किसी को निम्नलिखित समीकरण मिलता है:
+पूर्व दोनों समीकरणों को <math>{\mathbf T}^n</math> से गुणा करने पर निम्नलिखित समीकरण प्राप्त होता है:
 : <math>
 \begin{bmatrix} 1 & \varepsilon^n_b \\
@@ Line 152: / Line 150: @@
 & 1
 \end{bmatrix}.</math>
-अब, ऊपर दिए गए दो वैक्टरों के बीच के सभी शून्यों को नजरअंदाज कर दिया गया है और ध्वस्त कर दिया गया है, केवल निम्नलिखित समीकरण बचा है:
+अब, ऊपर दिए गए दो सदिशों के बीच के सभी शून्यों को अनदेखा कर दिया गया है और ध्वस्त कर दिया गया है, मात्र निम्नलिखित समीकरण शेष है:
 : <math> \begin{bmatrix} 1 & \varepsilon^n_b \\ \varepsilon^n_f & 1 \end{bmatrix} \begin{bmatrix} \alpha^n_f & \alpha^n_b \\ \beta^n_f & \beta^n_b \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}.</math>
-इन्हें हल करने के साथ (क्रैमर 2×2 मैट्रिक्स व्युत्क्रम सूत्र का उपयोग करके), नए फॉरवर्ड और बैकवर्ड वेक्टर हैं:
+इन्हें हल करने के साथ (क्रैमर 2×2 आव्यूह व्युत्क्रम सूत्र का उपयोग करके), नवीन अग्र और पश्च सदिश हैं:
 : <math>\vec f^n = {1 \over { 1 - \varepsilon_b^n \varepsilon_f^n }}          \begin{bmatrix} \vec f^{n-1} \\ 0 \end{bmatrix}
@@ Line 161: / Line 159: @@
 : <math>\vec b^n =  { 1 \over { 1 - \varepsilon_b^n \varepsilon_f^n }}         \begin{bmatrix} 0 \\ \vec b^{n-1} \end{bmatrix}
                   - { \varepsilon_b^n \over { 1 - \varepsilon_b^n \varepsilon_f^n }}\begin{bmatrix} \vec f^{n-1} \\ 0 \end{bmatrix}.</math>
-इन सदिश योगों को निष्पादित करने पर, n प्राप्त होता है<sup>वें</sup> पिछले वाले से आगे और पीछे के वेक्टर। जो कुछ बचा है वह इन वैक्टरों में से पहले को ढूंढना है, और फिर कुछ त्वरित योग और गुणन से शेष को प्राप्त करना है। पहले आगे और पीछे वाले वेक्टर बस हैं:
+इन सदिश योगों को निष्पादित करने से, पहले वाले सदिशों से अग्र और पश्च का n<sup>वां</sup> सदिश प्राप्त होता है। जो कुछ शेष है वह इन सदिशों में से पहले को ढूंढना है, और फिर कुछ त्वरित योग और गुणन से शेष को प्राप्त करना है। पहले अग्र और पश्च वाले सदिश मात्र हैं:
 : <math>\vec f^1 = \vec b^1 = \left[ {1 \over M_{11}} \right] = \left[ {1 \over t_0} \right].</math>
+=== पश्च सदिश का उपयोग करना ===
-=== पिछड़े वैक्टर का उपयोग करना ===
+उपरोक्त चरण 'M' के लिए n पश्च सदिश देते हैं। वहां से, अधिक यादृच्छिक समीकरण है:
-उपरोक्त चरण 'एम' के लिए एन बैकवर्ड वैक्टर देते हैं। वहां से, एक अधिक मनमाना समीकरण है:
 : <math> \vec y = \mathbf M \  \vec x. </math>
-समाधान उसी पुनरावर्ती तरीके से बनाया जा सकता है जैसे बैकवर्ड वैक्टर बनाए गए थे। इसलिए, <math>\vec x</math> मध्यवर्ती के अनुक्रम में सामान्यीकृत किया जाना चाहिए <math>\vec x^n</math>, ऐसा है कि <math>\vec x^N = \vec x</math>.
+हल उसी पुनरावर्ती विधि से बनाया जा सकता है जैसे पश्च सदिश बनाए गए थे। इसलिए, <math>\vec x</math> मध्यवर्ती के अनुक्रम में सामान्यीकृत किया जाना चाहिए <math>\vec x^n</math>, ऐसा है कि <math>\vec x^N = \vec x</math>.
-समाधान तब पुनरावर्ती रूप से यह ध्यान देकर बनाया जाता है कि यदि
+हल तब पुनरावर्ती रूप से यह ध्यान देकर बनाया जाता है कि यदि
 : <math> \mathbf T^{n-1}
@@ Line 185: / Line 182: @@
                     y_{n-1}
    \end{bmatrix}.</math>
-फिर, शून्य के साथ फिर से विस्तार करना, और जहां आवश्यक हो, एक त्रुटि स्थिरांक को परिभाषित करना:
+फिर, शून्य के साथ फिर से विस्तार करना, और जहां आवश्यक हो, त्रुटि स्थिरांक को परिभाषित करना:
 : <math> \mathbf T^{n}
@@ Line 200: / Line 197: @@
                     \varepsilon_x^{n-1}
    \end{bmatrix}.</math>
-फिर हम n का उपयोग कर सकते हैं<sup>त्रुटि शब्द को खत्म करने और इसे वांछित सूत्र के साथ बदलने के लिए बैकवर्ड वेक्टर निम्नानुसार है:
+फिर हम n का उपयोग कर सकते हैं<sup>त्रुटि शब्द को खत्म करने और इसे वांछित सूत्र के साथ बदलने के लिए पश्च सदिश निम्नानुसार है:
 : <math> \mathbf T^{n} \left (
@@ Line 215: / Line 212: @@
                     y_n
    \end{bmatrix}.</math>
-इस विधि को n = N तक विस्तारित करने से समाधान प्राप्त होता है <math>\vec x</math>.
+इस विधि को n = N तक विस्तारित करने से हल प्राप्त होता है <math>\vec x</math>.
-व्यवहार में, ये चरण अक्सर शेष प्रक्रिया के साथ-साथ किए जाते हैं, लेकिन वे एक सुसंगत इकाई बनाते हैं और उन्हें अपने स्वयं के चरण के रूप में माना जाना चाहिए।
+व्यवहार में, ये चरण अक्सर शेष प्रक्रिया के साथ-साथ किए जाते हैं, परन्तु वे सुसंगत इकाई बनाते हैं और उन्हें अपने स्वयं के चरण के रूप में माना जाना चाहिए।
-== ब्लॉक लेविंसन एल्गोरिथ्म ==
+== कक्ष लेविंसन एल्गोरिदम ==
-यदि ''एम'' सख्ती से टोएप्लिट्ज़ नहीं है, लेकिन [[ब्लॉक मैट्रिक्स]] टोएप्लिट्ज़ है, तो लेविंसन रिकर्सन को मैट्रिक्स तत्वों के साथ टोएप्लिट्ज़ मैट्रिक्स के रूप में ब्लॉक टोएप्लिट्ज़ मैट्रिक्स के संबंध में उसी तरह से प्राप्त किया जा सकता है (म्यूजिकस 1988)। ब्लॉक टॉप्लिट्ज़ मैट्रिसेस सिग्नल प्रोसेसिंग एल्गोरिदम में स्वाभाविक रूप से उत्पन्न होते हैं जब कई सिग्नल स्ट्रीम (उदाहरण के लिए, सिस्टम विश्लेषण # सिस्टम सिस्टम की विशेषता) या साइक्लो-स्टेशनरी सिग्नल से निपटते हैं।
+यदि ''M'' सख्ती से टोएप्लिट्ज़ नहीं है, परन्तु [[ब्लॉक मैट्रिक्स|कक्ष आव्यूह]] टोएप्लिट्ज़ है, तो लेविंसन रिकर्सन को आव्यूह तत्वों के साथ टोएप्लिट्ज़ आव्यूह के रूप में कक्ष टोएप्लिट्ज़ आव्यूह के संबंध में उसी प्रकार से प्राप्त किया जा सकता है (म्यूजिकस 1988)। कक्ष टॉप्लिट्ज़ मैट्रिसेस सिग्नल प्रोसेसिंग एल्गोरिदम में स्वाभाविक रूप से उत्पन्न होते हैं जब कई सिग्नल स्ट्रीम (उदाहरण के लिए, सिस्टम विश्लेषण # सिस्टम सिस्टम की विशेषता) या साइक्लो-स्टेशनरी सिग्नल से निपटते हैं।
 == यह भी देखें ==
@@ Line 229: / Line 226: @@
 == टिप्पणियाँ ==
 {{reflist}}
 == संदर्भ ==
@@ Line 235: / Line 231: @@
 * Levinson, N. (1947). "The Wiener RMS error criterion in filter design and prediction." ''J. Math. Phys.'', v. 25, pp.&nbsp;261–278.
 * Durbin, J. (1960). "The fitting of time series models." ''Rev. Inst. Int. Stat.'', v. 28, pp.&nbsp;233–243.
-* Trench, W. F. (1964).  "An algorithm for the inversion of finite Toeplitz matrices."  ''J. Soc. Indust. Appl. Math.'', v. 12, pp.&nbsp;515–522.
+* Trench, W. F. (1964). "An algorithm for the inversion of finite टोएप्लिट्ज़ matrices." ''J. Soc. Indust. Appl. Math.'', v. 12, pp.&nbsp;515–522.
-* Musicus, B. R. (1988). "Levinson and Fast Choleski Algorithms for Toeplitz and Almost Toeplitz Matrices." ''RLE TR'' No. 538, MIT. [http://dspace.mit.edu/bitstream/1721.1/4954/1/RLE-TR-538-20174000.pdf]
+* Musicus, B. R. (1988). "Levinson and Fast Choleski Algorithms for टोएप्लिट्ज़ and Almost टोएप्लिट्ज़ Matrices." ''RLE TR'' No. 538, MIT. [http://dspace.mit.edu/bitstream/1721.1/4954/1/RLE-TR-538-20174000.pdf]
 * Delsarte, P. and Genin, Y. V. (1986). "The split Levinson algorithm." ''IEEE Transactions on Acoustics, Speech, and Signal Processing'', v. ASSP-34(3), pp.&nbsp;470–478.
 '''Further work'''
 *{{cite journal | last1 = Bojanczyk | first1 = A.W. | last2 = Brent | first2 = R.P. | last3 = De Hoog | first3 = F.R. | last4 = Sweet | first4 = D.R. | year = 1995 | title = On the stability of the Bareiss and related Toeplitz factorization algorithms | journal = [[SIAM Journal on Matrix Analysis and Applications]] | volume = 16 | pages = 40–57 | doi = 10.1137/S0895479891221563 | arxiv = 1004.5510 | s2cid = 367586 }}
 *[[Richard P. Brent|Brent R.P.]] (1999), "Stability of fast algorithms for structured linear systems", ''Fast Reliable Algorithms for Matrices with Structure'' (editors—T. Kailath, A.H. Sayed), ch.4 ([[Society for Industrial and Applied Mathematics|SIAM]]).
-* Bunch, J. R. (1985). "Stability of methods for solving Toeplitz systems of equations." ''SIAM J. Sci. Stat. Comput.'', v. 6, pp.&nbsp;349–364. [https://doi.org/10.1137/0906025]
+* Bunch, J. R. (1985). "Stability of methods for solving टोएप्लिट्ज़ systems of equations." ''SIAM J. Sci. Stat. Comput.'', v. 6, pp.&nbsp;349–364. [https://doi.org/10.1137/0906025]
 *{{cite journal | last = Krishna | first = H. |author2=Wang, Y.  | title = The Split Levinson Algorithm is weakly stable | journal = [[SIAM Journal on Numerical Analysis]] | volume = 30 | issue = 5 | pages = 1498–1508 | date = 1993 | url = http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SJNAAM000030000005001498000001&idtype=cvips&gifs=yes | doi = 10.1137/0730078}}
 '''Summaries'''
 * Bäckström, T. (2004). "2.2. Levinson–Durbin Recursion." ''Linear Predictive Modelling of Speech – Constraints and Line Spectrum Pair Decomposition.'' Doctoral thesis. Report no. 71 / Helsinki University of Technology, Laboratory of Acoustics and Audio Signal Processing. Espoo, Finland. [http://lib.tkk.fi/Diss/2004/isbn9512269473/isbn9512269473.pdf]
-* Claerbout, Jon F. (1976). "Chapter 7 – Waveform Applications of Least-Squares." ''Fundamentals of Geophysical Data Processing.''  Palo Alto: Blackwell Scientific Publications. [https://web.archive.org/web/20060921204908/http://sep.stanford.edu/oldreports/fgdp2/fgdp_07.pdf]
+* Claerbout, Jon F. (1976). "Chapter 7 – Waveform Applications of Least-Squares." ''Fundamentals of Geophysical Data Processing.'' Palo Alto: Blackwell Scientific Publications. [https://web.archive.org/web/20060921204908/http://sep.stanford.edu/oldreports/fgdp2/fgdp_07.pdf]
 *{{Citation |last1=Press|first1=WH|last2=Teukolsky|first2=SA|last3=Vetterling|first3=WT|last4=Flannery|first4=BP|year=2007|title=Numerical Recipes: The Art of Scientific Computing|edition=3rd|publisher=Cambridge University Press| publication-place=New York|isbn=978-0-521-88068-8|chapter=Section 2.8.2. Toeplitz Matrices|chapter-url=http://apps.nrbook.com/empanel/index.html?pg=96}}
-* Golub, G.H., and Loan, C.F. Van (1996). "Section 4.7 : Toeplitz and related Systems" ''Matrix Computations'', Johns Hopkins University Press
+* Golub, G.H., and Loan, C.F. Van (1996). "Section 4.7 : टोएप्लिट्ज़ and related Systems" ''Matrix Computations'', Johns Hopkins University Press
 [[Category: मैट्रिसेस]] [[Category: संख्यात्मक विश्लेषण]]

Anonymous

Search

लेविंसन रिकर्सन: Difference between revisions

Namespaces

More

Page actions

Revision as of 09:01, 28 July 2023

Contents

व्युत्पत्ति

पृष्ठभूमि

परिचयात्मक चरण

पश्च सदिश प्राप्त करना

पश्च सदिश का उपयोग करना

कक्ष लेविंसन एल्गोरिदम

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

लेविंसन रिकर्सन: Difference between revisions

Revision as of 09:01, 28 July 2023

व्युत्पत्ति

पृष्ठभूमि

परिचयात्मक चरण

पश्च सदिश प्राप्त करना

पश्च सदिश का उपयोग करना

कक्ष लेविंसन एल्गोरिदम

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories