Heath - Scientific Computing (523150), страница 41

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 41)

Considerthe symmetric eigenvalue problemH =I −2vv T,vT vwhere v is any nonzero vector?(b) What are the eigenvalues of the plane rotationc sG=,−s cσi 6=0OATAO uu=λ.vvwhere c2 + s2 = 1?(a) Show that if λ, u, and v satisfy this relationship, with u and v suitably normalized,then |λ| is a singular value of A with corresponding left and right singular vectors u andv, respectively.4.27 Let A be a symmetric tridiagonal matrix having no zero entries on its subdiagonal.Show that A must have distinct eigenvalues.(b) Is solving this eigenvalue problem a goodway to compute the SVD of the matrix A?Why?146CHAPTER 4.

EIGENVALUES AND SINGULAR VALUES4.33 Prove that the pseudoinverse A+ of anm × n matrix A, as defined using the SVDin Section 4.5.2, satisfies the following fourproperties, known as the Moore-Penrose conditions.(a) AA+ A = A.(b) A+ AA+ = A+ .(c) (AA+ )T = AA+ .(d ) (A+ A)T = A+ A.4.34 (a) If an n × n matrix A is nonsingular,prove that A+ = A−1 .(b) If an m × n matrix A has rank n, provethat A+ = (AT A)−1 AT .(c) If an m × n matrix A has rank m, provethat A+ = AT (AAT )−1 .4.35 (a) What is the pseudoinverse of the following matrix?1000(b) If > 0, what is the pseudoinverse of thefollowing matrix?100(c) What do these results imply about theconditioning of the problem of computing thepseudoinverse of a given matrix?Computer Problems4.1 (a) Implement the power method to findthe dominant eigenvalue and a correspondingeigenvector of the matrix2 3 2A =  10 3 4  .3 6 1TAs starting vector, take x0 = [ 0 0 1 ] .(b) Using any of the methods for deflationgiven in Section 4.3.5, deflate out the eigenvalue found in part a and apply the powermethod again to find the second largest eigenvalue of the same matrix.(c) Use a general real eigensystem library routine to compute all of the eigenvalues andeigenvectors of the matrix, and compare theresults with those obtained in parts a and b.4.2 (a) Implement inverse iteration with ashift to compute the eigenvalue nearest to 2,and the corresponding eigenvector, of the matrix6 2 1A = 2 3 1.1 1 1You may use an arbitrary starting vector.(b) Use a real symmetric eigensystem libraryroutine to compute all of the eigenvalues andeigenvectors of the matrix, and compare theresults with those obtained in part a.4.3 Write a program implementing Rayleighquotient iteration for computing an eigenvalueand corresponding eigenvector of a matrix.Test your program on the matrix in the previous exercise, using a random starting vector.4.4 (a) Use a library routine to compute theeigenvalues of the matrix−149 −50 −154A =  537 180546  .−27 −9 −25(b) Compute the eigenvalues of the same matrix again, except with the a22 entry changedto 180.01.(c) Compute the eigenvalues of the same matrix again, except with the a22 entry changedto 179.99.(d ) What conclusion can you draw about theconditioning of the eigenvalues of A?4.5 Implement the following simple versionof QR iteration with shifts for computing theeigenvalues of a general real matrix A.Repeat until convergence:1.

σ = an,n (use corner entry as shift)2. Compute QR factorization A − σI = QR3. A = RQ + σICOMPUTER PROBLEMS147(These steps will be easy if you use a packagesuch as MATLAB but more involved if you usea library routine for the QR factorization orwrite your own.)for computing roots of polynomials (see Table 5.2).

You may need to experiment withpolynomials of larger degree to see a significant difference.What convergence test should you use? Testyour program on the matrices in the first twocomputer exercises above.4.8 Compute the eigenvalues of the Hilbertmatrix of order n (see Computer Problem 2.6)for several values of n, say, up to n = 20. Canyou characterize the range of magnitudes ofthe eigenvalues as a function of n?4.6 Write a program implementing theLanczos method as given in Section 4.3.9. Testyour program using a random symmetric matrix A of order n having eigenvalues 1, 2, . .

. , n.To generate such a matrix, first generate ann × n matrix B with random entries uniformly distributed on the interval [0, 1) (seeSection 13.5), and then compute the QR factorization B = QR. Now take A = QDQT ,where D = diag(1, . . . , n). The Lanczos algorithm generates only the tridiagonal matrixTk at iteration k, so you will need to compute its eigenvalues (i.e., the Ritz values γi ,i = 1, . .

. , k) at each iteration, say, by usinga library routine based on QR iteration. Forthe purpose of this exercise, run the Lanczosalgorithm for a full n iterations.To see graphically how the Ritz values behaveas iterations proceed, construct a plot with theiteration number on the vertical axis and theRitz values at each iteration on the horizontalaxis. Plot each pair (γi , k), i = 1, .

. . , k, as adiscrete point at each iteration k (see Fig. 4.2).As iterations proceed and the number of Ritzvalues grows correspondingly, you should seevertical “trails” of Ritz values converging onthe true eigenvalues. Try several values for n,say, n = 10, 20, . . ., 50, making a separate plotfor each.4.7 Compute all the roots of the polynomialp(t) = 24 − 40t + 35t2 − 13t3 + t4by forming the companion matrix (see Section 4.2.1) and then calling an eigenvalue routine to compute its eigenvalues. Note that thecompanion matrix is already in lower Hessenberg form (there is also an equivalent upperHessenberg form), which you may be able totake advantage of, depending on the specificsoftware you use.

