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

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

Алгоритм Левинсона – Дурбина был впервые предложен Норманом Левинсоном в 1947 году, улучшен Джеймсом Дурбином в 1960 году, а затем улучшен до 4n, а затем 3n умножений с помощью WF Тренч и С. Зохар соответственно.

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

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

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

Содержание

• 1 Выведение
  • 1.1 Предпосылки
  • 1.2 Вводные шаги
  • 1.3 Получение обратных векторов
  • 1.4 Использование обратные векторы
• 2 Блок алгоритма Левинсона
• 3 См. также
• 4 Примечания
• 5 Ссылки

Вывод

Предпосылки

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

$M\; x\; \to \; =\; y\; \to .\; \{\backslash \; Displaystyle\; \backslash \; mathbf\; \{M\}\; \backslash \; \{\backslash \; vec\; \{x\}\}\; =\; \{\backslash \; vec\; \{y\}\}.\}$

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

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

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

$T\; n\; =\; [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\; ⋮\; ⋮\; ⋮\; \ddots \; ⋮\; tn\; -\; 1\; tn\; -\; 2\; tn\; -\; 3\dots \; t\; 0].\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{T\}\; ^\; \{n\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; t\_\; \{0\}\; t\; \_\; \{-\; 1\}\; t\; \_\; \{-\; 2\}\; \backslash \; dots\; t\; \_\; \{-\; n\; +\; 1\}\; \backslash \backslash \; t\_\; \{1\}\; t\_\; \{0\}\; t\; \_\; \{-\; 1\}\; \backslash \; dots\; t\; \_\; \{-\; n\; +\; 2\}\; \backslash \backslash \; t\_\; \{2\}\; t\_\; \{1\}\; t\_\; \{0\}\; \backslash \; dots\; t\; \_\; \{-\; n\; +\; 3\}\; \backslash \backslash \backslash \; vdots\; \backslash \; vdots\; \backslash \; vdots\; \backslash \; ddots\; \backslash \; vdots\; \backslash \backslash \; t\_\; \{n-1\}\; t\_\; \{n-2\}\; t\_\; \{n-3\}\; \backslash \; dots\; t\_\; \{0\}\; \backslash \; end\; \{bmatrix\}\}.\}$

Вводные шаги

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

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

$T\; nf\; \to \; n\; =\; e\; ^\; 1.\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{T\}\; ^\; \{n\}\; \{\backslash \; vec\; \{f\}\}\; ^\; \{n\}\; =\; \{\backslash \; hat\; \{e\}\}\; \_\; \{1\}.\}$

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

$T\; n\; b\; \to \; n\; =\; e\; ^\; n.\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{T\}\; ^\; \{n\}\; \{\backslash \; vec\; \{b\}\}\; ^\; \{n\}\; =\; \{\backslash \; hat\; \{e\}\}\; \_\; \{n\}.\}$

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

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

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

$T\; n\; [f\; \to \; n\; -\; 1\; 0]\; =\; [t\; -\; n\; +\; 1\; T\; n\; -\; 1\; t\; -\; n\; +\; 2\; ⋮\; tn\; -\; 1\; tn\; -\; 2\; \dots \; T\; 0]\; [f\; \to \; n\; -\; 1\; 0]\; =\; [1\; 0\; ⋮\; 0\; ϵ\; fn].\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{T\}\; ^\; \{n\}\; \{\backslash \; begin\; \{bmatrix\}\; \{\backslash \; vec\; \{f\}\}\; ^\; \{n-1\}\; \backslash \backslash \; 0\; \backslash \backslash \backslash \; end\; \{bmatrix\}\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; \backslash \; \backslash \; \backslash \; t\; \_\; \{-\; n\; +\; 1\}\; \backslash \backslash \backslash \; \backslash \; mathbf\; \{T\}\; ^\; \{n-1\}\; \backslash \; t\; \_\; \{-\; n\; +\; 2\}\; \backslash \backslash \backslash \; \backslash \; \backslash \; \backslash \; vdots\; \backslash \backslash \; t\_\; \{n\; -1\}\; t\_\; \{n-2\}\; \backslash \; dots\; t\_\; \{0\}\; \backslash \backslash \backslash \; end\; \{bmatrix\}\}\; \{\backslash \; begin\; \{bmatrix\}\; \backslash \; \backslash \backslash \; \{\backslash \; vec\; \{f\}\}\; ^\; \{n-1\}\; \backslash \backslash \backslash \; \backslash \; \backslash \; 0\; \backslash \backslash \backslash \; \backslash \backslash \backslash \; end\; \{bmatrix\}\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; 1\; \backslash \backslash \; 0\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; 0\; \backslash \backslash \backslash \; epsilon\; \_\; \{f\}\; ^\; \{n\}\; \backslash \; end\; \{bmatrix\}\}.\; \}$

