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

Problem 1Edit

Let   be a real symmetric matrix of order   with   distinct eigenvalues, and let   be such that   and the inner product   for every eigenvector   of  .

Problem 1aEdit

Let   denote the space of polynomials of degree at most  . Show that


 


defines an inner product on  , where the expression on the right above is the Euclidean inner product in  

Solution 1aEdit

SymmetryEdit

 

Linearity of 1st ArgumentEdit

Let  


 


 


Positive DefinitenessEdit

 


"Zeroness"Edit

We also need to show that   if and only if  .

Forward Direction (alt)Edit

Suppose  . It suffices to show  . However, this a trivial consequence of the fact that   (which is clear from the fact that   for   with degree less than   and that   does not lie in the orthogonal compliment of any of the   distinct eigen vectors of  ).

Forward DirectionEdit

Claim: If  , then  .


From hypothesis


 


where   are the orthogonal eigenvectors of   and all   are non-zero


 


Notice that   is a linear combination of  , the coefficients of the polynomial  , and the scaling coefficient   of the eigenvector e.g.  


Since   and  , this implies  .

Reverse DirectionEdit

If  , then  

Problem 1bEdit

Consider the recurrence


 


where the   and   are scalars and  . Show that  , where   is a polynomial of degree  

Solution 1bEdit

By induction.

Base CaseEdit

 


 

Induction StepEdit

Claim:  


Hypothesis:

Suppose

 

 


where   (respectively  ) has degree   (respectively  ). Then for  

 

which is as desired.

Problem 1cEdit

Suppose the scalars above are such that   and   is chosen so that  . Use this to show that that the polynomials in part (b) are othogonal with respect to the inner product from part (a.

Solution 1cEdit

Since   and  , it is equivalent to show that   for  .


Since

 ,


it is then sufficient to show that


 


Claim  Edit

By induction.

Base CaseEdit

 

Induction StepEdit

Assume:  


Claim:  


 

Claim  Edit

By induction.

Base CaseEdit

 


 

Induction StepEdit

Assume:  


Claim:  


 


 

Problem 2Edit

Consider the n-panel trapezoid rule   for calculating the integral   of a continuous function  ,

 

where  


Problem 2aEdit

Find a piecewise linear function   such that

 

for any continuous function   such that   is integrable over [0,1]. Hint: Find   by applying the fundamental theorem of calculus to  .

Solution 2aEdit

Rewrite given equation on specific intervalEdit

For a specific interval  , we have from hypothesis


 .


Distributing and rearranging terms gives


 

Apply HintEdit

Starting with the hint and applying product rule, we get


 .


Also, we know from the Fundamental Theorem of Calculus


 .


Setting the above two equations equal to each other and solving for   yields


 

Choose G'(t)Edit

Let  . Therefore since   is linear


 


By comparing equations (1) and (2) we see that


  and


 .


Plugging in either   or   into equation (3), we get that


 


Hence


 

Problem 2bEdit

Apply the previous result to  ,  , to obtain a rate of convergence.

Solution 2bEdit

Problem 3Edit

Let   denote the set of all real-valued continuous functions defined on the closed interval   be positive everywhere in  . Let   be a system of polynomials with   for each  , orthogonal with respect to the inner product


 


For a fixed integer  , let   be the   distinct roots of   in  . Let


 


be polynomials of degree  . Show that


 


and that


 


Hint: Use orthogonality to simplify  


Solution 3aEdit

 

Solution 3bEdit

 

ClaimEdit

 


ProofEdit

Since   is a polynomial of degree   for all  ,   is a polynomial of degree  .


Notice that   for   where   are the   distinct roots of  . Since   is a polynomial of degree   and takes on the value 1,   distinct times