1
$\begingroup$

I have a positive definite matrix $A$. I need to compute the max eigen value of $A$ using inverse iteration. The problem is that there are duplicate maximum eigen values and so inverse iteration does not converge on largest eigen value.

Square Matrix A is formed under two conditions:
1.  A[i][j] = 2 if i = j
2.  A[i][j] = -1 if i = j - 1 or i = j + 1
3.  All other values are 0
$\endgroup$
5
  • $\begingroup$ you'll want to orthogonalize the approximate eigenvectors after each iteration. $\endgroup$ Oct 30, 2013 at 17:57
  • $\begingroup$ Proceed normally, you'll end up with a vector in the 2d subspace spanned by the two eigenvectors but since you're just looking for the eigen value you'll be fine. $\endgroup$
    – Arthur B
    Oct 30, 2013 at 19:58
  • $\begingroup$ If I proceed normally, it converges to the 2nd largest eigen value; not the largest. $\endgroup$
    – codepk
    Oct 30, 2013 at 20:32
  • 1
    $\begingroup$ Looks a lot like homework. $\endgroup$ Oct 31, 2013 at 7:42
  • $\begingroup$ Why do you need to use inverse iteration: en.wikipedia.org/wiki/… $\endgroup$
    – Dirk
    Oct 31, 2013 at 11:22

2 Answers 2

2
$\begingroup$

expanding on my comment, you'll find a description of the approach you need, for example, in Michael Christensen's A general complex eigen-problem solver based on Lanczos algorithm and inverse iteration

Given a set of approximate eigenvalues of any non-defective matrix, inverse iteration can be used to generate all the eigenvectors, update the eigenvalues and estimate the errors. This can be done even for degenerate matrices. Here the inverse iteration is simply started with several different initial vectors for each eigenvalue until the subspace is spanned (use Gram-Schmidt orthogonalization for example), thereby determining the multiplicities of any eigenvalue.

$\endgroup$
0
$\begingroup$

codepk, I think that the words have a meaning: if "the max and 2nd max eigen values are equal" then they are not distinct. I assume that $\lambda_1>\lambda_2>\lambda_3\cdots$ and moreover $\lambda_2/\lambda_1$ is near $1$ and $\lambda_3/\lambda_2$ is not near $1$. Of course Beenakker is right, but I think that you can use a simpler method. Firstly, when you solve the iteration $(A-\mu I)x=b$, it is better to choose $\mu>\lambda_1$. Secondly, it is true that the inverse iteration can converge to $\lambda_2$ ; the limit depends on the random choice for the first vector. Yet, in general, the limit is once on two $\lambda_1$ and once on two $\lambda_2$. Thus you do several tests and you keep the maximum of the results. Moreover the eigenvectors associated to $\lambda_1,\lambda_2$ are far from one another because they are orthogonal. Thus, if during an iteration, you move near an already got approximation of an eigenvector, then you can stop the iteration very quickly.

EDIT: This matrix is associated to a PDE. This test is imposed on all beginners. All the eigenvalues of your matrix $A$ are SIMPLE but, when $n$ increases, there is a stack of larger eigenvalues and, then, the problem is difficult. Yet $sup(spectrum(A))$ is near $4$ and $<4$. You can choose $\mu=4$ (cf. above). Do several tests as I wrote above. If you do not find the correct eigenvalue, then follow the advice of Beenakker.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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