WikiDer > Рекурсия Левинсона

Рекурсия Левинсона или же Рекурсия Левинсона – Дурбина это процедура в линейная алгебра к рекурсивно вычислить решение уравнения, содержащего Матрица Теплица. В алгоритм вбегает Θ(п²) время, что значительно лучше Исключение Гаусса – Жордана, которая выполняется в Θ (п³).

Алгоритм Левинсона – Дурбина был впервые предложен Норман Левинсон в 1947 г. Джеймс Дурбин в 1960 году, а затем улучшено до 4п² а потом 3п² умножения на W. F. Trench и S. Zohar, соответственно.

Другие методы обработки данных включают: Разложение Шура и Разложение Холецкого. По сравнению с ними рекурсия Левинсона (в частности, разделенная рекурсия Левинсона) имеет тенденцию быть более быстрой в вычислительном отношении, но более чувствительна к вычислительным неточностям, таким как ошибки округления.

Алгоритм Барейса для Матрицы Теплица (не путать с общим Алгоритм Барейса) работает примерно так же быстро, как рекурсия Левинсона, но использует О(п²), тогда как рекурсия Левинсона использует только О(п) Космос. Однако алгоритм Барейсса численно стабильный,^[1][2] тогда как рекурсия Левинсона в лучшем случае лишь слабо устойчива (т. е. демонстрирует численную устойчивость для хорошо кондиционированный линейные системы).^[3]

Новые алгоритмы, называемые асимптотически быстрый или иногда сверх быстрый Алгоритмы Теплица, можно решить за Θ (п бревно^пп) для различных п (например. п = 2,^[4][5] п = 3 ^[6]). Рекурсия Левинсона остается популярной по нескольким причинам; во-первых, это относительно легко понять в сравнении; с другой стороны, он может быть быстрее сверхбыстрого алгоритма для небольших п (обычно п < 256).^[7]

Вывод

Фон

Матричные уравнения имеют вид:

${ displaystyle mathbf {M} { vec {x}} = { vec {y}}.}$

Алгоритм Левинсона – Дурбина может использоваться для любого такого уравнения, если M это известный Матрица Теплица с ненулевой главной диагональю. Здесь ${ displaystyle { vec {y}}}$ это известный вектор, и ${ displaystyle { vec {x}}}$ неизвестный вектор чисел Икс_я еще предстоит определить.

Ради этой статьи, ê_я представляет собой вектор, полностью состоящий из нулей, за исключением его я-е место, где находится значение один. Его длина будет неявно определяться окружающим контекстом. Период, термин N относится к ширине матрицы выше - M является N×N матрица. Наконец, в этой статье верхние индексы относятся к индекс индукции, а нижние индексы обозначают индексы. Например (и определение) в этой статье матрица Т^п является п × п матрица, которая копирует верхний левый п × п блокировать от M - то есть, Т^п_ij = M_ij.

Т^п также является матрицей Теплица; это означает, что это можно записать как:

${ displaystyle 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}}.}$

Вступительные шаги

Алгоритм выполняется в два этапа. На первом этапе два набора векторов, называемые вперед и назад векторы, установлены. Прямые векторы используются, чтобы помочь получить набор обратных векторов; тогда их можно сразу выбросить. Обратные векторы необходимы для второго шага, где они используются для построения желаемого решения.

Рекурсия Левинсона – Дурбина определяет п^th "прямой вектор", обозначенный ${ displaystyle { vec {f}} ^ {n}}$, как вектор длины п который удовлетворяет:

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

В п^th "обратный вектор" ${ displaystyle { vec {b}} ^ {n}}$ определяется аналогично; это вектор длины п который удовлетворяет:

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

Важное упрощение может произойти, когда M это симметричная матрица; то два вектора связаны соотношением б^п_я = ж^п_п+1−я- то есть они являются перестановками друг друга. Это может сэкономить дополнительные вычисления в этом особом случае.

Получение обратных векторов

Даже если матрица не симметрична, то п^th прямой и обратный вектор можно найти из векторов длины п - 1 следующим образом. Во-первых, прямой вектор может быть расширен нулем, чтобы получить:

${ displaystyle 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 epsilon _ {f} ^ {n} end {bmatrix}}. }$

При переходе от Т^п−1 к Т^п, дополнительные столбец добавление к матрице не нарушает решение, когда ноль используется для расширения прямого вектора. Однако дополнительные ряд добавлен в матрицу имеет возмутил решение; и он создал нежелательную ошибку ε_ж что происходит на последнем месте. Вышеприведенное уравнение дает ему значение:

