Heath - Scientific Computing (523150), страница 39
Текст из файла (страница 39)
Provided that σn+1 is simpleand vn+1,n+1 6= 0, the total least squares solution is then given byv1,n+11 .. x=− . .vn+1,n+1vn,n+1More general problems, for example with multiple right-hand sides and with some ofthe variables known exactly, can be handled by a similar approach but are rather morecomplicated (see [259] for details).4.6Software for Eigenvalues and Singular ValuesTable 4.3 is a list of some of the software available for eigenvalue and singular value problems.The routines listed are in most cases high-level drivers whose underlying routines can alsobe called directly if greater user control is required.
Only the most comprehensive andcommonly occurring cases are listed, and only for real matrices. There are many additional4.6. SOFTWARE FOR EIGENVALUES AND SINGULAR VALUES139routines available in these packages, including routines for complex matrices and for variousspecial situations, such as when only the eigenvalues and not the eigenvectors are needed,or when only a few eigenvalues are needed, or when the matrix has some special property,such as being banded. Routines are also available for both symmetric and nonsymmetricgeneralized eigenvalue problems. EISPACK and its successor LAPACK are the standards insoftware for dense eigenvalue problems, and the eigenvalue routines in most other librariesare based on them.Table 4.3: Software for standard dense eigenvalue and singular value problemsEigenvalues/eigenvectorsSingular valueSourceGeneralSymmetricdecompositionEISPACKrgrssvdFMMsvdHSLeb06ea06eb10IMSLevcrgevcsflsvrrLAPACKsgeevssyevsgesvdLawson/Hanson [163]svdrsLINPACKssvdcMATLABeigeigsvdNAGf02agff02abff02wefNAPACKdiagsdiagsingNRelmhes/hqr tred2/tqli svdcmpNUMALcomeig1qrisymqrisngvaldecSLATECrgrsssvdcConventional software for computing eigenvalues is fairly complicated, especially if eigenvectors are also computed.
The standard approach, QR iteration, is typically broken intoseparate routines for the preliminary reduction to tridiagonal or Hessenberg form, and thenQR iteration for computing the eigenvalues. The orthogonal or unitary similarity transformations may or may not be accumulated, depending on whether eigenvectors are alsodesired. Because of the complexity of the underlying routines, higher-level drivers are oftenprovided for applications that do not require fine control. Typically, the input required isa two-dimensional array containing the matrix, together with information about the sizeof the matrix and the array containing it. The eigenvalues are returned in one or twoone-dimensional arrays, depending on whether they are real or complex; and normalizedeigenvectors, if requested, are similarly returned in one or two two-dimensional arrays.Similar remarks apply to software for computing the singular value decomposition exceptthat arrays must be provided for both left and right singular vectors, if requested, and thedecomposition is always real if the input matrix is real.As usual, life is simpler using an interactive environment such as MATLAB, in whichfunctions for eigenvalue and singular value computations are built in.
A diagonal matrix Dof eigenvalues and full matrix V of eigenvectors of a (real or complex) matrix A are givenby the MATLAB function [V, D] = eig(A). Internally, the eigenvalues and eigenvectors arecomputed by Hessenberg reduction and then QR iteration to obtain the Schur form ofthe matrix, but the user need not be aware of this.
If the Hessenberg or Schur forms are140CHAPTER 4. EIGENVALUES AND SINGULAR VALUESdesired explicitly, they can be computed by the MATLAB functions hess and schur. TheMATLAB function for computing the singular value decomposition has the form [U, S, V]= svd(A).For software implementing the Lanczos algorithm for large sparse symmetric eigenvalueproblems, see laso from netlib, ea15 from the Harwell library, lancz from napack, or thesoftware published in [46].
In addition, the Arnoldi method for large sparse nonsymmetriceigenvalue problems is implemented in arpack, and the Lanczos method for computingsingular values and vectors of large sparse matrices is implemented in svdpack, both ofwhich are available from netlib. For solving total least squares problems, dtls is availablefrom netlib.4.7Historical Notes and Further ReadingThe Jacobi method for computing eigenvalues dates from the mid-nineteenth century. Thepower method is sufficiently obvious to have been rediscovered repeatedly, but as a practicalmethod its use dates from early in this century.
Inverse iteration was proposed by Wielandtin 1944. The Lanczos method was first published in 1950, and Arnoldi’s generalization ofit to nonsymmetric matrices followed in 1951. QR iteration was discovered independentlyand simultaneously by Francis and Kublanovskaya in 1961, based on the earlier LR methodof Rutishauser (1958), which uses less stable elementary eliminations instead of orthogonaltransformations. The first practical algorithm for computing the singular value decomposition was proposed by Golub and Kahan in 1965, and the basic algorithm that is still in usetoday was published by Businger and Golub in 1969. The direct precursors of most modernsoftware for eigenvalue and related problems were collected in [276], published in 1971.The definitive reference on eigenvalue computations is [275].
Other excellent referenceson this topic include [37, 108, 199]. Most of the books on matrix computations cited inChapter 2 also discuss eigenvalue and singular value computations in some detail, especially [104]. EISPACK is documented in [90, 233], and its successor LAPACK is documentedin [8].
For a detailed discussion of methods for large eigenvalue problems, see [46, 217]. Fora graphic example of the use of the SVD in image processing, see [9], and for its use incryptography, see [178].Review Questions4.1 True or false: The eigenvalues of a matrix are not necessarily all distinct.4.2 True or false: All the eigenvalues of areal matrix are necessarily real.4.3 True or false: An eigenvector corresponding to a given eigenvalue of a matrix isunique.4.4 True or false: Every n × n matrix A hasn linearly independent eigenvectors.4.5 True or false: If an n×n matrix is singular, then it does not have a full set of n linearlyindependent eigenvectors.4.6 True or false: A square matrix A is singular if and only if 0 is one of its eigenvalues.4.7 True or false: If λ = 0 for every eigenvalue λ of a matrix A, then A = O.4.8 True or false: The diagonal elements ofa complex Hermitian matrix must be real.4.9 True or false: The eigenvalues of a complex Hermitian matrix must be real.REVIEW QUESTIONS4.10 True or false: If two matrices have thesame eigenvalues, then the two matrices aresimilar.4.11 True or false: If two matrices are similar,then they have the same eigenvectors.4.12 True or false: Given any arbitrary squarematrix, there is some diagonal matrix that issimilar to it.4.13 True or false: Given any arbitrary squarematrix, there is some triangular matrix that isunitarily similar to it.4.14 True or false: The condition number ofa matrix that determines the sensitivity of thesolution to a system of linear equations also determines the sensitivity of the eigenvalues andeigenvectors to perturbations in the matrix.4.15 True or false: A matrix that is both symmetric and Hessenberg must be tridiagonal.4.16 True or false: If an n × n matrix A hasdistinct eigenvalues, then QR iteration appliedto A necessarily converges to a diagonal matrix.4.17 True or false: For a square matrix, theeigenvalues and the singular values are thesame thing.4.18 For a given matrix A,(a) Can the same eigenvalue correspond to twodifferent eigenvectors?(b) Can the same eigenvector correspond totwo different eigenvalues?4.19 What are the eigenvalues and eigenvectors of a diagonal matrix?4.20 Which of the following conditions necessarily imply that an n × n real matrix Ais diagonalizable (i.e., is similar to a diagonalmatrix)?(a) A has n distinct eigenvalues.(b) A has only real eigenvalues.(c) A is nonsingular.(d ) A is equal to its transpose.(e) A commutes with its transpose.1414.21 Which of the following classes of matrices necessarily have all real eigenvalues?(a) Real symmetric(b) Real triangular(c) Arbitrary real(d ) Complex symmetric(e) Complex Hermitian(f ) Complex triangular with real diagonal(g) Arbitrary complex4.22 Let A and B be similar matrices, i.e.,B = T −1 AT for some nonsingular matrix T .If y is an eigenvector of B, then exhibit aneigenvector of A.4.23 The eigenvalues of a matrix are the rootsof its characteristic polynomial.
Does this factprovide a generally effective numerical methodfor computing the eigenvalues? Why?4.24 Before applying QR iteration to find theeigenvalues of a matrix, the matrix is usuallyfirst transformed to a simpler form. For eachtype of matrix listed below, what intermediateform is appropriate?(a) A general real matrix(b) A real symmetric matrix4.25 A general matrix can be reduced to triangular form by a single QR factorization, andthe eigenvalues of a triangular matrix are itsdiagonal entries. Does this procedure sufficeto compute the eigenvalues of the original matrix? Why?4.26 Gauss-Jordan elimination reduces a matrix to diagonal form. Does this make theeigenvalues of the matrix obvious? Why?4.27 (a) Why is the Jacobi method for computing all the eigenvalues of a real symmetricmatrix relatively slowly convergent?(b) Name a method that is faster, and explainbriefly why it is faster.4.28 For which of the following classes of matrices of order n can the eigenvalues be computed in a finite number of steps for arbitraryn?(a) Diagonal(b) Tridiagonal(c) Triangular142CHAPTER 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
