3
$\begingroup$

This question is related to my previous question The algorithm to find the largest eigenvalue and one of its eigenvector of a symmetric tridiagonal matrix? The matrix in question is a symmetric tridiagonal matrix in the form of

$$\left( {\begin{array}{*{20}{c}} {{x_1}}&{{y_1}}&{}&{} \\ {{y_1}}&{{x_2}}& \ddots &{} \\ {}& \ddots & \ddots &{{y_{n - 1}}} \\ {}&{}&{{y_{n - 1}}}&{{x_n}} \end{array}} \right)$$

where $y_1,...,y_{n-1}$ are all positive numbers. The question is

Suppose now we already know an eigenvalue $\lambda$ of it, what is the right way to compute an eigenvector associated with $\lambda$?

There seems to be an naive method, but I am very not sure if it is correct. Suppose the eigenvector is $a=(a_1,...,a_n)$, Set $a_1$ to arbitrary non-zero number if $y_1 \neq \lambda$, and set $a_1 = 0$ otherwise, then solve $a_2$ by $x_1a_1+y_1a_2=\lambda (a_1+a_2)$, then solve $a_3$ by $y_1a_1+x_2a_2+y_2a_3=\lambda (a_1+a_2+a_3)$, and so on so forth. Will it really be so simple?

$\endgroup$
  • $\begingroup$ Yes, but it’s more tedious than it needs to be. $\endgroup$ – k.stm Jul 31 '17 at 15:48
  • $\begingroup$ Er, are you planning on implementing this? That is, is a computer supposed to do the algorithm? $\endgroup$ – k.stm Jul 31 '17 at 15:55
  • $\begingroup$ @k.stm Thanks for your comment and answer. Yes, however, it is desired to be done with a computer. $\endgroup$ – Ralph B. Jul 31 '17 at 17:54
  • $\begingroup$ I do not understand your method. To me, it seems relevant to compare $x_1$, rather than $y_1$ to $\lambda$. I believe the right hand side of the first equation and the second equations should be $\lambda a_1$ and $\lambda a_2$. $\endgroup$ – Carl Christian Aug 1 '17 at 20:30
2
$\begingroup$

If you already know an approximate eigenvalue $\hat{\lambda}$ of a (tridiagonal) symmetric matrix, then the "standard" way to refine it and compute the corresponding eigenvector is to apply the inverse power method to the matrix $A - \hat{\lambda}I$., i.e., execute the power method using the action of the matrix $(A - \hat{\lambda} I)^{-1}$ in place of $A$

You need not worry about the fact that your coefficient matrix $A - \hat{\lambda} I$ is nearly singular. It is known that the while the error of the solve can be quite large, it tends to point in the correct direction. Beresford Parlett has a discussion of this phenomenon in his textbook: "The symmetric eigenvalue problem".

If the spectrum of $A$ contains a cluster around $\lambda$, then the rate of convergence of the shifted-inverse power method may be insufficient. In this case you should try to apply the inverse subspace iteration with Rayleigh-Ritz acceleration to the matrix $A - \hat{\lambda} I$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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