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