Stability of Levinson-Durbin method for Toeplitz system solutions ?

How stable is Levinson-Durbin method for solution of systems of linear equations ?

I mean if condition number of matrix is $k$, does intermidiate steps involve matrixes with higher condition number ? For example QR is easy to see preserve condition number so it is stable, but Cholesky for example increase condition number from $k$ to $k^2$, so Cholesky is less stable.

The question is related with possible fix-point implementation of this method and we need to understand how many bits should be given, for matrices of small size.

-

1 Answer

It can be unstable, and the condition number is not an adequate measure to tell when it fails. You may want to check the numerical experiments in http://www.jstor.org/stable/2153371 for specific examples and discussion.

If I remember correctly, you can prove stability only for symmetric matrices whose principal minors are all positive (totally positive matrices), otherwise things can go wrong. More precisely, there are numbers called reflection coefficients that can be defined along the algorithm; you get stability only if they are all positive, as for instance in the totally positive case (sorry but I do not remember the details exactly, it's some years since I worked on that).

The GKO algorithm, developed in the article I linked above, is generally considered to be a more stable alternative. However, you have to pay for that with larger computational times and memory overhead (you can save the memory overhead though).

-
@Federico Thank you very much ! If matrices are positive definite, but may be not totally positive, if there any advice ? PS I do not have access to this paper :( If you can send me that would be great al.mylastname at gmail dot com –  Alexander Chervov Aug 16 '12 at 10:36
@Alexander The same paper shows some examples of PD matrices in which Levinson gives a much larger error than GKO and the conventional $O(n^3)$ Gaussian elimination methods. –  Federico Poloni Aug 16 '12 at 10:51
@Federico Thank you very much again !:) –  Alexander Chervov Aug 17 '12 at 6:21