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

Problem 1 Let be an arbitrary fixed partition of the interval . A function is a quadratic spline function if (i) (ii) On each subinterval , is a quadratic polynomial The problem is to construct a quadratic spline interpolating data points . The construction is similar to the construction of the cubic spline but much easier. Problem 1a Show that if we know , we can construct . Solution 1a Consider interval . Since is linear on this interval, using the point slope form we have Integrating, we have or, in a more convenient form, Problem 1b Find equations which enable us to determine the . You should find that one of the can be prescribed arbitrarily, for instance Solution 1 Since is continuous on , i.e. Simplifying and rearranging terms yields the reoccurrence formula Problem 2a Give the definition of the algorithm for finding the eigenvalues of a matrix . Define both the unshifted version and the version with shifts Solution 2a Unshifted Version Shifted Version Problem 2b Show that in each case the matrices generated by the algorithm are unitarily equivalent to (i.e. unitary). Solution 2b Suppose for some unitary . Since we have which is as desired as is unitary. For the shifted case, the same argument holds using the fact that . Problem 2c Let Use plane rotations (Givens rotations) to carry out one step of the algorithm on , first without shifting and then using the shift . Which seems to do better? The eigenvalues of are . (Recall that a plane rotation is a matrix of the form with Solution 2c The shifted iteration appears to work better because its diagonal entries are closer to the actual eigenvalues than the diagonal entries of the unshifted iteration. Unshifted Iteration Shifted Iteration Problem 3 Let be an symmetric, positive definite matrix. Then we know that solving is equivalent to minimizing the functional where denotes the standard inner product in . To solve the problem by minimization of we consider the general iterative method Problem 3a When and are given, show that the value of which minimizes as a function of is given in terms of the residual Solution 3a Useful Relationship Since is symmetric This relationship will used throughout the solutions. Substitute into Functional Take Derivative With Respect to Alpha Set Derivative Equal To Zero which implies Problem 3b Let be an -orthogonal basis of , . Consider the expansion of the solution in this basis: Use that orthogonality of the to compute the in terms of the solution and the 's Solution 3b which implies Problem 3c Let denote the partial sum so that where the 's are the coefficients found in (b). Use the fact that and the -orthogonality of the 's to conclude that the coefficient is given by the optimal i.e. Solution 3c which implies