The Numerical Stability of the Levinson-Durbin Algorithm for Toeplitz Systems of Equations

Abstract

The numerical stability of the Levinson-Durbin algorithm for solving the Yule-Walker equations with a positive-definite symmetric Toeplitz matrix is studied. Arguments based on the analytic results of an error analysis for fixed-point and floating-point arithmetics show that the algorithm is stable and in fact comparable to the Cholesky algorithm. Conflicting evidence on the accuracy performance of the algorithm is explained by demonstrating that the underlying Toeplitz matrix is typically ill-conditioned in most applications.