${ displaystyle epsilon _ {f} ^ {n} = sum _ {i = 1} ^ {n-1} M_ {ni} f_ {i} ^ {n-1} = сумма _ {i = 1} ^ {n-1} t_ {ni} f_ {i} ^ {n-1}.}$

Эта ошибка будет вскоре возвращена и устранена из нового прямого вектора; но сначала обратный вектор должен быть расширен аналогичным образом (хотя и в обратном направлении). Для обратного вектора

${ displaystyle 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} epsilon _ {b} ^ {n} 0 vdots 0 1 end {bmatrix}}.}$

Как и раньше, дополнительный столбец, добавленный к матрице, не нарушает этот новый обратный вектор; но дополнительная строка делает. Здесь у нас еще одна нежелательная ошибка ε_б со значением:

${ displaystyle epsilon _ {b} ^ {n} = sum _ {i = 2} ^ {n} M_ {1i} b_ {i-1} ^ {n-1} = сумма _ {i = 1} ^ {n-1} t _ {- i} b_ {i} ^ {n-1}. }$

Эти два члена ошибки могут использоваться для формирования прямого и обратного векторов более высокого порядка, описанных ниже. Учитывая линейность матриц, для всех ${ Displaystyle ( альфа, бета)}$:

${ displaystyle 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 epsilon _ {f} end {bmatrix}} + beta { begin {bmatrix} epsilon _ {b} 0 vdots 0 1 end {bmatrix}}.}$

Если α и β выбраны так, что правая часть дает ê₁ или же ê_п, то величина в скобках будет соответствовать определению п^th прямой или обратный вектор соответственно. Если выбраны альфа и бета, векторная сумма в скобках будет простой и даст желаемый результат.

Чтобы найти эти коэффициенты, ${ displaystyle alpha _ {f} ^ {n}}$, ${ displaystyle beta _ {f} ^ {n}}$ таковы, что:

${ displaystyle { 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}}}$

и соответственно ${ displaystyle alpha _ {b} ^ {n}}$, ${ displaystyle beta _ {b} ^ {n}}$ таковы, что:

${ displaystyle { 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}}.}$

Умножив оба предыдущих уравнения на ${ displaystyle { mathbf {T}} ^ {n}}$ получается следующее уравнение:

${ displaystyle { begin {bmatrix} 1 & epsilon _ {b} ^ {n} 0 & 0 vdots & vdots 0 & 0 epsilon _ {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}}.}$

Теперь, когда все нули в середине двух векторов выше игнорируются и сворачиваются, остается только следующее уравнение:

${ displaystyle { begin {bmatrix} 1 & epsilon _ {b} ^ {n} epsilon _ {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) новые прямые и обратные векторы:

${ displaystyle { vec {f}} ^ {n} = {1 over {1- epsilon _ {b} ^ {n} epsilon _ {f} ^ {n}}} { begin {bmatrix} { vec {f}} ^ {n-1} 0 end {bmatrix}} - { epsilon _ {f} ^ {n} over {1- epsilon _ {b} ^ {n} epsilon _ {f} ^ {n}}} { begin {bmatrix} 0 { vec {b}} ^ {n-1} end {bmatrix}}}$

${ displaystyle { vec {b}} ^ {n} = {1 over {1- epsilon _ {b} ^ {n} epsilon _ {f} ^ {n}}} { begin {bmatrix} 0 { vec {b}} ^ {n-1} end {bmatrix}} - { epsilon _ {b} ^ {n} over {1- epsilon _ {b} ^ {n} epsilon _ {f} ^ {n}}} { begin {bmatrix} { vec {f}} ^ {n-1} 0 end {bmatrix}}.}$

Выполнение этих векторных суммирований дает п^th прямые и обратные векторы от предыдущих. Остается только найти первый из этих векторов, а затем некоторые быстрые суммы и умножения дают оставшиеся. Первые прямые и обратные векторы просто:

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

Использование обратных векторов

Вышеуказанные шаги дают N обратные векторы для M. Отсюда более произвольное уравнение:

${ displaystyle { vec {y}} = mathbf {M} { vec {x}}.}$

Решение может быть построено тем же рекурсивным способом, что и обратные векторы. Соответственно, ${ displaystyle { vec {x}}}$ должен быть обобщен на последовательность промежуточных продуктов ${ displaystyle { vec {x}} ^ {n}}$, так что ${ displaystyle { vec {x}} ^ {N} = { vec {x}}}$.

Затем решение строится рекурсивно с учетом того, что если

${ displaystyle 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}}.}$

