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


Solution 1[edit | edit source]

Problem 2[edit | edit source]


Solution 2[edit | edit source]

Problem 3[edit | edit source]

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

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

Descent Direction[edit | edit source]

Optimal step size[edit | edit source]

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

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

Solution 3b[edit | edit source]

Note that . Then the minimal is given by

Given

For 
 

Problem 3c[edit | edit source]

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

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

Given

For