लेविंसन रिकर्सन

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

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

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

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

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

व्युत्पत्ति

पृष्ठभूमि

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

$\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)। कक्ष टॉप्लिट्ज़ मैट्रिसेस सिग्नल प्रोसेसिंग एल्गोरिदम में स्वाभाविक रूप से उत्पन्न होते हैं जब कई सिग्नल स्ट्रीम (उदाहरण के लिए, सिस्टम विश्लेषण # सिस्टम सिस्टम की विशेषता) या साइक्लो-स्टेशनरी सिग्नल से निपटते हैं।

यह भी देखें

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

संदर्भ

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