Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to calculate the minimum eigenvalue of a symmetric tridiagonal matrix using the Sturm sequence and its interlacing property, and the bisection method. One of the step in the process is calculating the number of sign changes in the sequence. I have got the correct answer by calculating the sign change count of the sequence, but this method breaks down for larger matrices, or matrices with large eigenvalues (or very small eigenvalues), in which case the procedure results in overflow or underflow. A solution, as stated in Jennings 1977 book, is to use the ratios of determinants instead:

$$q_k(\mu)=\frac{f_k(\mu)}{f_{k-1}(\mu)}$$

The recurrence relation is then:

$$q_1(\mu)=(\alpha_1 - \mu)$$ $$q_k(\mu)=(\alpha_k - \mu) - \frac{\beta_{k-1}^2}{q_{k-1}(\mu)} \quad \text{for $k=2,\dots,n$}$$

The book also states to replace zeros with a small quantity $(\delta)$ in order to avoid division failures. While trying it out, I do not seem to be getting the same result. Trying for the following symmetric tridiagonal matrix with diagonal elements $\alpha=\{1, 2, 3, 4, 5\}$ and off-diagonal $\beta=\{-1, -1, -1, -1 \}$, and $\mu=2$, I get the original sequence as $\{1, -1, -1, 0, 1, 3\}$ having the number of sign-change count=2. When I use the ratio recurrence formula though, I get the ratio sequence as $\{-1,1, 0.1,-8,11\}$, having sign-change count as 3. I used $\delta=0.1$ for zero.

Why is the difference?

share|improve this question
    
Overflow is really quite common when using the recursion relation for determinants of tridiagonal matrices. The usual cure is to consider ratios of determinants... check that you are using the correct formula for the ratios. See this for instance. –  J. M. Apr 10 '11 at 15:49
    
Looking at the whole mess again, I'd say your "original sequence" has three sign changes: going from 1 to -1, going from -1 to 0, and going from 0 to 1. The substitution with a tiny quantity is intended for the recurrence for the ratios (i.e., when you have a zero entry in the subdiagonal elements), not for the counting of sign changes. See the Algol code in the paper I linked to in my previous comment. –  J. M. Apr 11 '11 at 2:12
    
@J.M.: Thanks a lot for the comments and pointer. I did not count 0->1 in the original sequence, since that is how it is stated in Golub-VanLoan (Theorem 8.5.1, Ch. 8, Matrix Computations, 3rd Ed). I did not get what you meant in the line "The substitution with a tiny ...". Although I do not have any zero in the subdiagonal elements, the zero was appearing in the calculation of $q_3(\mu)$, for $k=3$. So, I am unable to calculate $q_4(\mu)$, without using $\delta$. I will check the Algol code in the paper. –  Samik R Apr 11 '11 at 22:24
add comment

1 Answer

up vote 1 down vote accepted

Finally found the answer to this question. Credit goes to J.M. for pointing out the relevant literature. Since he did not post it as an answer, I am posting it with due credits. The paper mentions the following line: sign change count for the modified Sturm sequence is the number of negative $q_i(\mu)$. Once I used that, I got the same sign change count as the original sequence.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.