Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/Jan05 667

Problem 4Edit

Let   be a nonlinear smooth function. To determine a (local) minimum of   one can use a descent method of the form


where   is a suitable parameter obtained by backtracking and   is a descent direction i.e. it satisfies


Problem 4aEdit

Write the steepest descent method (or gradient) method and show that there exist   such that the resulting method satisfies (2)

Solution 4aEdit

Steepest Descent MethodEdit


Choose   such that   minimizes   i.e.


Directional Derivative NegativeEdit

To satisfy (2), the directional derivative should be negative i.e.


which implies



Problem 4bEdit

Write the Newton method and examine whether or not there exist   which yield (2). Establish conditions on the Hessian   of   which guarantee the existence of  .

Solution 4bEdit

Newton's MethodEdit


Directional Derivative NegativeEdit

To have descent, we want the directional derivative to be negative i.e.


which implies


Therefore   is positive definite and therefore   is positive definite.

Problem 4cEdit

If we replace the Hessian by the matrix  , where   and   is the identity matrix, we obtain a quasi-Newton method. Find a condition on   which leads to (2).

Solution 4cEdit

We now want   to be positive definite.

Let  ,   be the eigenvalues of  .

Then  ,   are eigenvalues of  .

Since we want   to be positive definite, we equivalently have for  




Problem 5Edit

Consider the following nonlinear autonomous initial value problem in   with  .


Problem 5aEdit

Write the ODE in integral form and use the mid-point quadrature rule to derive the mid-point method with uniform time-step  :


Solution 5aEdit

For  ,


Problem 5bEdit

Define truncation error  . Assuming that  , show an estimate for the error  . What is the order of the method? (Hint: use that   is Lipschitz continuous.

Solution 5bEdit


where   is the Lipschitz constant of  . Rearranging terms we get


In particular,  

Then   is given by


Problem 5cEdit

Prove that   for this method. (Hint: expand first   and   around   and next expand   Also expand   around  .)

Solution 5cEdit

The midpoint method may be rewritten as follows:


which implies


Expanding each term around   yields  .


Problem 6Edit

Consider the following boundary two-point boundary value problem in   with  


Problem 6aEdit

Write the finite element method with piecewise linear elements over a uniform partition of   with meshsize  . If   is the vector of nodal values of the finite element solution, find the (stiffness) matrix   and right-hand side   such that  . Is   symmetric? Is   positive definite?

Solution 6aEdit

Weak Variational FormulationEdit

Multiplying the given equation by a test function   and integrating from 0 to 1 gives the equivalent weak variational formulation:

Find   such that for all   the following holds


Discrete Variational FormulationEdit

Let   for  

Then we have the discrete variational formulation which is an approximation to the weak variational formulation.

Find   such that for all  


Define basis for V_hEdit

Let   be the linear "hat" functions which defines a basis for  .


Then calculation yields the following: (draw pictures)





Discrete Variational Formulation in Matrix FormEdit

Since   is a basis for  ,


Also, the discrete variational formulation may be expressed as


which in matrix form is


  is not symmetric.   is positive definite if


Problem 6bEdit

Find a relation between the three parameters   for   to be an  matrix, i.e. to have   if   and  

Solution 6bEdit

The first,second, and last rows all yield the same inequality for   to be an  -matrix:


Problem 6cEdit

Consider the upwind modification of the ODE


Show that the resulting matrix   is an M-matrix without restrictions on   and  .

Solution 6cEdit

Substituting   for   yields the following matrix  :


All off diagonal entries are  . Diagonal entries are  

The first row meets the last condition since


The second row through (n-1) rows meets the last condition since


The last row meets the last condition since