Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 36
Текст из файла (страница 36)
. ,n - 1. For j = 1, . . . , n, let x(j) be the n-vector whose ithentry isProve that4.8-4 Use Exercises 4.8-1 and 4.8-3 to prove that if A is a tridiagonal matrix with aii = d,ai+1, i = ai, i+1 = e, all i, then the eigenvalues of A consist of the numbers4.8-5 Use the power method to estimate the eigenvalue of maximum modulus, and acorresponding eigenvector, for the tridiagonal matrix A of order 20 with aii = 4, ai+1, i =ai, i+1 = - 1, all i, and compare with the exact answer obtained from Exercise 4.8-4.4.8-6 Try to estimate an eigenvalue of maximum modulus for the matrix A of 4.8-3 (withn = 21, say) using the power method . Explain any difficulties you encounter.4.8-7 The power method breaks down if the matrix has two or more eigenvalues of the samemaximum modulus.
Discuss how one might use Exercise 4.8-1 to circumvent this difficulty.Try your remedy on the problem in Exercise 4.8-6.4.8-8 Show that the matrixdoes not have a complete set of eigenvectors.4.8-9 Let x and y be two eigenvectors for the matrix A belonging to the eigenvaluesof A, respectively. Show that ifthen x and y are linearly independent.4.8-10 Use 4.8-9 to show that the matrixmust have a complete set of eigenvectors.4.8-11 Find all the eigenvalues of the matrixby determining explicitly its characteristic polynomial, and then the zeros of this polynomial.4.8-12 Reduce the matrix A of Exercise 4.8-11 to tridiagonal form B by Householderreflections. (Since the characteristic polynomial of A has a triple root, according to Example4.16, at least two of the bi’s should be zero.) Then find the eigenvalues of B.4.8-13 Calculate all the eigenvalues of the tridiagonal matrix B of Example 4.17, using therecurrence (4.76) the Sturm sequence property to isolate the eigenvalues, and then Newton’smethod to obtain the individual eigenvalues.
(Consider writing a program for a generalsymmetric tridiagonal matrix.)4.8-14 Having done Exercise 4.8-13, use the inverse power method to determine the corresponding eigenvectors.4.8-15 Verify that a Hermitian matrix is similar to a diagonal matrix, and that all itseigenvalues are real. (Hint: Show that the upper-triangular matrix obtained in Schur’stheorem is necessarily Hermitian if B is.)4.8-16 Use Müller’s method to find the natural frequencies in Example 4.16 in case(n)4.8-17 Suppose the matrix A of order n has a complete set of eigenvectors x(1) , . . .
, x .Prove that then A is similar to a diagonal matrix (whose diagonal entries must be the*4.8THE EIGENVALUE PROBLEM207eigenvalues of A). [Hint: Consider the matrix C-1AC, where Ci j = x(j), j = 1, . . . , n. Whymust C be invertible?]4.8-18: Deflation for the power method Suppose that we have calculated, by the powermethod or by any other method, an eigenvalue λ for the matrix A of order n, withcorresponding eigenvector x, and assume thatLet B be the matrix of order n - 1obtained from the matrix C-1AC by omitting its last row and last column, where Ci j = ij , j= 1, .
. . , n - 1, and C in = x. Prove that all the eigenvalues of A are also eigenvalues of B,with the possible exception of the eigenvalue λ.Previous Home NextCHAPTERFIVE*SYSTEMS OF EQUATIONS ANDUNCONSTRAINED OPTIMIZATIONA general system of n equations in the n unknowns x1, . . . , xn can alwaysbe written in the form(5.1)i = 1, . . . , nf i(x1 ,. .
. ,xn ) = 0with f1, . . . ,fn n functions of n variables. We will continue to use vectornotation, as introduced in Chap. 4, and so write (5.1) more compactly asf(x) = 0(5.2)Thus, f is a vector-valued function of a vector. Its value at the n-vectorx = [x1 x2 · · · xn ]T is the n-vector f(x) = [f 1 (x) f2(x) · · ·f n (x)] T .This notation not only saves some writing, but it is also suggestive ofthe fact that the iterative methods for solving one equation in one unknown, as discussed in Chap.
3, should be applicable here, too, in somesense. In particular, we will discuss fixed-point iteration, and Newton’smethod and some of its variants. But we will not be able to get as deeplyinto the mathematical analysis of those methods. A thorough discussion ofthe wealth of available material can be found in the monograph of Ortegaand Rheinboldt [33]. Also, the solution of systems of equations continuesto be an area of active research, particularly in the construction of efficientalgorithms.208*5.1OPTIMIZATION AND STEEPEST DESCENT209A particular example of a system (5.1) is the linear systemAx-b=0We discussed its direct solution at some length in Chap.
4. Now, thegeneral system (5.2) usually has to be solved by iteration, i.e., by solving anequivalent sequence of linear systems, usually by the direct methodsdiscussed in Chap. 4. But, for some of the iterative methods, especially therelaxation methods, the sequence of linear systems to be solved is so simplethat these methods may be (and have been) applied with profit to systemswhich are themselves linear. We will pay particular attention to suchiterative solution of linear systems.Finally, we stress the close relationship between the solution of systems of equations and the search for extrema of a real-valued function of nvariables, as explained further in the first section of this chapter.*5.1 OPTIMIZATION AND STEEPEST DESCENTOptimization is a steady source of systems of equations to be solved, andsome methods for their solution are directly influenced by this fact.
Torecall, if a real-valued function F(x) = F( x1, . . . , xn ) of n variables is to beminimized (or maximized), then it is sufficient to look just at its values atits critical points, that is, at points x at whichHere,F is the gradient of F, that is, the vectorwhose entries are the corresponding first partial derivativesof F. We writeif we want to emphasize the point x at which thegradient is to be evaluated.Recall that the gradientserves as the “first derivative” of thefunction F(x) of n variables: By Theorem 1.8, the derivative of thefunctiong(t) = F(x + t u)of the one variable t at t = 0 is given byThis number gives information about the behavior of the function F as westrike out from the point x in the direction u.
Thus, F increases in alldirections u which have angle less than 90” with the gradient vectorwith the rate of increase greatest in the direction of the gradient. This is so210*SYSTEMS OF EQUATIONS AND UNCONSTRAINED OPTlMlZATlONbecause(5.3)with θ the angle between the two vectors. Actually, this is something of atautology because, on inquiring what the angle θ between the two vectors uand v might be, one usually gets the answer thatBut, the point is that, forroughly half of the possible directions u,namely those for whichlead to an increase for F, with thisincrease greatest if and only if u is parallel toBy the same token,roughly half of all possible directions u lead to a decrease for F, with thedecrease greatest when u is parallel toIt follows that x cannot be aminimum or maximum for F unlessExample 5.1 The functionhas the gradientThe equation= 0 therefore has the four solutions (0, 0), (0, -2) (4/3, 0) and(4/3, -2) and no others.
To understand the nature of these critical points and to getsome exercise with gradients, we consider now the various regions into which the (x1, x2)plane is cut by the curvesandWe find that f 1 =vanishes at the two straight lines x l = 0 andisnegative between these lines and positive elsewhere. Thus the first component of thegradientis negative between these two lines and positive elsewhere.
Also, f2 =vanishes at the two straight lines x2 = -2 and x2 = 0, is negative between theselines and is positive elsewhere. This gives the qualitative picture shown in Fig. 5.1 for thedirection of the gradient in the various regions defined by the lines f1 = 0 and f2 = 0.The figure makes apparent that the critical point (0, -2) is a local maximum (since allgradients in its neighborhood point toward it), while the critical pointis a localminimum (since all gradients in its neighborhood point away from it). The other twocritical points are not extrema but saddle points, since in their neighborhood there areboth gradients pointing toward them and gradients pointing away from them.A basic method for finding an extremum is the method of steepestdescent (or, ascent). This method goes back to Cauchy and attempts tosolve the problem of finding a minimum of a real-valued function of nvariables by finding repeatedly minima of a function of one variable.
Thebasic idea is as follows. Given an approximation x to the minimum x* ofF, one looks for the minimum of F nearest to x along the straight lineThis means that one finds thethrough x in the direction ofminimum t* > 0 closest to 0 of the univariate functionand, having found it, takes the next approximation to the minimum x* to*5.1OPTIMIZATION AND STEEPEST DESCENT211Figure 5.1 Schematic of gradient directions for the functionbe the pointAlgorithm 5.1: Steepest descent Given a smooth function F(x) of then-vector x, and an approximation x(0) to a (local) minimum x* of F.For m = 0, 1, 2, . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
