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

Problem 1Edit

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

Show that the quadrature error   satisfies


Hint: Use integration by parts over each subinterval  .

Solution 1aEdit

Integrating   by parts over arbitrary points   and   gives


Since   is defined on   we use




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

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

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

Consider the (unshifted)   method for finding the eigenvalues of an invertible matrix  

Problem 2aEdit

Give the algorithm.

Solution 2aEdit

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

Show that each of the matrices   generated by this algorithm are orthogonally similar to  .

Solution 2bEdit

From the factor step (QR decomposition) of the algorithm, we have


which implies


Substituting into the reverse multiply step, we have


Problem 2cEdit

Show that if   is upper Hessenberg then so are each of the matrices   generated by this algorithm.

Solution 2cEdit

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




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



For this   the sequence   has a limit. Find this limit. Give your reasoning.

Solution 2dEdit

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

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

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

We know that   for every  , so if we can choose a   such that


then we can solve part a.

Rewrite r^(0)Edit

First note from definition of  


Rewrite Krylov spaceEdit

Therefore, we can rewrite   as follows:


Write y explicitlyEdit

We can then write   explicitly as follows:


Substitute and Apply InequalityEdit

We substitute   into the hypothesis inequality and apply a norm inequality of matrix norms to get the desired result.


Problem 3bEdit

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


We want to show that


Maximize Numerator of p_n(z)Edit

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_nEdit

Let  . Then






Max of T_n is 1Edit

Denote the argument of   as   since the argument depends on  . Hence,





Thus  .

Now, since   is real for  ,




Show T_n(1)=1Edit

Let  , then


Using our formula we have,


In other words, if  ,   achieves its maximum value of  .