При переходе от T к T дополнительный столбец, добавленный к матрице, не нарушает решение, когда ноль используется для расширения прямого вектора. Однако дополнительная строка, добавленная к матрице, нарушила решение; и он создал нежелательный член ошибки ε f, который встречается на последнем месте. Приведенное выше уравнение дает ему значение:

$ϵ\; f\; n\; =\; \sum \; i\; =\; 1\; n\; -\; 1\; M\; n\; i\; f\; i\; n\; -\; 1\; =\; \sum \; i\; =\; 1\; n\; -\; 1\; t\; n\; -\; i\; f\; i\; n\; -\; 1.\; \{\backslash \; displaystyle\; \backslash \; epsilon\; \_\; \{f\}\; ^\; \{n\}\; \backslash \; =\; \backslash \; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n-1\}\; \backslash \; M\_\; \{ni\}\; \backslash \; f\_\; \{i\}\; ^\; \{n-1\}\; \backslash \; =\; \backslash \; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n-1\}\; \backslash \; t\_\; \{ni\}\; \backslash \; f\_\; \{i\}\; ^\; \{n-1\}.\}$

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

$T\; n\; [0\; b\; \to \; n\; -\; 1]\; =\; [t\; 0\dots \; t\; -\; n\; +\; 2\; t\; -\; n\; +\; 1\; ⋮\; tn\; -\; 2\; T\; n\; -\; 1\; tn\; -\; 1]\; [0\; b\; \to \; n\; -\; 1]\; =\; [ϵ\; bn\; 0\; ⋮\; 0\; 1].\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{T\}\; ^\; \{n\}\; \{\backslash \; begin\; \{bmatrix\}\; 0\; \backslash \backslash \; \{\backslash \; vec\; \{b\}\}\; ^\; \{n-1\}\; \backslash \backslash \backslash \; end\; \{bmatrix\}\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; t\_\; \{0\}\; \backslash \; dots\; t\; \_\; \{-\; n\; +\; 2\}\; t\; \_\; \{-\; n\; +\; 1\}\; \backslash \backslash \backslash \; vdots\; \backslash \; \backslash \; \backslash \; \backslash \backslash \; t\_\; \{n-2\}\; \backslash \; \backslash \; mathbf\; \{T\}\; ^\; \{n-\; 1\}\; \backslash \; \backslash \backslash \; t\_\; \{n-1\}\; \backslash \; \backslash \; \backslash \; end\; \{bmatrix\}\}\; \{\backslash \; begin\; \{bmatrix\}\; \backslash \; \backslash \backslash \; 0\; \backslash \backslash \backslash \; \backslash \backslash \; \{\backslash \; vec\; \{b\}\}\; ^\; \{n-1\; \}\; \backslash \backslash \backslash \; \backslash \backslash \backslash \; end\; \{bmatrix\}\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; \backslash \; epsilon\; \_\; \{b\}\; ^\; \{n\}\; \backslash \backslash \; 0\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; 0\; \backslash \backslash \; 1\; \backslash \; end\; \{bmatrix\}\}.\}$

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

