Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Levinson recursion
open-in-new
<p>Levinson recursion or Levinson–Durbin recursion is a procedure in <a href="/facts/Linear_algebra/8VaB4VWk">linear algebra</a> to <a href="/facts/Recursion/CxSKxJoW">recursively</a> calculate the solution to an equation involving a <a href="/facts/Toeplitz_matrix/WAjSdlaW">Toeplitz matrix</a>. The <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> runs in <a href="/facts/Big_O_notation/weFFjSWg">Θ</a>(<i>n</i>2) time, which is a strong improvement over <a href="/facts/Gauss%25E2%2580%2593Jordan_elimination/23Rvf4ht">Gauss–Jordan elimination</a>, which runs in Θ(<i>n</i>3). </p><p>The Levinson–Durbin algorithm was proposed first by <a href="/facts/Norman_Levinson/BoReyjDH">Norman Levinson</a> in 1947, improved by <a href="/facts/James_Durbin/kz8vxCXs">James Durbin</a> in 1960, and subsequently improved to 4<i>n</i>2 and then 3<i>n</i>2 multiplications by W. F. Trench and S. Zohar, respectively. </p><p>Other methods to process data include <a href="/facts/Schur_decomposition/EYNrqHmh">Schur decomposition</a> and <a href="/facts/Cholesky_decomposition/Q3IjkuTs">Cholesky decomposition</a>. In comparison to these, Levinson recursion (particularly split Levinson recursion) tends to be faster computationally, but more sensitive to computational inaccuracies like <a href="/facts/Round-off_error/aF9N8X4I">round-off errors</a>. </p><p>The Bareiss algorithm for <a href="/facts/Toeplitz_matrix/WAjSdlaW">Toeplitz matrices</a> (not to be confused with the general <a href="/facts/Bareiss_algorithm/uUKd5hKv">Bareiss algorithm</a>) runs about as fast as Levinson recursion, but it uses <i>O</i>(<i>n</i>2) space, whereas Levinson recursion uses only <i>O</i>(<i>n</i>) space. The Bareiss algorithm, though, is <a href="/facts/Numerical_stability/jRDdo8zV">numerically stable</a>, whereas Levinson recursion is at best only weakly stable (i.e. it exhibits numerical stability for <a href="/facts/Condition_number/9Tjtk6wh">well-conditioned</a> linear systems). </p><p>Newer algorithms, called <i>asymptotically fast</i> or sometimes <i>superfast</i> Toeplitz algorithms, can solve in Θ(<i>n</i> log<i>p</i><i>n</i>) for various <i>p</i> (e.g. <i>p</i> = 2, <i>p</i> = 3 ). Levinson recursion remains popular for several reasons; for one, it is relatively easy to understand in comparison; for another, it can be faster than a superfast algorithm for small <i>n</i> (usually <i>n</i> < 256). </p>