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

Problem 1Edit

Let   be a function with 3 continuous derivatives. Let   be a quadratic polynomial that interpolates   at  . Let   and


Problem 1aEdit

Show that


where   depends only on   and determine  . (Hint: the key to this is to prove that   vanishes at some point in  . The result can then be obtained by integration.)

Solution 1aEdit

Proof of HintEdit

Claim: There exists   such that  

Proof: The interpolation polynomial may be expressed using dividing difference coefficients i.e.


which implies


In general, the divided difference coefficients may be expressed as a factorial weighted point of a derivative of   i.e.




which implies


Application of HintEdit

From the hint we know that


which implies


Since   is quadratic,   is constant i.e.   for all  



By the fundamental theorem of calculus,




Problem 1bEdit

Now suppose   and   has 4 continuous derivatives. In this case show


where  . What is   in terms of the derivatives of  ?

Solution 1bEdit

Third Derivative of f has ZeroEdit

We know that  , because  . Now, by   we can conclude that there exists   such that  .

Application of Fundamental Theorem of Calculus (Twice)Edit


Problem 2aEdit

Find   such that   is a polynomial of degree   and this set is orthogonal on   with respect to the weight function  . (Note:  ,  )

Solution 2aEdit

Apply Gram SchmidtEdit

To find orthogonal   use the Gram Schmidt method.

Let   be a basis of  .

Calculate p_0Edit

Choose  .

Calculate p_1Edit

From Gram Schmidt, we have

 , where




Calculate p_2Edit

Proceeding with Gram Schmidt, we have








Problem 2bEdit

Derive the 2-point Gaussian formula


i.e. find the weights and nodes

Solution 2bEdit

Find the NodesEdit

The nodes   and   are the roots of the  th orthogonal polynomial i.e.  

Applying the quadratic formula yields the roots:



Find the WeightsEdit

The approximation is exact for polynomials at most of degree  . Hence, we have the following system of equations



Solving the solving the system of equation by substitution yields the weights:



Problem 3Edit

Let   be an   nonsingular matrix, and consider the linear system  

Problem 3aEdit

Write down the Jacobi iteration for solving   in a way that it would be programmed on a computer

Solution 3aEdit



<convergence condition>


Where  ,   is diagonal,   are lower and upper triangular, respectively.

Problem 3bEdit

Suppose   has   non-zero elements with  . How many operations per iteration does the Jacobi iteration take?

Solution 3bEdit

The   diagonal entries of   are non-zero since otherwise   would not exist.

Therefore   contains   off-diagonal non-zero entries.

The computation during each iteration is given by


Therefore there are   multiplies in each iteration.

Problem 3cEdit

Assume that   is strictly diagonally dominant: for  


Show that the Jacobi iteration converges for any guess  . (Hint: You may use Gerschgorin's theorem without proving it.)

Solution 3cEdit

Let  .

Theorem 8.2.1 [SB] states that   if and only if the Jacobi iteration converges.

Matrix multiplication and the definitions of   gives the explicit entrywise value of  

  for   and  

Then, using Gerschgorin's Theorem and diagonal dominance, we have the result.