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 | edit source]

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 | edit source]

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

Solution 4a[edit | edit source]

Steepest Descent Method[edit | edit source]

Choose such that minimizes i.e.

Directional Derivative Negative[edit | edit source]

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

which implies


Problem 4b[edit | edit source]

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 | edit source]

Newton's Method[edit | edit source]

Directional Derivative Negative[edit | edit source]

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 | edit source]

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 | edit source]

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

Consider the following nonlinear autonomous initial value problem in with .

Problem 5a[edit | edit source]

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 | edit source]

For ,

Problem 5b[edit | edit source]

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 | edit source]

where is the Lipschitz constant of . Rearranging terms we get

In particular,

Then is given by

Problem 5c[edit | edit source]

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

Solution 5c[edit | edit source]

The midpoint method may be rewritten as follows:

which implies

Expanding each term around yields .

Problem 6[edit | edit source]

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

Problem 6a[edit | edit source]

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 | edit source]

Weak Variational Formulation[edit | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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

Solution 6b[edit | edit source]

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

Problem 6c[edit | edit source]

Consider the upwind modification of the ODE

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

Solution 6c[edit | edit source]

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