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



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).



is symmetric:

since symmetric

is positive definite:

since positive definite

Pseudocode[edit | edit source]