The Eigenvalue Problem Revisited, Numerically.
The eigenvalue problem is a fundamental problem of linear algebra that arises in many different settings in physics, chemistry, statistics, and mathematics. For any n x n matrix A, the eigenvalues of that matrix are the n roots l1, l2, ..., ln of the characteristic equation of the matrix A, that is, the roots of equation 1,
| lI - A | = 0 (1)
where I is the standard n x n identity matrix. Equation one expanded becomes
c(x) = xn + c1xn-1 + c2xn-2 + ... + cn-1x + cn (2)
The problem is in obtaining the coefficients c1, c2,..., cn of the characteristic polynomial which results from expanding the above determinant.
Le Verrier's method, as modified by Souriau and Frame, uses a recursive algorithm. The algorithm is as follows:
For an n by n matrix A
set Bo = I
For k = 1 to n
Ak = ABk-1
ck = -(1/k) tr(Ak) Where the ck are in Equation 2.
Bk = Ak + ckI
End.The characteristic equation is then solved by any standard root-solver for the eigenvalues.
Sample Program For HP-75C w/ Math ROM:
10 OPTION BASE 1 ! Array lower limit is 1 20 DIM A(10,10), B(10,10), C(11), E(10,2) ! Dimension arrays for n=10 30 INPUT "DIM: "; N ! Input order 40 REDIM A(N,N) ! Resize matrix for entry 50 MAT INPUT A ! Input matrix coefficients 60 MAT B=IDN(N,N) ! Initialize B to identity 70 MAT C=CON(N+1) ! Init. Characteristic coeff. 80 FOR I=1 TO N 90 MAT B=A*B ! Let B = A*B 100 T = 0 ! Set Trace = 0 110 FOR J=1 TO N 120 T=T+B(J,J) ! Trace of A*B 130 NEXT J 140 C(I+1), Z = -T/I ! Char eq. Coeffs. computed 150 FOR J=1 TO N 160 B(J,J)=B(J,J) + Z ! Add coeff. to B 170 NEXT J 180 NEXT I 190 MAT E=PROOT(C) ! Solve characteristic eq. 200 MAT DISP USING "6d.7d,2x,6d.7d" ; E ; ! Display complex roots 210 ENDThis routine will solve for the eigenvalues of any real matrix (symmetric or non-symmetric) by solving the computed characteristic equation by a general polynomial root-solver, PROOT which gives all roots (real and complex) of any polynomial with real coefficients.
This method of calculating eigenvalues has generally been discouraged in the past due to its need for a root-finder,4 which has its own problems, but most good numerical libraries contain a root-finder that can be used. An example of the simple elegance of this routine may be seen in the sample program listing which is from a Hewlett-Packard HP-75C portable computer, which has up to 24K of CMOS RAM and a very powerful built-in 48K BASIC/operating system. With the addition of a 16K Math ROM, this portable computer has built-in BASIC keywords for matrix manipulations, complex numbers, numerical integration, and root-finding. A condensed version of this program only requires 436 bytes of memory, and thus all of the eigenvalues may be solved for in a matrix up to 28 x 28, all in a battery operated portable computer!
The following are some sample times: