Avoiding Eigenvalues in Computing Matrix Powers
Raghib Abu-Saris, Wajdi Ahmad · American Mathematical Monthly · 2005
In particular, if the forcing term g(n) is absent, the solution is given by x(n) = Axo. To compute one can use similarity transformation methods: An = SBnS-', where B is a square matrix (e.g., the Schur's canonical matrix (triangular) or the Jordan canonical matrix) whose powers are relatively easier to compute than those of A. To do so, however, one needs to determine the eigenvalues of A and the associated eigenvectors or generalized eigenvectors. This process can be tedious and computationally involved. Alternatively, one can apply the discrete analog [2, pp. 106-109] of Putzer's algorithm for the matrix exponential [5] or the recently developed algorithm by Elaydi and Harris [3], which is analogous to Leonard's algorithm for the matrix exponential [4]. A common feature of the aforementioned methods is that they, too, require the determination of the eigenvalues of A, which means finding the zeros of the characteristic polynomial of A, a challenging and difficult problem to solve exactly for polynomials of degree five or more. So we pose the question: Do we really need the eigenvalues of A to compute An ?