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

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Problem 4[edit]

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 4a[edit]

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

Solution 4a[edit]

Steepest Descent Method[edit]


Choose such that minimizes i.e.


Directional Derivative Negative[edit]

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



which implies



since

Problem 4b[edit]

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 4b[edit]

Newton's Method[edit]

Directional Derivative Negative[edit]

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 4c[edit]

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 4c[edit]

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 5[edit]

Consider the following nonlinear autonomous initial value problem in with .


Problem 5a[edit]

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


Solution 5a[edit]

For ,


Problem 5b[edit]

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 5b[edit]

where is the Lipschitz constant of . Rearranging terms we get



In particular,


Then is given by


Problem 5c[edit]

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

Solution 5c[edit]

The midpoint method may be rewritten as follows:



which implies



Expanding each term around yields .


Problem 6[edit]

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


Problem 6a[edit]

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 6a[edit]

Weak Variational Formulation[edit]

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 Formulation[edit]

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_h[edit]

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



Then calculation yields the following: (draw pictures)





Discrete Variational Formulation in Matrix Form[edit]

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 6b[edit]

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

Solution 6b[edit]

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


Problem 6c[edit]

Consider the upwind modification of the ODE



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

Solution 6c[edit]

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