1
$\begingroup$

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?

  • 0
    @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.2011-04-11

1 Answers 1

1

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.