Levinson recursion oder Levinson-Durbin recursion sind ein Verfahren in der geradlinigen Algebra, um die Lösung einer Gleichung rekursiv zu berechnen, die eine Matrix von Toeplitz einschließt. Der Algorithmus führt in Θ (n) Zeit, die eine starke Verbesserung über die Beseitigung von Gauss-Jordan ist, die in Θ (n) läuft.

Neuere Algorithmen, genannt asymptotisch schnell oder manchmal superschnelle Algorithmen von Toeplitz, können in Θ (n logn) für verschiedenen p (z.B p = 2, p = 3) lösen. Levinson recursion bleibt populär aus mehreren Gründen; für einen ist es relativ leicht, im Vergleich zu verstehen; für einen anderen kann es schneller sein als ein superschneller Algorithmus für kleinen n (gewöhnlich n

Der Algorithmus von Levinson-Durbin wurde zuerst von Norman Levinson 1947 vorgeschlagen, von James Durbin 1960 verbessert, und hat sich nachher zu 4n und dann 3n Multiplikationen durch W. F. Trench und S. Zohar beziehungsweise verbessert.

Andere Methoden, Daten zu bearbeiten, schließen Zergliederung von Schur und Zergliederung von Cholesky ein. Im Vergleich mit diesen neigt Levinson recursion (besonders Spalt-Levinson recursion) dazu, rechenbetont schneller, aber zu rechenbetonten Ungenauigkeiten wie Runde - von Fehlern empfindlicher zu sein.

Abstammung

Hintergrund

Matrixgleichungen folgen der Form:

:

Der Algorithmus von Levinson-Durbin kann für jede solche Gleichung verwendet werden, nicht weniger als ist M eine bekannte Matrix von Toeplitz mit einer Nichtnullhauptdiagonale. Hier ist ein bekannter Vektor, und ist ein unbekannter Vektor von Zahlen x noch, um bestimmt zu werden.

Wegen dieses Artikels, ê ist ein Vektor zusammengesetzt völlig aus zeroes abgesehen von seinem I'Th-Platz, der den Wert ein hält. Seine Länge wird durch den Umgebungszusammenhang implizit bestimmt. Der Begriff N bezieht sich auf die Breite der Matrix oben - M ist N×N Matrix. Schließlich, in diesem Artikel, beziehen sich Exponenten auf einen induktiven Index, wohingegen Subschriften Indizes anzeigen. Zum Beispiel (und Definition), in diesem Artikel, ist die Matrix T n×n Matrix, die das obere verlassen n×n Block von der M - d. h. T = M. kopiert

T ist auch eine Matrix von Toeplitz; das Meinen, dass es als geschrieben werden kann:

:

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}. </Mathematik>

Einleitende Schritte

Der Algorithmus geht in zwei Schritten weiter. Im ersten Schritt, zwei Sätzen von Vektoren, hat den nachschicke und die rückwärts gerichteten Vektoren genannt, werden gegründet. Die Vorwärtsvektoren werden verwendet, um zu helfen, den Satz von rückwärts gerichteten Vektoren zu bekommen; dann können sie sofort verworfen werden. Umgekehrt sind Vektoren für den zweiten Schritt notwendig, wo sie verwendet werden, um die gewünschte Lösung zu bauen.

Levinson-Durbin recursion definiert den n "Vorwärtsvektor", angezeigt, als der Vektor der Länge n, der befriedigt:

:

Der n "rückwärts gerichteter Vektor" wird ähnlich definiert; es ist der Vektor der Länge n, der befriedigt:

:

Eine wichtige Vereinfachung kann vorkommen, wenn M eine symmetrische Matrix ist; dann sind die zwei Vektoren durch b = f verbunden - d. h. sie sind Reihe-Umkehrungen von einander. Das kann etwas Extraberechnung in diesem speziellen Fall sparen.

Das Erreichen der rückwärts gerichteten Vektoren

Selbst wenn die Matrix nicht symmetrisch ist, dann kann der n fortgeschrittener und rückwärts gerichteter Vektor von den Vektoren der Länge n-1 wie folgt gefunden werden. Erstens kann der Vorwärtsvektor mit einer Null erweitert werden, um vorzuherrschen:

:

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

Im Gehen von T bis T stört die zur Matrix hinzugefügte Extrasäule die Lösung nicht, wenn eine Null verwendet wird, um den Vorwärtsvektoren zu erweitern. Jedoch hat die zur Matrix hinzugefügte Extrareihe die Lösung gestört; und es hat einen unerwünschten Fehlerbegriff &epsilon geschaffen; der im letzten Platz vorkommt. Die obengenannte Gleichung gibt ihm den Wert:

