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


 


since  

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  


 


i.e.


 

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