If is an eigenvalue of A that is larger in absolute value than any other eigenvalue, it is called the dominant eigenvalue. An eigenvector corresponding to is called a dominant eigenvector.
An eigenvector V is said to be normalized if the coordinate of largest magnitude is equal to unity (i.e., the largest coordinate in the vector V is the number 1).
Remark:
It is easy to normalize an eigenvector by forming a new vector where and .
Theorem (Power Method):
Assume that the n×n matrix A has n distinct eigenvalues and that they are ordered in decreasing magnitude; that is, . If is chosen appropriately, then the sequences and generated recursively by
and
where and , will converge to the dominant eigenvector and eigenvalue , respectively. That is,
and .
Remark:
If is an eigenvector and , then some other starting vector must be chosen.
Speed of Convergence
In the iteration in the theorem uses the equation
,
and the coefficient of that is used to form goes to zero in proportion to . Hence, the speed of convergence of to is governed by the terms . Consequently, the rate of convergence is linear. Similarly, the convergence of the sequence of constants to is linear. The Aitken method can be used for any linearly convergent sequence to form a new sequence,
,
that converges faster. The Aitken can be adapted to speed up the convergence of the power method.
Shifted-Inverse Power Method
We will now discuss the shifted inverse power method. It requires a good starting approximation for an eigenvalue, and then iteration is used to obtain a precise solution. Other procedures such as the QM and Givens’ method are used first to obtain the starting approximations. Cases involving complex eigenvalues, multiple eigenvalues, or the presence of two eigenvalues with the same magnitude or approximately the same
magnitude will cause computational difficulties and require more advanced methods. Our illustrations will focus on the case where the eigenvalues are distinct. The shifted inverse power method is based on the following three results (the proofs are left as exercises).
Theorem (Shifting Eigenvalues):
Suppose that ,V is an eigenpair of A. If is any constant, then ,V is an eigenpair of the matrix .
Theorem (Inverse Eigenvalues):
Suppose that ,V is an eigenpair of A. If , then ,V is an eigenpair of the matrix .
Theorem (Shifted-Inverse Eigenvalues):
Suppose that ,V is an eigenpair of A. If , then ,V is an eigenpair of the matrix .
Theorem (Shifted-Inverse Power Method):
Assume that the n×n matrix A has distinct eigenvalues and consider the eigenvalue . Then a constant can be chosen so that is the dominant eigenvalue of . Furthermore, if is chosen appropriately, then the sequences and generated recursively by
and
where and , will converge to the dominant eigenpair , of the matrix . Finally, the corresponding eigenvalue for the matrix A is given by the calculation
Remark. For practical implementations of this Theorem, a linear system solver is used to compute in each step by solving the linear system .
Comments
Post a Comment