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

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Problem 1[edit]


Solution 1[edit]

Problem 2[edit]


Solution 2[edit]

Problem 3[edit]

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[edit]

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

Descent Direction[edit]

Optimal step size[edit]

Choose such that is minimized i.e.





Setting the above expression equal to zero gives the optimal :



Note that since is symmetric


Problem 3b[edit]

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

Solution 3b[edit]

Note that . Then the minimal is given by

Given

For 
 

Problem 3c[edit]

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[edit]

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


Then


Hence,



is symmetric:


since symmetric


is positive definite:


since positive definite


Pseudocode[edit]

Given

For