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

Problem 4 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 Write the steepest descent method (or gradient) method and show that there exist such that the resulting method satisfies (2) Solution 4a Steepest Descent Method Choose such that minimizes i.e. Directional Derivative Negative To satisfy (2), the directional derivative should be negative i.e. which implies since Problem 4b 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 Newton's Method Directional Derivative Negative 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 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 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 Consider the following nonlinear autonomous initial value problem in with . Problem 5a 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 For , Problem 5b 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 where is the Lipschitz constant of . Rearranging terms we get In particular, Then is given by Problem 5c Prove that for this method. (Hint: expand first and around and next expand Also expand around .) Solution 5c The midpoint method may be rewritten as follows: which implies Expanding each term around yields . Problem 6 Consider the following boundary two-point boundary value problem in with Problem 6a 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 Weak Variational Formulation 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 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 Let be the linear "hat" functions which defines a basis for . Then calculation yields the following: (draw pictures) Discrete Variational Formulation in Matrix Form 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 Find a relation between the three parameters for to be an matrix, i.e. to have if and Solution 6b The first, second, and last rows all yield the same inequality for to be an -matrix: Problem 6c Consider the upwind modification of the ODE Show that the resulting matrix is an M-matrix without restrictions on and . Solution 6c 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