The Development of an Iterative Procedure for Calculating Eigenvalues in Investment Decision-Making
Tedja Santanoe Oepomo · 2012
The aim of this manuscript is to study and to compare several iterative procedures based on the Oepomo, Power, and QR methods for solving dominant eigenvalues of essentially positive matrices. Ascending and descending techniques lead to a new iterative method, new algorithm. The new technique was compared to the Power and QR methods in term of speed of convergence, number of required mathematical operations, and effectiveness to numerically calculate dominant eigenvalues of essentially positive matrices. Numerical examples illustrate the purpose. A potential use of the new algorithm is to numerically calculate eigenvalues in the making of business decisions. (ProQuest: ... denotes formulae omitted.) Introduction For solving the system of eigenvalues Ax=Kx, we consider any convergent methods using the Power and QR iterative methods. Quite often the convergence is too slow and it has to be accelerated. There exist many processes for that purpose whose references can be easily found. The second fundamental problem in linear algebra is to compute the eigenvalues and eigenvectors of a square matrix. In other words, to diagonalize a square matrix. In theory we know what to do. We have to compute the characteristic polynomial P(λ) find the roots λ^sub i^, then for each i we have the equation (A-λ^sub i^)x = 0 for the eigenvectors. However, this procedure is not satisfactory. Newtown's method give a very fast way to compute roots of polynomial P(λ) , it can also easily be extended to complex roots. But remember, that Newton's method usually works very well once you are reasonably close to the root, but it may diverge if you start far away. Still you need ad hoc method to get close to the root. To reduce the chance element in this hit or miss strategy, another numerical computations were invented, i.e. power, QR iterative, and Oepomo 's methods. Moreover, we also have to care about the stability of the method, as the eigenvalue problem can be quite ill conditioned, so we do not want to make it much worse by an unstable algorithm. Example. Consider the nxn matrix ... (1) where £ is a tiny number with all entries are zero. The characteristic polynomial of A is P(λ) = - e. Clearly all eigenvalues are 0 if e = 0. However for e F 0 there are n complex eigenvalues, the n-th roots of unity. Even if we focus on the real eigenvalue e^sup 1/n^, it is clear that the problem is very ill conditioned. Let n=40 and choose e = 10^sup -40^ which is an extremely tiny relative error of order 10^sup -40^/1 = 10^sup -40^. However, one of the eigenvalue is λ = 10^sup -1^ = 0.1, which is at a distance of 10' from the unperturbed eigenvalue of 0. Hence the change in the eigenvalues is equal to the change in the perturbation parameter e multiplied by 10^sup +39^. There is another disquieting aspect of this phenomenon. The number e = 10^sup -40^ is automatically replaced by 0 in the computer, and this rounding introduces an error of order 10' in the result. Fortunately the eigenvalue problem is not so ill conditioned for most matrices, this example was particularly nasty one. However, it shows that we should aim at stable algorithms, which at least do not make bad things much worse, since the problem itself can be quite bad. Power Method This method is extremely simple. Let A be a square matrix. Pick any vector X0 and start successively multiplying it with A . We can claim, that unless you are extremely unlucky with the choice of X^sub 0^ , we can easily find the eigenvalue with the largest modulus. Theorem 1: Suppose that the square matrix A has ? distinct eigenvalues β^sub 1^ , β^sub 2^ , β^sub 3^, ......... ,β^sub n^ and that they are ordered in decreasing magnitude; that is |β^sub 1^| > |β^sub 2^| ≥ |β^sub 3^| ≥ ........ ≥ β^sub n^|. If x^sub 0^ is chosen appropriately, then the sequences {x^sub k^ = (x^sup k^^sub 1^, x^sup k^^sub 2^, ..... x^sup k^^sub n^)^sup T^} and {C^sub k^} generated recursively by Y^sub k^ = Ax^sub k^ and X^sub k+1^ = 1 Y^sub k^/C^sub k+1^------ yk where . …