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

Problem 4a Describe Newton's method for finding a root of a smooth function Solution 4a Newton's method: Problem 4b Assume that is a smooth function, satisfies and has a root . Draw a geometric picture illustrating the convergence of the method and give an analytic proof that Newton's method converges to for any initial guess Solution 4b From the picture, notice that if , then after one step will be greater than . This is because from hypothesis, the function is always increasing and concave up. Then without loss of generality assume . Subtracting from both sides of Newton's method gives an expression for the relationship between consecutive errors. Expanding around using Taylor expansion gives where Substituting this expression into (*), we have Since and is always increasing (from hypothesis), is a positive number less than 1. Therefore the error decreases as increases which implies the method always converges. Problem 5 The goal of this problem is to solve the boundary value problem in a suitable finite element space. Problem 5a For , let . Define a suitable dimensional subspace in associated with the points . Let be any basis in . Explain how you can determine the coefficients in the representation element solution by solving a linear system. Prove that there exists a unique solution Solution 5a Define Suitable Subspace which has a basis the hat functions defined as follows: How to Determine Coefficients The discrete weak variational form is given as such: Find such that for all Since we have a basis , we have a system of equations (that can be expressed in matrix form): For Existence of Unique Solution The existence of a unique solution follows from Lax-Milgram. Note the following: bilinear form continuous (bounded) e.g. bilinear form coercive e.g. Poincare Inequality: Problem 5b Show that defines an inner product on and thus a notion of orthogonality in Solution 5b Problem 5c Let be the basis of the one-dimensional space . Find an orthogonal basis in that contains the basis function . Sketch the basis functions. Indicate how you would construct a basis of that contains the basis of Solution 5c Define a new hat function on each new pair of adjoining subintervals. The hat functions should have all have the same height as the previous basis's hat functions. Problem 5d What is the structure of the linear system in (a) for this special basis? Solution 5d For our system in (a), this system yields a diagonal matrix. Problem 6 For solving the equation , consider the scheme where and Problem 6a Show that this scheme is fourth-order accurate. Solution 6a Problem 6b For stability analysis, one takes . State what it means for to belong to the region of absolute stability for this scheme, and show that the region of absolute stability contains the entire negative real axis. Solution 6b Letting and rearranging terms gives If is a negative real number, then