Jump to content

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

From Wikibooks, open books for an open world

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