Левинсон-Дурбин рекурсиясы: Топлиц матрицаларын шешу алгоритмі
Levinson recursion
Линейлік алгебрадағы Левинсон рекурсиясы – Toeplitz матрицасын шешуге арналған тиімді әдіс. Гаусс-Жорданмен салыстырғанда жылдам, бірақ қателерге сезімтал.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Левинсон рекурсиясы немесе Левинсон-Дурбин рекурсиясы — Топлиц матрицасы бар теңдеудің шешімін рекурсивті есептеуге арналған сызықтық алгебрадағы процедура. Алгоритм [[Big O нотациялық уақыты]]нда жұмыс істейді, бұл Гаусс-Жорданды жоюға қарағанда үлкен жетістік, себебі ол Θ(n³) уақытында жұмыс істейді. Левинсон-Дурбин алгоритмін алғаш рет 1947 жылы Норман Левинсон ұсынды, 1960 жылы Джеймс Дурбин жетілдірді, ал кейін В. Ф. Тренч және С. Зохар оны сәйкесінше 4n² және 3n² көбейтуге дейін жетілдірді. Деректерді өңдеудің басқа әдістеріне Шур ыдырауы және Чолески ыдырауы жатады. Бұлармен салыстырғанда Левинсон рекурсиясы (әсіресе бөлінген Левинсон рекурсиясы) есептеу жағынан жылдам, бірақ дөңгелектеу қатесі сияқты есептеулердегі қателерге сезімтал. Топлиц матрицалары үшін Барейсс алгоритмі (жалпы Барейсс алгоритмімен шатастырмау керек) Левинсон рекурсиясымен шамамен бірдей жылдамдықпен жұмыс істейді, бірақ ол O(n²) кеңістік алады, ал Левинсон рекурсиясына тек O(n) кеңістік жеткілікті. Барейсс алгоритмі сандық тұрақты, ал Левинсон рекурсиясы ең жақсы жағдайда ғана әлсіз тұрақты (яғни, жақсы шартталған сызықтық жүйелер үшін сандық тұрақтылық көрсетеді). Жаңа алгоритмдер, асимптотикалық жылдам немесе кейде супержедел Топлиц алгоритмдері деп аталады, әртүрлі p мәндері үшін Θ(n logᵖn) уақытында шешім таба алады (мысалы, p = 2, p = 3). Левинсон рекурсиясы бірнеше себепке байланысты танымал: біріншіден, оны салыстырмалы түрде түсіну оңай; екіншіден, ол кішкентай n үшін супержедел алгоритмнен жылдам болуы мүмкін (әдетте n < 256).
Levinson recursion or Levinson–Durbin recursion is a procedure in linear algebra to recursively calculate the solution to an equation involving a Toeplitz matrix. The algorithm runs in [[Big O notation time, which is a strong improvement over Gauss–Jordan elimination, which runs in Θ(n3). The Levinson–Durbin algorithm was proposed first by Norman Levinson in 1947, improved by James Durbin in 1960, and subsequently improved to 4n^(2) and then 3n^(2) multiplications by W. F. Trench and S. Zohar, respectively. Other methods to process data include Schur decomposition and Cholesky decomposition. In comparison to these, Levinson recursion (particularly split Levinson recursion) tends to be faster computationally, but more sensitive to computational inaccuracies like round off errors. The Bareiss algorithm for Toeplitz matrices (not to be confused with the general Bareiss algorithm) runs about as fast as Levinson recursion, but it uses O(n^(2)) space, whereas Levinson recursion uses only O(n) space. The Bareiss algorithm, though, is numerically stable, whereas Levinson recursion is at best only weakly stable (i. e. it exhibits numerical stability for well conditioned linear systems). Newer algorithms, called asymptotically fast or sometimes superfast Toeplitz algorithms, can solve in Θ(n log^(p)n) for various p (e. g. p = 2, p = 3 ). Levinson recursion remains popular for several reasons; for one, it is relatively easy to understand in comparison; for another, it can be faster than a superfast algorithm for small n (usually n < 256).
Блок Левинсон алгоритмі
Егер M қатаң Топлицтік болмаса, бірақ блоктық Топлицтік болса, Левинсон рекурсиясын блоктық Топлицтік матрицаны матрицалық элементтері бар Топлицтік матрица ретінде қарастыру арқылы шамамен осылай алуға болады (Musicus 1988). Блоктық Топлицтік матрицалары сигналдарды өңдеу алгоритмдерінде көптеген сигнал ағындарымен (мысалы, MIMO жүйелерінде) немесе циклдік стационарлық сигналдармен жұмыс істегенде естемелі түрде туындайды.
If M is not strictly Toeplitz, but block Toeplitz, the Levinson recursion can be derived in much the same way by regarding the block Toeplitz matrix as a Toeplitz matrix with matrix elements (Musicus 1988). Block Toeplitz matrices arise naturally in signal processing algorithms when dealing with multiple signal streams (e. g., in MIMO systems) or cyclo stationary signals.