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


(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 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  ,


 


i.e.


 


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

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