:

Dieser Fehler wird in kurz zurückgegeben und vom neuen Vorwärtsvektoren beseitigt; aber zuerst umgekehrt muss Vektor in einem ähnlichen (obgleich umgekehrt) Mode erweitert werden. Für umgekehrt Vektoren,

:\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}. </Mathematik>

Wie vorher stört die zur Matrix hinzugefügte Extrasäule das neu umgekehrt Vektor nicht; aber die Extrareihe tut. Hier haben wir einen anderen unerwünschten Fehler &epsilon; mit dem Wert:

:

Diese zwei Fehlerbegriffe können gebraucht werden, um einander zu beseitigen. Mit der Linearität von matrices,

: \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}. </Mathematik>

Wenn α und β gewählt werden, so dass die rechte Seite ê oder ê nachgibt, dann wird die Menge in den Parenthesen die Definition des n fortgeschrittener oder rückwärts gerichteter Vektor beziehungsweise erfüllen. Mit denjenigen sind Alpha und Beta gewählt, die Vektorsumme in den Parenthesen einfach und geben das gewünschte Ergebnis nach.

Um diese Koeffizienten zu finden, sind dass solch:

:

\vec f_n = \alpha^n_ {f} \begin {bmatrix} \vec f_ {n-1 }\\\

0

\end {bmatrix}

+ \beta^n_ {f }\\beginnen {bmatrix} 0 \\

\vec b_ {n-1 }\

\end {bmatrix }\</Mathematik>

und beziehungsweise, sind dass solch:

:\begin {bmatrix }\

\vec f_ {n-1 }\\\

0\end {bmatrix}

+ \beta^n_ {b }\\beginnen {bmatrix }\

0 \\

\vec b_ {n-1 }\

\end {bmatrix}.

</Mathematik>Indem

man beide vorherigen Gleichungen damit multipliziert, bekommt man die folgende Gleichung:

:

\begin {bmatrix} 1 & \epsilon^n_b \\

0 & 0 \\

\vdots & \vdots \\

0 & 0 \\

\epsilon^n_f & 1

\end {bmatrix} \begin {bmatrix} \alpha^n_f & \alpha^n_b \\\beta^n_f & \beta^n_b \end {bmatrix}

\begin {bmatrix}

1 & 0 \\

0 & 0 \\\vdots & \vdots \\0 & 0 \\

0 & 1

\end {bmatrix}. </Mathematik>

Jetzt ist der ganze zeroes in der Mitte der zwei Vektoren über dem ignorieren und zusammengebrochen, nur die folgende Gleichung wird verlassen:

:

Mit diesen, die für (durch das Verwenden vom Cramer 2x2 umgekehrte Matrixformel) gelöst sind, sind die neuen fortgeschrittenen und rückwärts gerichteten Vektoren:

:

- {\epsilon_f^n \over {1 - \epsilon_b^n \epsilon_f^n} beginnen }\\{bmatrix} 0 \\\vec B^ {n-1} \end {bmatrix} </Mathematik>

:

- {\epsilon_b^n \over {1 - \epsilon_b^n \epsilon_f^n} beginnen }\\{bmatrix} \vec F^ {n-1} \\0 \end {bmatrix}. </Mathematik>

Das Durchführen dieser Vektor-Summierungen gibt dann dem n fortgeschrittene und rückwärts gerichtete Vektoren von den vorherigen. Alles, was bleibt, soll den ersten von diesen Vektoren finden, und dann geben einige schnelle Summen und Multiplikationen die restlichen. Die ersten fortgeschrittenen und rückwärts gerichteten Vektoren sind einfach:

:

Das Verwenden der rückwärts gerichteten Vektoren

Die obengenannten Schritte geben dem N rückwärts gerichtete Vektoren für die M. Von dort ist eine willkürlichere Gleichung:

:

Die Lösung kann auf dieselbe rekursive Weise gebaut werden, wie umgekehrt Vektoren gebaut wurden. Entsprechend, muss zu einer Folge, von der verallgemeinert werden.

Die Lösung wird dann rekursiv dadurch gebaut, das wenn zu bemerken:

:

\begin {bmatrix} X_1^ {n-1} \\

X_2^ {n-1} \\

\dots \\

x_ {n-1} ^ {n-1} \\

\end {bmatrix} =

\begin {bmatrix} y_1 \\

y_2 \\

\dots \\

y_ {n-1} \\

\end {bmatrix}. </Mathematik>

Dann, sich mit einer Null wieder ausstreckend, und einen unveränderlichen Fehler wo notwendig definierend:

