Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/August 2006

Problem 1 Consider the definite integral Let denote the approximation of by the composite midpoint rule with uniform subintervals. For every set . Let be defined by . Assume that . Problem 1a Show that the quadrature error satisfies Hint: Use integration by parts over each subinterval . Solution 1a Integrating by parts over arbitrary points and gives Since is defined on we use and Using the first interval we get And for the second we get Since these apply to arbitrary half-subintervals, we can rewrite equation with the its indecies shifted by one unit. The equation for the interval is Combining and and writing it in the same form as the integration by parts, we have Then our last step is to sum this over all of our subintervals, noting that Problem 1b Derive a sharp bound on the error of the form for every . Here denotes the maximum norm over . Recall that the above bound is sharp when the inequality is an equality for some nonzero . Solution 1b Applying the result of part (a), the triangle inequality, and pulling out the constant , we have, is some constant less than infinity since is compact and is continuous on each of the finite number of intervals for which it is defined. The above inequality becomes an equality when where is any constant. Problem 2 Consider the (unshifted) method for finding the eigenvalues of an invertible matrix Problem 2a Give the algorithm. Solution 2a The QR algorithm produces a sequence of similar matrices whose limit tends towards being upper triangular or nearly upper triangular. This is advantageous since the eigenvalues of an upper triangular matrix lie on its diagonal. i = 0 A_1 = A while ( error > tolerance ) A_i=Q_i R_i (QR decomposition/factorization) A_{i+1}=R_i Q_i (multiply R and Q, the reverse multiplication) i=i+1 (increment) Problem 2b Show that each of the matrices generated by this algorithm are orthogonally similar to . Solution 2b From the factor step (QR decomposition) of the algorithm, we have which implies Substituting into the reverse multiply step, we have Problem 2c Show that if is upper Hessenberg then so are each of the matrices generated by this algorithm. Solution 2c A series of Given's Rotations matrices pre-multiplying , a upper Heisenberg matrix, yield an upper triangular matrix i.e. Since Givens Rotations matrices are each orthogonal, we can write i.e. If we let , we have , or more generally for . In each case, the sequence of Given's Rotations matrices that compose have the following structure So is upper Hessenberg. From the algorithm, we have We conclude is upper Hessenberg because for the th column of is a linear combination of the first columns of since is also upper Hessenberg. Problem 2d Let For this the sequence has a limit. Find this limit. Give your reasoning. Solution 2d The eigenvalues of can be computed. They are and . Furthermore, the result of matrix multiplies in the algorithm shows that the diagonal difference, , is constant for all . Since the limit of is an upper triangular matrix with the eigenvalues of on the diagonal, the limit is Problem 3 Let be symmetric and positive definite. Let . Consider solving using the conjugate gradient method. The iterate then satisfies for every , where denotes the vector A-norm, is the initial residual, and . Problem 3a Prove that the error is bounded by , where is any real polynomial of degree or less that satisfies . Here denotes the matrix norm of that is induced by the vector A-norm. Solution 3a We know that for every , so if we can choose a such that , then we can solve part a. Rewrite r^(0) First note from definition of Rewrite Krylov space Therefore, we can rewrite as follows: Write y explicitly We can then write explicitly as follows: Substitute and Apply Inequality We substitute into the hypothesis inequality and apply a norm inequality of matrix norms to get the desired result. Problem 3b Let denote the Chebyshev polynomial. Let and denote respectively the smallest and largest eigenvalues of . Apply the result of part (a) to to show that . You can use without proof the fact that , where denotes the set of eigenvalues of , and the facts that for every the polynomial has degree , is positive for , and satisfies . Solution 3b Overview We want to show that Maximize Numerator of p_n(z) By hypothesis, Since only the numerator of depends on , we only need to maximize the numerator in order to maximize . That is find Rewrite T_n Let . Then Hence, so Max of T_n is 1 Denote the argument of as since the argument depends on . Hence, , Then, Thus . Now, since is real for , Hence, Show T_n(1)=1 Let , then Using our formula we have, In other words, if , achieves its maximum value of .