Рекурсия Левинсона или рекурсия Левинсона – Дурбина - это процедура в линейной алгебре для рекурсивного вычисления решения уравнения, содержащего матрицу Теплица . В алгоритме работает в & thetas ; ( п 2 ) время, что является сильным улучшением по сравнению с Гаусс-Жордан , который работает в Q ( п 3 ).
Алгоритм Левинсона – Дарбина был впервые предложен Норманом Левинсоном в 1947 году, усовершенствован Джеймсом Дурбином в 1960 году, а затем улучшен до умножений 4 n 2, а затем 3 n 2 У. Ф. Тренчем и С. Зохаром, соответственно.
Другие методы обработки данных включают разложение Шура и разложение Холецкого . По сравнению с ними рекурсия Левинсона (особенно разделенная рекурсия Левинсона) имеет тенденцию быть более быстрой в вычислительном отношении, но более чувствительна к неточностям вычислений, таким как ошибки округления .
Алгоритм Барейса для матриц Теплица (не путать с общим алгоритмом Барейса ) работает примерно так же быстро, как рекурсия Левинсона, но он использует пространство O ( n 2 ) , тогда как рекурсия Левинсона использует только пространство O ( n ). Алгоритм Bareiss, однако, является численно стабильным , [1] [2] , тогда как Левинсон рекурсия в лучшем случае лишь слабо устойчивая (т.е. он обладает числовой стабильностью для хорошо кондиционированных линейных систем). [3]
Новые алгоритмы, называемые асимптотически быстрыми или иногда сверхбыстрыми алгоритмами Теплица, могут решать за Θ ( n log p n ) для различных p (например, p = 2, [4] [5] p = 3 [6] ). Рекурсия Левинсона остается популярной по нескольким причинам; во-первых, это относительно легко понять в сравнении; с другой стороны, он может быть быстрее сверхбыстрого алгоритма для малых n (обычно n <256). [7]
Вывод
Задний план
Матричные уравнения имеют вид:
Алгоритм Левинсона – Дарбина может использоваться для любого такого уравнения, если M - известная матрица Теплица с ненулевой главной диагональю. Здесь- известный вектор , и- неизвестный вектор чисел x i, который еще предстоит определить.
В данной статье ê i - это вектор, полностью состоящий из нулей, за исключением его i- го места, которое содержит значение один. Его длина будет неявно определяться окружающим контекстом. Термин N относится к ширине указанной выше матрицы - M - это матрица N × N. Наконец, в этой статье верхние индексы относятся к индуктивному индексу , тогда как нижние индексы обозначают индексы. Например (и определение), в этой статье матрица T n - это матрица размера n × n, которая копирует верхний левый блок размером n × n из M, то есть T n ij = M ij .
T n также является матрицей Теплица; это означает, что это можно записать как:
Вступительные шаги
Алгоритм состоит из двух шагов. На первом этапе устанавливаются два набора векторов, называемых прямым и обратным векторами. Прямые векторы используются, чтобы помочь получить набор обратных векторов; тогда их можно сразу выбросить. Обратные векторы необходимы для второго шага, где они используются для построения желаемого решения.
Рекурсия Левинсона – Дурбина определяет n- й «прямой вектор», обозначенный, как вектор длины n, который удовлетворяет:
П е «вектора обратного»определяется аналогично; это вектор длины n, который удовлетворяет:
Важное упрощение может произойти, когда M - симметричная матрица ; тогда два вектора связаны соотношением b n i = f n n + 1− i - то есть они переворачивают строки друг друга. Это может сэкономить дополнительные вычисления в этом особом случае.
Получение обратных векторов
Даже если матрица не является симметричной, то n- й прямой и обратный вектор можно найти из векторов длины n - 1 следующим образом. Во-первых, прямой вектор может быть расширен нулем, чтобы получить:
При переходе от T n −1 к T n дополнительный столбец, добавленный к матрице, не нарушает решение, когда ноль используется для расширения прямого вектора. Однако дополнительная строка, добавленная к матрице , нарушила решение; и это создало нежелательный член ошибки ε f, который встречается на последнем месте. Вышеприведенное уравнение дает ему значение:
Эта ошибка будет вскоре возвращена и устранена из нового прямого вектора; но сначала обратный вектор должен быть расширен аналогичным образом (хотя и в обратном направлении). Для обратного вектора
Как и раньше, дополнительный столбец, добавленный к матрице, не нарушает этот новый обратный вектор; но дополнительная строка делает. Здесь у нас есть еще одна нежелательная ошибка ε b со значением:
Эти два члена ошибки могут быть использованы для формирования прямого и обратного векторов более высокого порядка, описанных ниже. Учитывая линейность матриц, для всех:
Если α и β выбраны так, что правая часть дает ê 1 или ê n , то величина в скобках будет соответствовать определению n- го прямого или обратного вектора, соответственно. Если выбраны альфа и бета, векторная сумма в скобках проста и дает желаемый результат.
Чтобы найти эти коэффициенты, , таковы, что:
и соответственно , таковы, что:
Умножив оба предыдущих уравнения на получается следующее уравнение:
Теперь, когда все нули в середине двух векторов выше игнорируются и сворачиваются, остается только следующее уравнение:
После решения этих задач (с использованием обратной формулы матрицы Крамера 2 × 2) новые прямые и обратные векторы:
Выполнение этих векторных суммирований дает n- й прямой и обратный векторы из предыдущих. Остается только найти первый из этих векторов, а затем несколько быстрых сумм и умножений дают оставшиеся. Первые прямые и обратные векторы просто:
Использование обратных векторов
Вышеуказанные шаги дают N обратные векторы для М . Отсюда более произвольное уравнение:
Решение может быть построено тем же рекурсивным способом, что и обратные векторы. Соответственно, должен быть обобщен на последовательность промежуточных продуктов , так что .
Затем решение строится рекурсивно с учетом того, что если
Затем снова добавив ноль и определив при необходимости константу ошибки:
Затем мы можем использовать n- й обратный вектор, чтобы исключить член ошибки и заменить его желаемой формулой следующим образом:
Продолжение этого метода до n = N дает решение.
На практике эти шаги часто выполняются одновременно с остальной частью процедуры, но они образуют единое целое и заслуживают того, чтобы их рассматривали как отдельный шаг.
Блокировать алгоритм Левинсона
Если M не является строго теплицевым, но блочным теплицем, рекурсия Левинсона может быть получена почти таким же образом, если рассматривать блочную матрицу Теплица как матрицу Теплица с матричными элементами (Musicus 1988). Блочные матрицы Теплица возникают естественным образом в алгоритмах обработки сигналов при работе с множественными потоками сигналов (например, в системах MIMO ) или циклостационарными сигналами.
Смотрите также
- Расщепленная рекурсия Левинсона
- Линейное предсказание
- Авторегрессионная модель
Заметки
- ^ Боянчик и др. (1995).
- ^ Брент (1999).
- ^ Кришна и Ван (1993).
- ^ http://www.maths.anu.edu.au/~brent/pd/rpb143tr.pdf
- ^ «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 15 ноября 2009 года . Проверено 28 апреля 2009 .CS1 maint: заархивированная копия как заголовок ( ссылка )
- ^ https://web.archive.org/web/20070418074240/http://saaz.cs.gsu.edu/papers/sfast.pdf
- ^ http://www.math.niu.edu/~ammar/papers/amgr88.pdf
Рекомендации
Определение источников
- Левинсон, Н. (1947). «Критерий ошибки Wiener RMS при проектировании и прогнозировании фильтров». J. Math. Phys. , v. 25, pp. 261–278.
- Дурбин, Дж. (1960). «Подгонка моделей временных рядов». Rev. Inst. Int. Стат. , т. 28, с. 233–243.
- Тренч, WF (1964). «Алгоритм обращения конечных тёплицевых матриц». J. Soc. Indust. Прил. Математика. , т. 12, с. 515–522.
- Musicus, BR (1988). «Левинсон и быстрые алгоритмы Холецкого для теплицевых и почти теплицевых матриц». RLE TR № 538, MIT. [1]
- Дельсарт П. и Генин Ю.В. (1986). «Сплит-алгоритм Левинсона». IEEE Transactions по акустике, речи и обработке сигналов , v. ASSP-34 (3), стр. 470–478.
Дальнейшая работа
- Боянчик, А.В.; Brent, RP; Де Хуг, Франция; Милый, Д.Р. (1995). «Об устойчивости алгоритмов факторизации Барейса и родственных ему алгоритмов Теплица». Журнал SIAM по матричному анализу и приложениям . 16 : 40–57. arXiv : 1004,5510 . DOI : 10.1137 / S0895479891221563 .
- Брент Р.П. (1999), "Устойчивость быстрых алгоритмов для структурированных линейных систем", Быстрые надежные алгоритмы для матриц со структурой (редакторы - Т. Кайлат, А. Х. Сайед), глава 4 ( SIAM ).
- Банч, младший (1985). «Устойчивость методов решения теплицевых систем уравнений». SIAM J. Sci. Стат. Comput. , т. 6, с. 349–364. [2]
- Кришна, Х .; Ван, Ю. (1993). «Алгоритм Сплит Левинсона слабо устойчив» . Журнал СИАМ по численному анализу . 30 (5): 1498–1508. DOI : 10.1137 / 0730078 .
Резюме
- Бэкстрём, Т. (2004). «2.2. Рекурсия Левинсона – Дурбина». Линейное прогнозирующее моделирование речи - ограничения и разложение пар линейного спектра. Докторская диссертация. № отчета 71 / Хельсинкский технологический университет, лаборатория акустики и обработки аудиосигналов. Эспоо, Финляндия. [3]
- Клаербут, Джон Ф. (1976). «Глава 7 - Применение формы сигнала наименьших квадратов». Основы обработки геофизических данных. Пало-Альто: Научные публикации Блэквелла. [4]
- Нажмите, WH; Теукольский, С.А. Феттерлинг, Вашингтон; Фланнери, Б.П. (2007), «Раздел 2.8.2. Матрицы Теплица» , Численные рецепты: Искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8
- Голуб, Г. Х., и Ссуда, К. Ф. Ван (1996). «Раздел 4.7: Теплиц и родственные системы» Матричные вычисления , Johns Hopkins University Press