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

Problem 1Edit


Solution 1Edit

Problem 2Edit


Solution 2Edit

Problem 3Edit

Let   be symmetric and positive definite matrices, and let  . Consider the quadratic function   for   and a descent method to approximate the solution of  :


 

Problem 3aEdit

Define the concept of steepest descent   and show how to compute the optimal stepsize  

Descent DirectionEdit

 

Optimal step sizeEdit

Choose   such that   is minimized i.e.


 


 


 


Setting the above expression equal to zero gives the optimal  :


 


Note that since   is symmetric


 

Problem 3bEdit

Formulate the steepest descent (or gradient method) method and write a pseudocode which implements it.

Solution 3bEdit

Note that  . Then the minimal   is given by  

Given  

For  
  

Problem 3cEdit

Let   be a preconditioner of  . Show how to modify the steepest descent method to work for   and write a pseudocode. Note that   may not be symmetric. (Hint: proceed as with the conjugate gradient method).

Solution 3Edit

Since   is symmetric, positive definite,   where   is upper triangular (Cholesky Factorization).


Then  


Hence,


 


  is symmetric:


  since   symmetric


  is positive definite:


  since   positive definite


PseudocodeEdit

Given  

For