11.5 Reduction of a General Matrix to Hessenberg Form 483 Apart from referring you to the literature,and to the collected routines in [1,2].we are going to sidestep the problem of eigenvectors,giving algorithms for eigenvalues only.If you require just a few eigenvectors,you can read 811.7 and consider finding them by inverse iteration.We consider the problem of finding all eigenvectors of a nonsymmetric matrix as lying beyond the scope of this book. Balancing The sensitivity of eigenvalues to rounding errors during the execution of some algorithms can be reduced by the procedure of balancing.The errors in the eigensystem found by a numerical procedure are generally proportional to the g Euclidean norm of the matrix,that is,to the square root of the sum of the squares of the elements.The idea of balancing is to use similarity transformations to make corresponding rows and columns of the matrix have comparable norms,thus reducing the overall norm of the matrix while leaving the eigenvalues unchanged. A symmetric matrix is already balanced. 之物 Balancing is a procedure with of order N2 operations.Thus,the time taken by the procedure balanc,given below,should never be more than a few percent of the total time required to find the eigenvalues.It is therefore recommended that you ahways balance nonsymmetric matrices.It never hurts,and it can substantially improve the accuracy of the eigenvalues computed for a badly balanced matrix. 当寻%n 9 The actual algorithm used is due to Osborne.as discussed in 111.It consists of a sequence of similarity transformations by diagonal matrices D.To avoid introducing rounding errors during the balancing process,the elements of D are restricted to be exact powers of the radix base employed for floating-point arithmetic(i.e.,2 for most OF SCIENTIFIC machines,but 16 for IBM mainframe architectures).The output is a matrix that is balanced in the norm given by summing the absolute magnitudes of the matrix elements.This is more efficient than using the Euclidean norm,and equally effective: A large reduction in one norm implies a large reduction in the other. Note that if the off-diagonal elements of any row or column of a matrix are all zero,then the diagonal element is an eigenvalue.If the eigenvalue happens to be ill-conditioned(sensitive to small changes in the matrix elements),it will have relatively large errors when determined by the routine hgr(811.6).Had we merely Numerica 10621 inspected the matrix beforehand,we could have determined the isolated eigenvalue 43106 exactly and then deleted the corresponding row and column from the matrix.You should consider whether such a pre-inspection might be useful in your application. (For symmetric matrices,the routines we gave will determine isolated eigenvalues (outside Recipes 腿 accurately in all cases.) The routine balanc does not keep track of the accumulated similarity trans- North formation of the original matrix,since we will only be concerned with finding eigenvalues of nonsymmetric matrices,not eigenvectors.Consult [1-3]if you want to keep track of the transformation. #include <math.h> #define RADIX 2.0 void balanc(float *a ,int n) Given a matrix a[1..n][1..n],this routine replaces it by a balanced matrix with identical eigenvalues.A symmetric matrix is already balanced and is unaffected by this procedure.The parameter RADIX should be the machine's floating-point radix.11.5 Reduction of a General Matrix to Hessenberg Form 483 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). Apart from referring you to the literature, and to the collected routines in [1,2], we are going to sidestep the problem of eigenvectors, giving algorithms for eigenvalues only. If you require just a few eigenvectors, you can read §11.7 and consider finding them by inverse iteration. We consider the problem of finding all eigenvectors of a nonsymmetric matrix as lying beyond the scope of this book. Balancing The sensitivity of eigenvalues to rounding errors during the execution of some algorithms can be reduced by the procedure of balancing. The errors in the eigensystem found by a numerical procedure are generally proportional to the Euclidean norm of the matrix, that is, to the square root of the sum of the squares of the elements. The idea of balancing is to use similarity transformations to make corresponding rows and columns of the matrix have comparable norms, thus reducing the overall norm of the matrix while leaving the eigenvalues unchanged. A symmetric matrix is already balanced. Balancing is a procedure with of order N 2 operations. Thus, the time taken by the procedure balanc, given below, should never be more than a few percent of the total time required to find the eigenvalues. It is therefore recommended that you always balance nonsymmetric matrices. It never hurts, and it can substantially improve the accuracy of the eigenvalues computed for a badly balanced matrix. The actual algorithm used is due to Osborne, as discussed in [1]. It consists of a sequence of similarity transformations by diagonal matrices D. To avoid introducing rounding errors during the balancing process, the elements of D are restricted to be exact powers of the radix base employed for floating-point arithmetic (i.e., 2 for most machines, but 16 for IBM mainframe architectures). The output is a matrix that is balanced in the norm given by summing the absolute magnitudes of the matrix elements. This is more efficient than using the Euclidean norm, and equally effective: A large reduction in one norm implies a large reduction in the other. Note that if the off-diagonal elements of any row or column of a matrix are all zero, then the diagonal element is an eigenvalue. If the eigenvalue happens to be ill-conditioned (sensitive to small changes in the matrix elements), it will have relatively large errors when determined by the routine hqr (§11.6). Had we merely inspected the matrix beforehand, we could have determined the isolated eigenvalue exactly and then deleted the corresponding row and column from the matrix. You should consider whether such a pre-inspection might be useful in your application. (For symmetric matrices, the routines we gave will determine isolated eigenvalues accurately in all cases.) The routine balanc does not keep track of the accumulated similarity trans￾formation of the original matrix, since we will only be concerned with finding eigenvalues of nonsymmetric matrices, not eigenvectors. Consult [1-3] if you want to keep track of the transformation. #include <math.h> #define RADIX 2.0 void balanc(float **a, int n) Given a matrix a[1..n][1..n], this routine replaces it by a balanced matrix with identical eigenvalues. A symmetric matrix is already balanced and is unaffected by this procedure. The parameter RADIX should be the machine’s floating-point radix