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

Рекурсия Левинсона или рекурсия Левинсона-Дурбина — это процедура в линейной алгебре , позволяющая рекурсивно вычислить решение уравнения, включающего матрицу Теплица . Алгоритм Θ за $n (работает 2)$ время, что является значительным улучшением по сравнению с методом исключения Гаусса–Жордана , который работает за Θ( n ³).

Алгоритм Левинсона-Дурбина был впервые предложен Норманом Левинсоном в 1947 году, улучшен Джеймсом Дурбином в 1960 году и впоследствии улучшен до $4 n 2$ а затем $3 н 2$ умножения У. Ф. Тренча и С. Зохара соответственно.

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

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

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

Вывод [ править ]

Предыстория [ править ]

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

\mathbf {M} \,{\vec {x}}={\vec {y}}.

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

В рамках этой статьи ê _i — это вектор, полностью состоящий из нулей, за исключением i -го места, которое содержит значение единицы. Его длина будет неявно определяться окружающим контекстом. Термин N относится к ширине приведенной выше матрицы — M — размера N × N. матрица Наконец, в этой статье верхние индексы относятся к индуктивному индексу , тогда как нижние индексы обозначают индексы. Например (и определение) в этой статье матрица T ^н — это матрица размера n × n , которая копирует верхний левый размера n × n блок из M , то есть T ^н_{ij знак} равно M _ij .

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

\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}.

Затем ^й «обратный вектор» ${\vec {b}}^{n}$ определяется аналогично; это вектор длины n, который удовлетворяет:

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

Важное упрощение может произойти, когда M является симметричной матрицей ; то эти два вектора связаны соотношением b ^н_я = ж ^н_{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}}.

Идя от Т ^{п -1} до Т ^н, дополнительный столбец, добавленный в матрицу, не искажает решение, когда для расширения прямого вектора используется ноль. дополнительная строка Однако добавленная в матрицу исказила решение; и это создало нежелательный член ошибки ε _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}}.

Если α и β выбраны так, что правая часть дает ê ₁ или ê _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].

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

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

{\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 не является строго Теплицем, а блочным Теплицем, рекурсия Левинсона может быть получена почти таким же способом, рассматривая блочную матрицу Теплица как матрицу Теплица с матричными элементами (Musicus 1988). Блочные матрицы Теплица естественным образом возникают в алгоритмах обработки сигналов при работе с несколькими потоками сигналов (например, в системах MIMO ) или циклостационарными сигналами.

См. также [ править ]

Примечания [ править ]

^ Боянчик и др. (1995).
^ Брент (1999).
^ Кришна и Ван (1993).
^ «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 25 марта 2012 г. Проверено 1 апреля 2013 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )
^ «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 15 ноября 2009 г. Проверено 28 апреля 2009 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )
^ «Архивная копия» (PDF) . saaz.cs.gsu.edu . Архивировано из оригинала (PDF) 18 апреля 2007 года . Проверено 12 января 2022 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )
^ «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 5 сентября 2006 г. Проверено 15 августа 2006 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )

Ссылки [ править ]

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

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

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

Боянчик, А.В.; Брент, РП; Де Хоог, Франция; Сладкий, ДР (1995). «Об устойчивости алгоритмов факторизации Барейсса и связанных с ним Теплица». Журнал SIAM по матричному анализу и приложениям . 16 : 40–57. arXiv : 1004.5510 . дои : 10.1137/S0895479891221563 . S2CID 367586 .
Брент Р.П. (1999), «Стабильность быстрых алгоритмов для структурированных линейных систем», Быстрые надежные алгоритмы для матриц со структурой (редакторы — Т. Кайлат, А. Х. Сайед), глава 4 ( SIAM ).
Банч, младший (1985). «Устойчивость методов решения систем уравнений Теплица». СИАМ J. Sci. Стат. Вычислить. , т. 6, стр. 349–364. [2]
Кришна, Х.; Ван, Ю. (1993). «Алгоритм Сплит-Левинсона слабо устойчив» . SIAM Journal по численному анализу . 30 (5): 1498–1508. дои : 10.1137/0730078 .

Резюме

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

[1] Боянчик и др. (1995).

[2] Брент (1999).

[3] Кришна и Ван (1993).

[4] «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 25 марта 2012 г. Проверено 1 апреля 2013 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )

[5] «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 15 ноября 2009 г. Проверено 28 апреля 2009 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )

[6] «Архивная копия» (PDF) . saaz.cs.gsu.edu . Архивировано из оригинала (PDF) 18 апреля 2007 года . Проверено 12 января 2022 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )

[7] «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 5 сентября 2006 г. Проверено 15 августа 2006 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )

[1]

[2]

[3]

[4]

[5]

[6]

[7]