Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/January 2008

Problem 1 Consider the system . The GMRES method starts with a point and normalizes the residual so that has 2-norm one. It then constructs orthonormal Krylov bases satisfying where is a upper Hessenberg matrix. One then looks for an approximation to of the form choosing so that is minimized, where is the usual Euclidean norm. Problem 1a Show that minimizes . Solution 1a We wish to show that Problem 1b Suppose we choose to solve the least squares problem in part a for by the method of orthogonal triangularization (QR). What is the order of the floating point operation for this method. Give reasons. Solution 1b We would like to transform , a upper Hessenberg matrix, into QR form. The cost is on the order of from the cost of Given's Rotations and backsolving. Given's Rotations Cost We need Given's Rotation multiplies to zero out each of the subdiagonal entries and hence transform into upper triangular form , Each successive Given's Rotations multiply on an upper Hessenberg matrix requires four fewer multiplies because each previous subdiagonal entry has been zeroed out by a Given's Rotation multiply. Hence the cost of Given's Rotations multiplies is Back Solving Cost is a upper triangular matrix with last row zero. Hence, we need to backsolve upper triangular rows. Problem 2 We wish to approximate the integral Problem 2a State the composite trapezoidal rule for approximating on a uniform partitioning of width , and give a formula for the error that is in a form suitable for extrapolation. Solution 2a The composite trapezoidal rule is The error is where . Derivation of Composite Trapezoidal Error The local error, the error on one interval, is . Observe that which implies Hence, the Intermediate Value Theorem implies there exists a such that . Multiplying both sides of the equation by , Using this relationship, we have Derivation of Local Error The error in polynomial interpolation can be found by using the following theorem: Assume exists on and interpolates at . Then there is a ( is dependent on ) such that where lies in , , Applying the theorem yields, Hence, Since is the start of the interval, is always positive. Conversely, since is the end of the interval, is always negative. Hence, is always of one sign. Hence from the mean value theorem of integration, there exists a such that Note that is a constant and does not depend on . Integrating , yields, Problem 2b Use the error formula to derive a new quadrature rule obtained by performing one step of extrapolation on the composite trapezoidal rule. What is this rule, and how does its error depend on ? You may assume here that is as smooth as you need it to be. Solution 2b STOER AND BUESCH pg 162 INTRODUCTION TO APPLIED NUMERICAL ANALYSIS by RICHARD HAMMING pg 178 The error for the composite trapezoidal rule at points in is With points, there are twice as many intervals, but the intervals are half as wide. Hence, the error for the composite trapezoidal rule at points in is We can eliminate the term by choosing using an appropriate linear combination of and . This gives a new error rule with error. Substituting our equations for and on the left had side gives If we call our new rule we have whose error is on the order of Problem 3 Consider the shifted QR iteration for computing a 2 x 2 matrix : starting with , compute where is a scalar shift. Problem 3a If specify the orthogonal matrix used to perform this step when Givens rotations are used. The matrix should be described in terms of the entries of the shifted matrix. Solution 3a Let be the -shifted matrix of i.e. is an orthogonal 2x2 Given's rotations matrix. 's entries are chosen such that when is pre-multiplied against the 2x2 matrix , will zero out the (2,1) entry of and scale 's remaining three entries i.e. where denotes calculable scalar values we are not interested in and is our desired upper triangular matrix sought by the QR algorithm. Since is orthogonal, the above equation implies The Given's rotation is given by where Taking the transpose of yields Problem 3b Suppose , a small number, and . Demonstrate that with an appropriate shift , the (2,1)-entry of is of magnitude . What does this suggest about the convergence rate of the QR iteration? Solution 3b From hypothesis and part (a), Let be the (2,1) entry of . Using the above equation, we can find by finding the inner product of the second row of and first column and adding the (2,1) entry of i.e. We need to find the value of so we need to calculate . From hypothesis and the orthogonality of , we have From , we can find its (2,2) entry by using inner products. Now that we have we can calculate by using appropriate substitutions since is a small number. Let our shift . Then the above equation yields, Hence, since Hence we have shown that is of order . If is small, the QR convergence rate will be quadratic.