$ϵ\; b\; n\; =\; \sum \; i\; =\; 2\; n\; M\; 1\; i\; b\; i\; -\; 1\; n\; -\; 1\; =\; \sum \; i\; =\; 1\; n\; -\; 1\; t\; -\; i\; b\; i\; n\; -\; 1.\; \{\backslash \; displaystyle\; \backslash \; epsilon\; \_\; \{b\}\; ^\; \{n\}\; \backslash \; =\; \backslash \; \backslash \; sum\; \_\; \{i\; =\; 2\}\; ^\; \{n\}\; \backslash \; M\_\; \{1i\}\; \backslash \; b\_\; \{i-1\}\; ^\; \{n-1\}\; \backslash \; =\; \backslash \; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n-1\}\; \backslash \; t\; \_\; \{-\; i\}\; \backslash \; b\_\; \{i\}\; ^\; \{n-1\}.\; \backslash \}$

Эти два условия ошибки могут использоваться для формирования форвардных и обратные векторы описываются следующим образом. Используя линейность матриц, для всех $(\alpha ,\; \beta )\; \{\backslash \; displaystyle\; (\backslash \; alpha,\; \backslash \; beta)\}$:

$T\; (\alpha \; [f\; \to \; 0]\; +\; \beta \; [0\; b\; \to ])\; выполняется\; следующее\; тождество.\; =\; \alpha \; [1\; 0\; ⋮\; 0\; ϵ\; f]\; +\; \beta \; [ϵ\; b\; 0\; 0\; 1].\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{T\}\; \backslash \; left\; (\backslash \; alpha\; \{\backslash \; begin\; \{bmatrix\}\; \{\backslash \; vec\; \{f\}\}\; \backslash \backslash \backslash \; \backslash \backslash \; 0\; \backslash \backslash \backslash \; end\; \{bmatrix\}\}\; +\; \backslash \; beta\; \{\backslash \; begin\; \{bmatrix\}\; 0\; \backslash \backslash \backslash \; \backslash \backslash \; \{\backslash \; vec\; \{b\}\}\; \backslash \; end\; \{bmatrix\}\}\; \backslash \; right)\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{bmatrix\}\; 1\; \backslash \backslash \; 0\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; 0\; \backslash \backslash \backslash \; epsilon\; \_\; \{f\}\; \backslash \; \backslash \backslash \; end\; \{bmatrix\}\}\; +\; \backslash \; beta\; \{\backslash \; begin\; \{bmatrix\}\; \backslash \; epsilon\; \_\; \{b\}\; \backslash \backslash \; 0\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; 0\; \backslash \backslash \; 1\; \backslash \; end\; \{bmatrix\}\}.\}$

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

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

$f\; \to \; n\; =\; \alpha \; fn\; [f\; \to \; n\; -\; 1\; 0]\; +\; \beta \; fn\; [0\; b\; \to \; n\; -\; 1]\; \{\backslash \; displaystyle\; \{\backslash \; vec\; \{f\}\}\; ^\; \{n\; \}\; =\; \backslash \; alpha\; \_\; \{f\}\; ^\; \{n\}\; \{\backslash \; begin\; \{bmatrix\}\; \{\backslash \; vec\; \{f\}\}\; ^\; \{n-1\}\; \backslash \backslash \; 0\; \backslash \; end\; \{bmatrix\}\}\; +\; \backslash \; beta\; \_\; \{f\}\; ^\; \{n\; \}\; \{\backslash \; begin\; \{bmatrix\}\; 0\; \backslash \backslash \; \{\backslash \; vec\; \{b\}\}\; ^\; \{n-1\}\; \backslash \; end\; \{bmatrix\}\}\}$

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

$b\; \to \; n\; =\; \alpha \; bn\; [f\; \to \; n\; -\; 1\; 0]\; +\; \beta \; bn\; [0\; b\; \to \; n\; -\; 1].\; \{\backslash \; displaystyle\; \{\backslash \; vec\; \{b\}\}\; ^\; \{n\}\; =\; \backslash \; alpha\; \_\; \{b\}\; ^\; \{n\}\; \{\backslash \; begin\; \{bmatrix\}\; \{\backslash \; vec\; \{f\}\}\; ^\; \{n-1\}\; \backslash \backslash \; 0\; \backslash \; end\; \{\; bmatrix\}\}\; +\; \backslash \; beta\; \_\; \{b\}\; ^\; \{n\}\; \{\backslash \; begin\; \{bmatrix\}\; 0\; \backslash \backslash \; \{\backslash \; vec\; \{b\}\}\; ^\; \{n-1\}\; \backslash \; end\; \{bmatrix\}\}.\}$

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