: \begin {bmatrix} X_1^ {n-1} \\ X_2^ {n-1} \\ \dots \\ x_ {n-1} ^ {n-1} \\

0 \\

\end {bmatrix} = \begin {bmatrix} y_1 \\ y_2 \\ \dots \\ y_ {n-1} \\

\epsilon_x^ {n-1 }\

\end {bmatrix}. </Mathematik>

Wir können dann den n rückwärts gerichteter Vektor verwenden, um den Fehlerbegriff zu beseitigen und es durch die gewünschte Formel wie folgt zu ersetzen:

: \begin {bmatrix} X_1^ {n-1} \\ X_2^ {n-1} \\ \dots \\ x_ {n-1} ^ {n-1} \\ 0 \\

\end {bmatrix} + (y_n - \epsilon_x^ {n-1}) \\vec B^n \right) =

\begin {bmatrix} y_1 \\ y_2 \\ \dots \\ y_ {n-1} \\

y_n \\

\end {bmatrix}. </Mathematik>Wenn er

diese Methode bis n = erweitert, gibt N die Lösung nach.

In der Praxis werden diese Schritte häufig gleichzeitig mit dem Rest des Verfahrens getan, aber sie bilden eine zusammenhängende Einheit und verdienen es, als ihr eigener Schritt behandelt zu werden.

Blockieren Sie Algorithmus von Levinson

Wenn M nicht ausschließlich Toeplitz, aber Block Toeplitz ist, kann der Levinson recursion auf die ziemlich gleiche Weise durch die Bewertung des Blocks Matrix von Toeplitz als eine Matrix von Toeplitz mit Matrixelementen (Musicus 1988) abgeleitet werden. Block Toeplitz matrices entsteht natürlich in Signalverarbeitungsalgorithmen wenn, sich mit vielfachen Signalströmen (z.B, in MIMO Systemen) oder cyclo-stationäre Signale befassend.

Siehe auch

• Spalten Sie Levinson recursion
• Geradlinige Vorhersage

Zeichen

Das Definieren von Quellen

• Levinson, N. (1947). "Der Wiener RMS Fehlerkriterium im Filterdesign und der Vorhersage." J. Mathematik. Phys. v. 25, Seiten 261-278.
• Durbin, J. (1960). "Die Anprobe von Zeitreihe-Modellen." Hochwürdiger. Inst. Interne Nummer. Stat. v. 28, Seiten 233-243.
• Graben, W. F. (1964). "Ein Algorithmus für die Inversion von begrenztem Toeplitz matrices." J. Soc. Indust. Appl. Mathematik. v. 12, Seiten 515-522.
• Musicus, B. R. (1988). "Levinson und Schnelle Algorithmen von Choleski für Toeplitz und Almost Toeplitz Matrices." RLE TR Nr. 538, MIT.

http://dspace.mit.edu/bitstream/1721.1/4954/1/RLE-TR-538-20174000.pdf

• Delsarte, P. und Genin, Y. V. (1986). "Der Spalt Algorithmus von Levinson." IEEE Transaktionen auf der Akustik, Rede und Signalverarbeitung, v. ASSP-34 (3), Seiten 470-478.

Weitere Arbeit

• Bündel, J. R. (1985). "Stabilität von Methoden, für Gleichungssysteme von Toeplitz zu lösen." SIAM J. Sci. Stat. Comput. v. 6, Seiten 349-364.

http://locus.siam.org/fulltext/SISC/volume-06/0906025.pdf

Zusammenfassungen

• Bäckström, T. (2004). "2.2. Levinson-Durbin Recursion." Das geradlinige Prophetische Modellieren der Rede - Einschränkungen und Linienspektrum-Paar-Zergliederung. Doktorthese. Bericht Nr. 71 / Helsinkier Universität der Technologie, Laboratorium der Akustik und Audiosignalverarbeitung. Espoo, Finnland.

http://lib.tkk.fi/Diss/2004/isbn9512269473/isbn9512269473.pdf

• Claerbout, Jon F. (1976). "Kapitel 7 - Wellenform-Anwendungen von Am-Wenigsten-Quadraten." Grundlagen der Geophysikalischen Datenverarbeitung. Palo Altstimme: Blackwell Wissenschaftliche Veröffentlichungen.

http://sep.stanford.edu/oldreports/fgdp2/fgdp_07.pdf

• Golub, G.H. und Darlehen, C.F. Van (1996). "Abschnitt 4.7: Toeplitz und verwandte Systeme" Matrixberechnung, Universität von Johns Hopkins Presse