Рекурсия Левенсона-Дурбина: алгоритм для топлицевых матриц
Levinson recursion
Рекурсия Левинсона-Дурбина: быстрый алгоритм для решения уравнений с матрицами Топлица. Эффективнее метода Гаусса, но чувствительна к ошибкам округления.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Рекурсия Левинсона или рекурсия Левинсона-Дурбина — это процедура в линейной алгебре для рекурсивного вычисления решения уравнения, включающего матрицу Топлица. Алгоритм выполняется за время O(n), что является значительным улучшением по сравнению с исключением Гаусса-Жордана, которое выполняется за Θ(n³). Алгоритм Левинсона-Дурбина был впервые предложен Норманом Левинсоном в 1947 году, улучшен Джеймсом Дурбином в 1960 году, а затем оптимизирован до 4n² и затем 3n² умножений соответственно У. Ф. Тренчем и С. Зохаром. Другие методы обработки данных включают разложение Шура и разложение Холецкого. По сравнению с ними рекурсия Левинсона (особенно разделенная рекурсия Левинсона) обычно быстрее в вычислительном плане, но более чувствительна к вычислительным неточностям, таким как ошибки округления. Алгоритм Барейса для матриц Топлица (не следует путать с общим алгоритмом Барейса) работает примерно так же быстро, как рекурсия Левинсона, но использует O(n²) памяти, в то время как рекурсия Левинсона использует только O(n) памяти. Однако алгоритм Барейса численно устойчив, в то время как рекурсия Левинсона в лучшем случае лишь слабо устойчива (то есть демонстрирует численную устойчивость для хорошо обусловленных линейных систем). Новые алгоритмы, называемые асимптотически быстрыми или иногда сверхбыстрыми алгоритмами Топлица, могут решать за Θ(n logᵖ n) для различных p (например, 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.