$[1\; ϵ\; bn\; 0\; 0\; ⋮\; ⋮\; 0\; 0\; ϵ\; fn\; 1]\; [\alpha \; fn\; \alpha \; bn\; \beta \; fn\; \beta \; bn]\; =\; [1\; 0\; 0\; 0\; ⋮\; ⋮\; 0\; 0\; 0\; 1].\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; 1\; \backslash \; epsilon\; \_\; \{b\}\; ^\; \{n\}\; \backslash \backslash \; 0\; 0\; \backslash \backslash \backslash \; vdots\; \backslash \; vdots\; \backslash \backslash \; 0\; 0\; \backslash \backslash \backslash \; epsilon\; \_\; \{f\}\; ^\; \{n\}\; 1\; \backslash \; end\; \{bmatrix\; \}\}\; \{\backslash \; begin\; \{bmatrix\}\; \backslash \; alpha\; \_\; \{f\}\; ^\; \{n\}\; \backslash \; alpha\; \_\; \{b\}\; ^\; \{n\}\; \backslash \backslash \backslash \; beta\; \_\; \{f\}\; ^\; \{n\}\; \backslash \; beta\; \_\; \{b\}\; ^\; \{\; n\}\; \backslash \; end\; \{bmatrix\}\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; 1\; 0\; \backslash \backslash \; 0\; 0\; \backslash \backslash \backslash \; vdots\; \backslash \; vdots\; \backslash \backslash \; 0\; 0\; \backslash \backslash \; 0\; 1\; \backslash \; end\; \{bmatrix\}\}.\}$

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

$[1\; ϵ\; bn\; ϵ\; fn\; 1]\; [\alpha \; fn\; \alpha \; bn\; \beta \; fn\; \beta \; bn]\; =\; [1\; 0\; 0\; 1].\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; 1\; \backslash \; epsilon\; \_\; \{b\}\; ^\; \{n\}\; \backslash \backslash \backslash \; epsilon\; \_\; \{f\}\; ^\; \{n\}\; 1\; \backslash \; end\; \{bmatrix\}\}\; \{\backslash \; begin\; \{bmatrix\}\; \backslash \; alpha\; \_\; \{f\; \}\; ^\; \{n\}\; \backslash \; alpha\; \_\; \{b\}\; ^\; \{n\}\; \backslash \backslash \backslash \; beta\; \_\; \{f\}\; ^\; \{n\}\; \backslash \; beta\; \_\; \{b\}\; ^\; \{n\}\; \backslash \; end\; \{bmatrix\}\}\; =\; \{\backslash \; begin\; \{\; bmatrix\}\; 1\; 0\; \backslash \backslash \; 0\; 1\; \backslash \; end\; \{bmatrix\}\}.\}$

После решения этих задач (с использованием формулы обратной матрицы Крамера 2 × 2) новые прямые и обратные векторы:

$f\; \to \; n\; =\; 1\; 1\; -\; ϵ\; bn\; ϵ\; fn\; [е\; \to \; n\; -\; 1\; 0]\; -\; ϵ\; fn\; 1\; -\; ϵ\; bn\; ϵ\; fn\; [0\; b\; \to \; n\; -\; 1]\; \{\backslash \; displaystyle\; \{\backslash \; vec\; \{f\}\}\; ^\; \{n\}\; =\; \{1\; \backslash \; over\; \{1-\; \backslash \; epsilon\; \_\; \{b\}\; ^\; \{n\}\; \backslash \; epsilon\; \_\; \{f\}\; ^\; \{n\}\}\}\; \{\backslash \; begin\; \{bmatrix\}\; \{\backslash \; vec\; \{f\}\}\; ^\; \{n-1\}\; \backslash \backslash \; 0\; \backslash \; end\; \{\; bmatrix\}\}\; -\; \{\backslash \; epsilon\; \_\; \{f\}\; ^\; \{n\}\; \backslash \; over\; \{1-\; \backslash \; epsilon\; \_\; \{b\}\; ^\; \{n\}\; \backslash \; epsilon\; \_\; \{f\}\; ^\; \{n\}\}\}\; \{\backslash \; begin\; \{bmatrix\}\; 0\; \backslash \; \backslash \; \{\backslash \; vec\; \{b\}\}\; ^\; \{n-1\}\; \backslash \; end\; \{bmatrix\}\}\}$