Compare the speed and accuracy of the companion matrix method withthose of a library routine designed specifically4.9 A singular matrix must have a zeroeigenvalue, but must a nearly singular matrixhave a “small” eigenvalue? Consider a matrixof the form1 −1 −1 −1 −1 01 −1 −1 −1  001 −1 −1 , 0001 −1 00001whose eigenvalues are obviously all ones. Usea library routine to compute the singular values of such a matrix for various orders. Howdoes the ratio σmax /σmin behave as the orderof the matrix grows? What conclusions canyou draw?4.10 A symmetric tridiagonal matrix with amultiple eigenvalue must have a zero on itssubdiagonal, but do a close pair of eigenvalues imply that some subdiagonal elementmust be small? Consider the symmetric tridiagonal matrix of order n = 2k + 1 havingk, k − 1, .

. . , 1, 0, 1, . . . , k as its diagonal entriesand all ones as its subdiagonal and superdiagonal entries. Compute the eigenvalues of thismatrix for various values of n. Does it have anymultiple or nearly multiple eigenvalues? Whatconclusions can you draw?4.11 A Markov chain is a system that hasn possible states and passes through a seriesof transitions from one state to another. Theprobability of a transition from state j to stateiPis given by aij , where 0 ≤ aij ≤ 1 andni=1 aij = 1. Let A denote the matrix of(k)transition probabilities, and let xi denote theprobability that the system is in state i aftertransition k. If the initial probability distribution vector is x(0) , then the probability distribution vector after k steps is given byx(k) = Ax(k−1) = Ak x(0) .148CHAPTER 4.

EIGENVALUES AND SINGULAR VALUESThe long-term behavior of the system is therefore determined by the value of limk→∞ Ak .4.12 Consider the spring-mass system......................................................1 ............1......2 ............2......3 ..........kConsider a system with three states and transition matrix•mk•m0.8 0.2 0.1A =  0.1 0.7 0.3  ,0.1 0.1 0.6and suppose that the system is initially in state1.(a) What is the probability distribution vectorafter three steps?k• m3with three masses m1 , m2 , and m3 at vertical locations y1 , y2 , and y3 connected by threesprings having spring constants k1 , k2 , and k3 .According to Newton’s Second Law, the motion of the system is governed by the systemof ordinary differential equations(b) What is the long-term value of the probability distribution vector?(c) Does the long-term value of the probabilitydistribution vector depend on the particularstarting value x(0) ?(d ) What is the value of limk→∞ Ak , and whatis the rank of this matrix?(e) Explain your previous results in terms ofthe eigenvalues and eigenvectors of A.(f ) Must 1 always be an eigenvalue of the transition matrix of a Markov chain? Why?(g) A probability distribution vector x is saidto be stationary if Ax = x.

How can youdetermine such a stationary value x using theeigenvalues and eigenvectors of A?(h) How can you determine a stationary valuex without knowledge of the eigenvalues andeigenvectors of A?(i ) In this particular example, is it possible fora previous distribution vector to recur, otherthan a stationary distribution? For Markovchains in general, is such nontrivial cyclic behavior possible? If not, why? If so, give anexample. (Hint: Think about the location ofthe eigenvalues of A in the complex plane.)(j ) Can there be more than one stationary distribution vector for a given Markov chain? Ifnot, why? If so, give an example.(k ) Of what numerical method does this problem remind you?M y 00 + Ky = 0,wherem1M = 000m2000 m3is the mass matrix andk1 + k2−k2K =  −k2k2 + k30−k30−k3 k3is the stiffness matrix .

Such a system exhibits simple harmonic motion with naturalfrequency ω, i.e., the solution components aregiven byyk (t) = xk eiωt ,where√ xk is the amplitude, k = 1, 2, 3, andi = −1. To determine the frequency ω andmode of vibration (i.e., the amplitudes xk ), wenote that for each solution component,yk00 (t) = −ω 2 xk eiωt .Substituting this relationship into the differential equation, we obtain the algebraic equationKx = λM x,where λ = ω 2 . Thus, the natural frequenciesand modes of vibration can be determined bysolving a generalized eigenvalue problem (seeSection 4.4).For purposes of this problem, assume the values k1 = k2 = k3 = 1, m1 = 2, m2 = 3, andm4 = 4, in arbitrary units.COMPUTER PROBLEMS(a) For this particular problem, the mass matrix M is diagonal, so there is no harm in converting the generalized eigenvalue problem to astandard eigenvalue problem. Taking this approach, determine all three natural frequenciesand modes of vibration for the system, usingany combination you choose of the power andinverse iteration methods (you may use shifts,or deflation, or both).(b) If you have access to a library routine forsolving generalized eigenvalue problems, use itto solve this problem directly in its originalform, and compare the results with those obtained in part a.4.13 (a) The matrix exponential function ofan n × n matrix A is defined by the infiniteseriesexp(A) = I + A +A3A2++ ···.2!3!Write a program to evaluate exp(A) using theforegoing series definition.(b) An alternative way to compute the matrixexponential uses the eigenvalue-eigenvector decompositionA = U diag(λ1 , .

Характеристики

Список файлов книги