Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 35
Текст из файла (страница 35)
One begins with the reduction toHessenberg form H as just outlined. Once this is accomplished, the matrixH becomes the first in a sequence,with A(k+1) obtained from A(k) as follows: One factors A(k) into a unitary200MATRICES AND SYSTEMS OF LINEAR EQUATIONS(k)matrix Q and an upper- (or right-) triangular matrix R, A = QR, andthen forms(k)(k+1)is again a Hessenberg matrixThus A (k+1) is similar to A . Further, A(k)since A is one.
This greatly reduces the number of operations necessaryto obtain its factorization. Now, in many circumstances, A(k) converges forlarge k to an upper-triangular matrix whose diagonal entries then necessarily provide all the eigenvalues of B.The details of, and the theory behind, this calculation are quite tricky,particularly since one factors (A(k) - skI) rather than A(k) itself, with theshifts sk chosen to accelerate convergence.
But the reader should be awareof the fact that this method, and other methods particularly suited forspecial classes of matrices B, have been translated into a package ofcarefully designed FORTRAN subroutines called EISPACK, availablefrom Argonne National Laboratory, or directly at many scientific computing centers. A complete description of the package, including programlistings, can be found in Smith et al. [32].LocalizationAt times, one is only interested in a rough estimate of some or all of theeigenvalues of a matrix B. Even if one eventually intends to calculate theeigenvalues, one may have to start with some information about theirapproximate location.
Such information is provided by localization theorems which describe regions in the complex plane in which eigenvalues ofB are known to lie.which implies(4.74)and for every matrix norm.A more precise statement is the following:Theorem 4.14: Gershgorin’s disks Every eigenvaluematrix B = (bij) satisfiesof the n × nIn other words, all the eigenvalues of B can be found in the union ofcertain disks in the complex plane. Indeed, if*4.8then the matrixExercise 4.6-3,of B.THE EIGENVALUE PROBLEM201is strictly (row) diagonally dominant; hence, byis then invertible; that is, is then not an eigenvalueExample 4.14 According to (4.74), each eigenvalue of the matrixof Example 4.11 must have absolute value no bigger thanprovide the more detailed information that every eigenvalueGershgorin’s disksof B must satisfyA Hermitian matrix, in particular a real symmetric matrix, has all itseigenvalues real.
It is similar to a diagonal matrix; that is, it has a completeset of eigenvectors. This is an easy consequence of Schur’s theorem; seeExercise 4.8-15. For a Hermitian matrix B, bothare eigenvalues of B, and any other eigenvalue of B lies between these two.Recall that these Rayleigh quotients appeared earlier in this section, in thediscussion of the power method.Combination of Lemma 4.4 and Theorem 4.10 produces the followingprecise localization theorem.Theorem 4.15 is an eigenvalue of the matrix B if and only if solvesthe characteristic equationThe matrixdiffers from B only in thathas been subtractedfrom each diagonal entry of B.
If we use the Kronecker symboltodenote the (i, j) entry of the identity matrix, so thatthenHenceshowingto be the sum of polynomials in the variableSince202MATRlCES AND SYSTEMS OF LINEAR EQUATIONSeach summand has n factors, each summand is a polynomial in of degreeat most n, while the summand corresponding to the identity permutationpT = [ 1 2 · · ·n] is simplyhence of exact degree n in . if follows thatfunction ofis a polynomial inof exact degree n,considered as aThis polynomial is called the characteristic polynomial of B.Example 4.15 Ifthenand expansion by elements of the last row or column givesHence the eigenvalues of A, that is, the zeros ofbeginning of this Section by different means.are - 1 and 3, as found at theSince a polynomial of degree n can have at most n distinct zeros (seeSec.
2.1), it follows that an n × n matrix can have at most n eigenvalues.On the other hand, by the fundamental theorem of algebra, every polynomial of positive degree has at least one zero (see Theorem 1.10): henceevery square matrix has at least one eigenvalue. These eigenvalues maywell be complex even if B is a real matrix.Theorem 4.15 makes the techniques for finding roots of equations,particularly polynomial equations, as discussed in Chap. 3, available forfinding eigenvalues.The method of quadratic interpolation (Miiller’s method), for instance, discussed in Sec.
3.7, can be employed to find one or moreeigenvalues, real or complex, of a given matrix. To use this method wemust be able only to evaluate the polynomialfor any value of . Sincefor a given value ofis simply a determinant of order n, any methodfor evaluating a determinant can be used. In particular, this can be doneby elimination, as explained in Sec. 4.7. But one would do well to bring thematrix into Hessenberg, or, if possible, tridiagonal form first, as discussedearlier, since that brings the cost of one determinant evaluation down toIn any event, to apply quadratic interpolation to find a*4.8THE EIGENVALUE PROBLEMrootof the characteristic polynomialceed as follows:203we pro-1.
Letbe any three approximations totion is available, take2. Evaluate(or if no informa-.3. Apply Algorithm 3.11 until convergence to a rootresults.4. To find the next root, repeat this process using, instead ofdeflated functionthe5. Continue as described in Sec. 3.7.The method of quadratic interpolation is not competitive, relative tocomputational efficiency, with some of the more advanced methods. However, it is simple to apply, it is completely general, it almost invariablyconverges, and it provides satisfactory accuracy in most cases.
It can alsobe applied to solve the more general eigenvalue problemwhere A and B are both matrices of order n.Example 4.16: Free vibrations of simple structures In civil engineering a problemfrequently encountered is to determine the natural frequencies of the free vibrations ofan undamped structure for several masses and degrees of freedom. This problem can beexpressed in the form(4.75)where M =mass matrix of systemA =stiffness of systemx =natural modeSince (4.75) represents a homogeneous system of equations, it will have a nontrivialsolution x if the determinant of the coefficients vanishes, i.e., if(4.75a )Thus, if the matrices A and M are given, the values of for which (4.75 a) is satisfied arethe required natural frequencies.
Müller’s method can be applied directly to find theseeigenvalues. For example, for a certain system, M = I, and the stiffness matrix A isgiven byFind the natural frequenciesof this system.204MATRICES AND SYSTEMS OF LINEAR EQUATIONSA computer program using the gaussian elimination algorithm 4.2 to evaluate thedeterminants and the Müller Algorithm 3.11 as a root finder produced the followingestimates for the eigenvalues:The exact eigenvalues are easily seen to be 1,5,5,5. The effectiveness of Müller’s methodas a root finder is demonstrated by this example, where a triple root has been found tofairly good accuracy.Example 4.17 The elements of the tridiagonal matrix B are generated as follows:Write a computer program to find the eigenvalues of B for n = 20.For n = 20, Müller’s method produced the following machine results on an IBM7094:Note that the eigenvalues are all real, are symmetrically placed with respect to theorigin, and are all less than one in modulus.
For this matrix the eigenvalues are knownexplicitly (see Exercise 4.8-4) and are given byThe accuracy of the machine results can be checked from this formula. For k = 7 andand the machine result underlined above indicates anaccuracy of seven significant figures.The matrix of Example 4.17 is real symmetric and tridiagonal. Forsuch matrices, special methods are available.
This is of importance sincewe saw earlier that any real symmetric matrix can be transformed bysimilarity into a real symmetric tridiagonal matrix.It is customary to write such a matrix in the form4.8THE EIGENVALUE PROBLEMIts characteristic polynomial can be obtained as205with(4.76)Here,is the determinant of the matrix formed by the first j rows andand one verifies (4.76) using Rule 6, expansion by acolumns ofrow or column, of Sec. 4.7 (see Exercise 4.7-11). The recurrence (4.76)allows the evaluation ofin about 3n operations. Further, the recurrence is easily differentiated with respect tomaking it possible tocalculateby recurrence, and so allows for the application of Newton’smethod.If bi = 0 for some i, then we see from the recurrence (4.76) that thepolynomialis a factor ofThe zeros ofare then those of the two polynomialsof smallerdegree, and we can concentrate on those.
Otherwise, iffor all i, thenB has n distinct eigenvalues. Also, the sequenceofvalues calculated during the evaluation ofcarries the followingadditional information: The number of (strong) sign changes in thatsequence equals the number of eigenvalues of B which are less than . This isdue to the fact that the polynomialsform a Sturmsequence, which allows the quick construction of intervals containing justone eigenvalue.Example 4.18 For the matrix of Example 4.17, the recurrence (4.76) simplifies toChoosing n = 10, andwe get the sequencewhich has five sign changes. Forwe get insteadshowing six sign changes. [Here we have listed only the first two significant digits, exceptfor the value offollows that there is exactly one eigenvalue of B in the interval[0, 0.2].
Modified regula falsi (Algorithm 3.3) starting with this interval produces in foursteps (on a Hewlett-Packard 67) the eigenvalue 0.142314837, corresponding to thecorrect eigenvalue(see Exercise 4.8-4).EXERCISES4.8-1 Let a, b be scalars and A be a square matrix. Prove that, if is an eigenvalue of A, thenis an eigenvalue of the matrix aA + bI. [Hint: Consider (aA + bI) x, where x is aneigenvector of A belonging to4.8-2 Prove that ifis an eigenvalue of the square matrix A and p(x) is some polynomial,thenis an eigenvalue of p(A) (see Exercise 4.1-12).206MATRICES AND SYSTEMS OF LINEAR EQUATIONS4.8-3 Let A be the tridiagonal matrix of order n with diagonal entries equal to zero andai,i+1 = ai+1,i = 1, i = 1, . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
