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

Problem 4a Show that the two-step method is of order 2 but does not satisfy the root condition. Solution 4a Method of Order 2 Method finds an approximation for such that . Let be the th point of evaluation where is the starting point and is the step size. Taylor Expansion of y' about a_0 Substituting into the second term on the right hand side of and simplifying yields Taylor Expansion of y about a_0 Since , we also take Taylor Expansion of about Substituting and simplifying yields, Take Difference of Taylor Expansions Hence shows that (1) is a method of order 2. Does Not Satisfy Root Condition The Characteristic equation of (1) is Giving the roots clearly does not satisfy Problem 4b Give an example to show that the method (1) need not converge when solving . Solution 4b Let . Then . We have the difference equation which has general solution (use the roots) If , then as Hence, . Therefore if , then . Problem 5 Consider the boundary value problem Problem 5a Prove that has at most one solution Solution 5a Let and be solutions. Let . By subtracting the two equations and their conditions we have Multiplying by test function and integrating by parts from 0 to 1, we want to find such that for all Let . Then, we have Since , , and are all , . Hence . Problem 5b Discretize the problem. Take a uniform partition of Use the three point difference formula for and the simplest difference formula for the boundary condition at . Write the resulting system as a matrix vector equation where Solution 5b The three point difference formula for is given by Equations for i=2,...,n-2 Substituting into with our difference formula we have in matrix formulation Equation for i=1 We can eliminate the variable by using the approximation which implies Using this relationship and the three difference formula, we have Equations for i=n-1 Since , we can eliminate the variable by substituting into the n-1 equation. Problem 5c Prove that the equation found in has a unique solution Solution 5c Since the matrix is diagonally dominant, the system has unique solution. Problem 5d Transform the problem into an equivalent problem with homogeneous boundary conditions. Solution 5d Let ,a solution of the boundary value problem, be represented as the sum of solutions to two different boundary value problems i.e. where Suppose . Then and which implies and hence Substituting into , we then have which implies Since , we have Therefore an equivalent boundary value problem with hemogenous boundary conditions is given by Problem 5e Obtain the variational formulation of the problem formulated in . Specify the Sobolev space involved. Prove that this problem has a unique solution, which we denote by . Solution 5e Variational Formulation and Sobolev space Using the problem's notation, we want to find such that for all , we have The above comes from integrating by parts and applying the boundary conditions. Unique Solution To show that is unique, we show that the hypothesis of the Lax-Milgram Theorem are met. a(v,w) bounded and continuous a(v,v) coercive F(v) bounded Problem 5f Consider the approximation of by piecewise linear finite elements. Define precisely the piecewise linear finite element subspace (use the partition (3)). Show that the finite element problem has a unique solution. Problem 5g Show that and indicate how the constant depends on the derivatives of . Solution 5 Problem 6 Let be a nonlinear function with zero : , . Consider the iteration , . Problem 6a Prove (4) is locally convergent. Solution 6a is a fixed point iteration. By the contraction mapping theorem, if is a contraction in some neighborhood of then the iteration converges at least linearly. We have to show there exists such that . By the mean value theorem we have that , that is for some in our neighborhood of . In particular, , implying that is a contraction and that the iterative method converges at least linearly. Calculating the Jacobian Problem 6b Show that the convergence is at least quadratic. Solution 6b where satisfies when . Then, we obtain . Problem 6c Write the Newton iteration and compare it with (4) Solution 6c The Newton iteration looks like this: Where B is the inverse of the Jacobian of f. That is, in the Newton Iteration gives (4).