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

Problem 1Edit

Let   be an arbitrary fixed partition of the interval  . A function   is a quadratic spline function if


(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 1aEdit

Show that if we know  , we can construct  .

Solution 1aEdit

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 1bEdit

Find equations which enable us to determine the  . You should find that one of the   can be prescribed arbitrarily, for instance  

Solution 1Edit

Since   is continuous on  ,




Simplifying and rearranging terms yields the reoccurrence formula


Problem 2aEdit

Give the definition of the   algorithm for finding the eigenvalues of a matrix  . Define both the unshifted version and the version with shifts  

Solution 2aEdit

Unshifted VersionEdit


Shifted VersionEdit


Problem 2bEdit

Show that in each case the matrices   generated by the   algorithm are unitarily equivalent to   (i.e.   unitary).

Solution 2bEdit

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 2cEdit



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



Solution 2cEdit

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 IterationEdit


Shifted IterationEdit


Problem 3Edit

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 3aEdit

When   and   are given, show that the value of   which minimizes   as a function of   is given in terms of the residual  


Solution 3aEdit

Useful RelationshipEdit

Since   is symmetric


This relationship will used throughout the solutions.

Substitute into FunctionalEdit


Take Derivative With Respect to AlphaEdit


Set Derivative Equal To ZeroEdit


which implies


Problem 3bEdit

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 3bEdit


which implies


Problem 3cEdit

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 3cEdit


which implies