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

Problem 1Edit

Let   be continuous on  . A polynomial   of degree not greater than   is said to be a best (or Chebyshev) approximation to   if   minimizes the expression


Problem 1aEdit

Show that a sufficient condition for   to be a best approximation is that there exists points   such that


Solution 1aEdit

Assume there exists   such that


Then for  


Let   and  .

Then   takes on the sign of   since


Since   changes signs   times (by hypothesis),   has   zeros.

However   and thus can only have at most   zeros. Therefore   and  

Problem 1bEdit

Compute the best linear approximation to  . [Hint: Drawing a line through the parabola will allow you to conjecture where two points of oscillation must lie. Use conditions from (a) to determine the third point and coefficients of  .]

Solution 1bEdit

First we need to find the roots of   in [0,1], which are given by


So our points at which to interpolate are



Our linear interpolant passes through the points   and  , which using point-slope form gives the equation




Problem 2Edit

We will be concerned with the least squares problem of minimizing


Here   is an   matrix of rank   (which implies  ) and   is the Euclidean vector norm. Let


be the QR decomposition of  . Here   are respectively  .

Problem 2aEdit

Show that the solution of the least squares problem satisfies the QR equation   and that the solution is unique. Further show that  .

Solution 2aEdit

The two problems are equivalentEdit

First notice


Then we can write


Note that multiplying by orthogonal matrices does not affect the norm.

Then solving   is equivalent to solving  , which is equivalent to solving  . Note that a solution exists and is unique since   is n-by-n and non-singular.

Show that  Edit




 , or simply  , as desired.

Problem 2bEdit

Use the QR equation to show that the least squares solution satisfies the normal equations  .

Solution 2bEdit


Problem 3Edit

  Let   be real symmetric and let   be given. For  , define   as the linear combination of the vectors   with the coefficient of   equal to one and orthogonal to the vectors  ; i.e.


Problem 3aEdit

Find formulas for   and  

Solution 3aEdit

Using Gram Schmidit, we have


Problem 3bEdit

Show that   Where do you use the symmetry of  ?

Solution 3bEdit



, if  , then


Since   is symmetric,


From hypothesis,  

Also from hypothesis,


Using the above results we have,


Problem 3cEdit

For which non-zero vectors   does   hold?

Solution 3cEdit

For  ,


If  , then


Since   is a scalar,   is an eigenvector of  .