Затем снова добавив ноль и определив при необходимости константу ошибки:

${ Displaystyle 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} epsilon _ {x} ^ {n-1} end {bmatrix}}.}$

Затем мы можем использовать п^th обратный вектор, чтобы исключить член ошибки и заменить его нужной формулой следующим образом:

${ displaystyle 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} - epsilon _ {x} ^ {n-1}) { vec {b}} ^ {n} right) = { begin {bmatrix} y_ {1} y_ {2} vdots y_ {n-1} y_ {n} end {bmatrix}}.}$

Расширение этого метода до п = N дает решение ${ displaystyle { vec {x}}}$.

На практике эти шаги часто выполняются одновременно с остальной частью процедуры, но они образуют единое целое и заслуживают того, чтобы их рассматривали как отдельный шаг.

Блокировать алгоритм Левинсона

Если M не совсем Теплиц, но блокировать Теплица, рекурсия Левинсона может быть получена почти таким же образом, если рассматривать блочную матрицу Теплица как матрицу Теплица с матричными элементами (Musicus 1988). Блочные матрицы Теплица возникают естественным образом в алгоритмах обработки сигналов при работе с несколькими потоками сигналов (например, в MIMO системы) или циклостационарные сигналы.

Смотрите также

• Расщепленная рекурсия Левинсона
• Линейное предсказание
• Авторегрессионная модель

Примечания

Рекомендации

Определение источников

• Левинсон, Н. (1947). «Критерий ошибки Wiener RMS при проектировании и прогнозировании фильтров». J. Math. Phys., v. 25, pp. 261–278.
• Дурбин, Дж. (1960). «Подгонка моделей временных рядов». Rev. Inst. Int. Стат., v. 28, pp. 233–243.
• Тренч, У. Ф. (1964). «Алгоритм обращения конечных тёплицевых матриц». J. Soc. Indust. Appl. Математика., т. 12, с. 515–522.
• Musicus, Б. Р. (1988). «Левинсон и быстрые алгоритмы Холецкого для теплицевых и почти теплицевых матриц». RLE TR № 538, Массачусетский технологический институт. [1]
• Дельсарт П. и Генин Ю. В. (1986). «Сплит-алгоритм Левинсона». Транзакции IEEE по акустике, речи и обработке сигналов, v. ASSP-34 (3), pp. 470–478.

Дальнейшая работа

• Bojanczyk, A.W .; Brent, R.P .; De Hoog, F.R .; Sweet, D.R. (1995). «Об устойчивости алгоритмов факторизации Барейса и родственных ему алгоритмов Теплица». Журнал SIAM по матричному анализу и приложениям. 16: 40–57. arXiv:1004.5510. Дои:10.1137 / S0895479891221563.
• Брент Р.П. (1999), «Устойчивость быстрых алгоритмов для структурированных линейных систем», Быстрые надежные алгоритмы для матриц со структурой (редакторы - Т. Кайлат, А. Х. Сайед), гл.4 (СИАМ).
• Банч, Дж. Р. (1985). «Устойчивость методов решения тёплицевых систем уравнений». SIAM J. Sci. Стат. Comput., v. 6, pp. 349–364. [2]
• Кришна, Х .; Ван, Ю. (1993). «Алгоритм Сплит Левинсона слабо устойчив». Журнал SIAM по численному анализу. 30 (5): 1498–1508. Дои:10.1137/0730078.

Резюме

• Бэкстрём, Т. (2004). «2.2. Рекурсия Левинсона – Дурбина». Линейное прогнозирующее моделирование речи - ограничения и разложение пар линейного спектра. Докторская диссертация. № отчета 71 / Технологический университет Хельсинки, лаборатория акустики и обработки аудиосигналов. Эспоо, Финляндия. [3]
• Клаербут, Джон Ф. (1976). «Глава 7 - Применение формы сигнала наименьших квадратов». Основы обработки геофизических данных. Пало-Альто: Научные публикации Блэквелла. [4]
• Нажмите, WH; Теукольский С.А.; Феттерлинг, штат Вашингтон; Фланнери, BP (2007), «Раздел 2.8.2. Теплицевые матрицы», Числовые рецепты: искусство научных вычислений (3-е изд.), Нью-Йорк: Издательство Кембриджского университета, ISBN 978-0-521-88068-8
• Голуб Г.Х., Лоан К.Ф. Ван (1996). «Раздел 4.7: Теплиц и родственные системы» Матричные вычисления, Издательство Университета Джона Хопкинса