Heath - Scientific Computing (523150), страница 40
Текст из файла (страница 40)
EIGENVALUES AND SINGULAR VALUES(d ) Hessenberg(e) General real matrix with distinct eigenvalues(f ) General real matrix with eigenvalues thatare not necessarily distinct4.29 In using QR iteration for computing theeigenvalues of a matrix, why is the matrix usually first reduced to some simpler form, suchas Hessenberg or tridiagonal?4.30 Applied to a given matrix A, QR iteration for computing eigenvalues converges toeither diagonal or triangular form. What property of A determines which of these two formsis obtained?4.31 As a preliminary step before computingits eigenvalues, a matrix A is often first reduced to Hessenberg form by a unitary similarity transformation. Why stop there? If sucha preliminary reduction to Hessenberg form isgood, wouldn’t triangular form be even better?What is wrong with this argument?4.32 Order the following algorithms 1through 4, from least work required to mostwork required, for a general square matrix A:(a) LU factorization by Gaussian eliminationwith partial pivoting(b) Computing all of the eigenvalues and eigenvectors(c) Solving a triangular system by backsubstitution(d ) Computing the inverse of the matrix4.33 The power method converges to whicheigenvector of a matrix?4.34 (a) If a matrix A has a simple dominant eigenvalue λ1 , what quantity determinesthe convergence rate of the power method forcomputing λ1 ?(b) How can the convergence rate of the powermethod be improved?4.35 Given an approximate eigenvector x fora matrix A, what is the best estimate (inthe least squares sense) for the correspondingeigenvalue?4.36 List three conditions under which thepower method for computing an eigenvaluemay fail.4.37 Inverse iteration converges to whicheigenvector of a matrix?4.38 In the power method or inverse iteration for computing eigenvalues and eigenvectors, why are the vector iterates normalized ateach iteration?4.39 What is the main reason that shifts areused in iterative methods for computing eigenvalues, such as the power, inverse iteration,and QR iteration methods?4.40 Given a general square matrix A, whatmethod would you use to find the following?(a) The smallest eigenvalue of A(b) The largest eigenvalue of A(c) The eigenvalue of A closest to some specified scalar β(d ) All of the eigenvalues of A4.41 (a) Given an approximate eigenvalue λfor a matrix, how can one obtain a good approximate eigenvector?(b) Given an approximate eigenvector x for amatrix, how can one obtain a good approximate eigenvalue?4.42 What is a Krylov sequence, and for whatpurpose is it useful?4.43 Why is the Lanczos method faster thanthe power method for computing a few eigenvalues of a real symmetric matrix?4.44 What features make the Lanczos methodsuitable for large sparse symmetric eigenvalueproblems?4.45 What is meant by the inertia of a realsymmetric matrix?4.46 (a) What is meant by a congruencetransformation of a real symmetric matrix?(b) What properties of the matrix, if any, arepreserved by such a transformation.4.47 Explain briefly how spectrum-slicingmethods work for computing individual eigenvalues of a real symmetric matrix.4.48 (a) List two reasons why converting ageneralized eigenvalue problem Ax = λBx tothe standard eigenvalue problem (B −1 A)x =λx might not be a good idea.(b) What is a better approach?EXERCISES1434.49 List at least two applications for the singular value decomposition (SVD) of a matrix.4.50 How are the singular values of an m × nmatrix A related to the eigenvalues of the n×nmatrix AT A?4.51 Let A be an m × n matrix.(a) What is the maximum number of nonzerosingular values that A can have?(b) If rank(A) = k, how many nonzero singularvalues does A have?4.52 Let a be a nonzero column vector.
Considered as an n × 1 matrix, a has only onepositive singular value. What is its value?4.53 Is forming AT A and computing itseigenvalues a good way to compute the singular values of a matrix A? Why?4.54 What is the condition number of a matrix with respect to the Euclidean vector norm,expressed in terms of the singular values of thematrix?4.55 List two reliable methods for determining the rank of a rectangular matrix numerically.4.56 If A is a 2n × n matrix, rank the following methods according to the amount of workrequired to solve the linear least squares problem Ax ≈ b.(a) QR factorization by Householder transformations(b) Normal equations(c) Singular value decompositionExercises4.1 (a) Prove thatmatrix60A=005 is an eigenvalue of the3700345015.48(b) Exhibit an eigenvector of A correspondingto the eigenvalue 5.4.2 What are the eigenvalues and corresponding eigenvectors of the following matrix?1 2 −40 210 034.3 LetA=114.1Your answers to the following questions shouldbe numeric and specific to this particular matrix, not just the general definitions.(a) What is the characteristic polynomial ofA?(b) What are the roots of the characteristicpolynomial of A?(c) What are the eigenvalues of A?(d ) What are the corresponding eigenvectorsof A?(e) Perform one iteration of the power methodTon A, using x0 = [ 1 1 ] as starting vector.(f ) To what eigenvector of A will the powermethod ultimately converge?(g) What eigenvalue estimate is given bythe Rayleigh quotient, using the vector x =T[1 1] ?(h) To what eigenvector of A would inverseiteration ultimately converge?(i ) What eigenvalue of A would be obtained ifinverse iteration were used with shift σ = 2?(j ) If QR iteration were applied to A, to whatform would it converge: diagonal or triangular? Why?4.4 Give an example of a 2 × 2 matrix Aand a nonzero starting vector x0 such that thepower method fails to converge to the eigenvector corresponding to the dominant eigenvalueof A.4.5 Suppose that all of the row sums of ann × n matrix A have the same value, say, α.(a) Show that α is an eigenvalue of A.(b) What is the corresponding eigenvector?4.6 Show that an n × n matrix A is singularif and only if zero is one of its eigenvalues.144CHAPTER 4.
EIGENVALUES AND SINGULAR VALUES4.7 Let A be an n × n matrix.(a) Show that A and AT have the same eigenvalues.(b) Do A and AT also have the same eigenvectors? Prove or give a counterexample.4.16 If λ is an eigenvalue of an n × n matrixA, show that λ2 is an eigenvalue of A2 .4.8 Prove that an n × n matrix A is diagonalizable by a similarity transformation if andonly if it has a complete set of n linearly independent eigenvectors.4.18 What are the eigenvalues of an idempotent matrix (i.e., A2 = A)?4.9 (a) Prove that all the eigenvalues of areal symmetric matrix A are real (Hint: Consider xT Ax).(b) Prove that all the eigenvalues of a complexHermitian matrix A are real (Hint: ConsiderxH Ax).4.10 Prove that the eigenvalues of a positivedefinite matrix A are all positive.4.11 Prove that for any matrix norm subordinate to a vector norm, ρ(A) ≤ kAk.4.17 Prove that if Ak = 0 for some positiveinteger k (such a matrix is said to be nilpotent), then all of the eigenvalues of A are zero.4.19 (a) Suppose that A is an n × n symmetric matrix.
Let λ and γ, with λ 6= γ, be eigenvalues of A with corresponding eigenvectors xand y, respectively. Show that y T x = 0 (i.e.,eigenvectors corresponding to distinct eigenvalues of a symmetric matrix are orthogonal).(b) More generally, suppose now that A isnot necessarily symmetric. If Ax = λx andAT y = γy, with λ 6= γ, show that y T x = 0(i.e., right and left eigenvectors correspondingto distinct eigenvalues are orthogonal).4.20 Let A be an n × n matrix such thatρ(A) < 1.4.12 Is there any real value for the parameterα such that the matrix1 0 α4 2 0 6 5 3(a) Show that I − A is nonsingular.(a) Has all real eigenvalues?(b) Has all complex eigenvalues with nonzeroimaginary parts?In each case, either give such a value for α orgive a reason why none exists.4.21 If A is an n × n matrix of rank one,then A must have the form A = uv T for somenonzero vectors u and v.4.13 Give an example of a symmetric complex matrix (not Hermitian) that has complex eigenvalues (i.e., with nonzero imaginaryparts).4.14 If A and B are n × n matrices and A isnonsingular, show that the matrices AB andBA are similar.4.15 Assume that A is a nonsingular n × nmatrix.(a) What is the relationship between the eigenvalues of A and those of A−1 ? Prove youranswer.(b) What is the relationship between the eigenvectors of A and those of A−1 ? Prove youranswer.(b) Show that(I − A)−1 =∞XAk .k=0(a) Show that the scalar uT v is an eigenvalueof A.(b) What are the other eigenvalues of A?(c) If the power method is applied to A, howmany iterations are required for it to convergeexactly to the eigenvector corresponding to thedominant eigenvalue?4.22 Let λ1 ≤ λ2 ≤ · · · ≤ λn be the (real)eigenvalues of an n × n real symmetric matrixA.(a) To which of the eigenvalues of A is it possible for the power method to converge by usingan appropriately chosen shift σ?(b) In each such case, what value for the shiftgives the most rapid convergence?(c) Answer the same two questions for the inverse iteration method.EXERCISES1454.23 Let the n × n complex Hermitian matrixC be written as C = A + iB (i.e., the matrices A and B are its real and imaginary parts,respectively).
Define the 2n × 2n real matrixC̄ byA −BC̄ =.BALet λ be an eigenvalue of C with corresponding eigenvector x + iy.(a) Show that C̄ is symmetric.(b) Show that λ is an eigenvalue of C̄, withboth x−yandyxas corresponding eigenvectors.(c) The previous results show that a routinefor real symmetric eigenvalue problems can beused to solve complex Hermitian eigenvalueproblems. Is this a good approach? Why?4.24 (a) What are the eigenvalues of the following complex symmetric matrix?2i 11 0(b) How many linearly independent eigenvectors does it have?(c) Contrast this situation with that for a realsymmetric or complex Hermitian matrix.4.28 Let A be a singular upper Hessenbergmatrix having no zero entries on its subdiagonal.
Show that the QR method applied toA produces an exact eigenvalue after only oneiteration. This result suggests that the convergence of the QR method will be very rapid ifwe use a shift that is approximately equal toan eigenvalue.4.29 Verify that the successive orthogonalvectors produced by the Lanczos algorithm(Section 4.3.9) satisfy a three-term recurrence.For example, Aq3 is already orthogonal to q1and hence need be orthogonalized only againstq2 and q3 .4.30 (a) Consider the column vector a as ann × 1 matrix.
Write out its singular value decomposition, showing the matrices U , Σ, andV explicitly.(b) Consider the row vector aT as a 1 × nmatrix. Write out its singular value decomposition, showing the matrices U , Σ, and Vexplicitly.4.31 If A is an m × n matrix and b is an mvector, prove that the solution x of minimumEuclidean norm to the least squares problemAx ≈ b is given byx=X uT bivi ,σi4.25 (a) If λ is an eigenvalue of an orthogonalmatrix Q, show that |λ| = 1.(b) What are the singular values of an orthogonal matrix?where the σi , ui , and vi are the singular valuesand corresponding singular vectors of A.4.26 (a) What are the eigenvalues of theHouseholder transformation4.32 Let A be an m×n real matrix.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
