3
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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).

Improve this answer
$\endgroup$
3
  • $\begingroup$ @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 $\endgroup$
    – Alexander Chervov
    Commented Aug 16, 2012 at 10:36
  • $\begingroup$ @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. $\endgroup$
    – Federico Poloni
    Commented Aug 16, 2012 at 10:51
  • $\begingroup$ @Federico Thank you very much again !:) $\endgroup$
    – Alexander Chervov
    Commented Aug 17, 2012 at 6:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .