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

Problem 1 Solution 1 Problem 2 Solution 2 Problem 3 Let be symmetric and positive definite matrices, and let . Consider the quadratic function for and a descent method to approximate the solution of : Problem 3a Define the concept of steepest descent and show how to compute the optimal stepsize Descent Direction Optimal step size Choose such that is minimized i.e. Setting the above expression equal to zero gives the optimal : Note that since is symmetric Problem 3b Formulate the steepest descent (or gradient method) method and write a pseudocode which implements it. Solution 3b Note that . Then the minimal is given by Given For Problem 3c 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 3 Since is symmetric, positive definite, where is upper triangular (Cholesky Factorization). Then Hence, is symmetric: since symmetric is positive definite: since positive definite Pseudocode Given For