11.3 Eigenvalues and Eigenvectors of a Tridiagonal Matrix 475 f+=e[j]*a[i][j]; hh=f/(h+h); Form K,equation (11.2.11). for(j=1;j<1;j+)[ Form q and store in e overwriting p. f=a[i][j]; e[j]=gme[j]-hh*f; for (k=1;k<=j;k++) Reduce a,equation (11.2.13) a[j][k]-(f*e[k]+g*a[i][k]); else e[i]=a[i][1]; d[i]=h; /Next statement can be omitted if eigenvectors not wanted*/ 83g d[1]=0.0: granted for 19881992 e[1]=0.0: /Contents of this loop can be omitted if eigenvectors not 1.200 wanted except for statement d[i]=a[i][i];/ for (i=1;i<=n;i++){ Begin accumulation of transformation ma- 1=1-1; trices. if (a[i]){ This block skipped when i=1 for(j=1;j<=1;j+){ g=0.0; for(k=1;k<=1;k++) Use u and u/H stored in a to form P.Q. (North g+=a[i]k]*a[k][]: for(k=1;k<=1;k++) America computer, THE ak][j]-=g*a[k][1]; ART d[i]=a[i][i]; This statement remains. 9 Programs a[i][i]=1.0; Reset row and column of a to identity for(j=1;j<=1;j++)a[j][1]=a[i][j]=0.0; matrix for next iteration. IENTIFIC to dir CITED REFERENCES AND FURTHER READING: Golub,G.H.,and Van Loan,C.F.1989,Matrix Computations,2nd ed.(Baltimore:Johns Hopkins University Press),85.1.[1] COMPUTING(ISBN 198918920 Smith,B.T.,et al.1976,Matrix Eigensystem Routines-EISPACK Guide,2nd ed.,vol.6 of Lecture Notes in Computer Science(New York:Springer-Verlag). 10-621 Wilkinson,J.H.,and Reinsch,C.1971,Linear Algebra,vol.Il of Handbook for Automatic Com- putation (New York:Springer-Verlag).[2] Numerical Recipes 43108 11.3 Eigenvalues and Eigenvectors of a (outside Tridiagonal Matrix North Software. Amer ying of visit website Evaluation of the Characteristic Polynomial machine Once our original,real,symmetric matrix has been reduced to tridiagonal form, one possible way to determine its eigenvalues is to find the roots of the characteristic polynomial pn(A)directly.The characteristic polynomial of a tridiagonal matrix can be evaluated for any trial value of A by an efficient recursion relation(see [1],for example).The polynomials of lower degree produced during the recurrence form a11.3 Eigenvalues and Eigenvectors of a Tridiagonal Matrix 475 Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). f += e[j]*a[i][j]; } hh=f/(h+h); Form K, equation (11.2.11). for (j=1;j<=l;j++) { Form q and store in e overwriting p. f=a[i][j]; e[j]=g=e[j]-hh*f; for (k=1;k<=j;k++) Reduce a, equation (11.2.13). a[j][k] -= (f*e[k]+g*a[i][k]); } } } else e[i]=a[i][l]; d[i]=h; } /* Next statement can be omitted if eigenvectors not wanted */ d[1]=0.0; e[1]=0.0; /* Contents of this loop can be omitted if eigenvectors not wanted except for statement d[i]=a[i][i]; */ for (i=1;i<=n;i++) { Begin accumulation of transformation ma￾l=i-1; trices. if (d[i]) { This block skipped when i=1. for (j=1;j<=l;j++) { g=0.0; for (k=1;k<=l;k++) Use u and u/H stored in a to form P·Q. g += a[i][k]*a[k][j]; for (k=1;k<=l;k++) a[k][j] -= g*a[k][i]; } } d[i]=a[i][i]; This statement remains. a[i][i]=1.0; Reset row and column of a to identity for (j=1;j<=l;j++) a[j][i]=a[i][j]=0.0; matrix for next iteration. } } CITED REFERENCES AND FURTHER READING: Golub, G.H., and Van Loan, C.F. 1989, Matrix Computations, 2nd ed. (Baltimore: Johns Hopkins University Press), §5.1. [1] Smith, B.T., et al. 1976, Matrix Eigensystem Routines — EISPACK Guide, 2nd ed., vol. 6 of Lecture Notes in Computer Science (New York: Springer-Verlag). Wilkinson, J.H., and Reinsch, C. 1971, Linear Algebra, vol. II of Handbook for Automatic Com￾putation (New York: Springer-Verlag). [2] 11.3 Eigenvalues and Eigenvectors of a Tridiagonal Matrix Evaluation of the Characteristic Polynomial Once our original, real, symmetric matrix has been reduced to tridiagonal form, one possible way to determine its eigenvalues is to find the roots of the characteristic polynomial pn(λ) directly. The characteristic polynomial of a tridiagonal matrix can be evaluated for any trial value of λ by an efficient recursion relation (see [1], for example). The polynomials of lower degree produced during the recurrence form a