$b\; \to \; n\; =\; 1\; 1\; -\; ϵ\; bn\; ϵ\; fn\; [0\; b\; \to \; n\; -\; 1]\; -\; ϵ\; bn\; 1\; -\; ϵ\; bn\; ϵ\; fn\; [f\; \to \; n\; -\; 1\; 0].\; \{\backslash \; displaystyle\; \{\backslash \; vec\; \{b\}\}\; ^\; \{n\}\; =\; \{1\; \backslash \; over\; \{1-\; \backslash \; epsilon\; \_\; \{b\}\; ^\; \{n\}\; \backslash \; epsilon\; \_\; \{f\}\; ^\; \{n\}\}\}\; \{\backslash \; begin\; \{bmatrix\}\; 0\; \backslash \backslash \; \{\backslash \; vec\; \{b\}\}\; ^\; \{n-1\}\; \backslash \; end\; \{bmatrix\}\}\; -\; \{\backslash \; epsilon\; \_\; \{b\}\; ^\; \{n\}\; \backslash \; over\; \{1-\; \backslash \; epsilon\; \_\; \{b\}\; ^\; \{n\}\; \backslash \; epsilon\; \_\; \{f\}\; ^\; \{n\}\}\}\; \{\backslash \; begin\; \{bmatrix\}\; \{\backslash \; vec\; \{f\}\}\; ^\; \{n-1\}\; \backslash \backslash \; 0\; \backslash \; end\; \{bmatrix\}\}.\}$

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

$f\; \to \; 1\; =\; b\; \to \; 1\; =\; [1\; M\; 11]\; =\; [1\; t\; 0].\; \{\backslash \; displaystyle\; \{\backslash \; vec\; \{f\}\}\; ^\; \{1\}\; =\; \{\backslash \; vec\; \{b\}\}\; ^\; \{1\}\; =\; \backslash \; left\; [\{1\; \backslash \; over\; M\_\; \{11\}\}\; \backslash \; right]\; =\; \backslash \; left\; [\{1\; \backslash \; over\; t\_\; \{0\}\}\; \backslash \; right].\}$

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

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

$y\; \to \; =\; M\; x\; \to .\; \{\backslash \; displaystyle\; \{\backslash \; vec\; \{y\}\}\; =\; \backslash \; mathbf\; \{M\}\; \backslash \; \{\backslash \; vec\; \{x\}\}.\}$

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

Решение затем строится рекурсивно, замечая, что if

$T\; n\; -\; 1\; [x\; 1\; n\; -\; 1\; x\; 2\; n\; -\; 1\; ⋮\; xn\; -\; 1\; n\; -\; 1]\; =\; [y\; 1\; y\; 2\; ⋮\; yn\; -\; 1].\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{T\}\; ^\; \{n-1\}\; \{\backslash \; begin\; \{bmatrix\}\; x\_\; \{1\}\; ^\; \{n-1\}\; \backslash \backslash \; x\_\; \{2\}\; ^\; \{n-1\}\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; x\_\; \{\; n-1\}\; ^\; \{n-1\}\; \backslash \backslash \backslash \; end\; \{bmatrix\}\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; y\_\; \{1\}\; \backslash \backslash \; y\_\; \{2\}\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; y\_\; \{n-1\}\; \backslash \; end\; \{\; bmatrix\}\}.\}$

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

$T\; n\; [x\; 1\; n\; -\; 1\; x\; 2\; n\; -\; 1\; ⋮\; xn\; -\; 1\; n\; -\; 1\; 0]\; =\; [y\; 1\; y\; 2\; ⋮\; yn\; -\; 1\; ϵ\; xn\; -\; 1].\; \{\backslash \; Displaystyle\; \backslash \; mathbf\; \{T\}\; ^\; \{n\}\; \{\backslash \; begin\; \{bmatrix\}\; x\_\; \{1\}\; ^\; \{n-1\}\; \backslash \backslash \; x\_\; \{2\}\; ^\; \{n-1\}\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; x\_\; \{n-\; 1\}\; ^\; \{n-1\}\; \backslash \backslash \; 0\; \backslash \; end\; \{bmatrix\}\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; y\_\; \{1\}\; \backslash \backslash \; y\_\; \{2\}\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; y\_\; \{n-1\}\; \backslash \backslash \backslash \; epsilon\; \_\; \{x\}\; ^\; \{n-1\}\; \backslash \; end\; \{bmatrix\}\}.\}$

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

$T\; n\; (\; [x\; 1\; n\; -\; 1\; x\; 2\; n\; -\; 1\; ⋮\; xn\; -\; 1\; n\; -\; 1\; 0]\; +\; (yn\; -\; ϵ\; xn\; -\; 1)\; b\; \to \; n)\; =\; [y\; 1\; y\; 2\; ⋮\; yn\; -\; 1\; yn].\; \{\backslash \; Displaystyle\; \backslash \; mathbf\; \{T\}\; ^\; \{n\}\; \backslash \; left\; (\{\backslash \; begin\; \{bmatrix\}\; x\_\; \{1\}\; ^\; \{n-1\}\; \backslash \backslash \; x\_\; \{2\}\; ^\; \{n-1\}\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; x\_\; \{n-1\}\; ^\; \{n-1\}\; \backslash \backslash \; 0\; \backslash \backslash \backslash \; end\; \{bmatrix\}\}\; +\; (y\_\; \{n\}\; -\; \backslash \; epsilon\; \_\; \{x\}\; ^\; \{n-1\})\; \backslash \; \{\backslash \; vec\; \{b\}\}\; ^\; \{n\}\; \backslash \; right)\; =\; \{\backslash \; begin\; \{bmatrix\}\; y\_\; \{1\}\; \backslash \backslash \; y\_\; \{2\}\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; y\_\; \{n-1\}\; \backslash \backslash \; y\_\; \{n\}\; \backslash \; end\; \{bmatrix\}\}.\}$

Расширение этого метода до тех пор, пока n = N не даст решение $x\; \to \; \{\backslash \; displaystyle\; \{\backslash \; vec\; \{x\}\}\}$.

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

Блочный алгоритм Левинсона

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

См. Также

• Линейное предсказание
• Модель авторегрессии

Примечания

Ссылки

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

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

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

• Bojanczyk, A.W.; Brent, R.P.; De Hoog, F.R.; Сладкий, Д. (1995). «Об устойчивости алгоритмов факторизации Барейса и родственных ему алгоритмов Теплица». Журнал SIAM по матричному анализу и приложениям. 16: 40–57. arXiv : 1004.5510. doi : 10.1137 / S0895479891221563.
• Brent RP (1999), «Стабильность быстрых алгоритмов для структурированных линейных систем», Быстрые надежные алгоритмы для матриц со структурой (редакторы - Т. Кайлат, AH Sayed), глава 4 (SIAM ).
• Bunch, JR (1985). «Устойчивость методов решения систем уравнений Теплица». SIAM J. Sci. Stat. Comput., V. 6, стр.. 349–364. [2]
• Krishna, H.; Wang, Y. (1993). «Сплит-алгоритм Левинсона слабо устойчив». SIAM Journal on Numerical Анализ. 30(5): 1498–1508. doi : 10.1137 / 0730078.

Резюме

• Бэкстрем, Т. (2004). «2.2. Рекурсия Левинсона – Дурбина». Линейное прогнозирующее моделирование речи - ограничения и разложение пар линейного спектра. Докторская диссертация. Отчет № 71 / Технологический университет Хельсинки, Лаборатория акустики и обработки аудиосигналов. Эспоо, Финляндия. [3]
• Клаербут, Джон F. (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